Asymptotic Behavior of Aldous' Gossip Process
Shirshendu Chatterjee and Rick Durrett
Abstract.
Aldous (2007) defined a gossip process in which space is a discrete N x 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 \ep is small then, for large N, the time until
\rho_s reaches \ep is T(\ep) \approx T + N^{\alpha/3} \log(3\ep/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.
Preprint
Back to Durrett's home page