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

Let $R$ count red balls and let $h_r$ be the probability of eventual absorption at $R=0$ starting from $R=r$. The birth-death chain moves to $r-1$ with probability $r/4$ and to $r+1$ with probability $(4-r)/4$. Its absorbing states have $h_0=1$, $h_4=0$. First-step analysis givesSubstitution yields $h_2=1/2$, $h_1=5/8$ and $h_3=3/8$. The initial state has one red ball, so the probability that all balls end white is $5/8$.

Absorption occurs almost surely: from each interior state there is probability at least $1/4$ of absorption within the next two draws. The chance of surviving $2m$ draws is therefore at most $(3/4{)}^m$. This also justifies the finite expected times used in part (ii). The process is the absorbing four-ball Ehrenfest chain.

Let $t_r$ be the expected hitting time of either absorbing state. The boundary values are $t_0=t_4=0$. The colour symmetry gives $t_1=t_3$, and first-step analysis givesSolving gives $t_1=t_3=7$ and $t_2=8$. Thus the expected total number of draws from the stated initial condition is seven. The additive one counts the current draw. Finiteness follows from the uniform two-step absorption bound in part (i), so the first-step equations do not hide an assumption of finite expectation.