Dirichlet form of a Markov chain ($\mathcal{E}(f,g)$)

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$,