Paper 3, Section I, H

Markov Chains
Part IB, 2017

(a) What does it mean to say that a Markov chain is reversible?

(b) Let GG be a finite connected graph on nn vertices. What does it mean to say that XX is a simple random walk on GG ?

Find the unique invariant distribution π\pi of XX.

Show that XX is reversible when X0πX_{0} \sim \pi.

[You may use, without proof, results about detailed balance equations, but you should state them clearly.]