As usual we start by repeating the definition

$\tau_{0}\equiv\sum_{i}\sum_{j}\pi_{j}\pi_{i}E_{i}T_{j}$ | (4.6) |

and recalling what we already know. We know (a result not using reversibility: Chapter 2 Corollary yyy) the random target lemma

$\sum_{j}\pi_{j}E_{i}T_{j}=\tau_{0}\mbox{ for all }i$ | (4.7) |

and we know the eigentime identity (Chapter 3 yyy)

$\tau_{0}=\sum_{m\geq 2}(1-\lambda_{m})^{-1}\mbox{ in discrete time}$ | (4.8) |

$\tau_{0}=\sum_{m\geq 2}\lambda_{m}^{-1}\mbox{ in continuous time}$ | (4.9) |

In Chapter 3 yyy we proved a lower bound for $n$-state discrete-time chains:

$\tau_{0}\geq\frac{(n-1)^{2}}{n}$ |

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 $a$ let ${\bf f}^{a\rightarrow\pi}=(f_{ij}^{a\rightarrow\pi})$ be a flow from $a$ to $\pi$ of volume $\pi_{a}$, that is a unit flow scaled by $\pi_{a}$. Then

$\tau_{0}=w\ \min\left\{\frac{1}{2}\sum_{i}\sum_{j}\sum_{a}\frac{(f_{ij}^{a% \rightarrow\pi})^{2}}{\pi_{a}w_{ij}}\right\}$ |

the $min$ being over families of flows ${\bf f}^{a\rightarrow\pi}$ described above.

By writing

$\tau_{0}=\frac{1}{2}\sum_{i}\sum_{j}\pi_{i}\pi_{j}(E_{i}T_{j}+E_{j}T_{i})\leq% \frac{1}{2}\max_{ij}(E_{i}T_{j}+E_{j}T_{i})$ |

we see that $\tau_{0}\leq\frac{1}{2}\tau^{*}$. It may happen that $\tau^{*}$ is substantially larger than $\tau_{0}$. A fundamental example is the $M/M/1/n$ queue (xxx) where $\tau_{0}$ is linear in $n$ but $\tau^{*}$ grows exponentially. A simple example is the two-state chain with

$p_{01}=\varepsilon,p_{10}=1-\varepsilon,\ \ \pi_{0}=1-\varepsilon,\pi_{1}=\varepsilon$ |

for which $\tau_{0}=1$ but $\tau^{*}=\frac{1}{\varepsilon}+\frac{1}{1-\varepsilon}$. This example shows that (without extra assumptions) we can’t improve much on the bound

$\tau^{*}\leq\frac{2\tau_{0}}{\min_{j}\pi_{j}}$ | (4.10) |

which follows from the observation $E_{i}T_{j}\leq\tau_{0}/\pi_{j}$.

One can invent examples of random walks on regular graphs in which also $\tau^{*}$ is substantially larger than $\tau_{0}$. Under symmetry conditions (vertex-transitivity, Chapter 7) we know a priori that $E_{\pi}T_{i}$ is the same for all $i$ and hence by (4.2) $\tau^{*}\leq 4\tau_{0}$. In practice we find that $\tau_{0}$ and $\tau^{*}$ 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 $i$ and $j$.

Let $\tilde{w}_{e}\geq w_{e}$ be edge-weights and let $\tilde{\tau}_{0}$ and $\tau_{0}$ be the corresponding parameters for the random walks. Then

$\tilde{\tau}_{0}/\tau_{0}\leq\tilde{w}/w.$ |

In one sense this is mysterious, because in the eigentime identity the largest term in the sum is the first term, the relaxation time $\tau_{2}$, and Example yyy of Chapter 3 shows that there is no such upper bound for $\tau_{2}$.

Generated on Mon Jun 2 14:23:48 2014 by LaTeXML