xxx In next revision, we should change the definition [in Chapter 4, yyy:(14)] of so that what is now becomes .
This chapter concerns advanced -based techniques, developed mainly by Persi Diaconis and Laurent Saloff-Coste [115, 116, 117, 118] for bounding mixing times for (finite, irreducible) reversible Markov chains. For convenience, we will work in continuous time throughout this chapter, unless otherwise noted. Many of the results are conveniently expressed in terms of an “ threshold time” (xxx use different notation?) defined by
(8.1) |
xxx For NOTES: Discussion of discrete time, esp. negative eigenvalues.
Several preliminary comments are in order here. First, the definition of the distance may be recalled from Chapter 2 section yyy:6.2, and Chapter 3 yyy:(55) and the spectral representation give useful reexpressions:
(8.2) | |||||
Second, from (8.2) and Chapter 4 yyy:(14) we may also write the maximum distance appearing in (8.1) using
Third, by the application of the Cauchy–Schwarz lemma in Chapter 4 Lemma yyy:8, variation distance can be bounded by distance:
(8.3) | |||||
(8.4) |
these inequalities are the primary motivation for studying distance.
As argued in Chapter 4 yyy:just following (23),
(8.5) |
where is the relaxation time and . Thus if
then
(8.6) |
which is small if is large; in particular, (8.6) gives the upper bound in
(8.7) |
and the lower bound follows easily.
For many simple chains (see Chapter 5), can be computed exactly. Typically, however, can only be bounded. This can be done using the “distinguished paths” method of Chapter 4 Section yyy:3. In Section 1 we will see that that method may be regarded as a special case of a “comparison method” whereby a chain with “unknown” relaxation time is compared to a second chain with “known” relaxation time. The greater generality often leads to improved bounds on . As a bonus, the comparison method also gives bounds on the other “unknown” eigenvalues, and such bounds in turn can sometimes further decrease the time required to guarantee that , and hence also , is small.
A second set of advanced techniques, encompassing the notions of Nash inequalities, moderate growth, and local Poincaré inequaltities, is described in Section 3. The development there springs from the inequality
(8.8) |
established for all in Section 2, where
(8.9) |
Choosing in (8.8) gives
and maximizing over recaptures (8.5). The point of Section 3, however, is that one can sometimes reduce the bound by a better choice of and suitable estimates of the decay rate of . Such estimates can be provided by so-called Nash inequalities, which are implied by (1) moderate growth conditions and (2) local Poincaré inequalities. Roughly speaking, for chains satisfying these two conditions, judicious choice of shows that variation mixing time and are both of order , where is the diameter of the graph underlying the chain.
xxx Might not do (1) or (2), so need to modify the above.
To outline a third direction of improvement, we begin by noting that neither of the bounds in (8.7) can be much improved in general. Indeed, ignoring factors as usual, the lower bound is equality for the -cycle (Chapter 5, Example yyy:7) and the upper bound is equality for the M/M/1/ queue (Chapter 5, Example yyy:6) with traffic intensity .
In Section 4 we introduce the log-Sobolev time defined by
(8.10) |
where is the entropy-like quantity
recalling . Notice the similarity between (8.10) and the extremal characterization of (Chapter 3 Theorem yyy:22):
We will see that
and that is more closely related to than to , in the sense that
(8.11) |
To illustrate the improvement over (8.7), from the knowledge for the -cube (Chapter 5, Example yyy:15) that , one can deduce from (8.7) that
(8.12) |
In Section 4.4 (Example 27) we will see that ; then from (8.11) we can deduce the substantial improvement
(8.13) |
upon (8.12).
ZZZ!: Recall also the corrections in my notes on pages 8.2.11–12 (and 8.4.27). Continue same paragraph:
The upper bound here is remarkably tight: from Chapter 5 yyy:(65),
ZZZ!: In fact, the remainder term is . Continue same paragraph: