# 4.2 The average hitting time $\tau_{0}$

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$.

###### Corollary 4.4

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}$.