K번 출구

다음 차례가 모그이고 현재 연속 성공 횟수가 $i$일 때의 기댓값을 $E_M(i)$, 루날리티 차례일 때를 $E_L(i)$라 하자. $p=A/(A+B)$, $q=B/(A+B)$라 하면 $i<K$에서

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

이다. $i+1=K$인 항의 기댓값은 $0$으로 둔다.

$i=K-1$부터 거꾸로 계산하면 모든 $E_M(i)$와 $E_L(i)$를 $E_M(0)$, $E_L(0)$에 대한 일차식으로 나타낼 수 있다. $i=0$에서 얻은 두 식은 미지수가 두 개인 연립일차방정식이므로 행렬식으로 풀 수 있다. 필요한 시간은 $O(K)$, 추가 메모리는 $O(1)$이다.