On Spreading a Rumor 论文

详细信息

发表期刊/会议

SIAM Journal on Applied Mathematics

发表日期

1987-02-01

发表年份

1987

摘要

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.