Canonical paths comparison theorem Created 2026-09-28 Updated 2026-11-05
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 put
Then 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.
On a finite state space with at least two states, as in the surrounding questions, for a real function write and . The Poincare inequality for a reversible Markov chain with constant is
where the Dirichlet form of a Markov chain is
The associated spectral gap is the ordinary gap , with variational formula
Equivalently minimize subject to and . Thus the Poincare inequality for a reversible Markov chain holds precisely for , and the optimal constant is . It controls the ordinary rather than absolute spectral gap, so negative eigenvalues do not invalidate it. If the unspecified state space in this part is infinite, the Poincare inequality for a reversible Markov chain and the variational infimum still make sense on nonconstant functions in , using the self-adjoint operator on that Hilbert space; the resulting spectral gap need not be represented by an actual second eigenvalue. The finite-state formula above is the intended specialization.
For a finite irreducible Markov chain satisfying detailed balance, define the directed-edge capacity . For every ordered pair choose a path from to using only positive-capacity edges; take the empty path for . Let count occurrences of the directed edge . The canonical paths Poincare bound says that
is a valid Poincare inequality for a reversible Markov chain constant. Simple paths give ; allowing repetitions requires the multiplicities shown.
To prove the theorem, expand the variance using two independent samples from :
Telescoping along and applying the Cauchy-Schwarz inequality gives
Interchange the finite sums, then use the definition of :
Consequently . All edges here are directed, so the in the Dirichlet form of a Markov chain is retained consistently.
For each subset , take the Walsh character , including . Under the uniform distribution on a finite set these functions are an orthonormal basis: has mean zero unless , since the coordinates are independent fair signs. There are such functions, the full dimension of the function space.
Flipping a coordinate in changes the sign, while flipping one outside leaves the value unchanged. The total probability of a sign change is , so
The spectrum of lazy random walk on the hypercube is therefore
All eigenvalues are nonnegative and the second largest is . Hence both the ordinary spectral gap and the absolute spectral gap equal . The requested bound in part (c) is smaller than the exact gap by a factor ; even the refined increasing-coordinate canonical paths Poincare bound loses a factor . The true optimal Poincare inequality for a reversible Markov chain constant is .
Use . The Dirichlet form of a Markov chain is
The equality follows by expanding the square and using row sums one and the stationary distribution identity. For the reversible Markov chain, detailed balance makes a self-adjoint operator, with real orthonormal eigenbasis and ordered eigenvalues .
Adding a constant changes neither the variance nor the Dirichlet form of a Markov chain. Expand the centered function as . Then
For every nonconstant the quotient is at least , and equality is attained at . This proves
Equivalently minimize the Dirichlet form of a Markov chain over centered unit-norm functions. This is the variational characterization underlying the Poincare inequality for a reversible Markov chain, and does not require the transition matrix to have nonnegative eigenvalues. For a one-state chain there is no nonconstant test function; the displayed minimization concerns .
Poincare inequality for a reversible Markov chain Created 2026-10-06 Updated 2026-10-14
For a finite irreducible Markov chain with at least two states satisfying detailed balance, its Dirichlet form of a Markov chain obeys
Expand 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.
Tagged-label Rayleigh quotient for adjacent transpositions Created 2026-10-06 Updated 2026-11-05
For the random adjacent transposition shuffle on with , the position of one label is uniform on in equilibrium, so . Each adjacent transposition moves the label with Probability , giving . The Poincare inequality for a reversible Markov chain variational formula therefore gives . In particular the continuous uniform distribution on has variance , not .