Micromass' big probability challenge

[Samy_A]

No, you can't tell them to the same person who told you. However, if person A told B and C, then it is possibly for B to tell C. But B cannot tell A. Thank you for noticing this.

Is this true forever, or only for the next generation?

I mean: say A tells the secret to B. After a few generations, the secret is again told to B. Can he now tell it to A?

 

[Redbelly98]

Is this true forever, or only for the next generation?

I mean: say A tells the secret to B. After a few generations, the secret is again told to B. Can he now tell it to A?

Related: After a few generations, the secret is again told to A. Can A tell B again?

Common sense would say "no" to both questions, since A & B both realize that the other has heard the rumor already.

 

[micromass]

I mean: say A tells the secret to B. After a few generations, the secret is again told to B. Can he now tell it to A?

Yes that is possible

 

[micromass]

Related: After a few generations, the secret is again told to A. Can A tell B again?

Yes, otherwise things would be intractable.

 

[mfb]

The rumor spreading rules get complicated.Proof for problem 7: As Fightfish noted already, the number of ways we can get the votes in follows a law similar to the binomial coefficients. If x is the number of votes for Trump and y is the number of votes for Hillary, then
$$f(x,y) = \begin{cases} 1 \qquad \mathrm{if}\qquad y = 0 \\ 0 \qquad \mathrm{if}\qquad x = y \\ f(x-1,y) + f(x,y-1) \qquad \mathrm{otherwise} \end{cases}$$

We can show that $$f(x,y) = \frac{(x-y)(x+y-1)!}{x!y!}$$ is the solution to this by (two-dimensional) induction. It is clearly true for x=y (where the first expression in the numerator gets zero) and for y=0 (where we get x!/x!=1).

Induction step:
$$\begin{align*}
f(x-1,y) + f(x,y-1) &= \frac{(x-y-1)(x+y-2)!}{(x-1)!y!} + \frac{(x-y+1)(x+y-2)!}{x!(y-1)!} \\
&= \frac{x(x-y-1)(x+y-2)!}{x!y!} + \frac{y(x-y+1)(x+y-2)!}{x!y!}\\
&= \frac{(x+y-2)!}{x!y!} \left( (x+y)(x-y)-(x-y) \right)\\
&= \frac{(x+y-2)!}{x!y!} (x-y)(x+y-1)\\
&= \frac{(x-y)(x+y-1)!}{x!y!}\\
&= f(x,y) \end{align*}$$

Finally, we have to divide f(x,y) by the total number of ways the votes can go up, (x+y choose x):

$$P = \frac{(x-y)(x+y-1)!}{x!y!} \cdot \frac{x!y!}{(x+y)!} = \frac{x-y}{x+y}$$

 

[Isaac0427]

In a town of n+1n+1n+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 rrr will not contain the person who started the rumor. Find the median of this distribution assuming nnn large.

Well, I can answer part of the problem. In generation r, $2^r$ people will be told the rumor. The probability of anyone person being told the rumor would be the people being told the rumor divided by the people in the town, and thus $\frac{2^r}{n+1}$. Therefore, the probability of that person not being told the rumor is $1-\frac{2^r}{n+1}$ (I think I'm doing this right). I am assuming that somebody can't be told the rumor more than once in one generation, so $2^r\leq n+1$. I'm not quite sure what you mean by the median of the distribution.

 

[micromass]

In generation r, $2^r$ people will be told the rumor.

I am not convinced of this.

 

[Isaac0427]

I am not convinced of this.

In generation 1, 2 people will be told. Then, each of those people will tell 2 people. 4 people will be told (gen 2). And then those will tell 2 people. 8 people will be told (gen 3). This pattern has a constant multiplier, and thus an exponential function must be used. The multiplier is 2, and is therefore is the base of the exponent. We can check this with results that we know; $2^1=2$, $2^2=4$ and $2^3=8$.

 

[Redbelly98]

In generation 1, 2 people will be told. Then, each of those people will tell 2 people. 4 people will be told (gen 2).

But if those people tell the same 2 people, then only 2 people, not 4, will be told in gen 2.

Or, those 2 people might tell 3 people in total, if 1 person gets told by both of the "tellers" in gen 2.

 

[Isaac0427]

But if those people tell the same 2 people, then only 2 people, not 4, will be told in gen 2.

Or, those 2 people might tell 3 people in total, if 1 person gets told by both of the "tellers" in gen 2.

I said in my first post that I was assuming that somebody couldn't be told more than once in the same generation, because

each person tells a rumor to two people at random without regard to the past development.

And I took that to assume that they were aware of present development (as @micromass specifically talked about past development)

 

[andrewkirk]

I said in my first post that I was assuming that somebody couldn't be told more than once in the same generation, because

And I took that to assume that they were aware of present development (as @micromass specifically talked about past development)

Micromass makes clear in post 70 that it is possible for somebody to be told the rumour more than once in the same generation, by two different people.

One quasi-realistic implementation of this would be if the communication were by private, one-way medium such as email or text. That way there is no opportunity for Hermann to stop Lakshmi as she verbally tells him the rumour by saying 'Stop, Arjun has just told me that'. Lakshmi will forward the email to Hermann anyway because she doesn't know Arjun has already forwarded it to Hermann. But Lakshmi would not forward the email to Hermann if she has only just received it from him in the same generation (say, on the same day).

The fact that Lakshmi can forward the email to Hermann if he forwarded it to her in a previous generation can be explained by the supposition that people have short memories.

I was trying to think this one through yesterday and the questions raised in the above posts came up. With the clarifications, the process of determining the size of each generation really does seem quite complicated. No doubt there is a clever way to cut through, but what is it?

 

[Isaac0427]

Micromass makes clear in post 70 that it is possible for somebody to be told the rumour more than once in the same generation, by two different people.

That's not what I got out of post #70.

 

[micromass]

That's not what I got out of post #70.

It's what I meant anyway. Sorry if that was unclear.

 

[andrewkirk]

Can I make a further request for clarification on this rumour question. The last sentence asks for the median of the distribution, but it does not say what the random variable is of which the median is to be calculated. I can think of a few different possibilities. My best guess is that it's the median of $X_n$, as a function of $n$, where $X_n$ is the number of people who are told the rumour in generation $n$.

I'm nowhere near up to that part of the question, but thought it might be best to plan ahead.

 

[micromass]

Can I make a further request for clarification on this rumour question. The last sentence asks for the median of the distribution, but it does not say what the random variable is of which the median is to be calculated. I can think of a few different possibilities. My best guess is that it's the median of $X_n$, as a function of $n$, where $X_n$ is the number of people who are told the rumour in generation $n$.

I'm nowhere near up to that part of the question, but thought it might be best to plan ahead.

For every $r$, you have the probability $P(r)$ that generation $r$ will contain the original starter. I want the median of those $P(r)$.

 

[andrewkirk]

I'm afraid I don't follow. $P(r)$ is a deterministic infinite sequence, not a random variable (assuming we are referring to unconditional probabilities, which I'm pretty confident we are). What does it mean to take the median of a deterministic infinite sequence?

 

[micromass]

I'm afraid I don't follow. $P(r)$ is a deterministic infinite sequence, not a random variable (assuming we are referring to unconditional probabilities, which I'm pretty confident we are). What does it mean to take the median of a deterministic infinite sequence?

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$.

 

[Samy_A]

Deleted:

Note to myself: read the question before answering.

 

[Samy_A]

Second shot at 5:

I'm not sure about terminology. Here I define generation m as the people who are told the rumor during the m'th iteration of the process.

EDIT: it wasn't clear in the OP, but from post #87, it appears that generation m consists of all the people who have been told the rumor up to the m'th iteration.

So "solution" deleted.

 

[Samy_A]

Never mind, one of those days.

 

[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). 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: [COLOR=#black]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. [/COLOR]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.