随机算法 (Fall 2011)/Cover Time

For any [math]\displaystyle{ u,v\in V }[/math], the hitting time [math]\displaystyle{ \tau_{u,v} }[/math] is the expected number of steps before vertex [math]\displaystyle{ v }[/math] is visited, starting from vertex [math]\displaystyle{ u }[/math].

Recall that any irreducible aperiodic Markov chain with finite state space converges to the unique stationary distribution [math]\displaystyle{ \begin{align} \pi_v=\frac{1}{\tau_{v,v}}. \end{align} }[/math] Combining with what we know about the stationary distribution [math]\displaystyle{ \pi }[/math] of a random walk on an undirected graph [math]\displaystyle{ G(V,E) }[/math] where [math]\displaystyle{ |E|=m }[/math], we have that for any vertex [math]\displaystyle{ v\in V }[/math],

[math]\displaystyle{ \tau_{v,v}=\frac{1}{\pi_v}=\frac{2m}{d(v)}. }[/math]

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

Lemma

For a random walk on an undirected graph [math]\displaystyle{ G(V,E) }[/math] where[math]\displaystyle{ |E|=m }[/math], for any [math]\displaystyle{ u,v\in V }[/math] that [math]\displaystyle{ (u,v)\in E }[/math], the mean hitting time [math]\displaystyle{ \begin{align}\tau_{u,v}\lt 2m\end{align} }[/math].

Proof. The proof is by double counting. We know that [math]\displaystyle{ \tau_{v,v}=\frac{1}{\pi_v}=\frac{2m}{d(v)}. }[/math] Let [math]\displaystyle{ N(v) }[/math] be the set of neighbors of vertex [math]\displaystyle{ v }[/math]. We run the random walk from [math]\displaystyle{ v }[/math] for one step, and by the law of total expectation, [math]\displaystyle{ \tau_{v,v}=\sum_{w\in N(v)}\frac{1}{d(v)}(1+\tau_{w,v}). }[/math] Combining the above two equations, we have [math]\displaystyle{ 2m=\sum_{w\in N(v)}(1+\tau_{w,v}), }[/math] which implies that [math]\displaystyle{ \tau_{u,v}\lt 2m }[/math]. [math]\displaystyle{ \square }[/math]

Note that the lemma holds only for the adjacent [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math]. With this lemma, we can prove an upper bound on the cover time.

• Let [math]\displaystyle{ C_u }[/math] be the expected number of steps taken by a random walk which starts at [math]\displaystyle{ u }[/math] to visit every vertex in [math]\displaystyle{ G }[/math] at least once. The cover time of [math]\displaystyle{ G }[/math], denoted [math]\displaystyle{ C(G) }[/math] is defined as [math]\displaystyle{ C(G)=\max_{u\in V}C_u }[/math].

Theorem (cover time)

For any connected undirected graph [math]\displaystyle{ G(V,E) }[/math] with [math]\displaystyle{ |V|=n }[/math] and [math]\displaystyle{ |E|=m }[/math], the cover time [math]\displaystyle{ C(G)\le 4nm }[/math]

Proof. Let [math]\displaystyle{ T }[/math] be an arbitrary spanning tree of [math]\displaystyle{ G }[/math]. There exists an Eulerian tour of [math]\displaystyle{ T }[/math] in which each edge is traversed once in each direction. Let [math]\displaystyle{ v_1\rightarrow v_2\rightarrow \cdots \rightarrow v_{2(n-1)}\rightarrow v_{2n-1}=v_1 }[/math] 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, [math]\displaystyle{ C(G)\le\sum_{i=1}^{2(n-1)}\tau_{v_{i},v_{i+1}}\lt 2(n-1)\cdot 2m\lt 4nm. }[/math] [math]\displaystyle{ \square }[/math]

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