Canonical paths comparison theorem

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.