On the symmetric group , this Markov chain chooses uniformly from the identity and the adjacent transpositions, and multiplies on the right. Its stationary distribution is the uniform distribution on a finite set, because the generators are self-inverse. A fixed label's position is a lumped Markov chain on a path graph with off-diagonal transition probabilities to existing neighbours.
Random transposition shuffle Created 2026-10-06 Updated 2026-11-05
Choose two positions independently and uniformly from and swap them. This Markov chain on the symmetric group holds with Probability and assigns Probability to each unordered transposition. Its stationary distribution is uniform, and its ordinary spectral gap is for . The latter follows from the Aldous spectral gap theorem: the single-label continuous-time Markov chain has rate between every pair of positions, whose mean-zero eigenvalues are all .
Random walk on a graph Created 2026-09-24 Updated 2026-11-05
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 is
Its 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.
Random walk on a multigraph Created 2026-10-07 Updated 2026-11-05
For a loopless undirected multigraph, let be the number of parallel graph edges between distinct graph vertices . Assume . Choosing an incident edge uniformly gives the transition probabilities
The measure is reversible since . It becomes a stationary distribution only when the total vertex degree is finite. On a finite graph this holds; on an infinite locally finite graph, a reversible measure need not be a normalizable probability measure. Self-loops need a stated incidence-counting convention and are excluded from the formula here.
For example, two parallel edges from to and one edge from to give degrees , stationary probabilities , and . Collapsing the parallel edges to a single unweighted edge would change the random walk.
Apply the Skorokhod reflection map on the half-line to Brownian motion with negative constant drift and positive variance parameter . The result is kept nonnegative by a regulator acting only at zero. It has a stationary distribution, unlike zero-drift reflection on the whole half-line.
Reflected chain with geometric downward jumps Created 2026-10-14 Updated 2026-11-05
Fix and put . For independent geometric random variables with for , the Reflected chain with geometric downward jumps obeys . Its transition probabilities are for and .
The Probability of hitting zero from is one when and when . The first-step boundary equation at is essential for the extra exponent. Before reflection the mean increment is : downward drift corresponds to .
The chain is positive recurrent for , with Stationary distribution for . The ratio ensures these weights sum to one. It is null recurrent at and transient for . The parameter restriction matters: does not define the displayed geometric distribution, and produces deterministic upward motion rather than an irreducible chain.
For , consider the Markov chain on the nonnegative integers with the displayed transition probabilities. From zero it starts a new upward run; from each positive state it either increments or resets. Writing , its stationary distribution is
The balance equations give and for ; the geometric series normalizes the result, and the zero-state equation agrees. It is an irreducible Markov chain and is positive recurrent. Equivalently, its first return time to zero is one plus a geometric random variable with success probability , so its mean recurrence time is . Return paths of lengths two and three also make it aperiodic.
Residual lifetime Markov chain Created 2026-09-24 Updated 2026-11-05
For a positive integer-valued lifetime , one discrete-time residual lifetime Markov chain uses states . From state it moves to . From zero it draws an independent new lifetime and moves to :
The subtraction of one specifies the sampling convention: the next step has already consumed one unit of the new lifetime. With this convention, successive visits to zero are separated by exactly steps, not .
Its Stationary distribution is . The tail-sum identity normalizes these masses, and the balance equations verify them, with the obvious top-state equation. If deterministically, the chain cycles and its stationary law is uniform. It is periodic, so a Stationary distribution does not imply convergence from every initial state.
Reversible density-ratio propagation Created 2026-10-06 Updated 2026-11-05
Let be a reversible Markov kernel with stationary Probability measure , and let the initial Probability measure have Radon-Nikodym derivative . After steps, Detailed balance gives
for -almost every . To prove the identity, integrate a bounded measurable test function against the evolved measure: , because reversibility makes self-adjoint in the integral pairing.
To express the result with ordinary probability density functions, fix a reference measure , write , and let . On the support where , , so the evolved density is
This formula uses the initial density , not the Probability measure evaluated at a point. The unknown normalizing constant cancels. Reverse simulation from can estimate this expression without evaluating the Transition density, provided the displayed integrand can be evaluated.
For example, the symmetric two-state kernel with holding Probability has Stationary distribution . Starting at state zero gives , then ; multiplying by the stationary masses recovers the one-step distribution .
Reversible four-cycle flow model Created 2026-10-05 Updated 2026-10-06
The proportionally fair allocation on a four-cycle produces a reversible Markov chain with stationary distribution proportional to . This is normalizable exactly when every resource's offered load is strictly below capacity, equivalently .
Place six positions on a cycle and distinguish two labels. At each step choose one of the fifteen unordered pairs of distinct positions uniformly and transpose their contents. This convention excludes identity moves. The shorter circular distance between the distinguished labels takes values . Cycle symmetry and exchangeability of the other labels make this distance a Lumped Markov chain.
Counting transpositions gives the transition matrix and Stationary distribution
The stationary weights also follow by counting unordered position pairs: six pairs have distance one, six have distance two, and three are opposite. If has every row equal to , then and . Starting with adjacent labels, the Probability of opposite labels after steps is therefore .
The parent Random transposition shuffle uses a different convention: two positions are sampled independently, allowing an identity move with Probability . Under that convention the distance transition matrix is , and the opposite-label Probability is . Explicitly stating the sampling convention prevents a spurious change in the convergence rate.
Separation distance Created 2026-09-24 Updated 2026-11-05
For a finite Markov chain with stationary distribution , the Separation distance from an initial state is
If is a strong stationary time, then , and total variation distance is at most Separation distance.
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 .
Spectral profile Created 2026-09-24 Updated 2026-11-05
The Spectral profile records the energy needed to concentrate a function on sets of a given stationary mass. For a finite irreducible Reversible Markov chain with Stationary distribution , define
Here is its Dirichlet form of a Markov chain, and ensures that admissible nonempty sets exist. This is the variance-normalized convention.[ref]
The profile is nonincreasing in , because enlarging permits more supports. The ordinary spectral gap is a lower bound on every , but small supports can force a larger Rayleigh quotient. For the symmetric two-state chain with off-diagonal Transition probability , a function supported on one state has energy and variance , so .
The denominator matters. Replacing variance by gives a restricted Dirichlet eigenvalue instead. On a support of mass at most , the Cauchy-Schwarz inequality gives , relating the two conventions within a factor .
Stationarity equations 2026-10-25
For a discrete-time Markov chain with transition matrix , these equations, together with and , say that is a stationary distribution. Incoming probability mass equals the current mass at each state. They are global balance equations and do not require detailed balance.
Stationary cycle occupation formula Created 2026-09-24 Updated 2026-11-05
For an irreducible positive recurrent Discrete-time Markov chain with Stationary distribution , fix a state and its positive first return . The Stationary cycle occupation formula is
The cycle includes the initial visit to and excludes the returning visit. Thus for the left side is exactly one, consistent with the ratio.
Successive return cycles are independent with the same law by the Strong Markov property. The renewal reward ratio gives the long-run visit fraction as expected cycle occupation divided by expected cycle length. Kac's lemma supplies , so the ergodic visit fraction gives the displayed identity. positive recurrence ensures the cycle length and all its occupation rewards are integrable.
For distinct , the Two-state excursion visit law gives the same expected occupation as , where and . Consequently
This identity does not require reversibility: it follows from return-cycle occupation. It also does not require aperiodicity, since time averages still converge in a periodic positive recurrent chain.
Stationary distribution Created 2026-09-24 Updated 2026-10-14
A stationary distribution is a probability distribution preserved by a Markov chain's evolution. For a Discrete-time Markov chain in the row convention,
Thus is a normalized nonnegative left eigenvector of the transition matrix for eigenvalue one. Starting with distributed as makes every have that same probability distribution. For a time-homogeneous Markov chain, the path probabilities are also unchanged by shifting all observation times together: the process has strict stationarity. This does not mean its individual paths are constant. See Hao Wu's MIT lecture 2, stationary distributions.
For the sunny/rainy transition matrix, write . The sunny component of gives , so and
Moreover,
These equal stationary flows verify detailed balance and show that the Markov chain is reversible. The diagonal detailed balance equations hold automatically. Only of the stationary days are rainy, but of the days following a rainy day are rainy: stationarity permits dependence.
A finite Markov chain that is an irreducible Markov chain has a unique stationary distribution. If it is also an aperiodic Markov chain, for every initial probability distribution. The sunny/rainy example satisfies both conditions: both directions are possible and each state has a positive holding probability of a Markov chain. See Hao Wu's MIT lecture 4, convergence theorem. For an infinite state space, the additional positive recurrence hypothesis in the countable-state Markov chain convergence theorem matters.
Existence of a stationary distribution alone does not give this convergence. Consider the deterministic two-cycle
Here , but starting in the first state gives alternating probability distributions . Its period of a state in a Markov chain is two. The running fraction of visits to either state nevertheless tends to , illustrating the Markov chain ergodic theorem. Starting with instead keeps the one-time probability distributions stationary even though every path alternates.
Figure 1.
A deterministic two-cycle has a stationary law, but its one-time probabilities oscillate while its time-averaged visits converge.
Details.
Stationary distribution existence for a finite Markov chain Created 2026-10-25 Updated 2026-11-05
Every finite Markov chain has a stationary distribution, without requiring Markov chain irreducibility or aperiodicity. For a row-stochastic matrix , put and choose a column probability vector . Every lies in the probability simplex. Their arithmetic averages therefore lie in this compact set, while telescoping gives
A convergent subsequence has a limit in the probability simplex. Continuity of matrix multiplication gives , so is a stationary distribution. The individual iterates need not converge: a deterministic two-state swap alternates its point masses forever.
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.
Stationary distribution of an M-M-infinity queue Created 2026-09-24 Updated 2026-11-05
For every , an queue is positive recurrent and has the Poisson distribution with mean as its unique Stationary distribution: