Chapter 6 Cover Times (October 31, 1994)

The maximal mean hitting time $\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 $n$-vertex graph”. Such questions are dealt with in this Chapter, in parallel with a slightly different topic. The cover time for a $n$-state Markov chain is the random time $C$ taken for the entire state-space $I$ to be visited. Formally,

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

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