TheAnnalsofAppliedProbability 2011,Vol.21,No.6,2447–2482 DOI:10.1214/10-AAP750 (cid:13)c InstituteofMathematicalStatistics,2011 1 ASYMPTOTIC BEHAVIOR OF ALDOUS’ GOSSIP PROCESS 2 1 By Shirshendu Chatterjee and Rick Durrett 0 2 Cornell University and Duke University r Aldous[(2007) Preprint]defined a gossip process in which space a M is a discrete N ×N torus, and the state of the process at time t is thesetofindividualswhoknowtheinformation.Informationspreads fromasitetoitsnearestneighborsatrate1/4eachandatrateN−α 2 toasitechosenatrandomfromthetorus.Wewillbeinterestedinthe ] case in which α<3, where the long range transmission significantly R accelerates the time at which everyone knows the information. We P provethreeresultsthatpreciselydescribethespreadofinformationin . aslightlysimplifiedmodelontherealtorus.Thetimeuntileveryone h knows the information is asymptotically T =(2−2α/3)Nα/3logN. t a If ρ is the fraction of the population who know the information at s m time s and ε is small then, for large N, the time until ρ reaches ε s [ is T(ε)≈T +Nα/3log(3ε/M), where M is a random variable de- termined by the early spread of the information. The value of ρs at 2 times=T(1/3)+tNα/3isalmostadeterministicfunctionh(t)which v satisfies an odd looking integro-differential equation. The last result 8 confirms a heuristic calculation of Aldous. 0 6 1 1. Introduction. We study a model introduced by Aldous (2007) for the . 5 spread of gossip and other more economically useful information. His paper 0 considers various game theoretic aspects of random percolation of informa- 0 tionthroughnetworks.Hereweconcentrateononesmallpart,afirstpassage 1 : percolation model with nearest neighbor and long-range jumps introduced v in his Section 6.2. The work presented here is also related to work of Filipe i X and Maule (2004) and Cannas, Marco and Montemurro (2006), who con- r sidered the impact of long-range dispersal on the spread of epidemics and a invading species. Space is the discrete torus Λ(N)=(Z modN)2. The state of the process at time t is ξ Λ(N), the set of individuals who know the information at t ⊂ Received May 2010; revised September2010. 1Supportedin part by NSFGrant DMS-07-04996 from the probability program. AMS 2000 subject classifications. Primary 60K35; secondary 60J80. Key words and phrases. Gossip, branching process, first-passage percolation, integro- differential equation. This is an electronic reprint of the original article published by the Institute of Mathematical Statistics in The Annals of Applied Probability, 2011,Vol. 21, No. 6, 2447–2482. This reprint differs from the original in pagination and typographic detail. 1 2 S. CHATTERJEE ANDR.DURRETT time t. Information spreads from i to j at rate 1/4, if j is a (nearest) neighbor of i, ν = ij λ /N2, if not. N (cid:26) If λ =0, this is ordinary first passage percolation on the torus. If we start N with ξ = (0,0) , then the shapetheorem for nearest-neighbor firstpassage 0 { } percolation, see Cox and Durrett (1981) or Kesten (1986), implies that until theprocess exits ( N/2,N/2)2,theradiusof theset ξ grows linearly and ξ t t − has an asymptotic shape. From this we see that if λ =0, then there is N a constant c so that the time T , until everyone knows the information, 0 N satisfies T N P c , 0 N → P where denotes convergence in probability. → To simplify things, we will remove the randomness from the nearest neighbor part of the process, and formulate it on the (real) torus Γ(N)= (R modN)2. One should be able to prove a similar result for the first pas- sage percolation model but there are two difficulties. The first and easier to handle is that the limiting shape is not round. The second and more diffi- cult issue is that the growth is not deterministic but has fluctuations. One should be able to handle both of these problems, but the proof is already long enough. We consider what we call the “balloon process,” in which the state of the process at time t is Γ(N). It starts with one “center” chosen uniformly t C ⊂ from the torus at time 0. When a center is born at x, a disk with radius 0 is put there, and its radius grows deterministically as r(s)=s/√2π, so that the area of the disk at time s after its birth is s2/2. If the area covered at time t is C , then births of new centers occur at rate λ C . The location of t N t each new center is chosen uniformly from the torus. If the new point lands at x , it will never contribute anything to the growth of the set, but we t will c∈ouCnt it in the total number of centers, which we denote by X˜ . t Before turning to the details of our analysis we would like to point out that a related balloon process was used by Barbour and Reinert (2001) in their study of distances on the small world graph. Consider a circle of ra- dius L and introduce a Poisson mean ρL/2 number of chords with length 0 connecting randomly chosen points on the circle. To study the distance be- tween a fixed point O and a point chosen at random one wants to examine S(t)= x:dist(O,x) t . If we ignore overlaps and let M(t) be the num- { ≤ } ber of intervals in S(t) then S′(t)=2M(t) and M(t) is a Yule process with births at rate 2ρM(t) due to the interval ends encountering points in the Poisson process of chords. This a balloon process in which the new births come from the boundaries. As in our case one first studies the growth of ALDOUS’GOSSIPPROCESS 3 the ballon process and then estimates the difference from the real process to prove the desired result. There are interesting parallels and differences between the two proofs, see Section 5.2 of Durrett (2007) for a proof. Here we will be concerned with λ =N−α. To begin we will get rid of N trivial cases. If the diameter of grows linearly, then c0NC dt=O(N3). Ct 0 t So if α>3, with probability tending to 1 as N goes to , there is no long R∞ range jump before the initial disk covers the entire torus, and the time T N until the entire torus is covered satisfies T N P c where c =√π. 1 1 N → If α=3, then with probabilities bounded away from 0, (i) there is no long range jump and T c N, and (ii) there is one that lands close enough to N 1 ≈ (N/2,N/2) to make T (1 δ)Nc . Using for weak convergence, this N 1 ≤ − ⇒ suggests that Theorem 0. When α=3, T /N a random limit concentrated on N ⇒ [0,c ] and with an atom at c . 1 1 Proof. Supposewithoutloss of generality thattheinitialcenter isat0, and view the torus as ( N/2,N/2]2. The key observation is that the set- − valued process /N,t 0 converges to a limit . Before the first long- Nt t {C ≥ } D rangedispersal,thestateof istheintersection ofthediskofradiust/√2π t D with ( 1/2,1/2]2. Long range births occur at rate equal to the area of t − D and are dispersed uniformly. Since the distance from (0,0) to (1/2,1/2) is 1/√2, if there are no long range births before time c =√π or if all long 1 range births land inside then the torus is covered at time c . Computing t 1 D the distribution of the cover time when it is <c is complicated, but the 1 answer is a continuous functional of the limit process, and standard weak convergence results give the result. (cid:3) For the remainder of the paper we suppose λ =N−α with α<3. The N overlaps between disks in pose a difficulty in analyzing the process, so we t C begin by studying a simpler “balloon branching process” , in which A is t t A the sum of the areas of all of the disks at time t, births of new centers occur at rate λ A , and the location of each new center is chosen uniformly from N t the torus. Let X be the number of centers at time t in . t t A Suppose we start and from the same randomly chosen point. The 0 0 C A areas C =A until the time of the first birth, which can be made to be the t t same in the two processes. If we couple the location of the new centers at that time, and continue in the obvious way letting and give birth at t t C A thesametimewiththemaximumratepossible,tothesameplacewhenthey give birth simultaneously, and letting give birth by itself otherwise, then t A 4 S. CHATTERJEE ANDR.DURRETT we will have (1.1) , C A , X˜ X for all t 0. t t t t t t C ⊂A ≤ ≤ ≥ X is a Crump–Mode–Jagers branching process, but saying these words t does not magically solve our problems. Define the length process L to be t √2π times the sum of the radii of all the disks at time t. t t L = (t s)dX = X ds, t s s − (1.2) Z0 Z0 t (t s)2 t A = − dX = L ds. t s s 2 Z0 Z0 t Here and later we use for integration over the closed interval [0,t], that 0 is, we include the contribution from the atom in dX at 0 (X =1 while s 0 R X =0 for s<0). For the second equality on each line integrate by parts s or note that L′ =X and A′ =L . Since X increases by 1 at rate λ A , t t t t t N t (X ,L ,A ) is a Markov process. t t t To simplify formulas, we will often drop the subscript N from λ . For N comparison with C , the parameter λ is important, but in the analysis of A t t it is not. If we let (1.3) X1=X(tλ−1/3), L1=λ1/3L(tλ−1/3), A1=λ2/3A(tλ−1/3), t t t then (X1,L1,A1) is the process with λ=1. t t t To study the growth of A , first we will compute the means of X , L t t t and A . Let F(t)=λt3/3!. Using the independent and identical behavior of t all the disks in it is easy to show that (see the proof of Lemma 2.4) t A t EX =1+ EX dF(s). t t−s Z0 Solving the above renewal equation and using (1.2), we can show ∞ ∞ λkt3k EX = F∗k(t)=V(t)= , t (3k)! k=0 k=0 X X ∞ λkt3k+1 (1.4) EL = , t (3k+1)! k=0 X ∞ λkt3k+2 EA = . t (3k+2)! k=0 X ToevaluateV(t)wenotethatV′′′(t)=λV(t)withV(0)=1,V′(0)=V′′(0)=0, so (1.5) V(t)= 1[exp(λ1/3t)+exp(λ1/3ωt)+exp(λ1/3ω2t)]. 3 ALDOUS’GOSSIPPROCESS 5 Here ω =( 1+i√3)/2 is one of the complex cube roots of 1 and ω2 = − ( 1 i√3)/2 is the other. Note that each of ω and ω2 has real part 1/2. − − − So the second and third terms in (1.5) go to 0 exponentially fast. If =σ X ,L ,A :r s , then s r r r F { ≤ } X 0 0 λ X d t s (1.6) E L = 1 0 0 L . t s s dt  (cid:12)F (cid:12)    A (cid:12) (cid:12) 0 1 0 A t(cid:12) (cid:12)t=s s  (cid:12) (cid:12)    Let Q be the matrix in (1(cid:12).6). B(cid:12)y computing the determinant of Q ηI it (cid:12) (cid:12) − is easy to see that Q has eigenvalues η=λ1/3,ωλ1/3,ω2λ1/3, and e−ηt(X + t ηL +η2A ) is a (complex) martingale. To treat the three martingales sep- t t arately, let I =X +λ1/3L +λ2/3A , M =exp( λ1/3t)I , t t t t t t − J =X +(ωλ1/3)L +(ωλ1/3)2A , J˜ =exp( ωλ1/3t)J , t t t t t t − K =X +(ω2λ1/3)L +(ω2λ1/3)2A , K˜ =exp( ω2λ1/3t)K , t t t t t t − so that M is the real martingale, and J˜ and K˜ are the complex ones. t t t Theorem 1. M :t 0 is a positive square integrable martingale with t { ≥ } respect to the filtration :t 0 . EM =M =1. t t 0 {F ≥ } EM2= 8 1exp( λ1/3t)+O(exp( 5λ1/3t/2)), t 7 − 3 − − E J˜ 2, E K˜ 2= 1exp(2λ1/3t)+O(exp(λ1/3t/2)). | t| | t| 6 If we let M =lim M , then P(M >0)=1 and t→∞ t exp( λ1/3t)X , λ1/3exp( λ1/3t)L , λ2/3exp( λ1/3t)A M/3 t t t − − − → a.s. and in L2. The distribution of M does not depend on λ. Thelast resultfollows from(1.3),which with (1.2)explains why thethree quantitiesconvergetothesamelimit.Thekeytotheproofoftheconvergence results is to note that 1+ω+ω2=0 implies 3X =I +J +K , t t t t 3λ1/3L =I +ω2J +ωK , t t t t 3λ2/3A =I +ωJ +ω2K . t t t t The real parts of ω and ω2 are 1/2. Although the results for E J˜ 2 and t E K˜ 2 show that the martingale−s J˜ and K˜ are not L2 bounded, |it i|s easy t t t | | to show that exp( λ1/3t)J and exp( λ1/3t)K 0 a.s. and in L2, and t t − − → Theorem 1 then follows from M =exp( λ1/3t)I M. t t − → 6 S. CHATTERJEE ANDR.DURRETT Recall that λ =N−α and let N a(t)=(1/3)N2α/3exp(N−α/3t), l(t)=N−α/3a(t), (1.7) x(t)=N−2α/3a(t), so that A /a(t),L /l(t),X /x(t) M a.s. Let t t t → (1.8) S(ε)=Nα/3[(2 2α/3)logN +log(3ε)], − so a(S(ε))=εN2. Let (1.9) σ(ε)=inf t:A εN2 and τ(ε)=inf t:C εN2 . t t { ≥ } { ≥ } The first of these is easy to study. Theorem 2. If 0<ε<1, then as N →∞ N−α/3(σ(ε) S(ε)) P log(M). − →− The coupling in (1.1) implies τ(ε) σ(ε). In the other direction, for any ≥ γ>0 ε1/3 limsupP[τ(ε)>σ((1+γ)ε)] P(M (1+γ)ε1/3)+11 . ≤ ≤ γ N→∞ The last result implies that for ε<1 (1.10) τ(ε) (2 2α/3)Nα/3logN. ∼ − Our next goal is to obtain more precise information about τ(ε) and about how C /N2 increases from a small positive level to reach 1. t | | ThefirstresultinTheorem2showsthat(σ(ε) S(ε))/Nα/3 isdetermined − by the random variable M from Theorem 1, which in turn is determined by what happens early in the growth of the branching balloon process. Let (1.11) R=Nα/3[(2 2α/3)logN log(M)], − − R is defined so that a(R)=(1/3)N2/M, and hence A /N2 P 1/3. Define R → (1.12) ψ(t) R+Nα/3t, W ψ(log(3ε)) and I =[log(3ε),t] ε,t ≡ ≡ forlog(3ε) t.W isdefinedsothata(W)=εN2/M andhenceA /N2 P ε. W ≤ → TheargumentsthatledtoTheorem2willshowthatifεissmallthenC /A W W is close to 1 with high probability. TogetalowerboundonthegrowthofC aftertimeW wedeclarethatthe t centers in and to be generation 0 in and , respectively, and we W W t t C A C A number the succeeding generations in the obvious way, a center born from an area of generation k is in generation k+1. For t log(3ε), let Ck ≥ W,ψ(t) and Ak denote the areas covered at time ψ(t) by respective centers of W,ψ(t) ALDOUS’GOSSIPPROCESS 7 generations j 0,1,...,k and let ∈{ } (t log(3ε))2 g (t)=ε 1+(t log(3ε))+ − , 0 − 2 (cid:20) (cid:21) (1.13) f (t)=g (t) ε7/6. 0 0 − To explain these definitions, we note that Lemma 4.3 will show that for any t, there is an ε =ε (t) so that for any 0<ε<ε 0 0 0 lim P sup N−2A0 g (s) >η =0 for any η>0, N→∞ s∈Iε,t| W,ψ(s)− 0 | (cid:16) (cid:17) P inf N−2(C0 A0 )< ε7/6 P(M <ε1/3)+ε1/12. s∈Iε,t W,ψ(s)− W,ψ(s) − ≤ (cid:16) (cid:17) Since C0 A0 , if ε is small, with high probability g (t) and f (t) W,ψ(t) ≤ W,ψ(t) 0 0 provide upper and lower bounds, respectively, for C0 . W,ψ(t) To begin to improve these bounds we let t (t s)2 f (t)=1 (1 f (t))exp − f (s)ds , 1 0 0 − − − 2 (cid:18) Zlog(3ε) (cid:19) and define g similarly. To explain this equation note that an x / C0 1 ∈ W,ψ(t) will not be in C1 if and only if no generation 1 center is born in the W,ψ(t) space–time cone Kε (y,s) Γ(N) [W,ψ(t)]: y x (ψ(t) s)/√2π . x,t≡{ ∈ × | − |≤ − } Lemma 4.4 shows that for 0<ε<ε and δ>0, 0 limsupP inf N−2C1 f (s)< δ P(M <ε1/3)+ε1/12. N→∞ s∈Iε,t W,ψ(s)− 1 − ≤ (cid:16) (cid:17) To iterate this we will let t (t s)2 f (t)=1 (1 f (t))exp − (f (s) f (s))ds k+1 k k k−1 − − − 2 − (cid:18) Zlog(3ε) (cid:19) for k 1. The difference f (s) f (s) in the integral comes from the k k−1 ≥ − fact that a new point in generation k+1 must come from a point that is in generation k butnotingeneration k 1.Combiningtheseequationswehave − 1 f (t) k+1 − t (t s)2 =(1 f (t))exp − (f (s) f (s))ds k k k−1 − − 2 − (cid:18) Zlog(3ε) (cid:19) t (t s)2 k =(1 f (t))exp − (f (s) f (s))ds k−1 l l−1 − − 2 − ··· Zlog(3ε) l=k−1 ! X 8 S. CHATTERJEE ANDR.DURRETT t (t s)2 k =(1 f (t))exp − (f (s) f (s))+f (s)ds 0 l l−1 0 − − 2 − Zlog(3ε) l=1 ! X so that t (t s)2 (1.14) f (t)=1 (1 f (t))exp − f (s)ds . k+1 0 k − − − 2 (cid:18) Zlog(3ε) (cid:19) Since f (t) f (t), letting k , f (t) f (t), where f is the unique so- 1 0 k ε ε ≥ →∞ ↑ lution of t (t s)2 (1.15) f (t)=1 (1 f (t))exp − f (s)ds ε 0 ε − − − 2 (cid:18) Zlog(3ε) (cid:19) with f (log(3ε))=ε ε7/6. g (t) and g (t) are defined similarly. ε k ε − g (t) and f (t) provide upper and lower bounds on the growth of C ε ε ψ(t) for t log(3ε). To close the gap between these bounds we let ε 0. ≥ → Lemma 1.1. For any t< , if I =[log(3ε),t], then as ε 0, ε,t ∞ → sup f (s) h(s), sup g (s) h(s) 0 ε ε | − | | − |→ s∈Iε,t s∈Iε,t for some nondecreasing h with (a) lim h(t)=0, (b) lim h(t)=1, t→−∞ t→∞ t (t s)2 (c) h(t)=1 exp − h(s)ds − − 2 (cid:18) Z−∞ (cid:19) and (d) 0<h(t)<1 for all t. If one removes the 2 from inside the exponential, this is equation (36) in Aldous (2007). Since there is no initial condition, the solution is only unique up to time translation. Theorem 3. Let h be the function in Lemma 1.1. For any t< and ∞ δ>0, lim P supN−2C h(s) δ =1. ψ(s) N→∞ s≤t| − |≤ (cid:16) (cid:17) Thisresultshowsthatthedisplacementofτ(ε)from(2 2α/3)Nα/3logN − on the scale Nα/3 is dictated by the random variable M that gives the rate of growth of the branching balloon process, and that once C reaches εN2, t the growth is deterministic. The solution h(t) never reaches 1, so we need a little more work to show that Theorem 4. Let T be the first time the torus is covered. As N N →∞ T /(Nα/3logN) P 2 2α/3. N → − ALDOUS’GOSSIPPROCESS 9 Theremainder of the paper is organized as follows. In Section 2, we prove the properties of presented in Theorem 1. In Section 3, we prove the t A properties of the hitting times s σ(ε) and τ(ε) stated in Theorem 2. In Section 4, we prove the limiting behavior of mentioned in Theorem 3. t C Finally in Section 5, we prove Theorem 4. 2. Properties of the balloon branching process At. Lemma 2.1. tsm(t s)nds= m!n! tm+n+1. 0 − (m+n+1)! R Proof. Ifyoucan rememberthedefinitionof thebetadistribution,this is trivial. If you cannot then integrate by parts and use induction. (cid:3) LetF(t)=λt3/3!fort 0,andF(t)=0fort<0.LetV(t)= ∞ F∗k(t), ≥ k=0 where k indicates the k-fold convolution. ∗ P Lemma 2.2. If ω=( 1+i√3)/2, then − ∞ λkt3k 1 V(t)= = [exp(λ1/3t)+exp(λ1/3ωt)+exp(λ1/3ω2t)]. (3k)! 3 k=0 X Proof. We first use induction to show that (2.1) F∗k(t)= λkt3k/(3k)!, t≥0, 0, t<0. (cid:26) This holds for k=0,1 by our assumption. If the equality holds for k=n, then using Lemma 2.1 we have for t 0 ≥ t t λn(t s)3nλs2 λn+1t3n+3 F∗(n+1)(t)= F∗n(t s)dF(s)= − ds= . − (3n)! 2 (3n+3)! Z0 Z0 It follows by induction that V(t)= ∞ λkt3k/(3k)!. To evaluate the sum k=0 we note that setting λ=1, U(t)= ∞ t3k/(3k)! solves k=0 P U′′′(t)=U(t) with U(0)=1 and U′(0)=U′′(0)=0. P This differential equation has solutions of the from eγt, where γ3=1, that is, γ=1,ω and ω2. This leads to the general solution U(t)=Aet+Beωt+Ceω2t for some constants A,B,C. Using the initial conditions for U(t) we have A+B+C =1, A+Bω+Cω2=0, A+Bω2+Cω=0. Since 1+ω+ω2=0, we have A=B =C =1/3. Since V(t)=U(λ1/3t), we have proved the desired result. (cid:3) Our next step is to compute the first two moments of X ,L and A . For t t t that we need the following lemma in addition to the previous one. 10 S. CHATTERJEE ANDR.DURRETT Lemma 2.3. Let N :t 0 be a Poisson process on [0, ) with inten- t { ≥ } ∞ sity λ() and let Π be the set of points at time t. If Y ,Z :t 0 are two t t t · { ≥ } complex valued stochastic processes satisfying Y =y(t)+ Yi , Z =z(t)+ Zi , t t−si t t−si sXi∈Πt sXi∈Πt where (Yi,Zi), i=1,2,..., are i.i.d. copies of (Y,Z), and independent of N, then t EY =y(t)+ EY λ(s)ds, t t−s Z0 t E(Y Z )=(EY )(EZ )+ E(Y Z )λ(s)ds. t t t t t−s t−s Z0 Proof. N has Poisson distribution with mean Λ = tλ(s)ds. Given t t 0 N = n, the conditional distribution of Π is same as the distribution of t t R t ,...,t , where t ,...,t are i.i.d. from [0,t] with density β()=λ()/Λ . 1 n 1 n t { } · · Hence Nt t E(Y N )=y(t)+ EYi =y(t)+N EY β(s)ds, t| t t−ti t t−s i=1 Z0 X t and taking expected values EY =y(t)+ EY λ(s)ds. t 0 t−s t SimilarlyEZ =z(t)+ EZ λ(s)ds.Usingtheconditionaldistribution t 0 t−s R of Π given N , t t R Nt Nt E(Y Z N )=y(t)z(t)+y(t)E Zi +z(t)E Yi t t| t t−ti t−ti i=1 i=1 X X Nt +E Yi Zi + Yi Zj t−ti t−ti t−ti t−tj " # i=1 i6=j X X t =y(t)z(t)+y(t)N EZ β(s)ds t t−s Z0 t t +z(t)N EY β(s)ds+N E(Y Z )β(s)ds t t−s t t−s t−s Z0 Z0 t t +N (N 1) EY β(s)ds EZ β(s)ds. t t t−s t−s − Z0 Z0 Taking expectation on both sides and using EN (N 1)=Λ2, we get t t− t t E(Y Z )=(EY )(EZ )+ E(Y Z )λ(s)ds, t t t t t−s t−s Z0 which completes the proof. (cid:3)