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 / i / Solution

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.