6 Cover Times (October 31, 1994)

6.2 Simple examples of cover times

There are a few (and only a few) examples where one can study ECEC by bare-hands exact calculations. Write hnh_{n} for the harmonic sum

hn=i=1ni-1logn.h_{n}=\sum_{i=1}^{n}i^{-1}\sim\log n. (6.7)

(a) The coupon collector’s problem. Many textbooks discuss this classical problem, which involves CC for the chain (Xt;t0)(X_{t};t\geq 0) whose values are independent and uniform on an nn-element set, i.e. random walk on the complete graph with self-loops. Write (cf. the proof of Matthews’ method, Chapter 2 yyy) CmC^{m} for the first time at which mm distinct vertices have been visited. Then each step following time CmC^{m} has chance (n-m)/n(n-m)/n to hit a new vertex, so E(Cm+1-Cm)=n/(n-m)E(C^{m+1}-C^{m})=n/(n-m), and so

EC=m=1n-1E(Cm+1-Cm)=nhn-1.EC=\sum_{m=1}^{n-1}E(C^{m+1}-C^{m})=nh_{n-1}. (6.8)

(By symmetry, EvCE_{v}C is the same for each initial vertex, so we just write ECEC) It is also a textbook exercise (e.g. [133] p. 124) to obtain the limit distribution

n-1(C-nlogn)dξn^{-1}(C-n\log n)\ \stackrel{d}{\rightarrow}\ \xi (6.9)

where ξ\xi has the extreme value distribution

P(ξx)=exp(-e-x),-<x<.P(\xi\leq x)=\exp(-e^{-x}),\ \ -\infty<x<\infty. (6.10)

We won’t go into the elementary derivations of results like (6.9) here, because in Chapter 7 yyy we give more general results.

(b) The complete graph. The analysis of CC for random walk on the complete graph (i.e. without self-loops) is just a trivial variation of the analysis above. Each step following time CmC^{m} has chance (n-m)/(n-1)(n-m)/(n-1) to hit a new vertex, so

EC=(n-1)hnnlogn.EC=(n-1)h_{n}\sim n\log n. (6.11)

And the distribution limit (6.9) still holds. Because EvTw=n-1E_{v}T_{w}=n-1 for wvw\neq v, we also have

EC+=EC+(n-1)=(n-1)(1+hn-1)nlogn.EC^{+}=EC+(n-1)=(n-1)(1+h_{n-1})\sim n\log n. (6.12)

(c) The nn-star (Chapter 5 Example yyy). Here the visits to the leaves (every second step) are exactly i.i.d., so we can directly apply the coupon collector’s problem. For instance, writing vv for the central vertex and ll for a leaf,

ElC\displaystyle E_{l}C =\displaystyle= 2(n-1)hn-22nlogn\displaystyle 2(n-1)h_{n-2}\sim 2n\log n
EvC+\displaystyle E_{v}C^{+} =\displaystyle= 1+ElC+1=2(n-1)hn-12nlogn\displaystyle 1+E_{l}C+1=2(n-1)h_{n-1}\sim 2n\log n

and C/2C/2 satisfies (6.9). Though we won’t give the details, it turns out that a clever inductive argument shows these are the minima over all trees.

Proposition 6.7 (Brightwell - Winkler [61])

On an nn-vertex tree,

minvEvC2(n-1)hn-2\min_{v}E_{v}C\geq 2(n-1)h_{n-2}
minvEvC+2(n-1)hn-1.\min_{v}E_{v}C^{+}\geq 2(n-1)h_{n-1}.

(d) The nn-cycle. Random walk on the nn-cycle is also easy to study. At time CmC^{m} the walk has visited mm distinct vertices, and the set of visited vertices must form an interval [j,j+m-1][j,j+m-1], say, where we add modulo nn. At time CmC^{m} the walk is at one of the endpoints of that interval, and Cm+1-CmC^{m+1}-C^{m} is the time until the first of {j-1,j+m}\{j-1,j+m\} is visited, which by Chapter 5 yyy has expectation 1×m1\times m. So

EC=m=1n-1E(Cm+1-Cm)=i=1n-1i=12n(n-1).EC=\sum_{m=1}^{n-1}E(C^{m+1}-C^{m})=\sum_{i=1}^{n-1}i=\frac{1}{2}n(n-1).

There is also an expression for the limit distribution (see Notes).

The nn-cycle also has an unexpected property. Let VV denote the last vertex to be hit. Then

P0(V=v)\displaystyle P_{0}(V=v) =\displaystyle= P0(Tv-1<Tv+1)Pv-1(Tv+1<Tv)\displaystyle P_{0}(T_{v-1}<T_{v+1})P_{v-1}(T_{v+1}<T_{v})
    +P0(Tv+1<Tv-1)Pv+1(Tv-1<Tv)\displaystyle\ \ \ \ +P_{0}(T_{v+1}<T_{v-1})P_{v+1}(T_{v-1}<T_{v})
=\displaystyle= n-(v+1)n-21n-1+v-1n-21n-1\displaystyle\frac{n-(v+1)}{n-2}\frac{1}{n-1}+\frac{v-1}{n-2}\frac{1}{n-1}
=\displaystyle= 1n-1.\displaystyle\frac{1}{n-1}.

In other words, the nn-cycle has the property

For any initial vertex v0v_{0}, the last-visited vertex VV is uniform on the states excluding v0v_{0}.

Obviously the complete graph has the same property, by symmetry. Lovasz and Winkler [219] gave a short but ingenious proof that these are the only graphs with that property, a result rediscovered in [179].