Author |
Topic: Rumor Spreading (Read 3587 times) |
|
Brett Danaher
Guest
|
You are part of a group of 10 people. All 10 people are in their respective and SEPERATE houses, waiting by the phone. You have a rumor. You pick up the phone to start spreading it and you call someone, beginning a chain such that the nth person to be called will then call and tell it to one other person, except that he will not call himself nor would he (naturally) call the person who just told him (assume, for simplicity, that he WOULD call someone who has told him the rumor before, as long as it was not the person who just called him).
So you make the first call. What is the probability that the 5th call is to you?
Now, can you rework the problem such that a person will NEVER call anyone who has ever told him the rumor before (more realistic, figuring they already know the rumor so why call)? Finally, can you generalize the formula to calculate the probability that the n-th call is to you?
|
| « Last Edit: Oct 12th, 2002, 11:22pm by william wu » |
 IP Logged |
|
|
|
S. Owen
Full Member
Gender: 
Posts: 221
|
 |
Re: New Problem - Rumor Spreading
« Reply #1 on: Sep 24th, 2002, 12:17pm » |
 Quote  Modify
|
I'll bite on the first, easy question.
You call someone, they call a third person: these are the first two calls. There is a 1/8 probability that the third call is to you, and if that's the case, you will make the fourth call to someone, and the next, fifth call will definitely not be right back to you.
There is a 7/8 chance that the third call is not to you. Similarly for the fourth call, there is a 1/8 chance that you get it, in which case you can't receive the fifth call because you're making the call!
There is a 7/8 chance that the fourth call is not to you, and then a 1/8 chance that the fifth call is. So I say the probability is (7/8)*(7/8)*(1/8) = 49/512 = 0.0957.
More on the rest as I work it out...
|
| « Last Edit: Sep 24th, 2002, 12:19pm by S. Owen » |
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: New Problem - Rumor Spreading
« Reply #2 on: Sep 24th, 2002, 12:28pm » |
Quote Modify
|
Oh, I guess the second question isn't much different... the argument for the first three calls remains the same.
The fourth call could be to you (1/8 chance), or to the fellow that you called initially (1/8 chance). Either way, you won't get the next, fifth call.
Otherwise, the fourth call goes to someone who will call you next with probability 1/8. So I think this answer is (7/8)*(3/4)*(1/8) = 21/256 = 0.082.
|
| « Last Edit: Sep 24th, 2002, 12:28pm by S. Owen » |
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New Problem - Rumor Spreading
« Reply #3 on: Sep 24th, 2002, 12:36pm » |
Quote Modify
|
This problem is a little messy (to say the least). The answer I get is 72/83 for the simple probability on the fifth call. I guess S. Owen beat me to the punch here...
If a person never calls anyone who has called him before, then the problem gets a lot hairier. Eventually, all people will settle down into a series of cycles, where they have a list of people they called (who, therefore, will never call them), and a list of people who called them (who, therefore, they will never call). The probabilities at this point will be Markovian, since you can only repeat what has already been done. The structure of the Markov matrix, however, will be rather random, and the probabilities will be derived from it.
What would be even more realistic would be to say that a person will never call anyone that they have talked to before (ie. who has called them, or who they have called). In this case, the rumor would stop spreading at some point.
When you say generalize, which scenario are you referring to?
|
| « Last Edit: Sep 24th, 2002, 12:38pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
Brett Danaher
Guest
|
|
Re: New Problem - Rumor Spreading
« Reply #4 on: Sep 25th, 2002, 6:36am » |
Quote Modify
 Remove
|
First, I agree, that the more complex version of the riddle should read that a person will not call anyone who has called him, nor anyone whom he has called. Good catch.
I still like the question of "what is the probability that the nth call is to you" but I don't have any idea if that's possible to calculate. An easier question might be "If this is a group of n people who know each other (in other words, there are n people waiting by the phone who all have each others phone numbers, and no others), what is the largest possible number of calls until we are sure that EVERYONE has heard the rumor?" Again, assume that a person will never call anyone who has called and told him the riddle, nor anyone he has already called.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: New Problem - Rumor Spreading
« Reply #5 on: Sep 25th, 2002, 9:41am » |
Quote Modify
|
Brett,
Scenario: a person will not call anyone who has called him before, or who he has called before.
To find out the largest number of calls that can be made before the last person finds out the rumour, compute the largest number of calls that you could have with only 9 people. This is equal to choose(9,2) (note that this formula only works for an ODD number of people!). After that, the tenth person must be called.
The probability for the nth person isn't terribly difficult to find for the original question. For the more realistic scenario, it's much harder. After the fifth call, the number of configurations of people just skyrockets, because the probability of you getting called depends (inversely) on the probability of the people you called getting called, which depends on how many times they have gotten called. There may be a simple formula, but my primitive spreadsheet techniques can't cope with the large number of possibilities.
It's also interesting to note that when the calls stop, it is quite likely that not all the call possibilities have been exhausted, meaning that the number of calls made before calling stops will be variable.
|
| « Last Edit: Sep 25th, 2002, 9:42am by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print