Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Discrete mathematics, continuous mathematics, and probability / 9 / b / ii / Solution

Let $t_i={\mathbb{E}}_i[X]$. Time is accumulated in each transient chamber before the next move; arrival at either terminal state ends the trial immediately. Thus $t_0=t_k=0$. A block of $k$ identical rightward choices forces absorption, so the geometric tail bound from a uniform escape probability gives finite expected value of $X$.

First-step analysis now givesThe quadratic $t_i=i(k-i)$ has the correct boundary values and second difference $t_{i+1}-2t_i+t_{i-1}=-2$, so it solves this system. The difference of two solutions would be linear in $i$ with zero values at both endpoints, hence zero. ThereforeThis is the expected duration of symmetric gambler's ruin. It includes the first minute in the starting transient chamber and does not add a minute after absorption.