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?

I was trying to verify Charlie's work; but I am only getting about 24 successes per million in my trials ... I would easily believe I have erred in my thoughts, as I have not found a real free moment to plow through Charlie's code. Here is my Mathematica code. S holds the number of susceptibles, II holds the rumor "hot" people, and R holds those who have been told and and have done their telling. I am going to go get some sleep, but am willing to walk through the code carefully if anyone cares :-)

(Way to crack on this one, Charlie! And I like Jer's use of statistics to gain faith in the simulation, though I need to think about what assumptions are being made about the random number generator.)

Module[{Success,S,II,R,INew,k,loopytimes=1000000},
Do[
   Success=49;II=1;R=0;
   While[II>0,
      INew=0;
      Do[
         If[Random[Integer,{1,S+II+R+INew-1}]£S,
            S=S-1;INew=INew+1,];
         If[Random[Integer,{1,S+II+R+INew-2}]£S,
            S=S-1;INew=INew+1,],{II}
      ];
      II=INew;R=R+II;
   ];
   If[S==0,Success=Success+1,],
   {k,1,loopytimes}];
Success]

Edited on December 6, 2004, 2:41 am

Edited on December 6, 2004, 3:23 am

Posted by owl on 2004-12-06 02:39:18