= 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> $x$ of positive finite <vertex degree> chooses each neighbor with <transition probability> $1/\deg(x)$. 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 $a-b-c$, the <transition matrix> in that order is
$$
P=\begin{pmatrix}0&1&0\\1/2&0&1/2\\0&1&0\end{pmatrix}.
$$
Its <stationary distribution> is $(1/4,1/2,1/4)$ because the central <graph vertex> has twice the <vertex degree> of either endpoint. Starting at $a$, 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>.
Back to article page