= Solution
Write $\mathcal E$ for the directed edges from parent to child and $x_v(i)$ for the state at site $i$. The <global Markov property for an undirected graph> on this <tree>, together with the specified parent transitions, gives the complete-data <likelihood function>
$$
p_K(x)=4^{-k}\prod_{(v,w)\in\mathcal E}\prod_{i=1}^kK(x_v(i),x_w(i)).
$$
One can obtain the factorization by successively removing terminal subtrees: after conditioning on their parent, each subtree is independent of the rest. The root factor and transition products also show that different sites are independent. Only ancestral states are <latent variables>.
At the current <Markov kernel> $K^{(o)}$, define expected transition counts
$$
N_{ab}=\sum_{i=1}^k\sum_{(v,w)\in\mathcal E}
\Pr_{K^{(o)}}(X_v(i)=a,X_w(i)=b\mid\text{observed leaves}).
$$
The E-step of the <expectation-maximization algorithm> is
$$
Q(K\mid K^{(o)})=\text{constant}+\sum_{a,b}N_{ab}\log K(a,b).
$$
Maximize separately for each row under $K(a,b)\geq0$ and $\sum_bK(a,b)=1$. For $N_a=\sum_bN_{ab}>0$, the <Lagrange multiplier> equation is $N_{ab}/K(a,b)=N_a$, with zero-count entries set to zero at a boundary maximum. Thus the <EM transition-count update on a tree> is
$$
\boxed{K^{\mathrm{new}}(a,b)=\frac{N_{ab}}{\sum_cN_{ac}}.}
$$
If $N_a=0$, that row does not occur in $Q$; any row <probability distribution>, including its previous value, maximizes the objective.
The expected counts can be computed exactly by the <Felsenstein pruning algorithm> and an outward <belief propagation> pass. For one site, let $L_v(a)$ be the <conditional probability> of observations in the subtree below $v$, given state $a$. For a leaf $v$ with observed state $d_v$, $L_v(a)=\mathbf1_{\{a=d_v\}}$. For an internal vertex,
$$
L_v(a)=\prod_{w\text{ child of }v}\sum_bK^{(o)}(a,b)L_w(b),\qquad
Z_i=\frac14\sum_a L_{v_0}(a).
$$
Define $A_v(a)$ as the joint mass of state $a$ at $v$ and all observations outside its subtree. The root has $A_{v_0}(a)=1/4$. For a child $w$ of $v$, put
$$
S_{vw}(a)=\prod_{u\text{ child of }v,\ u\ne w}\sum_cK^{(o)}(a,c)L_u(c),\qquad
A_w(b)=\sum_a A_v(a)S_{vw}(a)K^{(o)}(a,b).
$$
The edge <posterior probability> required above is
$$
\xi_{vw}^{(i)}(a,b)=\frac{A_v(a)S_{vw}(a)K^{(o)}(a,b)L_w(b)}{Z_i}.
$$
Multiply the inside and outside factors to obtain the joint mass of the observations and endpoint states; division by the site <likelihood function> proves this expression. Sum $\xi$ over edges and sites to form $N_{ab}$. The two passes take $O(k|\mathcal E|4^2)=O(kn)$ operations on a binary <tree>. Scaling messages or computing them logarithmically avoids underflow.
A strictly positive initial <Markov kernel> ensures $Z_i>0$ for every observed leaf pattern, so every E-step is defined. At a later boundary iterate, require positive likelihood for the actual data and restrict the <conditional distribution> to its support. <EM likelihood monotonicity> proves that the update cannot decrease observed-data <likelihood function>. It is a maximum-likelihood iteration, not a guarantee of finding the global <maximum-likelihood estimate>; different initial kernels may lead to different stationary points.
Back to article page
