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.
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.
Here the graph has vertices and edges. The bound is a deliberately loose canonical paths Poincare bound, sufficient for polynomial mixing time when both activity and reciprocal activity are polynomially bounded. Order the alternating graph paths and cycles of canonically. Convert each component from initial matching in a graph to final matching in a graph by moving an unmatched endpoint using exchanges; open a cycle with one deletion and finish it with one addition.
At an intermediate matching in a graph , the complementary encoding is a matching in a graph away from the active component and has at most two degree-two vertices. Remove at most two edges to obtain a matching in a graph . Record those edges and one bit selecting the initial alternating colour on the active component. For a fixed directed transition this data reconstructs , , the active component and its ordering, and then ; common edges are . There are at most auxiliary records per .
If , then . The transition capacity is at least , and the path length is at most . Summing over the injective encodings proves the displayed path congestion bound.
Let a Reversible Markov chain start in its Stationary distribution , and let . Define to be the first time an occurrence of has been followed strictly later by an occurrence of :For each fixed , the event says that the path segment contains before . Reversing that segment changes the event into the existence of before . Stationary reversibility therefore gives for every , so the two completion times have the same distribution.
For a finite irreducible chain, all these expected hitting times are finite. Let and , with . The Strong Markov property at gives . Applying the same argument with reversed yieldsIf the diagonal is instead defined by the positive mean return time , its contribution to each stationary-weighted mean is one by Kac's lemma. Those equal additions cancel in the displayed difference.
Let be a reversible Markov kernel with stationary Probability measure , and let the initial Probability measure have Radon-Nikodym derivative . After steps, Detailed balance givesfor -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 isThis 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 .
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.
For a Markov chain with transition matrix , Detailed balance with a probability distribution meansThe left side is the equilibrium Probability of the directed transition ; Detailed balance equates it to the reverse flow. Summing over gives , so Detailed balance implies stationarity. Under the stationary initial law, repeated application of the pairwise identity equates a finite path's Probability to that of its reversal, establishing reversibility.[ref]
Mixing Time Bounds via the Spectral Profile by Sharad Goel and others. Section 1.1: invariant measure and reversibility
For example, takeThe off-diagonal flows are both , which verifies Detailed balance and the Stationary distribution directly. A directed three-state cycle has a uniform Stationary distribution but no reverse transitions, so it is not reversible. Stationarity alone therefore does not imply Detailed balance, and Detailed balance alone does not imply rapid convergence.
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.
For a continuous-time Markov chain with transition rates , Detailed balance isfor every pair of distinct states. A probability distribution satisfying these equations is an invariant distribution of a continuous-time Markov chain, because summing over incoming rates gives . Under the standard nonexplosion assumptions, the equilibrium chain is reversible.
For a finite irreducible Markov chain with at least two states satisfying detailed balance, its Dirichlet form of a Markov chain obeysExpand in an orthonormal eigenbasis. The denominator is , and the numerator is . Their ratio is at least and equality holds for the second eigenfunction. Thus the optimal Poincare inequality for a reversible Markov chain constant is , for the ordinary rather than absolute spectral gap.
For a finite undirected graph with unit edge conductances, define the Discrete Dirichlet energy of a real-valued function byEach undirected edge is counted once. More generally, multiply each term by its edge conductance. The energy is nonnegative and vanishes exactly when is constant on every connected component. Large differences across strongly conducting edges are expensive; this is why Discrete Dirichlet energy appears in harmonic extension and electrical-network principles.
Normalization depends on the chain. For simple random walk on a finite connected unweighted graph with edges, the Stationary distribution is , so its Dirichlet form of a Markov chain is . On the three-vertex path with values , the graph energy is , whereas the simple-random-walk energy is . Stating which normalization is used matters when comparing spectral gaps or effective resistances.
The Canonical paths comparison theorem transfers a spectral-gap estimate from a reference Reversible Markov chain to another chain by routing reference transitions along allowed target transitions. Let and be finite reversible transition matrices with the same positive Stationary distribution . For every ordered pair with and , choose a path from to using positive transitions. Let count occurrences of a directed edge and putThen for every real-valued function . Indeed, telescope along the path and apply the Cauchy-Schwarz inequality, multiply by , and sum over ordered pairs. Collecting the contribution of each directed edge gives the stated capacity-normalized congestion.
The variational Poincare inequality for a reversible Markov chain now gives for the ordinary spectral gaps. Choosing the reference chain gives and , recovering the Canonical paths Poincare bound. This makes a local-transition chain comparable to a chain that resamples its entire state in one step. The common invariant distribution and directed-edge counting convention are part of this formulation.
Choose a directed path of positive-probability transitions for each ordered pair of states in a finite reversible Markov chain. Write for a directed edge , and let count its occurrences. DefineThe Cauchy-Schwarz inequality bounds by times the sum of squared differences along the path. Multiply by , sum and interchange finite sums. The identity proves the bound. This convention counts directed edges and retains the factor in the Dirichlet form of a Markov chain.
For a family of transition graph paths, Path congestion is the largest, over transitions, ratio of routed pair weight times path length to stationary transition capacity. The canonical paths Poincare bound makes this an upper bound on the relaxation time.
For a transient weighted graph, is the completion of the finitely supported functions in the norm . Its elements have finite Dirichlet energy and vanish at infinity in the energy sense.
The Relaxation time of a finite reversible lazy Markov chain is the reciprocal of its spectral gap: .
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.
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 , defineHere 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 .
For a finite irreducible Reversible Markov chain with Stationary distribution , let and define its conductance profile byFor and the variance-normalized Spectral profile,The star here names the small-set profile on this restricted domain; some sources reserve a star for its extension truncated at .[ref]
Mixing Time Bounds via the Spectral Profile by Sharad Goel and others. Section 2.2, Definition 2.2 and Lemma 2.4
For the upper bound, test the spectral-profile quotient with . Its energy is and its variance is . For the lower bound, take a nonnegative function supported on a set of mass at most . Applying the level-set integral identity to bounds by . Factoring the difference of squares and applying the Cauchy-Schwarz inequality bounds this last expression by . Squaring and using proves the lower bound. Thus a geometric obstruction to boundary flow produces an analytic obstruction to relaxation.
For a reversible Markov chain with stationary flow , the conductance of a set isIts Cheeger constant minimizes the boundary flow divided by the smaller stationary mass of the two sides of the cut.
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 isThis 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]
Mixing Time Bounds via the Spectral Profile by Sharad Goel and others. Section 2.2, conductance-profile comparison; cycle calculation supplied here
Articles by others on the same topic
There are currently no matching articles.