4.5 The flow parameter $\tau_{c}$

Define

where

and where such $sups$ are always over proper subsets $A$ of states. This parameter can be calculated exactly in only very special cases, where the following lemma is helpful.

Proof. Consider a split $\{A,A^{c}\}$ in which $A$ is the union of $m\geq 2$ connected components $(B_{i})$. Write $\gamma=\min_{i}\frac{Q(B_{i},B_{i}^{c})}{\pi(B_{i})\pi(B_{i}^{c})}$. Then

and so

But for $m\geq 2$ we have $\sum_{i}\pi^{2}(B_{i})\leq\left(\sum_{i}\pi(B_{i})\right)^{2}=\pi^{2}(A)$, which implies $\frac{Q(A,A^{c})}{\pi(A)\pi(A^{c})}>\gamma$. $\Box$

To see how $\tau_{c}$ arises, note that the extremal characterization of $\tau_{2}$ (4.22) applied to $g=1_{A}$ implies

for any subset $A$. But much more is true: Chapter 3 yyy may be rephrased as follows. For any subset $A$,

where $\alpha_{A}$ is the quasistationary distribution on $A^{c}$ defined at Chapter 3 yyy. So taking sups gives

In a two-state chain these inequalities all become equalities. This seems a good justification for our choice of definition of $\tau_{c}$, instead of the alternative

which has been used in the literature but which would introduce a spurious factor of $2$ into the inequality $\tau_{c}\leq\tau_{2}$.

Lemma 4.39 below shows that the final inequality of Corollary 4.37 can be reversed. In contrast, on the $n$-cycle $\tau_{c}=\Theta(n)$ whereas the other quantities in Corollary 4.37 are $\Theta(n^{2})$. This shows that the “square” in Theorem 4.40 below cannot be omitted in general. It also suggests the following question (cf. $\tau_{1}$ and $\tau^{(5)}_{1}$)

A positive answer would provide, via Chapter 3 yyy, a correct order-of-magnitude extremal characterization of $\tau_{2}$ in terms of flows.

Proof. $\tau_{2}=||h||_{2}^{2}/\mbox{${\cal E}$}(h,h)$ for the eigenvector $h$ associated with $\lambda_{2}$. Put

and assume $\pi(A)\geq 1/2$, by replacing $h$ by $-h$ if necessary. Write $h_{+}=\max(h,0)$. We shall show

and then the extremal characterization Chapter 3 yyy

implies $\tau_{2}\leq E_{\alpha_{A}}T_{A}$ for this specific $A$.

The proof of (4.35) requires us to delve slightly further into the calculus of Dirichlet forms. Write ${\bf P}_{t}f$ for the function $({\bf P}_{t}f)(i)=E_{i}f(X_{t})$ and write $\langle f,g\rangle$ for the inner product $\sum_{i}\pi_{i}f(i)g(i)$. Write $\partial(\cdot)$ for $\frac{d}{dt}(\cdot)_{t=0}$. Then

where

Now consider $\partial\langle h_{+},{\bf P}_{t}h\rangle$. On the one hand

where the inequality follows from the inequality $(a^{+}-b^{+})^{2}\leq(a^{+}-b^{+})(a-b)$ for real $a,b$. On the other hand, $\langle h_{+},h\rangle\leq\langle h_{+},h_{+}\rangle=||h_{+}||_{2}^{2}$, and the eigenvector $h$ satisfies $\partial({\bf P}_{t}h)=-\lambda_{2}h$, so

Combining these inequalities leads to (4.35).

A lot of attention has been paid to reverse inequalities which upper bound $\tau_{2}$ in terms of $\tau_{c}$ or related “flow rate” parameters. Motivation for such results will be touched upon in Chapter yyy. The prototype for such results is

This result follows by combining Lemma 4.39 above with Lemma 4.41 below. In discrete time these inequalities hold with $q^{*}$ deleted (i.e. replaced by $1$), by continuization. Our treatment of Cheeger’s inequality closely follows Diaconis and Stroock [122] – see Notes for more history.

Proof. Fix $A$ and $g$ with $g\geq 0$ and $g=0$ on $A$.

On the other hand

Rearranging,

and the first assertion of the Theorem follows from the extremal characterization (4.36) of $E_{\alpha_{A}}T_{A}$.

Lemma 4.25 and Theorem 4.40 imply a bound on $\tau^{*}$ in terms of $\tau_{c}$. But a direct argument, using ideas similar to those in the proof of Lemma 4.41, does better.

Example 4.43 below will show that the log term cannot be omitted. Compare with graph-theoretic bounds in Chapter 6 section yyy.

Proof. Fix states $a,b$. We want to use the extremal characterization (Chapter 3 yyy). So fix a function $0\leq g\leq 1$ with $g(a)=0,g(b)=1$. Order the states as $a=1,2,3,\ldots,n=b$ so that $g(\cdot)$ is increasing.

But

So by Cauchy-Schwarz and (4.37)

But $\pi(A_{j})\geq j\pi_{*}$, where $\pi_{*}\equiv\min_{i}\pi_{i}$, so

The same bound holds for the sum over $\{j:\pi(A_{j})\geq 1/2\}$, so applying (4.38) we get

and the Proposition follows from the extremal characterization.

This gives vertex-weights $w_{i}=2n$, and so the stationary distribution is uniform. By the commute interpretation of resistance,

Using Lemma 4.36, the value of $\tau_{c}$ is attained by a split of the form $\{[0,j],[j+1,n-1]\}$, and a brief calculation shows that the maximizing value is $j=0$ and gives

So in this example, the bound in Proposition 4.42 is sharp up to the numerical constant.