8.5 Combining the techniques
To get the maximum power out of the techniques of this chapter, it is sometimes
necessary to combine the various techniques. Before proceeding to a general
result in this direction, we record a simple fact. Recall (8.36).
Lemma 8.41
If and are conjugate exponents with , then
|
|
|
Proof.
Apply Hölder’s inequality
|
|
|
with
|
|
|
Theorem 8.42
Suppose that a continuous-time reversible chain satisfies
|
|
|
(8.75) |
for some constants satisfying . If , then
|
|
|
for
|
|
|
where is the relaxation time and is the log-Sobolev time.
Proof.
¿From Lemma 8.11 and a slight extension of (8.34), for any and any initial distribution we have
|
|
|
for any . Choose and
to be its conjugate. Then, as in the proof of Theorem 8.26(a),
|
|
|
According to Lemma 8.41, (8.39), and (8.75), if
then
|
|
|
Now choose . Combining everything so far,
|
|
|
The final idea is to choose so that the first factor is bounded by .
¿From the formula for , the smallest such is
|
|
|
With this choice, the theorem follows readily.
Example 8.43
Random walk on a -dimensional grid.
Return one last time to the walk of interest in Example 8.5.
Example 8.21 showed that (8.75) holds with
|
|
|
Also recall from (8.49) and from Example 8.40. Plugging these into
Theorem 8.42 with yields
|
|
|
xxx Finally of right order of magnitude.