A Nash inequality for a chain is an inequality of the form
|
|
|
(8.46) |
that holds for some positive constants , , and and for all
functions . 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.
8.3.1 Nash inequalities and mixing times
A Nash inequality implies a useful bound on the quantity
|
|
|
(8.47) |
appearing in the mixing time Lemma 8.13. This norm is continuous
in and decreases to as .
Here is the main result:
Theorem 8.17
If the Nash inequality (8.46) holds for a continuous-time reversible
chain, some , and all , then the norm at (8.47)
satisfies
|
|
|
Proof.
First note by Lemma 8.12.
Thus we seek a bound on independent of
satisfying ; the square root of such a bound will also
bound .
Substituting for in (8.46) and utilizing the identity in
Lemma 8.10(a) and the fact that is contractive on , we
obtain the differential inequality
|
|
|
Writing
|
|
|
the inequality can be equivalently rearranged to
|
|
|
Since , it follows that
|
|
|
or equivalently
|
|
|
But
|
|
|
so for these same values of we have
|
|
|
|
|
|
|
|
|
|
as desired.
We now return to Lemma 8.13 and, for , set .
(Indeed, using the bound on in Theorem 8.17, this is the
optimal choice of if .) This gives
xxx NOTE: In next theorem, only need conclusion of
Theorem 8.17, not hypothesis!
Theorem 8.18
In Theorem 8.17, if and
|
|
|
then ; in particular,
|
|
|
The following converse of sorts to Theorem 8.17 will be very useful
in conjunction with the comparison method.
Theorem 8.19
If a continuous time reversible chain satisfies
|
|
|
then it satisfies the Nash inequality
|
|
|
with
|
|
|
xxx Detail in proof to be filled in (I have notes): Show as , or at least that it’s maximized at .
Stronger of two statements is equivalent to assertion that
is convex in .
Proof.
As in the proof of Theorem 8.17, we note . Hence, for any and any ,
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
This gives
|
|
|
for any . The righthand side here is convex in and
minimized (for ) at
|
|
|
Plugging in this value, raising both sides to the power
and simplifying yields the desired Nash inequality. The upper bound
for is derived with a little bit of calculus.
8.3.2 The comparison method for bounding
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
of (8.47) using Nash inequalities. Then results on 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
|
|
|
(8.48) |
By Theorem 8.19, it then satisfies a Nash inequality. The - and
-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 threshold time .
Here is the precise result; the details of the proof are left to the reader.
Theorem 8.20 (comparison of bounds on )
If a reversible benchmark chain satisfies
|
|
|
for constants , then any other reversible chain on the same
state space satisfies
|
|
|
where, with and as defined in Corollary 8.2, and
with
|
|
|
we set
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
xxx Must correct this slightly. Works for any such that , not just minimal one. This is important since we need a lower bound on but generally only have an upper bound on . The same goes for (only need upper bound on ): we also need an upper bound on .
Example 8.21
Random walk on a -dimensional grid.
As in Example 8.5, consider the continuized walk on the
-dimensional grid . In Example 8.5 we
compared the Dirichlet form and variance for this walk to the -fold product
of random walk on the -path with end self-loops to obtain
|
|
|
(8.49) |
using the simple bound we then get
|
|
|
(8.50) |
which is of order . Here we will see how comparing ,
too, gives a bound of order . In Example 8.43, we
will
bring log-Sobolev techniques to bear, too, to lower this bound to order
xxx which is correct, at least for TV. New paragraph:
Recalling (8.45), we may apply Theorem 8.20 with
|
|
|
and, from the considerations in Example 8.5,
|
|
|
xxx See xxx following Theorem 8.20. Same paragraph:
This gives
|
|
|
Plugging these into Theorem 8.18 yields
|
|
|
(8.51) |
which is for .
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
-stuff (in any detail).