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

The expected value of an indicator random variable is the probability of its event. For a simple symmetric random walk absorbed at $0,k$, the gambler's ruin success probability from $i$ is $i/k$. HenceThe boundary values are $0$ at the left exit and $1$ at chamber $k$.

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.

Write $h_i={\mathbb{E}}_i[J]=i/k$ and $v_i={\mathbb{E}}_i[JX]$. Since $0\le JX\le X$, the latter expected value is finite. Conditional on the first move to $i-1$ or $i+1$, total time is one plus the remaining time, while the terminal success indicator random variable is unchanged. The Markov property and linearity of expectation giveAt either absorbing boundary the remaining time is zero, so $v_0=v_k=0$.

Let $w_i=i(k^2-i^2)/(3k)$. The linear term has zero second difference and $i^3$ has second difference $6i$. Consequentlywhich is exactly the required recurrence, and $w_0=w_k=0$. Uniqueness follows as before: the difference of two solutions has zero second difference and zero endpoint values. HenceThis is the success-weighted duration underlying the duration of gambler's ruin conditioned on a chosen boundary.

For $1\le i\le k$, the success probability is $i/k>0$, and the definition of conditional expectation on an event givesThereforeAt $i=k$ the value is zero because the trial has already ended. At the left absorbing state $i=0$, conditioning on success would be undefined because it has zero probability. The formula concerns the successful trajectories, so it need not equal the unconditional mean $i(k-i)$.