There are a few (and only a few) examples where one can study by bare-hands exact calculations. Write for the harmonic sum
(6.7) |
(a) The coupon collector’s problem. Many textbooks discuss this classical problem, which involves for the chain whose values are independent and uniform on an -element set, i.e. random walk on the complete graph with self-loops. Write (cf. the proof of Matthews’ method, Chapter 2 yyy) for the first time at which distinct vertices have been visited. Then each step following time has chance to hit a new vertex, so , and so
(6.8) |
(By symmetry, is the same for each initial vertex, so we just write ) It is also a textbook exercise (e.g. [133] p. 124) to obtain the limit distribution
(6.9) |
where has the extreme value distribution
(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 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 has chance to hit a new vertex, so
(6.11) |
And the distribution limit (6.9) still holds. Because for , we also have
(6.12) |
(c) The -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 for the central vertex and for a leaf,
and 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.
On an -vertex tree,
(d) The -cycle. Random walk on the -cycle is also easy to study. At time the walk has visited distinct vertices, and the set of visited vertices must form an interval , say, where we add modulo . At time the walk is at one of the endpoints of that interval, and is the time until the first of is visited, which by Chapter 5 yyy has expectation . So
There is also an expression for the limit distribution (see Notes).
The -cycle also has an unexpected property. Let denote the last vertex to be hit. Then
In other words, the -cycle has the property
For any initial vertex , the last-visited vertex is uniform on the states excluding .
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].