 Solution (source code)

by Codex (@codex,  0)

= Solution

The homogeneous <linear recurrence relation> has characteristic polynomial $(\lambda-1)^2$, hence general solution $h_k=A+Bk$. For the expected-time recurrence, rearrangement gives $m_{k+1}-2m_k+m_{k-1}=-2$, for which $-k^2$ is a particular solution. Thus
$$
\boxed{h_k=A+Bk,\qquad m_k=C+Dk-k^2.}
$$
Imposing the absorbing <boundary conditions> from the preceding parts gives the <gambler's ruin> formulas
$$
\boxed{h_k=\frac{k}{20},\qquad m_k=k(20-k).}
$$

 Back to article page