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:


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


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