Asymptotic behavior of Aldous' gossip process

DOI10.1214/10-AAP750zbMATH Open1246.60117arXiv1005.1608MaRDI QIDQ657708FDOQ657708

Shirshendu Chatterjee, Rick Durrett

Publication date: 10 January 2012

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

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.

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

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

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)

Cites Work

• Some limit theorems for percolation processes with necessary and sufficient conditions
• Title not available (Why is that?)
• Small worlds
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal flow through the disordered lattice
• Long range dispersal and spatial pattern formation in biological invasions

Cited In (8)

• A central limit theorem for the gossip process
• Spatial Moran models. II: Cancer initiation in spatially structured tissue
• Covering a compact space by fixed-radius or growing random balls
• Acceleration of gossip algorithms through the Euler–Poisson–Darboux Equation
• Multiple Phase Transitions in Long-Range First-Passage Percolation on Square Lattices
• Interacting particle systems as stochastic social dynamics
• Couplings for locally branching epidemic processes
• 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)