Past exam of the options II course of the University of Oxford / 2008 printed variant / M / M5

Condition on $X_m=k$ and apply the Markov property and time homogeneity:Thus the transition matrices satisfy $P(m+n)=P(m)P(n)$; since $P(1)=P$ and $P(0)=I$, induction gives $P(n)=P^n$. Averaging over the initial state givesIf $\mu P=\mu$, induction gives $\mu P^n=\mu$, so this probability equals ${\mu }_i$ for every $n$. This is stationarity of the initial distribution.

A state $i$ is recurrent if the probability of returning to $i$ at a strictly positive time, starting at $i$, equals one. It is transient if that probability is less than one. If $i$ and $j$ communicate, choose $r,s$ with $p_{ji}(r)>0$ and $p_{ij}(s)>0$. Chapman-Kolmogorov givesIf $i$ is recurrent, summing over $n$ makes the right-hand side diverge, so the allowed recurrence criterion proves $j$ recurrent. Interchanging $i,j$ proves recurrence is shared throughout a communicating class, and therefore transience is shared too.

For the simple random walk, an odd number of steps cannot return to its starting point, andFor $p=1/2$ the return series diverges like $\sum n^{-1/2}$, proving recurrence. For $0<p<1$, $p\ne 1/2$, its tail is bounded by a convergent geometric series since $4p(1-p)<1$, proving transience. At $p=0$ or $1$ the walk is deterministic and never returns. Translation invariance transfers the conclusion to every state. Thus recurrence holds exactly when $p=1/2$.