Past exam of the mathematics course of the University of Cambridge / 2018 / ib / Paper 2 / 20H / i / Solution

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