Waldo is having a party and has 50 guests, among whom is his brother Basil.

Basil starts a rumor about Waldo; a person hearing this rumor for the first time will then tell another person chosen uniformly at random the rumor, with the exceptions that no one will tell the rumor to Waldo or to the person they heard it from.

If a person who already knows the rumor hears it again, they will not tell it again.

What's the probability that everyone, except Waldo, will hear the rumor before it stops propagating?

What if each person told two people chosen uniformly at random?

(In reply to Stat. analysis of Charlie's part 2 by Jer)

I went back to the methodology of using the built-in random number generator to find its cycle length with a particular random number seed.  In the retry case, I found that the 48th and all subsequent trial results (number of people knowing the rumor when the rumor stopped propagating) repeated in a cycle of 194,068. 

So, other than the independent first 47 trials, the whole of the million trials was a mere repetition of sets of 194,068 trials.  At about 1/5 the purported size of the sample, the size of the 95% confidence interval increases by a factor of about 2.25--large enough to encompass the theoretic expected value.

Posted by Charlie on 2004-12-05 01:23:58