6 Cover Times (October 31, 1994)

6.7 Distributional aspects

In many examples one can apply the following result to show that hitting time distributions become exponential as the size of state space increases.

Corollary 6.32

Let i,ji,j be arbitrary states in a sequence of reversible Markov chains.

(i) If EπTj/τ2E_{\pi}T_{j}/\tau_{2}\rightarrow\infty then

Pπ(TjEπTj>x)e-x, 0<x<.P_{\pi}\left(\frac{T_{j}}{E_{\pi}T_{j}}>x\right)\rightarrow e^{-x},\ 0<x<\infty.

(ii) If EiTj/τ1E_{i}T_{j}/\tau_{1}\rightarrow\infty and EiTj(1-o(1))EπTjE_{i}T_{j}\geq(1-o(1))E_{\pi}T_{j} then EiTj/EπTj1E_{i}T_{j}/E_{\pi}T_{j}\rightarrow 1 and

Pi(TjEiTj>x)e-x, 0<x<.P_{i}\left(\frac{T_{j}}{E_{i}T_{j}}>x\right)\rightarrow e^{-x},\ 0<x<\infty.

Proof. In continuous time, assertion (i) is immediate from Chapter 3 Proposition yyy. The result in discrete time now holds by continuization: if TjT_{j} is the hitting time in discrete time and TjT^{\prime}_{j} in continuous time, then EπTj=EπTjE_{\pi}T^{\prime}_{j}=E_{\pi}T_{j} and Tj-TjT^{\prime}_{j}-T_{j} is order EπTj\sqrt{E_{\pi}T_{j}}. For (ii) we have (cf. Chapter 4 section yyy) TjUi+Tj*T_{j}\leq U_{i}+T^{*}_{j} where TjT_{j} is the hitting time started at ii, Tj*T^{*}_{j} is the hitting time started from stationarity, and EiUiτ1(2)E_{i}U_{i}\leq\tau^{(2)}_{1}. So ETjET*+O(τ1)ET_{j}\leq ET^{*}+O(\tau_{1}), and the hypotheses of (ii) force ETj/ETj*1ET_{j}/ET^{*}_{j}\rightarrow 1 and force the limit distribution of Tj/ETjT_{j}/ET_{j} to be the same as the limit distribution of Tj*/ETj*T^{*}_{j}/ET^{*}_{j}, which is the exponential distribution by (i) and the relation τ2τ1\tau_{2}\leq\tau_{1}. \Box

In the complete graph example, CC has mean nlogn\sim n\log n and s.d. Θ(n)\Theta(n), so that C/EC1C/EC\rightarrow 1 in distribution, although the convergence is slow. The next result shows this “concentration” result holds whenever the mean cover time is essentially larger than the maximal mean hitting time.

Theorem 6.33 ([23])

For states ii in a sequence of (not necessarily reversible) Markov chains,

if EiC/τ* then Pi(|CEiC-1|>ε)0,ε>0.\mbox{if }E_{i}C/\tau^{*}\rightarrow\infty\mbox{ then }P_{i}\left(\left|\frac{% C}{E_{i}C}-1\right|>\varepsilon\right)\rightarrow 0,\ \varepsilon>0.

The proof is too long to reproduce.