Paper 2, Section II, H

Markov Chains
Part IB, 2018

For a finite irreducible Markov chain, what is the relationship between the invariant probability distribution and the mean recurrence times of states?

A particle moves on the 2n2^{n} vertices of the hypercube, {0,1}n\{0,1\}^{n}, in the following way: at each step the particle is equally likely to move to each of the nn adjacent vertices, independently of its past motion. (Two vertices are adjacent if the Euclidean distance between them is one.) The initial vertex occupied by the particle is (0,0,,0)(0,0, \ldots, 0). Calculate the expected number of steps until the particle

(i) first returns to (0,0,,0)(0,0, \ldots, 0),

(ii) first visits (0,0,,0,1)(0,0, \ldots, 0,1),

(iii) first visits (0,0,,0,1,1)(0,0, \ldots, 0,1,1).