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

Condition on the fair coin choosing the initial chamber. The law of total probability gives $\mathbb{P}(\text{reach }k)=(p_1+p_2)/2$. With $r=(1-p)/p$, substituting the biased gambler's ruin probability givesBoth numerator and denominator in the first case have the same sign. Its limit as $r\to 1$ is the fair-walk value, since the ratio of their first derivatives is $3/(2k)$. The averaging is over initial locations, not over the transition probabilities.

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)$.

Treat one visit to a level as a whole gambler's ruin excursion, starting at its chamber $1$ and ending at local chamber $0$ or $4$. The room choices are fair, so the chance of reaching $4$ before $0$ is $1/4$, and the chance of reaching $0$ first is $3/4$. The one-way hatches reset the next excursion to chamber $1$ of the adjacent level. Thus the embedded Markov chain at level exits moves upward with probability $1/4$ and downward with probability $3/4$, even though individual room choices are unbiased.

Let $u$ be the food probability from the lower starting chamber, and $v$ that from the upper chamber $1$. The lower level either exits unsuccessfully or reaches the upper level, while the upper level either finds food or returns to the lower start. First-step analysis at these level exits givesSubstituting yields $u=1/16+3u/16$, soThis also follows from biased gambler's ruin probability on levels $0,1,2,3$, starting at $1$, with ratio $(1-p)/p=3$: $(1-3)/(1-3^3)=1/13$. Absorption occurs almost surely, since from each active level a fixed positive chance of terminal absorption occurs within two excursions; the original chamber excursions are also almost surely finite.