On Spreading a Rumor

Source abstract

Suppose that one of n people knows a rumor. At the first stage, he passes the rumor to someone chosen at random; at each stage, each person already informed (“knower”) communicates the rumor to a person chosen at random and independently of all other past and present choices. Denote by $S_n$ the random number of stages before everybody is informed. How large is $S_n$ typically? Frieze and Grimmet, who introduced this problem, proved that, in probability, $S_n /( \log _2 n + \log n ) \to 1$. In this paper we show that, in fact, $S_n = \log _2 n + \log n + O( 1 )$ in probability. Our proof demonstrates that the number $I( t )$ of persons informed after t stages obeys very closely, with high probability, a deterministic equation $I( {t + 1} ) = n - ( {n - I( t )} )\exp ( - I( t )/n )$, $t\geqq 0$. A case when each knower passes the rumor to several members at every stage is also discussed.