xxx For NOTES: Nash vs. Sobolev

A Nash inequality for a chain is an inequality of the form

$\|g\|^{2+\frac{1}{D}}_{2}\leq C\,[\mbox{${\cal E}$}(g,g)+{\textstyle\frac{1}{T% }}\|g\|^{2}_{2}]\,\|g\|^{1/D}_{1}$ | (8.46) |

that holds for some positive constants $C$, $D$, and $T$ and for all functions $g$. We connect Nash inequalities to mixing times in Section 8.3.1, and in Section 8.3.2 we discuss a comparison method for establishing such inequalities.

A Nash inequality implies a useful bound on the quantity

$N(t)=\|{\bf P}_{t}\|_{2\to\infty}$ | (8.47) |

appearing in the mixing time Lemma 8.13. This norm is continuous in $t$ and decreases to $\|{\bf E}\|_{2\to\infty}=1$ as $t\uparrow\infty$. Here is the main result:

Proof. First note $N(t)=\|{\bf P}_{t}\|_{1\to 2}$ by Lemma 8.12. Thus we seek a bound on $h(t):=\|{\bf P}_{t}g\|^{2}_{2}$ independent of $g$ satisfying $\|g\|_{1}=1$; the square root of such a bound will also bound $N(t)$.

Substituting ${\bf P}_{t}g$ for $g$ in (8.46) and utilizing the identity in Lemma 8.10(a) and the fact that ${\bf P}_{t}$ is contractive on $L^{1}$, we obtain the differential inequality

$h(t)^{1+\frac{1}{2D}}\leq C\,[-{\textstyle\frac{1}{2}}h^{\prime}(t)+{% \textstyle\frac{1}{T}}h(t)],\ \ \ t\geq 0.$ |

Writing

$H(t):=\left[{\textstyle\frac{1}{2}}Ch(t)e^{-2t/T}\right]^{-1/(2D)},$ |

the inequality can be equivalently rearranged to

$H^{\prime}(t)\geq\left[2D(C/2)^{1+\frac{1}{2D}}\right]^{-1}e^{\frac{t}{DT}},\ % \ \ t\geq 0.$ |

Since $H(0)>0$, it follows that

$H(t)\geq T\left[2(C/2)^{1+\frac{1}{2D}}\right]^{-1}\left(e^{\frac{t}{DT}}-1% \right),\ \ \ t\geq 0,$ |

or equivalently

$h(t)\leq\left[\frac{T}{C}\left(1-e^{-t/(DT)}\right)\right]^{-2D},\ \ \ t\geq 0.$ |

But

$0<t\leq T$ |

so for these same values of $t$ we have

$\displaystyle h(t)$ | $\displaystyle\leq$ | $\displaystyle\left[\frac{t}{C}\left(1-e^{-1/D}\right)\right]^{-2D}$ | ||

$\displaystyle=$ | $\displaystyle e^{2}\left[\frac{t}{C}\left(e^{1/D}-1\right)\right]^{-2D}\leq[e(% DC/t)^{D}]^{2},$ |

as desired.

We now return to Lemma 8.13 and, for $t\geq T$, set $s=T$. (Indeed, using the bound on $N(s)$ in Theorem 8.17, this is the optimal choice of $s$ if $T<D\tau_{2}$.) This gives

xxx NOTE: In next theorem, only need conclusion of Theorem 8.17, not hypothesis!

In Theorem 8.17, if $c\geq 1$ and

$t\geq T+\tau_{2}\left(D\log\left(\frac{DC}{T}\right)+c\right),$ |

then $\sqrt{{\hat{d}}(2t)}\leq e^{1-c}$; in particular,

${\hat{\tau}}\leq T+\tau_{2}\left(D\log\left(\frac{DC}{T}\right)+2\right).$ |

The following converse of sorts to Theorem 8.17 will be very useful in conjunction with the comparison method.

If a continuous time reversible chain satisfies

$0<t\leq T$ |

then it satisfies the Nash inequality

$g$ |

with

$C^{\prime}:=2\,(1+{\textstyle\frac{1}{2D}})\,[(1+2D)^{1/2}C]^{1/D}\leq 2^{2+% \frac{1}{2D}}\,C^{1/D}.$ |

xxx Detail in proof to be filled in (I have notes): Show $\mbox{${\cal E}$}({\bf P}_{t}g,{\bf P}_{t}g)\downarrow$ as $t\uparrow$, or at least that it’s maximized at $t=0$. Stronger of two statements is equivalent to assertion that $\|{\bf P}_{t}f\|^{2}_{2}$ is convex in $t$.

Proof. As in the proof of Theorem 8.17, we note $N(t)=\|{\bf P}_{t}\|_{1\to 2}$. Hence, for any $g$ and any $0<t\leq T$,

$\displaystyle\|g\|^{2}_{2}$ | $\displaystyle=$ | $\displaystyle\|{\bf P}_{t}g\|^{2}_{2}-\int_{s=0}^{t}{\textstyle\frac{d}{ds}}\|% {\bf P}_{s}g\|^{2}_{2}\,ds$ | ||

$\displaystyle=$ | $\displaystyle\|{\bf P}_{t}g\|^{2}_{2}+2\int_{s=0}^{t}\mbox{${\cal E}$}({\bf P}% _{s}g,{\bf P}_{s}g)\,ds\mbox{\ \ \ by Lemma~{}\ref{basic-1}(a)}$ | |||

$\displaystyle\leq$ | $\displaystyle\|{\bf P}_{t}g\|^{2}_{2}+2\mbox{${\cal E}$}(g,g)t\mbox{\ \ \ xxx % see above}$ | |||

$\displaystyle\leq$ | $\displaystyle 2\mbox{${\cal E}$}(g,g)t+C^{2}t^{-2D}\|g\|^{2}_{1}.$ |

This gives

$\|g\|^{2}_{2}\leq t[2\mbox{${\cal E}$}(g,g)+{\textstyle\frac{1}{T}}\|g\|^{2}_{% 2}]+C^{2}t^{-2D}\|g\|^{2}_{1}$ |

for any $t>0$. The righthand side here is convex in $t$ and minimized (for $g\neq 0$) at

$t=\left(\frac{2DC^{2}\|g\|^{2}_{1}}{2\mbox{${\cal E}$}(g,g)+T^{-1}\|g\|^{2}_{2% }}\right)^{1/(2D+1)}.$ |

Plugging in this value, raising both sides to the power $1+{\textstyle\frac{1}{2D}}$ and simplifying yields the desired Nash inequality. The upper bound for $C^{\prime}$ is derived with a little bit of calculus.

In Section 8.1 we compared relaxation times for two chains by comparing Dirichlet forms and variances. The point of this subsection is that the comparison can be extended to the norm function $N(\cdot)$ of (8.47) using Nash inequalities. Then results on $N(\cdot)$ like those in Section 8.2.3 can be used to bound mixing times for other chains on the same state space.

xxx For NOTES?: Can even use different spaces. New paragraph:

To see how this goes, suppose that a benchmark chain is known to satisfy

$0<t\leq{\tilde{T}}$ | (8.48) |

By Theorem 8.19, it then satisfies a Nash inequality. The $L^{1}$- and $L^{2}$-norms appearing in this inequality can be compared in the obvious fashion [cf. (8.18)] and the Dirichlet forms can be compared as in Theorem 8.1. This shows that the chain of interest also satisfies a Nash inequality. But then Theorem 8.17 gives a bound like (8.48) for the chain of interest, and Theorem 8.18 can then be used to bound the $L^{2}$ threshold time ${\hat{\tau}}$.

Here is the precise result; the details of the proof are left to the reader.

If a reversible benchmark chain satisfies

$0<t\leq{\tilde{T}}$ |

for constants ${\tilde{C}},{\tilde{D}},{\tilde{T}}>0$, then any other reversible chain on the same state space satisfies

$0<t\leq T$ |

where, with $a$ and $A$ as defined in Corollary 8.2, and with

$a^{\prime}:=\max_{i}({\tilde{\pi}}_{i}/\pi_{i}),$ |

we set

$\displaystyle D$ | $\displaystyle=$ | $\displaystyle{\tilde{D}},$ | ||

$\displaystyle C$ | $\displaystyle=$ | $\displaystyle a^{-(2+\frac{1}{D})}{a^{\prime}}^{1/D}A\times 2(1+{\textstyle% \frac{1}{2D}})[(1+2D)^{1/2}{\tilde{C}}]^{1/D}$ | ||

$\displaystyle\leq$ | $\displaystyle a^{-(2+\frac{1}{D})}{a^{\prime}}^{1/D}A\times 2^{2+\frac{1}{2D}}% {\tilde{C}}^{1/D},$ | |||

$\displaystyle T$ | $\displaystyle=$ | $\displaystyle\frac{2A}{{a^{\prime}}^{2}}{\tilde{T}}.$ |

xxx Must correct this slightly. Works for any $A$ such that ${\tilde{\cal E}}\leq A\mbox{${\cal E}$}$, not just minimal one. This is important since we need a lower bound on $T$ but generally only have an upper bound on ${\tilde{\cal E}}/\mbox{${\cal E}$}$. The same goes for $a^{\prime}$ (only need upper bound on ${\tilde{\pi}}_{i}/\pi_{i}$): we also need an upper bound on $T$.

Random walk on a $d$-dimensional grid.

As in Example 8.5, consider the continuized walk on the $d$-dimensional grid $I=\{0,\ldots,m-1\}^{d}$. In Example 8.5 we compared the Dirichlet form and variance for this walk to the $d$-fold product of random walk on the $m$-path with end self-loops to obtain

$\tau_{2}\leq{\tilde{\tau}}_{2}=d(1-\cos{\textstyle\frac{\pi}{m}})^{-1}\leq{% \textstyle\frac{1}{2}}dm^{2};$ | (8.49) |

using the simple bound $\sqrt{{\hat{d}}(2t)}\leq\pi^{-1/2}_{*}e^{-t/\tau_{2}}\leq(2n)^{-1/2}\exp\left(% -\frac{2t}{dm^{2}}\right)$ we then get

${\hat{\tau}}\leq{\textstyle\frac{1}{4}}m^{2}d[\log(2n)+2],$ | (8.50) |

which is of order $m^{2}d^{2}\log m$. Here we will see how comparing $N(\cdot)$, too, gives a bound of order $m^{2}d^{2}\log d$. In Example 8.43, we will bring log-Sobolev techniques to bear, too, to lower this bound to order $m^{2}d\log d$

xxx which is correct, at least for TV. New paragraph:

Recalling (8.45), we may apply Theorem 8.20 with

${\tilde{D}}=d/4,\ \ \ {\tilde{C}}=(4dm^{2})^{d/4},\ \ \ {\tilde{T}}=dm^{2}/16,$ |

and, from the considerations in Example 8.5,

$a\geq{\textstyle\frac{1}{2}},\ \ \ A=1,\ \ \ a^{\prime}=2.$ |

xxx See xxx following Theorem 8.20. Same paragraph:

This gives

$D=d/4,\ \ \ C\leq 2^{6+\frac{10}{d}}dm^{2}\leq 2^{16}dm^{2},\ \ \ T=dm^{2}/32.$ |

Plugging these into Theorem 8.18 yields

${\hat{\tau}}\leq{\textstyle\frac{1}{8}}m^{2}d^{2}\log d+({\textstyle\frac{19}{% 8}}\log 2)m^{2}d^{2}+{\textstyle\frac{33}{32}}m^{2}d,$ | (8.51) |

which is $\leq 3m^{2}d^{2}\log d$ for $d\geq 2$.

Other variants of the walk, including the thinned-grid walk of Example 8.6, can be handled in a similar fashion.

xxx Do moderate growth and local Poincaré? Probably not, to keep length manageable. Also, will need to rewrite intro a little, since not doing $\Delta^{2}$-stuff (in any detail).

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