Micromass' big probability challenge

[rjbeery]

In a town of n+1 inhabitants. A person tells a rumor to two distinct numbers, the "first generation". These repeat the performance and generally, each person tells a rumor to two people at random without regard to the past development. Find the probability that the generation r will not contain the person who started the rumor. Find the median of this distribution assuming n large.

OK first of all I apologize for not having my LATEX skills in order...anyway for #5...each generation r exposes 2^r inhabitants to the rumor out of a pool of (n+1) inhabitants. That means that ((n+1)-2^r) inhabitants are not exposed to the rumor during the rth generation and the odds of being in this pool of unexposed inhabitants is:

((n+1)-2^r)/(n+1)

The second question is confusing to me. You want the median of the distribution ending when at the first generation of the rumor-starter getting the rumor back, or the median of distribution of the entire population?

 

[mfb]

@rjbeery: that value gets negative for large r.

People can tell the rumor to people who know it already, so the 2^r assumption does not work. This has been discussed in the thread already.

 

[rjbeery]

@rjbeery: that value gets negative for large r.

People can tell the rumor to people who know it already, so the 2^r assumption does not work. This has been discussed in the thread already.

My apologies. Someone posted my exact thought process and was corrected in the same manner...

Anyway let's try again...the number of people a person could tell the rumor to (excluding "Patient Zero", heh) is (n-1)(n-2)/2 out of a total of n(n-1)/2 possibilities. This gives (n-2)/n chance each time the rumor is spread that Patient Zero is not included. Now we need to know how many times the rumor is spread to a new person as a function of r. This step is extraordinarily complex! Do you already have the answer to this Micromass?

1st generation Patient Zero spreads the rumor to A and B

2nd generation:
A spreads the rumor to two distinct people. We need to analyze whether or not B's choices overlap with A's.
B picks those same two people 2/n(n-1) times...if B and A were choosing from the same pool. However A can spread the rumor to B but B cannot spread the rumor to himself. Therefore B picks the same two people 2/n(n-1) given that B was not chosen by A, so we must multiply that by (n-2)/n giving us

2(n-2)/(n^2(n-1))

Now we need to analyze the odds of B overlapping with a single choice of A and the odds of no overlap at all. I'm posting my progress now because I'm out of time currently but I would love to see this solution...

 

[CynicusRex]

OP please don't reveal the solution if it's not found yet.

 

[TeethWhitener]

I'm having a really hard time understanding #5. Let's say we have 4 people: A, B, C, and D. A starts the rumor by telling B and C (generation 1). By the criteria @micromass has given (someone can't immediately (?? see below) tell the rumor to the person who told them), B has to tell C and D, and C has to tell B and D. So generation 2 is B, C and D. But D has been told by B and C in the immediately preceding generation, and therefore can only tell one person (namely A). So does D only tell one person? Or does D abstain from telling anyone? Do they tell the maximum number of people they can?

The other question is: if A tells B, B tells C, etc, and the rumor comes back to B after n>1 generations, can B now tell A? Or is B forever forbidden from telling the person they heard the rumor from in the first place?

 

[Megaquark]

So thinking about #5 a little bit more... In the first generation the probability the rumor starter will be told is zero, since he can't tell himself. Since he has to choose 2 distinct people, let's say he told Alice and Bob, the probability he'll be told by Alice is p=(1/n)+[1/(n-1)]. The probability he'll be told by Bob is the same. The total probability that he'll be told is 2p...so the probability he won't be told is 1-2p.
Now things get kind of sticky in the third generation. There are three distinct cases.

1. Alice and Bob told the same two people: Chad and Dorothy
2. Alice and Bob told three distinct people in total: Chad, Dorothy, and Eggbert
3. Alice and Bob told four distinct people in total: Chad, Dorothy, Eggbert, and Felicity

For case 1, the probability the rumor starter won't be told is still 1-2p
For case 2, it's 1-3p
For case 3, it's 1-4p

Things get even more complicated for generation 4, since each of the previous cases branch. Case 1 from above could branch into three scenarios, each with the aforementioned probabilities that the rumor starter won't be told. Case 2 would branch into 5 different scenarios with probabilities he won't be told of 1-2p, 1-3p, 1-4p, 1-5p, and 1-6p. Case 3 could branch into seven different scenarios...then in generation 5 each new scenario further branches.

This problem gets complicated fast, since the probability that the rumor starter won't be told seems to be case dependent and the number of cases increases exponentially in each generation. Does this line of reasoning seem correct, or am I missing something obvious that would simplify the problem greatly?

 

[mfb]

Since he has to choose 2 distinct people, let's say he told Alice and Bob, the probability he'll be told by Alice is p=(1/n)+[1/(n-1)]. The probability he'll be told by Bob is the same.

It is zero, Alice and Bob can't directly tell the rumor back to the person they got it from.

Alice can tell it to Bob, however, and Bob also to Alice, which generates another two cases (different in the next generation due to more correlated forbidden rumor directions).
A tells B and C, B tells A and C
A tells B and C, B tells A and D

 

[Megaquark]

It is zero, Alice and Bob can't directly tell the rumor back to the person they got it from.

Alice can tell it to Bob, however, and Bob also to Alice, which generates another two cases (different in the next generation due to more correlated forbidden rumor directions).
A tells B and C, B tells A and C
A tells B and C, B tells A and D

Just what this problem needs, more complexity. I doubt there's a simple solution to this because of all the cases and branching. It one of those "If z happens in generation x, then this range of probabilities occurs in generation x+1...but if z doesn't, then this range of probabilities occurs instead." type situations.

 

[CynicusRex]

Thought about it again in my study break, but it seems I'll have to take my time after the exams. I think I got the reasoning in my head though.

Btw, these challenges should happen regularly. They're awesome!

 

[micromass]

Btw, these challenges should happen regularly. They're awesome!

I am planning for them regularly! If you or anybody else has suggestions, please do PM me.

 

[micromass]

OK guys, I'm terribly sorry. For $5$, a person can also tell the rumor to the person who just told him the rumor (it seems the town is filled with dementia patients!). The problem should now be relatively easy.

I guess the original problem is the grand prize then. Sadly, I don't know the solution to that problem.

 

[rjbeery]

"Relatively easy"