On coalescence time in graphs: when is coalescing as fast as meeting? Extended abstract

DOI10.1137/1.9781611975482.59zbMATH Open1434.05137arXiv1611.02460OpenAlexW2907355031MaRDI QIDQ5236243FDOQ5236243

Authors: Varun Kanade, Frederik Mallmann-Trenn, Thomas Sauerwald 

Publication date: 15 October 2019

Published in: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1611.02460

Recommendations

• On the coalescence time of reversible random walks
• Meeting times of random walks on graphs
• Coalescing random walks and voting on connected graphs
• Coalescing random walks and voting on graphs
• Random walks on graphs: new bounds on hitting, meeting, coalescing and returning

zbMATH Keywords

couplingcoalescing random walksmeeting timereversible Markov chainharmonic mean formula

Mathematics Subject Classification ID

Random walks on graphs (05C81)

Cited In (21)

• Voter models on subcritical scale‐free random graphs
• Tight bounds for coalescing-branching random walks on regular graphs
• A stochastic process on a network with connections to Laplacian systems of equations
• On the meeting of random walks on random DFA
• Mean field conditions for coalescing random walks
• Random walks on dynamic graphs: mixing times, hitting times, and return probabilities
• Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
• Meeting, coalescence and consensus time on random directed graphs
• Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
• Asymptotic behaviour of the noisy voter model density process
• Reversible random walks on dynamic graphs
• Two-type annihilating systems on the complete and star graph
• Cover and hitting times of hyperbolic random graphs
• Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model
• Quasi-majority functional voting on expander graphs
• Biased opinion dynamics: when the devil is in the details
• Noidy conmunixatipn: on the convergence of the averaging population protocol
• Coalescing and branching simple symmetric exclusion process
• Phase transition of the \(k\)-majority dynamics in biased communication models
• Coalescing random walks and voting on connected graphs
• Mean field behavior during the big bang regime for coalescing random walks

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)