All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Rumor Mill (Posted on 2004-12-03)
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?

 No Solution Yet Submitted by SilverKnight Rating: 4.0000 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Part 2 solution? | Comment 3 of 13 |

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
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
ELSE
'no teller can be found -- all stay the same
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.0231450419610 0.00000009530                       36 0.0343693965911 0.00000012281                       37 0.0489455508812 0.00000016608                       38 0.0664587396113 0.00000023475                       39 0.0854709031014 0.00000034541                       40 0.1033253552415 0.00000052684                       41 0.1163720693516 0.00000082964                       42 0.1208165472917 0.00000134371                       43 0.1141310588018 0.00000223012                       44 0.0965186900319 0.00000377952                       45 0.0715441658920 0.00000651891                       46 0.0451697004321 0.00001140611                       47 0.0233077253822 0.00002018201                       48 0.0092110717823 0.00003600210                       49 0.0024770796024 0.00006455405                       50 0.0003398383425 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

 Search: Search body:
Forums (0)