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 Markov chain Created 2026-09-24 Updated 2026-11-05
A stationary Markov chain is reversible in equilibrium when it has the same finite-dimensional distributions as its time reversal . Equivalently, its stationary flow satisfies Detailed balance.
Spectral kernel expansion of a reversible chain Created 2026-10-06 Updated 2026-11-05
For a finite irreducible Markov chain satisfying detailed balance with , its transition matrix is a self-adjoint operator for . For a real orthonormal eigenbasis with eigenvalues ,
Indeed, apply the spectral decomposition of to the function , whose coefficient against is . For , every eigenvalue multiplier is interpreted as one.
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 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 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.
For the proportionally fair allocation on a linear flow network, independent Poisson flow arrivals at rates and exponential document sizes of rates give a continuous-time Markov chain with departures . Put . Under for each local route, the normalizing constant is . The binomial coefficient weight has adjacent-state ratios equal to the aggregate service rates, proving detailed balance. For more general network topologies, proportional fairness need not give this reversible product form.
The proportionally fair allocation on a four-cycle has aggregate service on each active odd route and on each active even route. With Poisson arrival rates and exponential document-size parameters , the departure intensity is . The adjacent ratios of the displayed binomial coefficient weight cancel those intensities in detailed balance, with .
On states , take an interior step of or with probability each and hold with probability . At an endpoint take the inward step with probability and hold with probability . For and , the chain is irreducible and its stationary distribution has endpoint weights and interior weights .
Detailed balance proves this: the doubled inward endpoint transition requires its stationary mass to be half that of an adjacent interior point, and all interior points have equal mass. The total unnormalized weight is . For there are just two equal endpoint masses.
When , positive self-loops make the chain aperiodic, so its transition probabilities converge to this law. At every move changes parity and two-step returns are possible, giving period two and no such convergence from a fixed starting state. At every state is absorbing and uniqueness of the stationary law is lost.
Stationary position of a transposed distinguished book Created 2026-10-31 Updated 2026-11-05
Place books in a row and distinguish one of them. At each step select the distinguished book with Probability and each of the other books with Probability . Swap the selected book with its left neighbour; selecting the leftmost book leaves the ordering unchanged.
The distinguished book's position is a birth-death chain. From an interior position it moves left with Probability , moves right with Probability when the book immediately to its right is selected, and otherwise holds. Missing outward moves at the endpoints become holding. Detailed balance therefore gives for . With ,
This finite Truncated geometric distribution is valid even when : both numerator and denominator then have the same negative sign. The uniform case is , when every book is selected equally often. Large selection Probability for the distinguished book biases it toward the left end. The strict range of ensures positive motion in both directions and avoids division by zero in the ratio.
Stationary weights of a reflected birth-death chain Created 2026-10-25 Updated 2026-11-05
Consider an irreducible Markov chain on the nonnegative integers with up-step probabilities and down-step probabilities for , reflected at zero. The displayed weights satisfy detailed balance. Every stationary distribution is proportional to them: the stationary equation at zero sets the edge flow to zero, and the remaining stationary equations make the flow constant along all edges. Hence positive recurrence is equivalent to , and then . This also allows holding probabilities of a Markov chain.
In an ordered queue, let be the fraction of service capacity assigned to position when customers are present. A symmetric discipline inserts an arrival into position with probability . The same position rule for service and insertion makes transitions satisfy detailed balance for the word weights . It accommodates class-dependent exponential service rates; processor sharing is an example.
Every full-conditional coordinate update satisfies detailed balance with the target distribution. Their systematic ordered composition preserves the target but need not satisfy detailed balance, since compositions of reversible kernels need not be reversible. A fixed-probability random-scan mixture remains reversible.
Three-level no claims discount equilibrium Created 2026-10-14 Updated 2026-11-05
For a three-level birth-death chain whose down-or-stay claim probabilities are , with each in , detailed balance is and . Normalizing gives the displayed stationary distribution. The finite chain is irreducible and has endpoint holding probabilities, so it is aperiodic and its level proportions converge to this distribution from any initial level.
Time reversal of a continuous-time Markov chain Created 2026-10-05 Updated 2026-11-05
For an equilibrium chain with strictly positive stationary probabilities, reversed jump rates are . Under detailed balance they equal the original rates, making the stationary path law reversible. Holding times and jump directions reverse together; this is more than symmetry of one-time distributions.
Time-reversed Markov chain Created 2026-09-29 Updated 2026-11-05
For a stationary Markov chain with transition matrix and Stationary distribution , the time-reversed Markov chain has transition matrix
on the support . The Stationary distribution is essential: Bayes' rule gives . The quotient is not defined at a zero-mass state, so arbitrary states outside the stationary support must not be included without an extra convention.
The stationarity equations give . Also , so the reversed kernel has the same invariant law. Multiplying the pairwise identity along a finite path proves equality between its forward Probability and the Probability of the reversed path under .
The reversed chain need not be the original chain. A directed three-state cycle has uniform Stationary distribution; time reversal traverses the cycle in the opposite direction. A stationary chain is reversible exactly when , which is equivalent to Detailed balance.
To minimize over models with different parameter dimensions, sample from a target proportional to and cool . A dimension-matching proposal augments the smaller model by auxiliary variables, transforms them bijectively into the larger parameter vector, and includes the proposal probability density function and absolute Jacobian determinant in the Metropolis–Hastings acceptance probability. For a positive Poisson mean and normal parameters , one convenient transformation is
Its absolute Jacobian determinant is one. If the forward and reverse model-jump selection probabilities are and , the Poisson-to-normal ratio is
The reverse ratio is its reciprocal at the inverse map. This enforces detailed balance. When the target is proper and the annealing chain explores it adequately, the low-temperature laws concentrate on the minimum Akaike information criterion, rather than the maximum marginal model evidence. Likelihoods compared across models must describe the same observed data with a compatible reference measure.
Weighted graph Created 2026-09-24 Updated 2026-11-05
An edge-weighted graph assigns a numerical weight to each graph edge. The meaning depends on the model: a weight can be a length, a cost, or an electrical conductance. Arbitrary weights do not automatically define transition probabilities.
For the random walk convention used here, take a locally finite undirected graph with symmetric nonnegative electrical conductances , and optional nonnegative killing weights . Assume
The Markov chain moves from to with probability and goes to a cemetery state with probability . These probabilities sum to one. With no killing, detailed balance holds with respect to the measure ; normalization gives a stationary distribution when its total mass is finite.
For example, electrical conductances and on the two edges incident to an graph vertex give outgoing probabilities and . Treating the same weights as electrical resistances would require reciprocal electrical conductances and reverse these preferences. The distinction is essential in the electrical network interpretation.
Weighted matching Markov chain Created 2026-10-14 Updated 2026-11-05
On the matchings in a graph, a lazy Markov chain proposes adding an edge, deleting an edge, or exchanging an edge for the unique matching edge incident with it. A proposal incident with two matching edges is rejected. Select the proposed edge uniformly and use the Metropolis–Hastings acceptance probability for the displayed weights. Symmetric proposals give detailed balance; deletions connect every state to the empty matching in a graph. The normalizing constant is the matching generating function.