| Summary: | <p>Coalescing random walks is a fundamental distributed process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single random walk. The <em>coalescence time</em> is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress such as by Cooper et al. [14] and Cooper et al. [19], the coalescence time for graphs such as binary trees, <em>d</em>-dimensional tori, hypercubes and more generally, vertex-transitive graphs, remains unresolved.</p>
<p>We provide a powerful toolkit that results in tight bounds for various topologies including the aforementioned ones. The meeting time is defined as the worst-case expected time required for two random walks to arrive at the same node at the same time. As a general result, we establish that for graphs whose meeting time is only marginally larger than the mixing time (a factor of log <sup>2</sup><em>n</em>), the coalescence time of <em>n</em> random walks equals the meeting time up to constant factors. This upper bound is complemented by the construction of a graph family demonstrating that this result is the best possible up to constant factors. Finally, we prove a tight worst case bound for the coalescence time of <em>O</em>(<em>n</em><sup>3</sup>). By duality, our results yield identical bounds on the voter model.</p>
<p>Our techniques also yield a new bound on the hitting time and cover time of regular graphs, improving and tightening previous results by Broder and Karlin [12], as well as those by Aldous and Fill [2].</p>
|
|---|