Optimal cover time for a graph-based coupon collector process
In this paper we study the following covering process defined over an arbitrary directed graph. Each node is initially uncovered and is assigned a random integer rank drawn from a suitable range. The process then proceeds in rounds. In each round, a uniformly random node is selected and its lowest-ranked uncovered outgoing neighbor, if such exists, is covered. We prove that if each node has in-degree ?(d) ? ( d ) and out-degree O(d) O ( d ) , then with high probability, every node is covered within O ( n + n log n d ) rounds, matching a lower bound due to Alon. A special case of our result is that for any ? ( log n ) -regular graph and a small rank range of ? ( log n ) , every node is covered within ?(n) ? ( n ) rounds. Alon has also shown that, for a certain class of d-regular expander graphs, the upper bound holds no matter what method is used to choose the uncovered neighbor. In contrast, we show that for arbitrary d-regular graphs, the method used to choose the uncovered neighbor can affect the cover time by more than a constant factor.
coupon collector process graph covering delay sequence argument