Past exam of the mathematics course of the University of Cambridge / 2016 / ib / Paper 1 / 20H (Markov Chains)

A Markov chain is irreducible if every state can reach every other state in finitely many steps with positive probability. It is a recurrent Markov chain if, starting at any state, it returns to that state with probability one; for an irreducible chain this property is shared by all states.

For the simple symmetric random walk on $\mathbb{Z}$, taking $|j-i|$ steps all in the appropriate direction reaches $j$ from $i$ with probability $2^{-|j-i|}>0$. Thus the chain is irreducible. Its return probabilities areBy Stirling formula, $p_{00}^{(2k)}\sim 1/\sqrt{\pi k}$, so their sum diverges. The standard recurrence criterion ${\sum }_{n\ge 0}{p}_{00}^{(n)}=\infty$ therefore proves the walk is recurrent.

The printed hint's constant is erroneous: the actual limit of $\sqrt{k}{p}_{00}^{(2k)}$ is $1/\sqrt{\pi }$. Its positivity is what the recurrence argument requires, but the reciprocal is necessary for the correct numerical value.

An irreducible Markov chain has positive recurrent states if the expected first return time to a state is finite; this then holds for every state. A recurrent chain with infinite mean return time has null recurrent states.

An irreducible positive recurrent chain admits a stationary distribution. If such a distribution $\pi$ existed for this walk, its stationarity equations would giveThus ${\pi }_{j+1}-{\pi }_j={\pi }_j-{\pi }_{j-1}$, so ${\pi }_j=A+Bj$. Nonnegativity for all positive and negative integers forces $B=0$. A constant sequence cannot sum to one over $\mathbb{Z}$, so no stationary probability distribution exists. Hence the walk is null recurrent, not positive recurrent: all its states are null recurrent states. The first-return generating function in part (c) also verifies directly that its mean return time is infinite.

Let $u_n={\mathbb{P}}_0(X_n=0)$ and $f_n={\mathbb{P}}_0(T=n)$. Decomposing at the first return and using the Markov property gives the renewal equationFor $0<s<1$, define the probability generating functions $U(s)={\sum }_{n\ge 0}{u}_n{s}^n$ and $F(s)={\sum }_{n\ge 1}{f}_n{s}^n={\mathbb{E}}_0[s^T]$. Absolute convergence, or nonnegative summation, justifies the convolution identity $U=1+FU$. The binomial series givesSolving the renewal identity gives the first-return generating function of the simple symmetric random walkAs consistency checks, $F(s)\to 1$ as $s\uparrow 1$, confirming recurrence, while $F^{\prime }(s)=s/\sqrt{1-s^2}\to \infty$. By monotone convergence of ${\sum }_{n}n{f}_n{s}^{n-1}$, this last limit is ${\mathbb{E}}_{0}T=\infty$, confirming null recurrent states.