On Spreading a Rumor

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ₙ the random number of stages before everybody is informed. How large is Sₙ typically? Frieze and Grimmet, who introduced this problem, proved that, in probability, Sₙ / (₂ n + n) 1. In this paper we show that, in fact, Sₙ = ₂ n + 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) ) (- I (t) /n), t 0. A case when each knower passes the rumor to several members at every stage is also discussed.