On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?

Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald

Abstract

Coalescence time ($t_{coal}$) measures the duration required for multiple independent random walks on a graph to merge into a single particle. This paper presents a comprehensive theoretical framework for analyzing $t_{coal}$, demonstrating that for a broad class of "well-behaved" graphs, the time for $n$ particles to merge is asymptotically equivalent to the meeting time ($t_{meet}$) of just two particles. The authors establish a universal $O(n^3)$ upper bound for any undirected graph and provide the first tight bounds for several fundamental topologies, including binary trees and hypercubes.

Introduction

In the study of distributed systems and opinion dynamics, the coalescing random walk process serves as a critical model. Starting with one particle at every node of a graph, particles move to random neighbors at each time step. When multiple particles occupy the same node, they coalesce into one. This process is the mathematical dual of the voter model, which describes consensus-reaching in networks.

A central question in this field is determining the coalescence time ($t_{coal}$)—the time until only one particle remains. While it was known that $t_{coal}$ lies between the meeting time ($t_{meet}$) and $O(t_{meet} \log n)$, precise bounds for common structures like binary trees or hypercubes remained elusive. This research addresses these gaps by identifying the conditions under which coalescence is as fast as a single meeting.

Methods

The authors depart from traditional mixing-time-centric analyses, introducing three primary theoretical tools:

  1. The Immortal Process: A simplification technique that partitions particles into "immortals" and "mortals" to manage complex dependencies, proving that the actual process is bounded by this restricted model.
  2. Conditional Expectation Approach: A method relating meeting probabilities to the expected number of collisions, enabling the analysis of random walk behavior before full mixing occurs.
  3. New Concentration Inequalities: Derivations of inequalities based on hitting time ($t_{hit}$) rather than mixing time ($t_{mix}$), allowing for tighter control on non-expander graphs where standard tools often fail.

Key Results

The study's most significant contribution is the discovery of a threshold for coalescence speed. If the meeting time significantly exceeds the mixing time (specifically $t_{meet} \gg t_{mix} \log^2 n$), then $t_{coal} = \Theta(t_{meet})$. This "Log Squared" rule implies that in many networks, the entire crowd merges as quickly as a single pair.

Summary of mixing, meeting, coalescence, and hitting times for various graph topologies.

Beyond specific topologies, the authors established a universal speed limit: for any undirected graph, $t_{coal} = O(n^3)$. This bound is tight, as demonstrated by the Barbell graph. Furthermore, the paper settles a discrete-time version of Aldous’s conjecture for almost-regular graphs, proving that $t_{coal}$ is bounded by the hitting time.

Specific findings for common graphs include:

  • Binary Trees and 2D Tori: Both exhibit $t_{coal} = \Theta(n \log n)$.
  • General Bound: For any graph, $t_{coal} = O\left(t_{meet} \left(1 + \sqrt{\frac{t_{mix}}{t_{meet}}} \cdot \log n\right)\right)$.
  • Regular Graphs: Improved bounds based on conductance ($\Phi$), where $t_{coal} = O\left(\frac{n \log n}{\Phi}\right)$.

Conclusion

This work provides a definitive toolkit for bounding coalescence times across diverse graph structures. While the $t_{coal} = O(t_{hit})$ result is currently limited to almost-regular graphs, it paves the way for a potential unified proof for all undirected graphs. Future research may also explore the subtle differences between synchronous and asynchronous particle movement in non-lazy random walks.

Summary updated

Abstract

Coalescing random walks is a fundamental stochastic 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 coalescence time is defined as the expected time until only one particle remains, starting from one particle at every node. Despite recent progress the coalescence time for graphs such as binary trees, d-dimensional tori, hypercubes and more generally, vertex-transitive graphs, remains unresolved. 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^2 n), the coalescence time of n 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. For almost-regular graphs, we bound the coalescence time by the hitting time, resolving the discrete-time variant of a conjecture by Aldous for this class of graphs. Finally, we prove that for any graph the coalescence time is bounded by O(n^3) (which is tight for the Barbell graph); surprisingly even such a basic question about the coalescing time was not answered before this work. By duality, our results give bounds on the voter model and therefore give bounds on the consensus time in arbitrary undirected graphs. We also establish a new bound on the hitting time and cover time of regular graphs, improving and tightening previous results by Broder and Karlin, as well as those by Aldous and Fill.
BibTeX
@article{kanade2016coalescence,
  author = {Varun Kanade and Frederik Mallmann-Trenn and Thomas Sauerwald},
  title = {{On Coalescence Time in Graphs: When Is Coalescing as Fast as Meeting?}},
  journal = {ACM Trans. Algorithms},
  year = {2016},
  doi = {10.1145/3576900},
}
Figure