# Finding a mixture of 1st and 0'th order Markov models that is closest to an empirical distribution

I am interested in finding the distribution "$p^*$" closest to an empirical distribution $\hat{p}$ where $p^*$ is a mixture of first and zeroth order Markov models. That is, I want to find $$p^* = \arg\min_p \sum_{i,j} D\left(\,\hat{p}(j|i)\, \| \, p(j|i) \,\right)$$ subject to the following constraints

1. $p(j|i) = \alpha \cdot r(j) + (1 - \alpha) \cdot q(j|i)$
2. $r(j) \ge 0$ for all $j$
3. $\sum_j r(j) = 1$
4. $q(j|i) \ge 0$ for all $i$ and $j$
5. $\sum_j q(j|i) = 1$ for all $i$

where $\alpha$ is a mixture parameter in $[0,1]$ that is given and fixed.

I know I can hand this off to a solver, but I am actually interested in deriving the updates and writing the optimization procedure myself. Therefore, any assistance in this endeavor is greatly appreciated.

• What do you mean by update equations? Do you have a specific optimization method in mind? I‘m not clear about what the main question is here: is it how to write a convex optimizer? There is plenty of literature on that. Please clarify your question to indicate where the main problem lies. – S.Surace Jan 21 '18 at 9:58
• Are you looking for a closed-form solution? – S.Surace Jan 21 '18 at 10:02
• Closed form would be great. But I'm actually looking for a simple iterative method, like proximal gradient descent. – ted Jan 23 '18 at 5:52
• Why do you implicitily include the zeroth order term? Unless I'm missing something, the zeroth order term can simply be included in the first order term. – Steve Jan 23 '18 at 15:41
• I was just going to comment the same. The model does not seem to be identifiable (and also not convex, contrary to what the tag suggests). – S.Surace Jan 23 '18 at 16:33