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

For any ${\displaystyle u,v\in V}$, the hitting time ${\displaystyle \tau _{u,v}}$ is the expected number of steps before vertex ${\displaystyle v}$ is visited, starting from vertex ${\displaystyle u}$.

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

${\displaystyle \tau _{v,v}={\frac {1}{\pi _{v}}}={\frac {2m}{d(v)}}.}$

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

 Lemma For a random walk on an undirected graph ${\displaystyle G(V,E)}$ where${\displaystyle |E|=m}$, for any ${\displaystyle u,v\in V}$ that ${\displaystyle (u,v)\in E}$, the mean hitting time {\displaystyle {\begin{aligned}\tau _{u,v}<2m\end{aligned}}}.
Proof.
 The proof is by double counting. We know that ${\displaystyle \tau _{v,v}={\frac {1}{\pi _{v}}}={\frac {2m}{d(v)}}.}$ Let ${\displaystyle N(v)}$ be the set of neighbors of vertex ${\displaystyle v}$. We run the random walk from ${\displaystyle v}$ for one step, and by the law of total expectation, ${\displaystyle \tau _{v,v}=\sum _{w\in N(v)}{\frac {1}{d(v)}}(1+\tau _{w,v}).}$ Combining the above two equations, we have ${\displaystyle 2m=\sum _{w\in N(v)}(1+\tau _{w,v}),}$ which implies that ${\displaystyle \tau _{u,v}<2m}$.
${\displaystyle \square }$

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

• Let ${\displaystyle C_{u}}$ be the expected number of steps taken by a random walk which starts at ${\displaystyle u}$ to visit every vertex in ${\displaystyle G}$ at least once. The cover time of ${\displaystyle G}$, denoted ${\displaystyle C(G)}$ is defined as ${\displaystyle C(G)=\max _{u\in V}C_{u}}$.
 Theorem (cover time) For any connected undirected graph ${\displaystyle G(V,E)}$ with ${\displaystyle |V|=n}$ and ${\displaystyle |E|=m}$, the cover time ${\displaystyle C(G)\leq 4nm}$
Proof.
 Let ${\displaystyle T}$ be an arbitrary spanning tree of ${\displaystyle G}$. There exists an Eulerian tour of ${\displaystyle T}$ in which each edge is traversed once in each direction. Let ${\displaystyle v_{1}\rightarrow v_{2}\rightarrow \cdots \rightarrow v_{2(n-1)}\rightarrow v_{2n-1}=v_{1}}$ 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, ${\displaystyle C(G)\leq \sum _{i=1}^{2(n-1)}\tau _{v_{i},v_{i+1}}<2(n-1)\cdot 2m<4nm.}$
${\displaystyle \square }$

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