Exit K

Let $E_M(i)$ be the expectation when the current run has length $i$ and Mog acts next, and define $E_L(i)$ similarly. With $p=A/(A+B)$ and $q=B/(A+B)$,

$$E_M(i)=1+pE_L(i+1)+qE_L(0),$$ $$E_L(i)=1+qE_M(i+1)+pE_M(0).$$

The term with $i+1=K$ is replaced by zero.

Process $i$ from $K-1$ down to $0$. Every expectation is an affine expression in $E_M(0)$ and . At , the two expressions form a linear system. Solving it gives the answer in time and extra space.