ASYMPTOTIC BEHAVIOR OF ALDOUS' GOSSIP PROCESS

• 成果类型: Article
• 署名作者: Chatterjee, Shirshendu; Durrett, Rick
• 署名单位: Cornell University; Duke University
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/10-AAP750
• 发表日期: 2011
• 页码: 2447-2482
• 关键词: percolation; dispersal

摘要

Aldous [(2007) Preprint] 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 epsilon is small then, for large N, the time until rho(s) reaches epsilon is T (epsilon) approximate to 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) + tN(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.