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 AZ
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 20041203 17:09:43 