Past exam of the mathematics course of the University of Cambridge / 2006 / ib / Paper 2 / 20C (Markov Chains)

Until the first visit to zero, the positive-side chain is a nearest-neighbour random walk with upward probability $2/3$ and downward probability $1/3$. For an integer $m>1$, let $h_i^{(m)}={\mathrm{Pr}}_i(T_0<T_m)$, $0\le i\le m$. The Markov property givesThe characteristic roots of this recurrence are $1$ and $1/2$. Solving its two boundary equations gives the biased gambler's ruin probabilityA finite path that reaches zero has a finite maximum before doing so, and is counted by $\{T_0<T_m\}$ for every sufficiently large $m$. Conversely each such event implies a visit to zero. Therefore these events increase to $\{T_0<\infty \}$, and continuity of probability givesMore generally the hitting probability from $i>0$ is $2^{-i}$. The finite-boundary derivation avoids choosing an unjustified solution of the infinite recurrence.

On the negative branch set $Y=-X$. Its outward step probability is $3/4$ and inward probability is $1/4$. The same finite gambler's ruin recurrence as in part (a), with root $(1/4)/(3/4)=1/3$, gives ${\mathrm{Pr}}_{-1}(T_0<\infty )=1/3$. Hence, following one departure from zero, the probability of returning isAt each return the Strong Markov property restarts the same excursion experiment. The probability of at least $m$ returns is $r^m$, tending to zero. Thus almost surely there is a last visit to zero.

After that visit the walk remains strictly positive or strictly negative, because nearest-neighbour steps cannot change sign without crossing zero. On the positive branch it can be coupled, up to any return, to independent steps of mean $2/3-1/3=1/3$. The strong law of large numbers gives a walk tending to $+\infty$ almost surely. This conclusion remains true on the event that the excursion never returns: conditioning on a positive-probability event cannot make a probability-zero failure of the law occur. On the negative branch the mean step is $1/4-3/4=-1/2$, giving $-\infty$ in the same way. Apply this at each possible departure time, a countable family, or use the Strong Markov property at the successive returns. ThereforeFinite visits to zero alone would not prove divergence on an arbitrary chain; the outward-drift argument is the additional step needed here.

One excursion from zero escapes forever on the positive branch with probability $a_{+}=\frac{1}{2}(1-\frac{1}{2})=1/4$, and on the negative branch with probability $a_{-}=\frac{1}{2}(1-\frac{1}{3})=1/3$. The remaining probability is the return probability $r=5/12$. By the last-excursion direction law at a transient junction, the eventual positive escape probability isEquivalently, if $p$ denotes the desired probability, the Strong Markov property gives $p=1/4+(5/12)p$. The negative escape probability is $4/7$, and their sum is one, as independently established in part (b).