Reversible Markov chain

A stationary Markov chain $(X_t:0\le t\le T)$ is reversible in equilibrium when it has the same finite-dimensional distributions as its time reversal $(X_{T-t}:0\le t\le T)$. 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 $2n$ vertices and $m\ge 1$ 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 $I△F$ canonically. Convert each component from initial matching in a graph $I$ to final matching in a graph $F$ 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 $M$, the complementary encoding $K=I△F△M$ 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 $K^{\prime }$. Record those edges and one bit selecting the initial alternating colour on the active component. For a fixed directed transition this data reconstructs $K$, $I△F$, the active component and its ordering, and then $I,F$; common edges are $M\cap K$. There are at most $2(m+1{)}^2$ auxiliary records per $K^{\prime }$.

If $d=|K|-|K^{\prime }|\le 2$, then ${\pi }_{\lambda }(I){\pi }_{\lambda }(F)={\lambda }^d{\pi }_{\lambda }(M){\pi }_{\lambda }(K^{\prime })$. The transition capacity is at least ${\pi }_{\lambda }(M)/(2m\max (\lambda ,{\lambda }^{-1}))$, and the path length is at most $4n$. Summing over the injective encodings proves the displayed path congestion bound.

Under a stationary initial law, reversal leaves the law of a finite reversible-chain path unchanged. The first time an ordered occurrence of state $a$ then state $b$ appears therefore has the same distribution as the reverse ordered occurrence. Decomposition at the first entrance relates this symmetry to differences of mean hitting times. If positive diagonal return times are used instead of zero diagonal entrance times, their stationary-weighted terms cancel by Kac's lemma.

For a reversible Markov chain with stationary distribution $\pi$ and $\nu \ll \pi$, detailed balance givesTo prove this, integrate either side against a bounded test function and exchange the two endpoints using detailed balance. If $\pi =h/Z$, the output probability density function is $q_t(x)=h(x){\mathbb{E}}_{B\sim K^t(x,\cdot )}[\nu (B)/h(B)]$. A reverse simulation can therefore estimate this density ratio without evaluating a transition probability density function.

For a finite irreducible Markov chain satisfying detailed balance with $\pi$, its transition matrix is a self-adjoint operator for $⟨f,g{⟩}_{\pi }={\sum }_x\pi (x)f(x)g(x)$. For a real orthonormal eigenbasis $(f_j)$ with eigenvalues $({\lambda }_j)$,Indeed, apply the spectral decomposition of $P^t$ to the function $1_{\{y\}}/\pi (y)$, whose coefficient against $f_j$ is $f_j(y)$. For $t=0$, every eigenvalue multiplier is interpreted as one.

Detailed balance is the identity pi_i P_ij = pi_j P_ji for every pair of states.

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 $1-\epsilon$ and off-diagonal $\epsilon$, $0<\epsilon <1/2$, has uniform stationary distribution and nontrivial eigenvalue $1-2\epsilon$. From either fixed state its total variation distance after $n$ steps is $\frac{1}{2}(1-2\epsilon {)}^n$, so convergence can be arbitrarily slow. Invariance, reachability and mixing time are distinct questions.

For a continuous-time Markov chain with transition rates $q_{ij}$, 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 $\pi Q=0$. Under the standard nonexplosion assumptions, the equilibrium chain is reversible.

For a reversible transition matrix $P$ with invariant distribution $\pi$,

This chain energy is a discrete example of a Dirichlet form.

For a finite irreducible Markov chain with at least two states satisfying detailed balance, its Dirichlet form of a Markov chain obeysExpand $f-\pi (f)$ in an orthonormal eigenbasis. The denominator is ${\sum }_{j\ge 2}{a}_j^2$, and the numerator is ${\sum }_{j\ge 2}(1-{\lambda }_j)a_j^2$. Their ratio is at least $1-{\lambda }_2$ and equality holds for the second eigenfunction. Thus the optimal Poincare inequality for a reversible Markov chain constant is $1/\gamma$, for the ordinary rather than absolute spectral gap.

On an unweighted graph, the discrete Dirichlet energy is proportional to ${\sum }_{xy\in E}(f(x)-f(y){)}^2$. It measures the squared variation of a function across edges.

The canonical paths comparison theorem compares two reversible chains by routing every transition of one chain along a path of transitions of the other. The maximum capacity-normalized path congestion bounds the ratio of their Dirichlet forms and hence their spectral gaps.

Choose a directed path ${\eta }_{xy}$ of positive-probability transitions for each ordered pair of states in a finite reversible Markov chain. Write $Q(e)=\pi (u)P(u,v)$ for a directed edge $e=(u,v)$, and let $N_e(\eta )$ count its occurrences. DefineThe Cauchy-Schwarz inequality bounds $(f(x)-f(y){)}^2$ by $|{\eta }_{xy}|$ times the sum of squared differences along the path. Multiply by $\pi (x)\pi (y)/2$, sum and interchange finite sums. The identity ${\mathrm{Var}}_{\pi }(f)=\frac{1}{2}{\sum }_{x,y}\pi (x)\pi (y)(f(x)-f(y){)}^2$ proves the bound. This convention counts directed edges and retains the factor $1/2$ 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, $H_0$ is the completion of the finitely supported functions in the norm $\Vert f{\Vert }_{H_0}=\mathcal{E}(f,f{)}^{1/2}$. 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: $t_{\mathrm{rel}}=(1-{\lambda }_2{)}^{-1}$.

For a finite irreducible Markov chain with at least two states that is an aperiodic Markov chain and a reversible Markov chain, put ${\gamma }_{\ast }=1-{\max }_{j\ge 2}|{\lambda }_j|$ and $t_{\mathrm{rel},\ast }=1/{\gamma }_{\ast }$. 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 $1-{\lambda }_2$ for a lazy Markov chain, but need not agree when there are negative eigenvalues.

The spectral profile minimizes a Dirichlet-form Rayleigh quotient over nonnegative functions supported on sets of stationary mass at most $r$.

For the isoperimetric profile ${\Phi }_{\ast }(r)$ of a reversible chain and $r\le 1/2$,

For a reversible Markov chain with stationary flow $Q(x,y)=\pi (x)P(x,y)$, the conductance of a set $A$ isIts Cheeger constant minimizes the boundary flow divided by the smaller stationary mass of the two sides of the cut.

The Cheeger constant of a finite reversible chain is the least stationary boundary flow divided by the smaller stationary mass of a set and its complement.

For a reversible chain with spectral gap $\gamma$ and Cheeger constant $\Phi$,