%0 Generic %1 chatterjee2010gossip %A Chatterjee, Shirshendu %A Durrett, Rick %D 2010 %K adaptation asymptotic gossip spatial_spread %T Asymptotic Behavior of Aldous' Gossip Process %U http://arxiv.org/abs/1005.1608 %X Aldous (2007) 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 $< 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 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) T + N^\alpha/3 łog(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.

@misc{chatterjee2010gossip, abstract = { Aldous (2007) 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 $\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. }, added-at = {2010-07-21T00:42:10.000+0200}, author = {Chatterjee, Shirshendu and Durrett, Rick}, biburl = {https://www.bibsonomy.org/bibtex/26cca724426ea8ec867bf92e0305ab39d/peter.ralph}, description = {[1005.1608] Asymptotic Behavior of Aldous' Gossip Process}, interhash = {5fe5b840b04fd3044e7e89c1f2e526cb}, intrahash = {6cca724426ea8ec867bf92e0305ab39d}, keywords = {adaptation asymptotic gossip spatial_spread}, note = {cite arxiv:1005.1608 }, timestamp = {2010-07-21T00:42:10.000+0200}, title = {Asymptotic Behavior of Aldous' Gossip Process}, url = {http://arxiv.org/abs/1005.1608}, year = 2010 }