The aim of this note is to give the simplest possible non-trivial calculation of the parameters of a HMM that maximize the probability of emitting a certain string.

Let $\{0,1\}$ be our alphabet.

Let $p$ be the probability of emitting 1 in state $s_0$.

Let $q$ be the probability of emitting 1 in state $s_1$.

Let $\epsilon$ be the probability of transitioning from $s_0$ to $s_1$.

Let $\delta$ be the probability of transitioning from $s_1$ to $s_0$.

Let $S(t)$ be the state after transitioning $t$ times, a random variable.

The probability of emitting the string 001 when starting in state $s_0$ is then

$$

f(p,q,\epsilon,\delta)=\Pr(001; S(1)=s_0=S(2))+\Pr(001; S(1)=s_0, S(2)=s_1)$$

$$+\Pr(001; S(1)=s_1, S(2)=s_0)+\Pr(001; S(1)=s_1=S(2))$$

$$=\overline p^2 p \overline\epsilon^2 + \overline p^2q\overline\epsilon\epsilon + \overline p\overline q p\epsilon\delta + \overline p\overline q q \epsilon\overline\delta.

$$

Which choice of parameters $p, q, \epsilon, \delta$ will maximize this probability?

To answer this we first compute $\partial f/\partial\delta$ and set it equal to 0.

We find the solution: $p=1$ or $q=1$ or $\epsilon=0$ or $p=q$. Going through these possibilities we keep finding values of $f$ bounded above by $1/4$.

The boundary value choice $\delta=0$ (and hence we also assume $p=0$, since there is no use in considering a positive probability of emitting a 1 in state $s_0$ if there is no chance of ever returning to that state), however, gives upon calculation of $\partial f/\partial q$ that $\epsilon=2\overline q$, which gives $f=2q^2\overline q$. This is maximized at $q=2/3$ which corresponds to $\epsilon=2/3$ as well, and gives a value $f=8/27>1/4$.

This $8/27$ is decomposable as a sum of two disjoint scenarios of probability $4/27$:

- One is that after writing the first 0 we stay in state $s_0$, write another 0, and then transition to state $s_1$ to write a 1.
- The other is that after writing the first 0 we move to state $s_1$, write the 2nd zero there, and stay there to write the 3rd letter, 1.