Mean Field Behavior during the Big Bang Regime for Coalescing Random Walks

Abstract

In this paper we consider coalescing random walks on a general connected graph $G=(V,E)$. We set up a unified framework to study the leading order of the decay rate of $P_t$, the expectation of the fraction of occupied sites at time $t$, particularly for the `Big Bang' regime where $t\ll t_{\text{coal}}:=\mathbb{E}[\inf \{s:\text{There is only one particle at time }s\}]$. Our results show that $P_t$ satisfies certain mean field behavior, if the graphs satisfy certain transience-like conditions. We apply this framework to two families of graphs: (1) graphs given by the configuration model with a degree distribution supported in $[3,\bar{d}]$ for some $\bar{d}\ge 3$, and (2) finite and infinite vertex-transitive graphs. In the first case, we show that for $1\ll t\ll |V|$, $P_t$ decays in the order of $t^{-1}$, and $(t{P}_t{)}^{-1}$ is approximately the probability that two particles starting from the root of the corresponding unimodular Galton-Watson tree never collide after one of them leaves the root, which is also roughly $|V|/(2t_{\text{meet}})$, where $t_{\text{meet}}$ is the mean meeting time of two walkers. By taking the local weak limit, for the unimodular Galton-Watson tree we prove the convergence of $t{P}_t$ as $t\to \infty$. For the second family of graphs, if we take a sequence of finite graphs $G_n=(V_n,E_n)$, such that $t_{\text{meet}}=O(|V_n|)$ and the inverse of the spectral gap $t_{\text{rel}}$ is $o(|V_n|)$, then for $t_{\text{rel}}\ll t\ll t_{\text{coal}}$, $(t{P}_t{)}^{-1}$ is approximately the probability that two random walks never meet before time $t$, and also $|V|/(2t_{\text{meet}})$. In addition, we define a natural uniform transience condition, and show that it implies the above for all $1\ll t\ll t_{\text{coal}}$. Such estimates of $t{P}_t$ are also obtained for all infinite transient transitive unimodular graphs, in particular, all transient transitive amenable graphs.

72 pages

References in corpus (1)

• On the universality of fluctuations for the cover time

Cited by in corpus (2)

• Discordant edges for the voter model on regular random graphs
• Diffusion-limited annihilating-coalescing systems