EM transition-count update on a tree ($K_{ab}^{\mathrm{new}}=N_{ab}/{\sum }_c{N}_{ac}$)

For a common unconstrained Markov kernel on the edges of a rooted tree, let $N_{ab}$ be the conditional expectation of the number of transitions $a\to b$, given observed leaves and the old Markov kernel. The expectation-maximization algorithm maximizes ${\sum }_{a,b}{N}_{ab}\log K_{ab}$ over row probability distributions, giving $K_{ab}^{\mathrm{new}}=N_{ab}/{\sum }_c{N}_{ac}$. A row with zero total count is unrestricted by this objective. Belief propagation computes the counts exactly on a tree.