4.5.1 Definition and easy inequalities
Define
|
|
|
(4.34) |
where
|
|
|
and where such are always over proper subsets of states.
This parameter can be calculated exactly in only very special
cases, where the following lemma is helpful.
Lemma 4.36
The sup in (4.34) is attained by some
split in which both and are
connected (as subsets of the graph of permissible transitions).
Proof.
Consider a split in which is the union of
connected components .
Write
.
Then
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
and so
|
|
|
But for we have
,
which implies
.
To see how arises, note that the extremal characterization of (4.22)
applied to implies
|
|
|
for any subset .
But much more is true: Chapter 3 yyy
may be rephrased as follows.
For any subset ,
|
|
|
where is the quasistationary distribution
on
defined at Chapter 3 yyy.
So taking sups gives
Corollary 4.37
|
|
|
In a two-state chain these inequalities all become equalities.
This seems a good justification for our choice of definition of
, instead of the alternative
|
|
|
which has been used in the literature but which would introduce a spurious
factor of into the inequality .
Lemma 4.39 below shows that the final inequality of Corollary
4.37 can be reversed.
In contrast,
on the -cycle whereas the other quantities
in Corollary 4.37 are .
This shows that the “square” in Theorem 4.40 below cannot
be omitted in general.
It also suggests
the following question (cf. and )
Open Problem 4.38
Does there exist a constant such that
|
|
|
for every reversible chain?
A positive answer would provide, via Chapter 3 yyy, a correct
order-of-magnitude extremal characterization of in terms of flows.
Lemma 4.39
|
|
|
and so in particular
|
|
|
Proof.
for the eigenvector associated with .
Put
|
|
|
and assume ,
by replacing by if necessary.
Write .
We shall show
|
|
|
(4.35) |
and then the extremal characterization Chapter 3 yyy
|
|
|
(4.36) |
implies
for this specific .
The proof of (4.35) requires us to delve slightly further into the
calculus of Dirichlet forms.
Write for the function
and write for the inner product
.
Write for .
Then
|
|
|
where
|
|
|
Now consider
.
On the one hand
|
|
|
where the inequality follows from the inequality
for real .
On the other hand,
,
and the eigenvector satisfies
, so
|
|
|
Combining these inequalities leads to (4.35).
4.5.2 Cheeger-type inequalities
A lot of attention has been paid to reverse inequalities which upper bound
in terms of
or related “flow rate” parameters.
Motivation for such results
will be touched upon in Chapter yyy.
The prototype for such results is
Theorem 4.40 (Cheeger’s inequality)
,
where .
This result follows by combining Lemma 4.39 above with
Lemma 4.41 below.
In discrete time these inequalities hold with deleted
(i.e. replaced by ), by continuization.
Our treatment of Cheeger’s inequality closely follows
Diaconis and Stroock [122] – see Notes for more history.
Lemma 4.41
For any subset ,
|
|
|
Proof.
Fix and with and on .
|
|
|
|
|
|
|
|
|
|
|
by the Cauchy-Schwarz inequality |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
On the other hand
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Rearranging,
|
|
|
and the first assertion of the Theorem follows from the extremal
characterization (4.36) of
.
4.5.3 and hitting times
Lemma 4.25 and Theorem 4.40
imply a bound on in terms of .
But a direct argument, using ideas similar to those in the proof of Lemma 4.41, does better.
Proposition 4.42
|
|
|
Example 4.43 below will show that the log term cannot be omitted.
Compare with graph-theoretic bounds in Chapter 6 section yyy.
Proof.
Fix states .
We want to use the extremal characterization (Chapter 3 yyy).
So fix a function with .
Order the states as
so that is increasing.
|
|
|
|
|
(4.37) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
But
|
|
|
So by Cauchy-Schwarz and (4.37)
|
|
|
(4.38) |
But , where , so
|
|
|
The same bound holds for the sum over ,
so applying (4.38) we get
|
|
|
and the Proposition follows from the extremal characterization.
Example 4.43
Consider the weighted linear graph with loops on vertices
, with edge-weights
|
|
|
This gives vertex-weights ,
and so the stationary distribution is uniform.
By the commute interpretation of resistance,
|
|
|
Using Lemma 4.36, the value of is attained by a split
of the form ,
and a brief calculation shows that the maximizing value is
and gives
|
|
|
So in this example, the bound in Proposition 4.42 is sharp
up to the numerical constant.