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 be arbitrary states in a sequence of reversible Markov chains.
(i) If then
(ii) If and then and
Proof. In continuous time, assertion (i) is immediate from Chapter 3 Proposition yyy. The result in discrete time now holds by continuization: if is the hitting time in discrete time and in continuous time, then and is order . For (ii) we have (cf. Chapter 4 section yyy) where is the hitting time started at , is the hitting time started from stationarity, and . So , and the hypotheses of (ii) force and force the limit distribution of to be the same as the limit distribution of , which is the exponential distribution by (i) and the relation .
In the complete graph example, has mean and s.d. , so that 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 in a sequence of (not necessarily reversible) Markov chains,
The proof is too long to reproduce.