Absolute relaxation time 2026-10-06
For a finite irreducible Markov chain with at least two states that is an aperiodic Markov chain and a reversible Markov chain, put and . This is the reciprocal of the absolute L2 spectral gap of a reversible Markov chain. It agrees with the reciprocal of the ordinary spectral gap for a lazy Markov chain, but need not agree when there are negative eigenvalues.
Bernoulli-Laplace diffusion model Created 2026-10-25 Updated 2026-11-05
In the Bernoulli-Laplace diffusion model, two urns each contain balls, with red and blue balls in total. Independently choose one ball uniformly from each urn and exchange them. The red count in the first urn is a Markov chain on , with
The upward event exchanges a blue ball from the first urn with a red ball from the second; the downward event reverses the colors. Hence
Starting from , the mean is , with the initial value understood separately if the geometric factor is zero. For , this mean tends to . For , however, the only two configurations alternate and the expected imbalance does not decay.
The Stationary distribution is the hypergeometric distribution
It counts uniformly allocated red/blue configurations. The ratio verifies Detailed balance with the displayed transitions. The chain is irreducible; for an interior holding Probability also makes it aperiodic, while the chain has period two. This model separates convergence of an average imbalance from the full probability law and its periodicity.
Birth-death recurrence classification Created 2026-09-24 Updated 2026-11-05
Consider a birth-death process on with constant birth rate , constant death rate at every positive state, and no deaths from zero. The reflecting boundary is essential: the result changes if zero is an absorbing state. Detailed balance would give
When , these weights normalize to a Geometric distribution, so the irreducible chain is positive recurrent. When , the embedded jump chain is the symmetric reflected random walk: it returns to zero almost surely, but its constant equilibrium weights have infinite sum, so the chain is null recurrent. When , its upward-biased embedded random walk has probability of hitting zero from state one, making the chain transient. The holding rates are bounded, so nonexplosion creates no additional qualification here.
Suppose a Markov kernel satisfies for a measurable . For and , the sublevel set gives . If is a small set, this is a geometric drift condition. The hypotheses of an irreducible Markov chain and an aperiodic Markov chain are also required for the usual geometric ergodicity theorem.
Communicating class Created 2026-09-24 Updated 2026-10-14
In a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix , write when is accessible from , meaning for some . States communicate, written , when both and . Communication is an equivalence relation, and a communicating class is an entire equivalence class
Thus communicating classes form a partition of the state space; a smaller mutually communicating subset is not itself a class. See Maria Cameron's Markov Chains notes, section 1.2.
The allowance of zero steps matters: , the identity matrix, makes true even for a state with no possible positive-time return. Symmetry is built into communication. For transitivity, concatenate a positive-probability path from to with one from to , and do the same in reverse. These observations prove the equivalence relation directly. One-way accessibility alone is not symmetric and does not define the classes; see Accessible state of a Markov chain.
A closed communicating class satisfies for every and . Once entered, it cannot be left. A singleton class is an absorbing state exactly when it is closed. An open communicating class has an outgoing transition; after a path leaves it, it cannot return, since that would make the visited outside states communicate with it. The internal motion of a closed class can nevertheless continue forever.
Figure 1.
A constructed chain has three communicating classes: an open singleton, a closed alternating pair, and a closed absorbing singleton; dashed outlines group states into classes.
Details.
For this constructed example, in state order , the transition matrix is
There are exactly three communicating classes: , , and . Only the first is open. The second is closed but neither of its states is an absorbing state; they alternate deterministically. Although via , the reverse accessibility fails. A direct matrix power check gives and .
Starting at , let be the first hitting time of either closed class. Staying at for steps has probability , so and . The two eventual destination classes each have probability . Hence the hitting probability of the absorbing state is only , and its unconditional expected hitting time from is infinite: on half the paths it is never hit. In particular, entering a closed class with certainty does not imply entering an absorbing state with certainty.
Classifying the state space separates two questions: which closed region will eventually be entered, and how does the Markov chain move inside that region? In this example the restriction to is an irreducible Markov chain with period two; the restriction to is a one-state irreducible Markov chain with period one. The whole Markov chain is reducible. The absorbing state example illustrates a different possibility: every closed class is a singleton, so eventual class selection is also terminal outcome selection.
Conductance profile 2026-11-05
The conductance profile records bottlenecks at different stationary sizes in a finite irreducible Markov chain with at least two states. With stationary distribution and stationary flow , one convention is
This domain ensures that the minimizing family is nonempty. Other normalizations use the smaller side of a cut, so a convention must accompany a quoted profile.
For a lazy nearest-neighbor walk on an -cycle, holding with probability , a consecutive block of vertices has boundary flow and stationary mass , hence conductance . A profile therefore reveals how bottlenecks change with set size rather than retaining only one global minimum.[ref]
To see why continuous time removes periodicity, fix . Every finite sequence of Markov chain states connected by positive transition intensities has positive probability of finishing before , followed by no further transition until . Consequently the transition matrix has positive entries between every pair of communicating Markov chain states, including its diagonal. It is an irreducible Markov chain and an aperiodic Markov chain with stationary distribution . The countable-state Markov chain convergence theorem gives convergence at times , also in total variation distance. For , , applying contracts total variation distance and preserves , giving the full continuous-time limit.
Convergence to an invariant distribution Created 2026-09-24 Updated 2026-11-05
A finite irreducible Aperiodic Markov chain converges to its unique invariant distribution.
A cooling schedule for simulated annealing specifies successive effective temperatures and how many proposals to attempt at each. For example, with , using the geometric sequence, can define stages of equal chosen length. Changing changes the transition matrix: if the state probability distribution is , then , which generally differs from . Time spent at one temperature must be compared with its mixing time before equilibrium intuition is justified.
In the five-state barrier example for simulated annealing, fixed gives a finite irreducible Markov chain, so is eventually visited with probability one. That unbounded-time statement gives no fixed finite deadline. Over any finite number of trials starting at , the probability of staying at throughout is
Each factor is the rejection probability at . This is an explicit failure event even when every is positive: the best visited objective function value remains , above the global minimum value . More exploratory proposals can help cross a barrier; cooling before those moves occur can preserve a poor local minimum. Successful asymptotic schedules need additional analysis of the allowed moves and barriers.
Historically, Scott Kirkpatrick, Charles Daniel Gelatt Jr. and Mario P. Vecchi connected statistical mechanics with mathematical optimization in 1983. They adapted the Metropolis–Hastings algorithm to cooling searches with symmetric proposals and illustrated computer-design problems.[ref]
For an irreducible Markov chain on a finite or countable state space, a positive recurrent state implies a unique stationary distribution . If the chain is also an aperiodic Markov chain, its transition probabilities satisfy the displayed limit for every pair of states. The same limit holds from any initial probability distribution by bounded convergence. Positive recurrence cannot be omitted in the countably infinite case, and aperiodicity is required for ordinary, rather than averaged, convergence. This is the standard discrete-time convergence theorem; the finite-state statement alone does not cover unbounded renewal countdowns.
Countable-state Markov chain ergodic theorem Created 2026-10-25 Updated 2026-11-05
For an irreducible Markov chain on a countable state space with positive recurrence and stationary distribution , the displayed almost sure convergence holds from every initial state whenever . In particular, the empirical fraction of visits to converges to . No aperiodicity is needed. Regeneration at successive returns to a state reduces the result to the strong law of large numbers for independent excursion lengths and rewards. This extends the finite-state Markov chain ergodic theorem.
Detailed balance without rapid convergence Created 2026-10-25 Updated 2026-11-05
Detailed balance does not imply that a Markov chain is an irreducible Markov chain: the identity transition matrix is reversible for every probability distribution. Even for an irreducible Markov chain with aperiodicity, the two-state matrix with diagonal and off-diagonal , , has uniform stationary distribution and nontrivial eigenvalue . From either fixed state its total variation distance after steps is , so convergence can be arbitrarily slow. Invariance, reachability and mixing time are distinct questions.
If for a finite irreducible Markov chain with at least two states, then its worst-case total variation distance from its stationary distribution satisfies . Choose a possibly complex eigenfunction for an eigenvalue of modulus , normalize , and start where the maximum is attained. Since , ; the defining sum for total variation distance bounds this difference by . For , this yields for , because .
Empirical occupation proportions of a finite Markov chain Created 2026-10-31 Updated 2026-11-05
The empirical occupation proportion is the fraction of the observed Markov chain states equal to . These nonnegative fractions sum to one. To simulate them from a transition matrix, sample an initial state and then draw each successive state from the current state's row, accumulating visit counts. They are empirical frequencies for a finite path, whether or not the chain is already stationary. Long-run convergence to a Stationary distribution requires the corresponding recurrence and irreducibility hypotheses.
Equilibrium distribution of a continuous-time Markov chain Created 2026-10-14 Updated 2026-11-05
An Equilibrium distribution of a continuous-time Markov chain is a probability row vector invariant under its transition semigroup:
It satisfies when the generator sums are defined. An invariant law is a property of the entire evolution, so formal generator equations must be interpreted with the process's nonexplosion and domain conditions.
For a finite irreducible chain, the equilibrium distribution is unique and every transition row converges to it. For a general finite chain, the limiting row from state is a mixture of the stationary distributions of its closed irreducible classes:
The chain eventually enters one of these classes and then mixes within it. If every closed class is a single absorbing state, this reduces to absorption probabilities at those states. Merely having some absorbing states does not exclude other closed classes.
Holding times explain the link to an embedded jump chain. For a finite irreducible chain with strictly positive exit rates and jump-chain Stationary distribution , the time-stationary distribution is
Visit frequency is multiplied by mean time per visit. In the countable setting, these time weights need a finite positive normalizer and a nonexplosive process before they define an equilibrium probability. For an alternating two-state jump chain, and rates give : slower holding rates increase time occupancy.
Ergodic state of a Markov chain Created 2026-10-06 Updated 2026-11-05
In the standard discrete-time state terminology, an ergodic state is a positive recurrent state with aperiodicity. Return occurs almost surely, the mean strictly positive return time is finite, and the greatest common divisor of possible return lengths is one. An irreducible chain shares these properties among all its states.
Ergodic theorem for a finite continuous-time Markov chain Created 2026-10-06 Updated 2026-11-05
For a finite irreducible Markov chain in continuous time, time averages converge almost surely to averages under its unique stationary distribution, from any initial state. Applying this to an activation indicator yields the corresponding throughput.
Excursion weights of a reflected birth-death chain Created 2026-10-14 Updated 2026-11-05
Consider an irreducible Birth-death chain on . At zero let and . At , let and , with . Define
In the recurrent case, is the expected number of visits to during a cycle started at zero, counting times . The initial visit gives . Each upward crossing of an edge before the return is paired with a downward crossing, giving and the product formula. Tonelli's theorem then gives . Consequently the recurrent chain is positive recurrent exactly when this sum is finite, and its Stationary distribution is .
The finiteness criterion also rules out transience without assuming recurrence in advance. Put and . Then . If , then , so and . The birth-death scale-function hitting formula therefore implies recurrence. This separates stationary occupation weights from the inverse-direction scale weights , which serve different purposes.
On a finite state space with finite objective function values, the fixed- target is a Boltzmann distribution:
The partition function normalizes the weights but cancels from the Metropolis–Hastings acceptance probability. A short detailed balance proof explains the target. With symmetric and ,
Summing over gives , so this is a stationary distribution. On a finite state space, a connected graph of positive symmetric proposals makes the accepted Markov chain an irreducible Markov chain. Convergence from any starting state additionally requires an aperiodic Markov chain; one positive self-transition suffices under irreducibility. Replacing by ensures this. For asymmetric , require connectivity through bidirectional proposals: one-way proposals are rejected.[ref]
In the five-state barrier example for simulated annealing, gives exact Boltzmann weights . Multiplying by gives
For the uphill edge, detailed balance is visible numerically:
Thus the global minimum has the largest individual stationary probability, , but is far from certain at this positive . At the exact stationary distribution is .
Figure 1.
Lower temperature concentrates equilibrium weights while suppressing uphill acceptance
. Exact Boltzmann distributions for the chosen five-state objective function, and the uphill acceptance probability conditional on the proposal . The one-step transition probability is half that acceptance probability. The bars describe equilibrium at each fixed temperature, not the evolving probability distribution during cooling. Details.
For any finite , let be the set of global minima and the smallest objective function value. Cancelling from numerator and denominator shows that each nonminimal state's weight tends to zero as , while every state in has equal weight. Therefore tends to the uniform distribution on . This is a statement about a family of equilibrium probability distributions; it does not prove that a cooling Markov chain follows that family.
Let . The proportional scaling limit of the Erlang loss formula makes its limits at and respectively and . Since and , sufficiently large give alternating signs at these four points. The intermediate value theorem supplies three distinct zeros in the intervening intervals. These are multiple solutions of the Erlang fixed point approximation, not multiple stationary laws of an exact finite irreducible Markov chain.