随机算法 (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.
- 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].