Asymptotic behavior of Aldous' gossip process

Abstract

Aldous [(2007) Preprint] defined a gossip process in which space is a discrete $N\times N$ 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-2\alpha /3)N^{\alpha /3}\log N$. If ${\rho }_s$ is the fraction of the population who know the information at time $s$ and $\epsilon$ is small then, for large $N$, the time until ${\rho }_s$ reaches $\epsilon$ is $T(\epsilon )\approx T+N^{\alpha /3}\log (3\epsilon /M)$, where $M$ is a random variable determined by the early spread of the information. The value of ${\rho }_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.

Published in at http://dx.doi.org/10.1214/10-AAP750 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Optimal flow through the disordered lattice
• When Knowing Early Matters: Gossip, Percolation and Nash Equilibria

Cited by in corpus (3)

• Interacting particle systems as stochastic social dynamics
• When Knowing Early Matters: Gossip, Percolation and Nash Equilibria
• A central limit theorem for the gossip process