Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#243520] of Richard T. Durrett

Papers Published

  1. Chatterjee, S; Durrett, R, Asymptotic behavior of Aldous' gossip process, The Annals of Applied Probability, vol. 21 no. 6 (December, 2011), pp. 2447-2482, Institute of Mathematical Statistics, ISSN 1050-5164 [math.PR/1005.1608], [doi]
    (last updated on 2021/05/18)

    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 logN. If ρ is the fraction of the population who know the information at time s and ε is small then, for large N, the time until ρ reaches ε is T (ε) ~ T + N log(3ε/M), where M is a random variable determined by the early spread of the information. The value of ρ at time s = T (1/3) + tN is almost a deterministic function h(t) which satisfies an odd looking integro-differential equation. The last result confirms a heuristic calculation of Aldous. © Institute of Mathematical Statistics, 2011. -α α/3 α/3 α/3 s s s
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320