4 Hitting and Convergence Time, and Flow Rate, Parameters for Reversible Markov Chains (October 11, 1994)

4.2 The average hitting time τ0\tau_{0}

As usual we start by repeating the definition

τ0ijπjπiEiTj\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

jπjEiTj=τ0 for all i\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)

τ0=m2(1-λm)-1 in discrete time\tau_{0}=\sum_{m\geq 2}(1-\lambda_{m})^{-1}\mbox{ in discrete time} (4.8)
τ0=m2λm-1 in continuous time\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 nn-state discrete-time chains:

τ0(n-1)2n\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 aa let 𝐟aπ=(fijaπ){\bf f}^{a\rightarrow\pi}=(f_{ij}^{a\rightarrow\pi}) be a flow from aa to π\pi of volume πa\pi_{a}, that is a unit flow scaled by πa\pi_{a}. Then

τ0=wmin{12ija(fijaπ)2πawij}\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 minmin being over families of flows 𝐟aπ{\bf f}^{a\rightarrow\pi} described above.

By writing

τ0=12ijπiπj(EiTj+EjTi)12maxij(EiTj+EjTi)\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 τ012τ*\tau_{0}\leq\frac{1}{2}\tau^{*}. It may happen that τ*\tau^{*} is substantially larger than τ0\tau_{0}. A fundamental example is the M/M/1/nM/M/1/n queue (xxx) where τ0\tau_{0} is linear in nn but τ*\tau^{*} grows exponentially. A simple example is the two-state chain with

p01=ε,p10=1-ε, π0=1-ε,π1=εp_{01}=\varepsilon,p_{10}=1-\varepsilon,\ \ \pi_{0}=1-\varepsilon,\pi_{1}=\varepsilon

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

τ*2τ0minjπj\tau^{*}\leq\frac{2\tau_{0}}{\min_{j}\pi_{j}} (4.10)

which follows from the observation EiTjτ0/πjE_{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 τ0\tau_{0}. Under symmetry conditions (vertex-transitivity, Chapter 7) we know a priori that EπTiE_{\pi}T_{i} is the same for all ii and hence by (4.2) τ*4τ0\tau^{*}\leq 4\tau_{0}. In practice we find that τ0\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 ii and jj.

Corollary 4.4

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

τ~0/τ0w~/w.\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 τ2\tau_{2}, and Example yyy of Chapter 3 shows that there is no such upper bound for τ2\tau_{2}.