Asymptotic behavior of Aldous. gossip process

Aldous [(2007) Preprint] defined a gossip process in which space is a discrete N . 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.. to a site chosen at random from the torus. We will be interested in the case in which . < 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 ./3)N./3log.N. If .s is the fraction of the population who know the information at time s and . is small then, for large N, the time until .s reaches . is T(.) . T + N./3log(3./M), where M is a random variable determined by the early spread of the information. The value of .s at time s = T(1/3) + tN./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.