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.

该研究提出了一种强大的工具包，用于估计具有共同随机行走和混淆时间的随机游走在无向图上的汇聚时间和会合时间，并对相似类别的图形的汇聚时间和会合时间进行了完整的探索。

关于图中的合并时间 —— 何时合并速度与相遇速度一样快？

On coalescence time in graphs--When is coalescing as fast as meeting?

Consider a system of coalescing random walks where each individual performs
random walk over a finite graph G, or (more generally) evolves according to
some reversible Markov chain generator Q. Let C be the first time at which all
walkers have coalesced into a single cluster. C is closely related to the
consensus time of the voter model for this G or Q.
We prove that the expected value of C is at most a constant multiple of the
largest hitting time of an element in the state space. This solves a problem
posed by Aldous and Fill and gives sharp bounds in many examples, including all
vertex-transitive graphs. We also obtain results on the expected time until
only k>1 clusters remain. Our proof tools include a new exponential inequality
for the meeting time of a reversible Markov chain and a deterministic
trajectory, which we believe to be of independent interest.

研究了一种随机漫步的聚合系统，其中每个个体都在有限图 G 上进行随机漫步，或者（更一般地）按照某个可逆马尔可夫链生成器 Q 进行演变，证明了所有漫步者聚合成单个群集的时间 C 的期望值最多仅为状态空间中某个元素的最大碰撞时间的常数倍，并且提出了关于仅剩下 k>1 个群集的预期时间的结果。