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?

The question mark after "solution" has to do with a caveat at the bottom of this post:

In the second part, the state at any given time can be specified by two numbers: the number of people who have already heard the rumor and passed it on, and the number of people who have heard the rumor but not yet passed it on.

We can develop a Markov chain connecting one step to the next of versions of this array, where each step represents one person's telling the rumor to two people.

During this step, part of the process is that the teller goes from being a new hearer (one who has heard the rumor but not yet told it) to being someone who has already heard and passed along the rumor.  The other part of the process is that zero, one or two people go from being people who have never heard the rumor to being one having newly heard it without having told it. If the teller in this phase tells someone who has heard the rumor but not yet told it, that is assumed to have no effect: that person, in his or her turn, will still go ahead, once only, to tell the rumor to two other people.

In the first generation, it is only Basil who has newly heard the rumor but has not yet told anyone, so there are 49 possible people to tell. From then on there are 48 possible people to tell (the base number).

The following program generates the probabilities for 50 generations of telling, the most it could take.  The desired probability at the end is that of 50 people already having heard the rumor and no one newly hearing it. Prints of intermediate probabilities are made for debugging purposes, to see the probabilities at each stage add up to 1. Results follow the program listing

DEFDBL A-Z

DIM howMany(50, 50)' first subscr is heard already, second is newly heard

howMany(0, 1) = 1
already = 0: new = 1

FOR generation = 1 TO 50
  REDIM howMany2(50, 50)
  FOR already = 0 TO 50
   FOR new = 0 TO 50 - already
    p1 = howMany(already, new)
    IF p1 > 0 THEN
      IF already = 0 AND new = 1 THEN bse = 49:  ELSE bse = 48
     
      fresh = 50 - already - new
      ' one of the "new"s is to tell two people
      ' both "already"s -> no change (except teller changes from new to already)
      ' both "new"s -> same (i.e., they still haven't told theirs yet)
      ' both "fresh" -> new increases by 2 (except for change due to teller)
      ' 1 "new" and one "fresh" -> new increases by 1 (except for that offset)
      ' 1 "new" and one "already" -> no change (except ...)
      ' 1 "fresh" and one "already" -> new increases by 1 (except...)
      pAddNone = p1 * ((bse - fresh) / bse) * ((bse - fresh - 1) / (bse - 1))
      pAddOne = p1 * 2 * (fresh / bse) * ((bse - fresh) / (bse - 1))
      pAddTwo = p1 * (fresh / bse) * ((fresh - 1) / (bse - 1))

      IF new > 0 THEN
        howMany2(already + 1, new - 1) = howMany2(already + 1, new - 1) + pAddNone
        howMany2(already + 1, new) = howMany2(already + 1, new) + pAddOne
        howMany2(already + 1, new + 1) = howMany2(already + 1, new + 1) + pAddTwo
      ELSE
        'no teller can be found -- all stay the same
        howMany2(already, new) = howMany2(already, new) + howMany(already, new)
      END IF
    END IF
   NEXT
  NEXT
  tt = 0
  FOR a = 0 TO 50
   FOR n = 0 TO 50
    howMany(a, n) = howMany2(a, n)
    IF howMany(a, n) THEN
     PRINT generation, a, n, howMany(a, n)
     tt = tt + howMany(a, n)
    END IF
   NEXT
  NEXT
  PRINT tt
  ' DO: LOOP UNTIL INKEY$ > ""
NEXT generation
PRINT howMany(50, 0), 1 / howMany(50, 0)
CLS
tt = 0: eVal = 0
FOR i = 0 TO 50
   LOCATE i MOD 26 + 1, (i \ 26) * 39 + 1
   PRINT USING "## #.###########"; i; howMany(i, 0);
   tt = tt + howMany(i, 0)
   eVal = eVal + i * howMany(i, 0)
NEXT
LOCATE 28, 1: PRINT tt, eVal, 1 / howMany(50, 0)

The results show the probability that any given number of people will have heard the rumor at the end of its travel:

 0 0.00000000000                       26 0.00020828003
 1 0.00000000000                       27 0.00037255493
 2 0.00000000000                       28 0.00066186917
 3 0.00000000000                       29 0.00116425226
 4 0.00000003275                       30 0.00202127733
 5 0.00000005008                       31 0.00345193061
 6 0.00000005610                       32 0.00577877183
 7 0.00000006046                       33 0.00944787483
 8 0.00000006700                       34 0.01502557265
 9 0.00000007785                       35 0.02314504196
10 0.00000009530                       36 0.03436939659
11 0.00000012281                       37 0.04894555088
12 0.00000016608                       38 0.06645873961
13 0.00000023475                       39 0.08547090310
14 0.00000034541                       40 0.10332535524
15 0.00000052684                       41 0.11637206935
16 0.00000082964                       42 0.12081654729
17 0.00000134371                       43 0.11413105880
18 0.00000223012                       44 0.09651869003
19 0.00000377952                       45 0.07154416589
20 0.00000651891                       46 0.04516970043
21 0.00001140611                       47 0.02330772538
22 0.00002018201                       48 0.00921107178
23 0.00003600210                       49 0.00247707960
24 0.00006455405                       50 0.00033983834
25 0.00011600047

 1             41.07268635093538           2942.575617956755
 
 

Where the bottom line shows a check of 1 that these probabilities add up to 1, then 41.07... is the expected number of people out of the 50, to know the rumor, and 2942.57..., representing the 1/2942.57... probability (= 0.0003398... from the table) that all 50 people know the rumor.  Note that at least 4 people must know it: Basil, the two people he told and the one other person besides each other that those people told, after which the 4th knower told Basil and the person that Basil told other than his own informant...
 
 Oh, Oh, there's a problem: if a newly informed person was told by two people before he had the chance to further spread the rumor, the program only counts one person (besides himself) as ineligible for receiving the news.  It probably should be anyone who had informed him.  But that raises the possibility of more than just 3 states a person might be in: in addition to uninformed, newly informed and already transmitted, there also are newly informed twice, newly informed thrice, etc., so that each generation of calculation would have to keep track of the probabilities of how many people are in each of these categories.

Posted by Charlie on 2004-12-03 17:09:43