Mean field conditions for coalescing random walks (Q378808)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Mean field conditions for coalescing random walks |
scientific article |
Statements
Mean field conditions for coalescing random walks (English)
0 references
12 November 2013
0 references
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. The 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.
0 references
coalescing random walks
0 references
voter model
0 references
hitting times
0 references
exponential approximation
0 references
0 references
0 references
0 references