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?

Both the analytic solution and the previous simulation assumed that each person would choose 2 from 48 people to tell the rumor--that is, anyone except himself and one of the people who told it to him.  I noted before, that this does not take into consideration that one person might be told "simultaneously" (i.e., close enoug in time not to have gotten around to telling another two) by more than one person, and therefore avoid telling any of those who told him, reducing the list of those eligible to be told.

I modified the program to keep track of all those who told any given new teller, and avoid telling any of those people.  Out of one million trials, all 50 people received the news on 357 occasions.  This is somewhat higher than the previously found probability (expected value actually), but I don't think decisively so outside statistical variation.

The new program is:

DECLARE FUNCTION rand50# (x#)
DEFDBL A-Z
RANDOMIZE TIMER
FOR trial = 1 TO 1000000
  REDIM person(50)
  REDIM who(50, 10)
  REDIM hitCt(50)
  person(1) = 1: p1Ct = 1: p2Ct = 0: hitCt(1) = 0
  DO
    FOR i = 1 TO 50
      IF person(i) = 1 THEN
       DO
        r = rand50(1)
        h = 0
        FOR j = 0 TO hitCt(r)
          IF who(i, j) = r THEN h = 1: EXIT FOR
        NEXT
       LOOP UNTIL r <> i AND h = 0
       DO
        s = rand50(1)
        h = 0
        FOR j = 0 TO hitCt(s)
          IF who(i, j) = s THEN h = 1: EXIT FOR
        NEXT
       LOOP UNTIL s <> i AND h = 0 AND s <> r
       IF person(r) = 0 THEN
         person(r) = 1
         p1Ct = p1Ct + 1
         who(r, 0) = i
         hitCt(r) = 1
       ELSEIF person(r) = 1 THEN
         who(r, hitCt(r)) = i
         hitCt(r) = hitCt(r) + 1
       END IF
       IF person(s) = 0 THEN
         person(s) = 1
         p1Ct = p1Ct + 1
         who(s, 0) = i
         hitCt(s) = 1
       ELSEIF person(s) = 1 THEN
         who(s, hitCt(s)) = i
         hitCt(s) = hitCt(s) + 1
       END IF
       person(i) = 2
       p2Ct = p2Ct + 1
       p1Ct = p1Ct - 1
      END IF
    NEXT
  LOOP UNTIL p1Ct = 0
  IF p2Ct = 50 THEN suc = suc + 1
  tot = tot + 1
  IF trial MOD 100 = 0 THEN
   PRINT suc, tot
  END IF
NEXT

FUNCTION rand50 (x)
 STATIC started
 STATIC number
 STATIC pulled
 IF started = 0 THEN OPEN "160megs.bin" FOR BINARY AS #1: started = 1: pulled = 3
 IF pulled > 3 THEN
   s$ = "   "
   GET #1, , s$
   IF EOF(1) THEN STOP
   number = ASC(s$) + ASC(MID$(s$, 2)) * 256# + ASC(MID$(s$, 3)) * 256# * 256#
   pulled = 0
 END IF
 r = number MOD 50 + 1
 number = number \ 50
 pulled = pulled + 1
 rand50 = r
END FUNCTION

 

 

Posted by Charlie on 2004-12-03 22:05:23