Random Walk on a Graph. Consider a connected graph with m nodes, and let Gi denote the set of nodes adjacent to node i. Whenever the particle is at node i, it moves to any j ∈ Gi with equal...

Random Walk on a Graph. Consider a connected graph with m nodes, and let Gi denote the set of nodes adjacent to node i. Whenever the particle is at node i, it moves to any j ∈ Gi with equal probability (i.e., 1/|Gi|). Let
_Xn
denote the location of the particle at time n. Show that
_Xn
is a Markov chain and specify its transition probabilities. Is the chain irreducible? aperiodic? recurrent? Assuming the graph is such that the chain is ergodic, show that its stationary distribution is πi = |Gi|/2|S