Asymptotic behavior of Aldous' gossip process

Details Asymptotic behavior of Aldous' gossip process Asymptotic behavior of Aldous' gossip process

2010-05-10

arxiv.org/abs/1005.1608v2

Annals of Applied Probability 2011, Vol. 21, No. 6, 2447-2482

Mathematics

Probability

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

Scientific paper

10.1214/10-AAP750

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 $\varepsilon$ is small then, for large $N$, the time until $\rho_s$ reaches $\varepsilon$ is $T(\varepsilon)\approx T+N^{\alpha/3}\log (3\varepsilon /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.

Affiliated with

Also associated with

No associations

Rating

Asymptotic behavior of Aldous' gossip process does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotic behavior of Aldous' gossip process, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic behavior of Aldous' gossip process will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-628666