Asymptotic behavior of Aldous' gossip process

DOI10.1214/10-AAP750MaRDI QIDQ657708zbMATHFDO

Authors Shirshendu Chatterjee, Rick Durrett

Publication date 10 January 2012

Published in The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

branching processesintegro-differential equationfirst-passage percolationgossip

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: Aldous [(2007) Preprint] defined a gossip process in which space is a discrete $NimesN$ torus, and the state of the process at time $t$ is the set of individuals who know the information. Information spreads from a site to its nearest neighbors at rate 1/4 each and at rate $N^{-alpha}$ to a site chosen at random from the torus. We will be interested in the case in which $alpha<3$, where the long range transmission significantly accelerates the time at which everyone knows the information. We prove three results that precisely describe the spread of information in a slightly simplified model on the real torus. The time until everyone knows the information is asymptotically $T=(2-2alpha/3)N^{alpha/3}logN$. If $h{o}_s$ is the fraction of the population who know the information at time $s$ and $varepsilon$ is small then, for large $N$, the time until $h{o}_s$ reaches $varepsilon$ is $T(varepsilon)approxT+N^{alpha/3}log(3varepsilon/M)$, where $M$ is a random variable determined by the early spread of the information. The value of $h{o}_s$ at time $s=T(1/3)+t{N}^{alpha/3}$ is almost a deterministic function $h(t)$ which satisfies an odd looking integro-differential equation. The last result confirms a heuristic calculation of Aldous.

Recommendations

• A central limit theorem for the gossip process
• Asymptotic Behaviour of Gossip Processes and Small-World Networks
• On rumour propagation among sceptics
• On Spreading a Rumor
• Rumor Processes on N

Cites work

• scientific article; zbMATH DE number 5819433 (Why is no real title available?)
• scientific article; zbMATH DE number 3971949 (Why is no real title available?)
• Long range dispersal and spatial pattern formation in biological invasions
• Optimal flow through the disordered lattice
• Random graph dynamics
• Small worlds
• Some limit theorems for percolation processes with necessary and sufficient conditions

Cited in

(9)

• Interacting particle systems as stochastic social dynamics
• Couplings for locally branching epidemic processes
• Acceleration of gossip algorithms through the Euler–Poisson–Darboux Equation
• A central limit theorem for the gossip process
• Multiple phase transitions in long-range first-passage percolation on square lattices
• Spatial Moran models. II: Cancer initiation in spatially structured tissue
• When knowing early matters: gossip, percolation and Nash equilibria
• Covering a compact space by fixed-radius or growing random balls
• Asymptotic Behaviour of Gossip Processes and Small-World Networks

This page was built for publication: Asymptotic behavior of Aldous' gossip process

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q657708)