# 随机算法 (Fall 2011)/Cover Time

For any , the **hitting time** is the expected number of steps before vertex is visited, starting from vertex .

Recall that any irreducible aperiodic Markov chain with finite state space converges to the unique stationary distribution Combining with what we know about the stationary distribution of a random walk on an undirected graph where , we have that for any vertex ,

This fact can be used to estimate the hitting time between two adjacent vertices.

**Lemma**- For a random walk on an undirected graph where, for any that , the mean hitting time .

**Proof.**The proof is by double counting. We know that Let be the set of neighbors of vertex . We run the random walk from for one step, and by the law of total expectation,

Combining the above two equations, we have

which implies that .

Note that the lemma holds only for the adjacent and . With this lemma, we can prove an upper bound on the cover time.

- Let be the expected number of steps taken by a random walk which starts at to visit every vertex in at least once. The
**cover time**of , denoted is defined as .

**Theorem (cover time)**- For any connected undirected graph with and , the cover time

**Proof.**Let be an arbitrary spanning tree of . There exists an Eulerian tour of in which each edge is traversed once in each direction. Let be such a tour. Clearly the expected time to go through the vertices in the tour is an upper bound on the cover time. Hence,

A tighter bound (with a smaller constant factor) can be proved with a more careful analysis. Please read the textbook [MR].