Challenge Micromass' big probability challenge

[mfb]

Every $P(r)$ is a probability. Namely the probability that generation $1$ and generation $2$ and ... and generation $r$ do not contain the original starter. Basically, I want to know when this probability is $1/2$.

That looks like an odd definition of median. While it does not happen here, in general P(r) could go down. Do we have multiple medians then?

If generation r has N(r) "active" people, then we have 2 N mails sent to nearly random people, neglecting that a 2N out of N(n+1) specific combinations are not possible (don't tell the rumor back, and don't tell it yourself) and that no one sents two mails to the same person (a very unrealistic assumption)[/size]. That gives a probability of (n/(n+1))^(2N) for everyone to not get the rumor, or E(N(r+1))=(n+1)(1-(n/(n+1))^(2N)) people hearing the rumor on average.

Initially, the growth is nearly exponential, but then levels off as more and more people hear the rumor twice within a generation. In the long run and for large n, on average about 79.68% of the population are active, which is given by the solution to E(N(r+1))=N(r), the analytic solution needs the product log function.

Without a proof, N(r) > (n+1)/2 first happens roughly at generation r=ld(n+1)+1.1 rounded up, if N(1)=1 is the first person and first generation.

 

[Megaquark]

In number 5, can you tell yourself the rumor?...Can a person look in the mirror and say, "Hey, want to hear some juicy gossip!?"

 

[Samy_A]

So, last last try at 5.

For fixed n, let $P(m)$ be the probability that the m'th generation still doesn't include the starter.

We have $P(1)=1, P(2)=1$.

For m>2:
For starter not to be in generation m+1, he has to satisfy two conditions: not be in generation m (probability P(m)), and not being selected for generation m+1.
There are $\binom{n-1}{2}= (n-1)(n-2)/2$ ways for selecting the people to tell the rumor to.
There are $\binom{n-2}{2}=(n-2)(n-3)/2$ ways for selecting the people to tell the rumor to, not including the starter.
So for one person not to select the starter, the probability is $(n-3)/(n-1)$.
Since there are two people telling the rumor in each generation, the probabilty that starter will not be selected by either is $((n-3)/(n-1))^2$.

This gives the recurrence relation $P(m+1)= P(m)*((n-3)/(n-1))^2$.
Since $P(2)=1$, we get $P(m)=(\frac{n-3}{n-1})^{2(m-2)}$ for m>2.

When will P(m) reach 1/2?

Let's solve $(\frac{n-3}{n-1})^{2(m-2)} =1/2$.
Notice that $\frac{n-3}{n-1}=1-\frac{2}{n-1}$.

Taking logarithm, we get $2(m-2)\log (1-2/(n-1))=\log(1/2)= -\log(2)$.
If n is large, $\log(1 -2/(n-1)) \approx -2/(n-1)$.
So we get $-4(m-2)/(n-1) \approx -\log(2)$.
Solving for m, we get $m \approx 2+\frac{1}{4}(n-1)\log(2)$.

 

[CynicusRex]

5) I'm probably wrong but I wanted to think about it. The first generation can not contain the instigator because he can not tell himself the rumor. Beyond the first generation, the 2 distinct persons told, each have $\left(\frac{\left(n+1\right)-3}{\left(n+1\right)-2}\right)$ ($\frac{8}{9}$ if there are 11 people) choices for the first person if they do not 'want' to pick the instigator and themselves and $\left(\frac{\left(n+1\right)-4}{\left(n+1\right)-3}\right)$ ($\frac{7}{8}$ if there are 11 people) choices for the second distinct person. Thus far the probability of the instigator not being picked is $\left(\frac{\left(n+1\right)-3}{\left(n+1\right)-2}\right)^2$ * $\left(\frac{\left(n+1\right)-4}{\left(n+1\right)-3}\right)^2$ =$\left(\frac{\left(n+1\right)-4}{\left(n+1\right)-2}\right)^2$. The third generation separately doubles the exponent because the amount of people picked is doubled. However, we shouldn't forget to multiply the chances of the instigator not being picked for each past generation. For example, the chance of instigator not being told after 4 generations is: $\left(\frac{n-3}{n-1}\right)^{2^{\left(2-1\right)}} * \left(\frac{n-3}{n-1}\right)^{2^{\left(3-1\right)}} * \left(\frac{n-3}{n-1}\right)^{2^{\left(4-1\right)}}$

P(instigator not told after r generations) = $\prod_{2}^{r}\left(\frac{n-3}{n-1}\right)^{2^{\left(r-1\right)}}$, where r ≠ 1

As an example I used population of n+1 = 11 people.
Probability of instigator not being picked in generation r separately:
r=1: $\left(\frac{8}{9}\frac{7}{8}\right)^{0}$ (exponent: $2^{\left(1-1\right)}$ = 1) (Probability of not choosing the instigator in generation one is 1)
r=2: $\left(\frac{8}{9}\frac{7}{8}\right)^{2}$ (exponent: $2^{\left(2-1\right)}$ = 2)
r=3: $\left(\frac{8}{9}\frac{7}{8}\right)^{4}$ (exponent: $2^{\left(3-1\right)}$ = 4)
r=4: $\left(\frac{8}{9}\frac{7}{8}\right)^{8}$ (exponent: $2^{\left(4-1\right)}$ = 8)

Probability of instigator not being picked after generation r:
Multiply the probabilities above until you've reached the generation. With the use of this example I then replaced the numbers with 11=n+1 accordingly.

I think the median has to be calculated with the log equalling 1/2 or something. But haven't thought about it yet.

As for sources; I used Quora to know if there was a notation like sigma, but for multiplication. Yes, I'm new to math beyond high school.

 

[mfb]

Since there are two people telling the rumor in each generation

Why? If the 2 people of generation 2 both tell the rumor to different people, we then have 4 people telling the rumor. 3 is also an option.

The third generation separately doubles the exponent because the amount of people picked is doubled.

It does not have to be doubled.

 

[Samy_A]

Why? If the 2 people of generation 2 both tell the rumor to different people, we then have 4 people telling the rumor.

Of course. As I said, one of those days ...

It could be 2, 3 or 4 people.

 

[CynicusRex]

Why? If the 2 people of generation 2 both tell the rumor to different people, we then have 4 people telling the rumor. 3 is also an option.It does not have to be doubled.

It doesn't, but the formula does, at least I think so.

 

[mfb]

It doesn't, but the formula does, at least I think so.

Well if the formula assumes something that is not true, the formula does not work.

 

[mpresic]

The Birthday Cereal problem reminds me of the m-m/s problem . In the 1990's I learned M&M were thinking of coming out in 23 colors. I wondered how many M&M would I have to buy in order to get one of each color assuming the colors are equally distributed. I solved it in the manner of Profusely Quarky. I believe the answer was 82 (or maybe it was 85, I do not remember).

 

[ProfuselyQuarky]

The Birthday Cereal problem

I think you're mixing up problems...

EDIT: Yeeesss, I'm post #100 !

 

[mpresic]

I did not mix the problems up but please take away the "birthday" It is just the Cereal problem.

 

[mpresic]

I did not mix the problems up but should not have added the term "birthday". The M&M problem is cereal problem with 23 mms in place of 20 toys. Incidently the method of solving the problem, can be found in an interesting book, " Gambling Ramblings " by Peter Griffin. Griffin examines and addresses many incident results in everyday probability.

 

[CynicusRex]

Well if the formula assumes something that is not true, the formula does not work.

Woops. I stand corrected. Went for a run in the rain and see my mistake now.
Spoiler: Each person must pick two distinct other persons. But others can pick the same persons. Also the more people who can pick, the less people you can pick from. Double woops. Probably some other woopses incoming. Spoiler end.

 

[CrackerMcGinger]

Who wants to bet that this thread will be on the "Interesting Discussions for the Week" list?

 

[CynicusRex]

A bet? Oh dear my, another probability incoming.

 

[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"