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.

For a finite undirected graph with unit edge conductances, define the Discrete Dirichlet energy of a real-valued function $f$ byEach undirected edge is counted once. More generally, multiply each term by its edge conductance. The energy is nonnegative and vanishes exactly when $f$ is constant on every connected component. Large differences across strongly conducting edges are expensive; this is why Discrete Dirichlet energy appears in harmonic extension and electrical-network principles.

Normalization depends on the chain. For simple random walk on a finite connected unweighted graph with $m$ edges, the Stationary distribution is $\pi (x)=\mathrm{deg}(x)/(2m)$, so its Dirichlet form of a Markov chain is ${\mathcal{E}}_P(f,f)={\mathcal{E}}_G(f,f)/(2m)$. On the three-vertex path with values $0,1,0$, the graph energy is $2$, whereas the simple-random-walk energy is $1/2$. Stating which normalization is used matters when comparing spectral gaps or effective resistances.

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.

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 records the energy needed to concentrate a function on sets of a given stationary mass. For a finite irreducible Reversible Markov chain with Stationary distribution $\pi$, defineHere $\mathcal{E}$ is its Dirichlet form of a Markov chain, and $r\ge {\pi }_{\ast }:={\min }_x\pi (x)$ ensures that admissible nonempty sets exist. This is the variance-normalized convention.^[ref]

The profile is nonincreasing in $r$, because enlarging $r$ permits more supports. The ordinary spectral gap is a lower bound on every $\Lambda (r)$, but small supports can force a larger Rayleigh quotient. For the symmetric two-state chain with off-diagonal Transition probability $a>0$, a function supported on one state has energy $a{c}^2/2$ and variance $c^2/4$, so $\Lambda (1/2)=2a$.

The denominator matters. Replacing variance by ${\sum }_x\pi (x)f(x{)}^2$ gives a restricted Dirichlet eigenvalue instead. On a support of mass at most $r<1$, the Cauchy-Schwarz inequality gives ${\mathrm{Var}}_{\pi }(f)\ge (1-r)\Vert f{\Vert }_{L^2(\pi )}^2$, relating the two conventions within a factor $1/(1-r)$.

For a finite irreducible Reversible Markov chain with Stationary distribution $\pi$, let $Q(x,y)=\pi (x)P(x,y)$ and define its conductance profile byFor ${\pi }_{\ast }:={\min }_x\pi (x)\le r\le 1/2$ and the variance-normalized Spectral profile,The star here names the small-set profile on this restricted domain; some sources reserve a star for its extension truncated at $1/2$.^[ref]

For the upper bound, test the spectral-profile quotient with $f=1_A$. Its energy is $Q(A,A^c)$ and its variance is $\pi (A)(1-\pi (A))$. For the lower bound, take a nonnegative function supported on a set of mass at most $r$. Applying the level-set integral identity to $f^2$ bounds ${\Phi }_{\ast }(r)\Vert f{\Vert }_2^2$ by $\frac{1}{2}{\sum }_{x,y}Q(x,y)|f(x{)}^2-f(y{)}^2|$. Factoring the difference of squares and applying the Cauchy-Schwarz inequality bounds this last expression by $\sqrt{2\mathcal{E}(f,f)}\Vert f{\Vert }_2$. Squaring and using ${\mathrm{Var}}_{\pi }(f)\le \Vert f{\Vert }_2^2$ proves the lower bound. Thus a geometric obstruction to boundary flow produces an analytic obstruction to relaxation.