Mean field conditions for coalescing random walks (Q378808)

The main result of this paper is to show that the time to full coalescence of random walks on a finite graph can, up to a rescaling by the expected meeting time of two walkers, be approximated by a sum of independent exponential random variables \(Z_i\), where \(Z_i \sim \mathrm{Exp}\left({i}\choose{2}\right)\), \(i\geq 2\). An explicit error bound in the \(L_1\)-Wasserstein distance is given. This is small when the mixing time for a single random walker is small. The error also vanishes as the graph size tends to infinity for a number of families of graphs, establishing a mean field result in this case.NEWLINENEWLINEThe paper is well presented and the reader is clearly led through the calculations with almost exponential distributions that form the backbone of the proofs. An important step is to show that the times at which the random walkers meet fall into this category.