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

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

(i) If $E_{\pi}T_{j}/\tau_{2}\rightarrow\infty$ then

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

(ii) If $E_{i}T_{j}/\tau_{1}\rightarrow\infty$ and $E_{i}T_{j}\geq(1-o(1))E_{\pi}T_{j}$ then $E_{i}T_{j}/E_{\pi}T_{j}\rightarrow 1$ and

$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 $T_{j}$ is the hitting time in discrete time and $T^{\prime}_{j}$ in continuous time, then $E_{\pi}T^{\prime}_{j}=E_{\pi}T_{j}$ and $T^{\prime}_{j}-T_{j}$ is order $\sqrt{E_{\pi}T_{j}}$. For (ii) we have (cf. Chapter 4 section yyy) $T_{j}\leq U_{i}+T^{*}_{j}$ where $T_{j}$ is the hitting time started at $i$, $T^{*}_{j}$ is the hitting time started from stationarity, and $E_{i}U_{i}\leq\tau^{(2)}_{1}$. So $ET_{j}\leq ET^{*}+O(\tau_{1})$, and the hypotheses of (ii) force $ET_{j}/ET^{*}_{j}\rightarrow 1$ and force the limit distribution of $T_{j}/ET_{j}$ to be the same as the limit distribution of $T^{*}_{j}/ET^{*}_{j}$, which is the exponential distribution by (i) and the relation $\tau_{2}\leq\tau_{1}$. $\Box$

In the complete graph example, $C$ has mean $\sim n\log n$ and s.d. $\Theta(n)$, so that $C/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.

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

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

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