Canonical paths comparison theorem

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 $P$ and $R$ be finite reversible transition matrices with the same positive Stationary distribution $\pi$. For every ordered pair with $R(x,y)>0$ and $x\ne y$, choose a path ${\gamma }_{xy}$ from $x$ to $y$ using positive $P$ transitions. Let $N_e(\gamma )$ count occurrences of a directed edge $e=(u,v)$ and putThen ${\mathcal{E}}_R(f,f)\le A{\mathcal{E}}_P(f,f)$ for every real-valued function $f$. Indeed, telescope $f(x)-f(y)$ along the path and apply the Cauchy-Schwarz inequality, multiply by $\pi (x)R(x,y)/2$, 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 ${\gamma }_P\ge {\gamma }_R/A$ for the ordinary spectral gaps. Choosing the reference chain $R(x,y)=\pi (y)$ gives ${\mathcal{E}}_R(f,f)={\mathrm{Var}}_{\pi }(f)$ and ${\gamma }_R=1$, 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 ${\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.