随机算法 (Fall 2011)/Cover Time

From EtoneWiki
Jump to: navigation, search

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].