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

Let $\tau$ be the absorption time. Its expectation is finite: from every interior state, a string of at most $n$ successive left moves reaches $0$, and the probability of such a string is at least $p=3^{-n}$. Hence the Markov property gives ${\mathbb{P}}_k(\tau >jn)\le (1-p{)}^j$, a geometric tail bound, and ${\mathbb{E}}_k[\tau ]<\infty$.

For $1\le k\le n-1$, one step is always spent before absorption or the remaining walk. Apply first-step analysis and the law of total expectation to the three possible first moves. The conditional expectations of the remaining absorption time are $e_{k+1},e_k,e_{k-1}$, respectively; independence of future moves gives the same law as a fresh random walk from the new position. Thuswhich rearranges toThe term $1$ also appears when the walk stays at $k$, because staying still consumes a step.

The absorbing states give $e_0=e_n=0$. Multiplying the difference equation in (i) by $3$ givesThe second finite difference of $k^2$ is $2$, so a particular solution is $-3k^2/2$; the homogeneous solutions are $A+Bk$. Imposing the two boundary conditions gives $A=0,B=3n/2$. ThereforeUniqueness follows because the difference of any two solutions has zero second finite difference, hence is affine function, and vanishes at both endpoints. This is the mean absorption time of a lazy symmetric random walk with holding probability $1/3$.