On coalescence time in graphs: when is coalescing as fast as meeting? Extended abstract
From MaRDI portal
Publication:5236243
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.
Recommendations
Cited in
(21)- Voter models on subcritical scale‐free random graphs
- Asymptotic behaviour of the noisy voter model density process
- Meeting, coalescence and consensus time on random directed graphs
- Random walks on dynamic graphs: mixing times, hitting times, and return probabilities
- Mean field behavior during the big bang regime for coalescing random walks
- Biased opinion dynamics: when the devil is in the details
- Cover and hitting times of hyperbolic random graphs
- Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model
- On the meeting of random walks on random DFA
- Coalescing and branching simple symmetric exclusion process
- Phase transition of the \(k\)-majority dynamics in biased communication models
- Reversible random walks on dynamic graphs
- Noidy conmunixatipn: on the convergence of the averaging population protocol
- Quasi-majority functional voting on expander graphs
- Tight bounds for coalescing-branching random walks on regular graphs
- Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
- Mean field conditions for coalescing random walks
- Coalescing random walks and voting on connected graphs
- A stochastic process on a network with connections to Laplacian systems of equations
- Two-type annihilating systems on the complete and star graph
- Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
This page was built for publication: On coalescence time in graphs: when is coalescing as fast as meeting? Extended abstract
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236243)
