Hitting and Covering consider a random walk on GV,E) hitting time:expected time to reach v from u Tw=min {n=Xo=u cover time:expected time to visit all vertices Cu=E minn.v Xo=u C(G)=max Cu u∈VHitting and Covering • hitting time: expected time to reach v from u • cover time: expected time to visit all vertices ￾u,v = E ⌅ min ￾ n > 0 ⇤ ⇤ Xn = v ⇥ ⇤ ⇤ ⇤ X0 = u ⇧ Cu = E ⌅ min ￾ n ⇤ ⇤ {X0,...,Xn} = V ⇥ ⇤ ⇤ ⇤ X0 = u ⇧ C(G) = max u￾V Cu consider a random walk on G(V,E)