Reversible Markov Chains and Random Walks on Graphs

Chapter 6 Cover Times (October 31, 1994)

The maximal mean hitting time maxi,jEiTj\max_{i,j}E_{i}T_{j} arises in many contexts. In Chapter 5 we saw how to compute this in various simple examples, and the discussion of τ*\tau^{*} in Chapter 4 indicated general methods (in particular, the electrical resistance story) for upper bounding this quantity. But what we’ve done so far doesn’t answer questions like “how large can τ*\tau^{*} be, for random walk on a nn-vertex graph”. Such questions are dealt with in this Chapter, in parallel with a slightly different topic. The cover time for a nn-state Markov chain is the random time CC taken for the entire state-space II to be visited. Formally,


It is sometimes mathematically nicer to work with the “cover-and-return” time

C+min{tC:Xt=X0}.C^{+}\equiv\min\{t\geq C:X_{t}=X_{0}\}.

There are several reasons why cover times are interesting.

  • Several applications involve cover times directly: graph connectivity algorithms (section 6.8.2), universal traversal sequences (section 6.8.1), the “white screen problem” (Chapter 1 yyy)

  • There remains an interesting “computability” open question (section 6.8.3)

  • In certain “critical” graphs, the uncovered subset at the time when the graph is almost covered is believed to be “fractal” (see the Notes on Chapter 7).

We are ultimately interested in random walks on unweighted graphs, but some of the arguments have as their natural setting either reversible Markov chains or general Markov chains, so we sometimes switch to those settings. Results are almost all stated for discrete-time walks, but we occasionally work with continuized chains in the proofs, or to avoid distracting complications in statements of results. Results often can be simplified or sharpened under extra symmetry conditions, but such results and examples are deferred until Chapter 7.

xxx contents of chapter