As usual we start by repeating the definition
(4.6) |
and recalling what we already know. We know (a result not using reversibility: Chapter 2 Corollary yyy) the random target lemma
(4.7) |
and we know the eigentime identity (Chapter 3 yyy)
(4.8) |
(4.9) |
In Chapter 3 yyy we proved a lower bound for -state discrete-time chains:
which is attained by random walk on the complete graph.
We can give a flow characterization by averaging over the characterization in Chapter 3 yyy. For each vertex let be a flow from to of volume , that is a unit flow scaled by . Then
the being over families of flows described above.
By writing
we see that . It may happen that is substantially larger than . A fundamental example is the queue (xxx) where is linear in but grows exponentially. A simple example is the two-state chain with
for which but . This example shows that (without extra assumptions) we can’t improve much on the bound
(4.10) |
which follows from the observation .
One can invent examples of random walks on regular graphs in which also is substantially larger than . Under symmetry conditions (vertex-transitivity, Chapter 7) we know a priori that is the same for all and hence by (4.2) . In practice we find that and have the same order of magnitude in most “naturally-arising” graphs, but I don’t know any satisfactory formalization of this idea.
The analog of Corollary 4.3 clearly holds, by averaging over and .
Let be edge-weights and let and be the corresponding parameters for the random walks. Then
In one sense this is mysterious, because in the eigentime identity the largest term in the sum is the first term, the relaxation time , and Example yyy of Chapter 3 shows that there is no such upper bound for .