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.)
 Better Simulation for Part 2 | Comment 5 of 13 |
(In reply to Stat. analysis of Charlie's part 2 by Jer)

The problem with the simulation was that it used QuickBasic's built-in random number generator, which starts repeating every so often.   The program calls it millions of times, so it is cycling over the random numbers more than once, and it apparently was repeating a smaller number of trials several times, rather than a million independent trials.

So I modified the program to use binary random numbers downloaded from www.random.org, and, out of one million trials, 343 trials resulted in all 50 guests knowing the rumor.  That's a probability of .000343, or 1 in 2915.  The 343 is quite close to the expected 339.8....

The revised program is

defdbl a-z
FOR trial = 1 TO 1000000
REDIM person(50)
REDIM who(50)
person(1) = 1: p1Ct = 1: p2Ct = 0
DO
FOR i = 1 TO 50
IF person(i) = 1 THEN
DO
r = rand50(1)
LOOP UNTIL r <> i AND r <> who(i)
DO
s = rand50(1)
LOOP UNTIL s <> i AND s <> who(i) AND s <> r
IF person(r) = 0 THEN
person(r) = 1
p1Ct = p1Ct + 1
who(r) = i
END IF
IF person(s) = 0 THEN
person(s) = 1
p1Ct = p1Ct + 1
who(s) = i
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 > 2 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 20:53:37

 Search: Search body:
Forums (0)