Paper 2, Section II, H
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 vertices of the hypercube, , in the following way: at each step the particle is equally likely to move to each of the 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 . Calculate the expected number of steps until the particle
(i) first returns to ,
(ii) first visits ,
(iii) first visits .