Maximum-Likelihood Reversible Transition Matrix¶

Here, we sketch out the objective function and gradient used to find the maximum likelihood reversible count matrix.

Let $C_{ij}$ be the matrix of observed counts. $C$ must be strongly connected for this approach to work! Below, $f$ is the log likelihood of the observed counts.

$f = \sum_{ij} C_{ij} \log T_{ij}$

Let $T_{ij} = \frac{X_{ij}}{\sum_j X_{ij}}$ , $X_{ij} = \exp(u_{ij})$ , $q_i = \sum_j \exp(u_{ij})$

Here, $u_{ij}$ is the log-space representation of $X_{ij}$ . It follows that $T_{ij} = \exp(u_{ij}) \frac{1}{q_i}$ , so $\log(T_{ij}) = u_{ij} - \log(q_{i})$

$f = \sum_{ij} C_{ij} u_{ij} - \sum_{ij} C_{ij} \log q_i$

Let $N_i = \sum_j C_{ij}$

$f = \sum_{ij} C_{ij} u_{ij} - \sum_{i} N_i \log q_i$

Let $u_{ij} = u_{ji}$ for $i > j$ , eliminating terms with $i>j$ .

Let $S_{ij} = C_{ij} + C_{ji}$

$f = \sum_{i \le j} S_{ij} u_{ij} - \frac{1}{2} \sum_i S_{ii} u_{ii} - \sum_i N_i \log q_i$

$\frac{df}{du_{ab}} = S_{ab} - \frac{1}{2} S_{ab} \delta_{ab} - \sum_i \frac{N_i}{q_i} \frac{dq_i}{du_{ab}}$

$\frac{dq_i}{du_{ab}} = \exp(u_{ab}) [\delta_{ai} + \delta_{bi} - \delta_{ab} \delta_{ia}]$

Let $v_i = \frac{N_i}{q_i}$

$\sum_i V_i \frac{dq_i}{du_{ab}} = \exp(u_{ab}) (v_a + v_b - v_a \delta_{ab})$

Thus,

$\frac{df}{du_{ab}} = S_{ab} - \frac{1}{2} S_{ab} \delta_{ab} - \exp(u_{ab}) (v_a + v_b - v_a \delta_{ab})$