Past exam of the mathematics course of the University of Cambridge / 2006 / ib / Paper 4 / 9C / Solution

Let $X_n=S_n\mathrm{mod}4$. The residue contains all information needed for the next residue, so $(X_n)$ is a four-state Markov chain. In the order $0,1,2,3$, its transition matrix isFor example, from residue $2$, a head returns to $0$ and a tail goes to $3$; from either odd residue the tail leaves that residue unchanged.

The stationary distribution $\pi$ solves $\pi P=\pi$. Its equations give ${\pi }_1={\pi }_0$, ${\pi }_2={\pi }_1/2$, and ${\pi }_3={\pi }_2$. Normalization therefore givesThe Markov chain is irreducible: the positive-probability transitions around $0\to 1\to 2\to 3\to 0$ reach all states. It is also aperiodic because it has self-loops. The finite irreducible Markov chain ergodic theorem says that empirical state frequencies converge almost surely to the unique stationary distribution, irrespective of the initial state. HenceAperiodicity also permits convergence of the one-time state probabilities, although it is not needed for this empirical-frequency theorem.