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 More refined simulation for part 2 by Charlie)

I scrambled the bits and ran another simulation of 1,000,000 trials, and this time had 364 occurrences of all 50 people knowing the rumor.  We might as well add that to the 357 from the previous million, making 721 / 2,000,000 = .0003605 or 1/2774, but it might be between 1/2700 and 1/2900 without being too surprising statistically.

Posted by Charlie on 2004-12-04 03:16:52