Random walk on a graph
ID: random-walk-on-a-graph
A random walk on a graph is a Markov chain whose allowed moves follow the graph edges. For the simple random walk on an unweighted graph, a graph vertex of positive finite vertex degree chooses each neighbor with transition probability . A weighted graph instead uses normalized edge weights, and directed graph edges permit asymmetric transitions. At an isolated graph vertex, a holding or termination convention is needed.
On a three-vertex path , the transition matrix in that order isIts stationary distribution is because the central graph vertex has twice the vertex degree of either endpoint. Starting at , the probability distribution nevertheless alternates between the two parts of the bipartite graph, so stationarity does not by itself imply convergence. Hitting times, recurrence, and mixing times ask different questions about the same Markov chain.
New to topics? Read the docs here!