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

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.

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

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

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.

$\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).

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

$\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.

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<g(x)}\pi_{x}q_{% xy}\right)\ dt$ | |||

$\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}$.

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.

$\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<k}\pi_{i}q_{ik}(g(k)-g(i))^{2}$ | (4.37) | ||

$\displaystyle\geq$ | $\displaystyle\sum\sum\sum_{i\leq j<k}\pi_{i}q_{ik}(g(j+1)-g(j))^{2}$ | ||||

$\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.

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.

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML