Simple random walk on the hypercube Created 2026-10-03 Updated 2026-11-05
On the -dimensional hypercube graph, simple random walk flips one uniformly chosen coordinate at each step. Its stationary distribution is uniform on the vertices, so its mean return time is .
Stationary distribution of a graph random walk Created 2026-09-24 Updated 2026-11-05
On a finite connected loopless undirected graph with at least two graph vertices, the stationary distribution of a graph random walk for the simple random walk is
More generally, for positive symmetric edge electrical conductances with no killing, replace the vertex degree by and by . The detailed balance identity proves stationarity directly.
The stationary distribution is uniform precisely when the connected unweighted graph is regular. For a star with leaves, the center has stationary mass and each leaf has stationary mass . Starting at the center, the probability distribution alternates between center and leaves, so it does not converge to stationarity without an aperiodicity mechanism such as a positive holding probability. For a disconnected graph, different closed components admit different stationary mixtures; isolated graph vertices require an explicit transition convention.
Take independent copies of the simple random walk on the integer line, each stepping left or right with equal probability at every integer time. Their product Markov chain moves all coordinates at once; each of its diagonal increments has probability . At odd times a return to the origin is impossible. At time , independence gives the displayed return probability, whose asymptotic equivalence follows from Stirling's approximation. The recurrence criterion by return probabilities and the p-series therefore imply recurrence for and a transient Markov chain for .
For the chain from the origin visits only the sublattice whose coordinates all have the same parity. This is one communicating class; restricting to it gives an irreducible Markov chain. The period of a state in a Markov chain is two here. The conclusion applies to that class, without incorrectly claiming Markov chain irreducibility on all of . This walk moves diagonally; the usual axis-step simple random walk has different transition probabilities, even though the same dimensional recurrence threshold holds.
Transient graph Created 2026-09-24 Updated 2026-11-05
A locally finite connected graph is transient when its simple random walk visits every vertex only finitely often almost surely.