Past exam of the mathematics course of the University of Cambridge / 2024 / ia / Paper 2 / 11F (Probability)

Let $B_n$ count the $+1$ steps. ThenConsequentlyand $S_n$ has probability zero at integers of the other parity. This is the finite-time law of a simple random walk on the integer line.

The preceding representation and the central limit theorem giveSinceone may takeFor $0<p<1$ this gives the required convergence to $\Phi (x)$ at every real $x$.

Let $m_j$ be the expected remaining time when the walk is at $j$. The first-step recurrence for gambler's ruin iswith $m_{-a}=m_b=0$. The quadraticsatisfies both the recurrence and the boundary conditions, and their finite linear system has a unique solution. Starting from zero therefore gives

Only even times contribute, and at time $2k$ the walk is at zero exactly when it has made $k$ steps in each direction. By linearity of expectation,The Stirling formula implies thatHence there is a constant $c_0>0$ such that this term is at least $c_0/\sqrt{k}$ for every $k\ge 1$, after decreasing $c_0$ to cover the finitely many small values. ThereforeThe final expression is $2c_0(\sqrt{n+1}-1)$, so, after another adjustment for small $n$, there is a constant $c>0$ withfor every $n$. This is the lower bound recorded by expected visits to the origin by a simple random walk.