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 the first part, Basil is starting a single thread: Basil tells A, who tells B, who tells C, etc.  At any point if the next person had already heard the rumor, the thread stops. This becomes increasingly likely as more and more people have heard the story.

Basil can tell any of 49 people, none of whom have heard the story yet.  Call the person he chooses A.  A has 48 people to choose from, also none of whom had heard the rumor before, so the probability of continuing from there is 48/48. So A chooses someone to be B. From here on there's a choice of 48 people to tell--any of the other guests other than the person who told him. But when B has to pass it on, there are only 47 who haven't heard the story.  At C's turn there are only 46, etc.

So the probability of making it all the way to the end is 47/48 * 46/48 * 45/48 * ... * 1/48.  That's 47!/48^47 or about 2.479*10^-20, or 1 chance in 4*10^19.  It's very unlikely that everyone will hear the rumor before it stops propagating.

Posted by Charlie on 2004-12-03 14:41:52