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

For a finite irreducible Markov chain with invariant distribution $\pi$, the mean recurrence time of state $i$ isThe simple random walk on the hypercube has the uniform invariant distribution because the hypercube graph is regular, so every vertex has mass $2^{-n}$. Therefore the expected first positive return time to the initial vertex is

Let $h$ be the expected hitting time from any neighbour of the origin back to the origin. After the first step, the return-time calculation from part (i) givesso $h=2^n-1$. Translation by the target vertex is a graph automorphism of the hypercube that exchanges the origin and that adjacent vertex, so the reverse expected hitting time is the same. Hence

Measure vertices by their Hamming distance from the target and let $h_k$ be the expected hitting time when that distance is $k$. We already know $h_1=2^n-1$. From distance one, one of the $n$ coordinate flips reaches the target and the other $n-1$ flips move to distance two. First-step analysis therefore givesFor $n\ge 2$,