We start by repeating the definition
(4.1) |
and recalling what we already know. Obviously
and by Chapter 3 Lemma yyy
(4.2) |
Arguably we could have used as the “named” parameter, but the virtue of is the resistance interpretation of Chapter 3 Corollary yyy.
For random walk on a weighted graph,
where is the effective resistance between and .
In Chapter 3 Proposition yyy we proved lower bounds for any -state discrete-time reversible chain:
which are attained by random walk on the complete graph. Upper bounds will be discussed extensively in Chapter 6, but let’s mention two simple ideas here. Consider a path , and let’s call this path (because we’ve run out of symbols whose names begin with “p”!) This path, considered in isolation, has “resistance”
which by the Monotonicity Law is at least the effective resistance . Thus trivially
(4.3) |
A more interesting idea is to combine the max-flow min-cut theorem (see e.g. [86] sec. 5.4) with Thompson’s principle (Chapter 3 Corollary yyy). Given a weighted graph, define
(4.4) |
the over proper subsets . The max-flow min-cut theorem implies that for any pair there exists a flow from to of size such that for all edges . So there is a unit flow from to such that for all edges . It is clear that by deleting any flows around cycles we may assume that the flow through any vertex is at most unity, and so
(4.5) |
So
and we have proved
Lemma 4.1 and the Monotonicity Law also make clear a one-sided bound on the effect of changing edge-weights monotonically.
Let be edge-weights and let and be the corresponding parameters for the random walks. Then
and so
In the case of unweighted graphs the bound in Corollary 4.3 is . Example yyy of Chapter 3 shows there can be no lower bound of this type, since in that example but (by straightforward calculations) .