# 4.5 The flow parameter $\tau_{c}$

In this section it’s convenient to work in continuous time, but the numerical quantities involved here are unchanged by continuization.

## 4.5.1 Definition and easy inequalities

Define

 $\tau_{c}=\sup_{A}\frac{\pi(A)\pi(A^{c})}{Q(A,A^{c})}$ (4.34)

where

 $Q(A,A^{c})\equiv\sum_{i\in A}\sum_{j\in A^{c}}\pi_{i}q_{ij}$

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.

###### Lemma 4.36

The sup in (4.34) is attained by some split $\{A,A^{c}\}$ in which both $A$ and $A^{c}$ are connected (as subsets of the graph of permissible transitions).

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

 $\displaystyle Q(A,A^{c})$ $\displaystyle=$ $\displaystyle\sum_{i}Q(B_{i},B_{i}^{c})$ $\displaystyle\geq$ $\displaystyle\gamma\sum_{i}\pi(B_{i})\pi(B_{i}^{c})$ $\displaystyle=$ $\displaystyle\gamma\sum_{i}(\pi(B_{i})-\pi^{2}(B_{i}))$ $\displaystyle=$ $\displaystyle\gamma\left(\pi(A)-\sum_{i}\pi^{2}(B_{i})\right)$

and so

 $\frac{Q(A,A^{c})}{\pi(A)\pi(A^{c})}\geq\gamma\ \frac{\pi(A)-\sum_{i}\pi^{2}(B_% {i})}{\pi(A)-\pi^{2}(A)}.$

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

 $\frac{\pi(A)\pi(A^{c})}{Q(A,A^{c})}\leq\tau_{2}$

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

 $\frac{\pi(A)\pi(A^{c})}{Q(A,A^{c})}\leq\frac{\pi(A)E_{\pi}T_{A}}{\pi(A^{c})}% \leq\pi(A)E_{\alpha_{A}}T_{A}\leq\tau_{2}$

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

###### Corollary 4.37
 $\tau_{c}\leq\sup_{A}\frac{\pi(A)E_{\pi}T_{A}}{\pi(A^{c})}\leq\sup_{A}\pi(A)E_{% \alpha_{A}}T_{A}\leq\tau_{2}.$

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

 $\sup_{A:\pi(A)\leq 1/2}\frac{\pi(A)}{Q(A,A^{c})}$

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}$)

###### Open Problem 4.38

Does there exist a constant $K$ such that

 $\tau_{2}\leq K\sup_{A}\frac{\pi(A)E_{\pi}T_{A}}{\pi(A^{c})}$

for every reversible chain?

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

###### Lemma 4.39
 $\tau_{2}\leq\sup_{A:\pi(A)\geq 1/2}E_{\alpha_{A}}T_{A}$

and so in particular

 $\tau_{2}\leq 2\sup_{A}\pi(A)E_{\alpha_{A}}T_{A}.$

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

 $A=\{x:h(x)\leq 0\}$

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

 $\tau_{2}\leq||h_{+}||_{2}^{2}/\mbox{{\cal E}}(h_{+},h_{+})$ (4.35)

and then the extremal characterization Chapter 3 yyy

 $E_{\alpha_{A}}T_{A}=\sup\{||g||_{2}^{2}/\mbox{{\cal E}}(g,g):g\geq 0,g=0% \mbox{ on }A\}$ (4.36)

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

 $\partial\langle f,{\bf P}_{t}g\rangle=-\mbox{{\cal E}}(f,g)$

where

 $\mbox{{\cal E}}(f,g)=\frac{1}{2}\ \sum_{i}\sum_{j}(f(j)-f(i))(g(j)-g(i))q_{% ij}.$

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

 $\partial\langle h_{+},{\bf P}_{t}h\rangle=-\mbox{{\cal E}}(h_{+},h)\leq-% \mbox{{\cal E}}(h_{+},h_{+})$

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

 $\partial\langle h_{+},{\bf P}_{t}h\rangle\geq-\lambda_{2}||h_{+}||_{2}^{2}.$

Combining these inequalities leads to (4.35).

## 4.5.2 Cheeger-type inequalities

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

###### Theorem 4.40 (Cheeger’s inequality)

$\tau_{2}\leq 8q^{*}\tau^{2}_{c}$, where $q^{*}\equiv\max_{i}q_{i}$.

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.

###### Lemma 4.41

For any subset $A$,

 $E_{\alpha_{A}}T_{A}\leq\frac{2q^{*}\tau^{2}_{c}}{\pi^{2}(A)}.$

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

 $\displaystyle\left(\sum\sum_{x\neq y}|g^{2}(x)-g^{2}(y)|\pi_{x}q_{xy}\right)^{2}$ $\displaystyle\leq$ $\displaystyle\sum\sum_{x\neq y}(g(x)-g(y))^{2}\pi_{x}q_{xy}\times\sum\sum_{x% \neq y}(g(x)+g(y))^{2}\pi_{x}q_{xy}$ by the Cauchy-Schwarz inequality $\displaystyle=$ $\displaystyle 2\mbox{{\cal E}}(g,g)\sum\sum_{x\neq y}(g(x)+g(y))^{2}\pi_{x}q% _{xy}$ $\displaystyle\leq$ $\displaystyle 4\mbox{{\cal E}}(g,g)\sum\sum_{x\neq y}(g^{2}(x)+g^{2}(y))\pi_% {x}q_{xy}$ $\displaystyle=$ $\displaystyle 8\mbox{{\cal E}}(g,g)\sum_{x}\pi_{x}q_{x}g^{2}(x)$ $\displaystyle\leq$ $\displaystyle 8q^{*}\mbox{{\cal E}}(g,g)\ ||g||_{2}^{2}.$

On the other hand

 $\displaystyle\sum\sum_{x\neq y}|g^{2}(x)-g^{2}(y)|\pi_{x}q_{xy}$ $\displaystyle=$ $\displaystyle 2\sum\sum_{g(x)>g(y)}(g^{2}(x)-g^{2}(y))\pi_{x}q_{xy}$ $\displaystyle=$ $\displaystyle 4\sum\sum_{g(x)>g(y)}\left(\int_{g(y)}^{g(x)}tdt\right)\pi_{x}q_% {xy}$ $\displaystyle=$ $\displaystyle 4\int_{0}^{\infty}t\ \left(\sum\sum_{g(y)\leq t $\displaystyle=$ $\displaystyle 4\int_{0}^{\infty}t\ Q(B_{t},B^{c}_{t})\ dt\mbox{ where }B_{t}% \equiv\{x:g(x)>t\}$ $\displaystyle\geq$ $\displaystyle 4\int_{0}^{\infty}t\ \frac{\pi(B_{t})\ \pi(B^{c}_{t})}{\tau_{c}}% \ dt\mbox{ by definition of }\tau_{c}$ $\displaystyle\geq$ $\displaystyle 4\int_{0}^{\infty}t\ \frac{\pi(B_{t})\ \pi(A)}{\tau_{c}}\ dt% \mbox{ because }g=0\mbox{ on }A$ $\displaystyle=$ $\displaystyle\frac{2\pi(A)||g||_{2}^{2}}{\tau_{c}}.$

Rearranging,

 $\frac{||g||_{2}^{2}}{\mbox{{\cal E}}(g,g)}\leq\frac{2q^{*}\tau^{2}_{c}}{\pi^% {2}(A)}$

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

## 4.5.3 $\tau_{c}$ and hitting times

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.

###### Proposition 4.42
 $\tau^{*}\leq\frac{4(1+\log n)}{\min_{j}\pi_{j}}\ \tau_{c}.$

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.

 $\displaystyle\mbox{{\cal E}}(g,g)$ $\displaystyle=$ $\displaystyle\sum\sum_{i (4.37) $\displaystyle\geq$ $\displaystyle\sum\sum\sum_{i\leq j $\displaystyle=$ $\displaystyle\sum_{j}(g(j+1)-g(j))^{2}Q(A_{j},A^{c}_{j}),\mbox{ where }A_{j}% \equiv[1,j]$ $\displaystyle\geq$ $\displaystyle\sum_{j}(g(j+1)-g(j))^{2}\frac{\pi(A_{j})\pi(A^{c}_{j})}{\tau_{c}}$

But

 $1=\sum_{j}(g(j+1)-g(j))=\sum_{j}(g(j+1)-g(j))\ \frac{\pi^{1/2}(A_{j})\pi^{1/2}% (A^{c}_{j})}{\tau_{c}^{1/2}}\ \frac{\tau_{c}^{1/2}}{\pi^{1/2}(A_{j})\pi^{1/2}(% A^{c}_{j})}.$

So by Cauchy-Schwarz and (4.37)

 $1\leq\tau_{c}\mbox{{\cal E}}(g,g)\sum_{j}\frac{1}{\pi(A_{j})\pi(A^{c}_{j})}.$ (4.38)

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

 $\sum_{j:\pi(A_{j})\leq 1/2}\frac{1}{\pi(A_{j})\pi(A^{c}_{j})}\leq\sum_{j}\frac% {2}{j\pi_{*}}\leq\frac{2}{\pi_{*}}(1+\log n).$

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

 $\frac{1}{\mbox{{\cal E}}(g,g)}\leq\tau_{c}\ \frac{4}{\pi_{*}}(1+\log n)$

and the Proposition follows from the extremal characterization.

###### Example 4.43

Consider the weighted linear graph with loops on vertices $\{0,1,2,\ldots,n-1\}$, with edge-weights

 $w_{i-1,i}=i,\ 1\leq i\leq n-1;\ \ \ \ w_{ii}=2n-i1_{(i\neq 0)}-(i+1)1_{(i\neq n% -1)}.$

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

 $\tau^{*}=E_{0}T_{n-1}+E_{n-1}T_{0}=wr_{0,n-1}=2n^{2}\sum_{i=1}^{n-1}1/i\sim 2n% ^{2}\log n.$

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

 $\tau_{c}=2(n-1).$

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