8.1 The comparison method for eigenvalues
xxx Revise Chapter 7, Sections 1.9 and 4, in light of this section?
The comparison method, introduced by Diaconis and Saloff-Coste [115, 116],
generalizes the distinguished path method of Chapter 4, Section yyy:3
for bounding the relaxation time of a reversible Markov chain. As before, we
first (xxx: delete word?) work in the setting of random walks on weighted
graphs. We will proceed for given state space (vertex set) by comparing a
collection of weights of interest to another collection
; the idea will be to use known results for the random walk with
weights to derive corresponding results for the walk of interest.
We assume that the graph is connected under each set of weights. As in
Chapter 4, Section yyy:4.3, we choose (“distinguish”) paths
from to . Now, however, this need be done only for those
with and , but we impose the additional constraint
for each edge in the path. (Here and below, denotes a directed edge in
the graph of interest.) In other words, roughly put, we need to construct a
-path to effect each given -edge. Recall from Chapter 3
yyy:(71) the definition of Dirichlet form:
|
|
|
|
|
(8.14) |
|
|
|
|
|
Theorem 8.1 (comparison of Dirichlet forms)
For each ordered pair
of distinct vertices with , let
be a path from to with for every . Then the Dirichlet forms (8.14) satisfy
|
|
|
for every .
Proof.
For an edge write . Then
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Remarks.
(a) Suppose the comparison weights are given by
|
|
|
The corresponding discrete-time random walk is then the “trivial”walk with
and
|
|
|
for all , and
|
|
|
|
|
|
|
|
|
|
In this case the conclusion of Theorem 1 reduces to
|
|
|
This inequality was established in the proof of the distinguished path theorem
(Chapter 4 Theorem yyy:32), and that theorem was an immediate consequence of
the inequality. Hence the comparison Theorem 1 may be regarded as a
generalization of the distinguished path theorem.
[xxx For NOTES: We’ve used simple Sinclair weighting. What about other
weighting in use of Cauchy–Schwarz? Hasn’t been considered, as far as I
know.]
(b) When specialized to the setting of reversible random flights on Cayley
graphs described in Chapter 7 Section yyy:1.9, Theorem 1 yields Theorem yyy:14
of Chapter 7. To see this, adopt the setup in Chapter 7 Section yyy:1.9, and
observe that the word
|
|
|
(8.15) |
corresponds uniquely to a path
|
|
|
(8.16) |
in the Cayley graph corresponding to the generating set of interest.
Having built paths for each , we then can build paths
for by exploiting vertex-transitivity, to wit, by
setting
|
|
|
where and the path is given by (8.16).
In Theorem 1 we then have both stationary distributions and
uniform,
|
|
|
and, if with and ,
|
|
|
Thus of Theorem 1 equals
|
|
|
which reduces easily to of Theorem yyy:14 of Chapter 7. Since and
are both uniform, the extremal characterization
|
|
|
(8.17) |
gives Theorem yyy:14 of Chapter 7.
Theorem 8.1 compares Dirichlet forms. To compare relaxation times
using the extremal characterization (8.17), we compare -norms
using the same “direct” technique as for Chapter 3 Lemma yyy:26. For
any ,
|
|
|
(8.18) |
where, as usual, and .
So if has -mean and -mean , then
|
|
|
(8.19) |
Thus
Corollary 8.2 (comparison of relaxation times)
In Theorem 1,
|
|
|
where
|
|
|
|
|
|
|
|
|
|
xxx Perhaps restate as
|
|
|
where
|
|
|
(and similarly for Corollaries 4 and 7)?
xxx Remark about best if ?
Here is a simple example, taken from [115], showing the improvement
in Corollary 8.2 over Theorem yyy:32 of Chapter 4 provided by
the freedom in choice of benchmark chain.
xxx NOTE: After the fact, I realized that the following example was already
Example yyy:20 of Chapter 7; must reconcile.
Example 8.3
Consider a card shuffle which transposes the top two cards in the deck,
moves the top card to the bottom, or moves the bottom card to the top, each
with
probability . This example fits the specialized group framework of
Chapter 7 Section yyy:1.9 (see also Remark (b) following
Theorem 8.1 above) with taken to be the symmetric group on
letters and
|
|
|
in cycle notation. [If the order of the deck is represented by a
permutation in such a way that is the position of the card
with label , and if permutations are composed left to right, then is the order resulting from by
moving the top card to the bottom.]
We obtain a representation (8.15) for any given permutation by
writing
|
|
|
in such a way that
|
|
|
(8.20) |
(i.e., and agree in positions through ) and
each is explicitly represented as a product of generators. To accomplish
this, we proceed inductively. Suppose that (8.20) holds for given , and that ,
with . Then let
|
|
|
|
|
|
|
|
|
|
In words, beginning with , we repeatedly move the top card to
the bottom until card has risen to the top; then we
repeatedly transpose and shift until the top cards, in order, are
; and finally we cut these
cards to the bottom.
xxx Either revise Section 1.9 of Chapter 7 to delete requirement of geodesic paths, or explain one can erase cycles.
It follows that the diameter of the Cayley graph associated
with satisfies
|
|
|
and so by Chapter 7 Corollary yyy:15 that
To improve this bound on the relaxation time we compare the chain of interest
to the random transposition chain of Chapter 7 Example yyy:18 and employ
Corollary 8.2, or rather its specialization,
(yyy:Theorem 14) of Chapter 7.
xxx Continue as in Chapter 7 Example yyy:20 to get
|
|
|
xxx Test function on page 2139 of [115] shows this is right
order.
Corollary 8.2 can be combined with the inequality
|
|
|
(8.21) |
from (8.7) to bound the threshold parameter
for the chain of interest, but Theorem 8.1 sometimes affords a
sharper result. From the Courant–Fischer “min–max” theorem ([183],
Theorem 4.2.11) it follows along the same lines as in Chapter 3
Section yyy:6.3 that
|
|
|
(8.22) |
where and xxx Say the conditions better!
|
|
|
|
|
|
|
|
and the in (8.22) is taken over all vectors that are orthogonal in (or, equivalently, that are
linearly independent). Using (8.19), Corollary 8.2
now generalizes to
Corollary 8.4 (comparison of eigenvalues)
In Theorem 8.1, the eigenvalues and in
the respective spectral representations satisfy
|
|
|
with and as defined in Corollary 8.2.
Here is a simple example [116] not possessing vertex-transitivity:
xxx NOTE: This is a DIRECT comparison!: see Chapter 3 Section 6.4.
Example 8.5
Random walk on a -dimensonal grid.
To keep the notation simple, we let and consider the grid as an (unweighted) subgraph
of . The eigenvalues are not known in closed form.
However,
if we add self-loops to make a benchmark graph where is regular with
degree , then the eigenvalues for the continuous-time walk are
|
|
|
xxx Product chain. Add discussion of all eigenvalues to
Section yyy:6.2
of Chapter 4?
xxx P.S. See Chapter 5, (66).
In particular, assuming we have
|
|
|
(8.23) |
Now we apply Corollary 8.4 to bound the
eigenvalues . In Theorem 8.1, the two graphs agree
except for self-loops, so
furthermore,
|
|
|
so
|
|
|
Thus for ; in
particular,
|
|
|
(8.24) |
Comparing the other way around gives
|
|
|
and in particular
|
|
|
The result extends to general , for which (for example)
|
|
|
where and .
Example 8.6
Random walk on a thinned grid.
As a somewhat more interesting example, suppose we modify the grid
in in Example 8.5 by deleting at most one edge from each unit
square.
xxx Copy picture on page 700 in [116] as example?
Again we can apply Corollary 8.4, using the same benchmark
graph as in Example 8.5. In Theorem 8.1, for
if and only if and are neighboring vertices in the
(unthinned) grid .
We can
choose to have length (if the edge joining and
has not
been deleted) or (if it has). For any directed edge in the grid, there
are at most two paths of length and at most one path of length passing
through . Thus , and so ; comparing the other way around is even easier (all paths have
length ), and we find
|
|
|
xxx REMINDER: NOTES OR ELSEWHERE?: Mention exclusion
process [149, 116].
Example 8.7
The -path with end self-loops.
The comparison technique
does not always provide results as sharp
as those in the preceding two examples, even when the two chains are
“close.”
For example, let the chain of interest be the -path, with self-loops
added at
each end added to make the graph regular with degree , and let the benchmark
graph be the -cycle (Chapter 5, Example yyy:7). Use of
Corollary 8.2 gives only , whereas in
fact
and
It is difficult in general to use Corollary 8.4 to improve
upon (8.21). However, when both the chain of interest and the benchmark
chain are symmetric reversible chains (as defined in Chapter 7
Section yyy:1.1), it follows from Chapter 4 yyy:(14) by averaging over
that
|
|
|
and hence from (8.1) we obtain
Corollary 8.8 (comparison of mixing times)
In Theorem 8.1, if both the graph of interest and the benchmark
graph are vertex-transitive, then the mixing time parameters
and
satisfy
|
|
|
Example 8.9
Returning to the slow card-shuffling scheme of Example 8.3 with
random transpositions benchmark, it is known from group representation methods
[123, 120] which make essential use of all the
eigenvalues , not just , that
|
|
|
Since and ( of Chapter 7, Theorem yyy:14) , it
follows that
|
|
|
(8.25) |
This improves upon Example 8.3, which combines with (8.21) to
give
only
|
|
|
xxx Show truth is ?