Past exam of the mathematics course of the University of Cambridge / 2017 / ia / Paper 2 / 12F / a

Write $K=k+1$ and $h_j={\mathbb{E}}_j{D}_j$. The expected duration of symmetric gambler's ruin satisfies $h_0=h_K=0$ and, by conditioning on the first step,These expected values are finite: from any interior state, $K$ consecutive right steps ensure absorption, an event of probability at least $2^{-K}$. Blocks of $K$ steps therefore bound the survival probability by a decreasing geometric sequence. The candidate $h_j=j(K-j)$ has the required boundary values and satisfies $h_{j+1}-2h_j+h_{j-1}=-2$. HenceFor completeness, the difference of two solutions of this linear recurrence relation has zero second difference and is affine in $j$; its two zero boundary values force it to vanish.