Past exam of the mathematics course of the University of Cambridge 2013 ib Paper 1 20H i Solution Created 2026-09-24 Updated 2026-10-07
First realize the chain as a random walk on a multigraph: put three parallel edges between , two between , and one between . There are six edges and vertex degrees . Choosing an incident edge uniformly gives exactly the stated transition probabilities. The stationary distribution of a graph random walk is the degree divided by twelve, , and detailed balance follows because each edge multiplicity contributes the same flux in both directions.
Past exam of the mathematics course of the University of Cambridge 2017 ib Paper 3 9H b Solution Created 2026-09-24 Updated 2026-10-05
For the usual undirected graph with at least two vertices, a simple random walk chooses a neighbor uniformly at each step, so when and are adjacent and zero otherwise, where is the degree of a vertex. The handshaking lemma gives . Thus the stationary distribution of a graph random walk isFor adjacent , , and for nonadjacent pairs both sides vanish. By detailed balance, this is an invariant distribution and the walk started from it is a reversible Markov chain. Connectedness makes the finite walk an irreducible Markov chain, giving uniqueness of its invariant distribution. No aperiodicity assumption is needed for uniqueness, so a bipartite graph is allowed.
If the connected graph has a single isolated vertex, the usual neighbor-choice formula is undefined. With the natural absorbing convention , its unique invariant distribution is and it is reversible. The degree-normalization formula presupposes at least one edge.
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 isMore 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.