Challenge Micromass' big probability challenge

[Charles Link]

I would like to try #9. For the probability that the first person has a Jan 1 birthday and all others different, that is $p=(1/365)(364/365)^{999}$. There are 1000 different people who can have this Jan.1 birthday, so that probability of one and only one Jan.1 birthday is $P=(1000/365)(364/365)^{999}$. (Not going to try to account for leap years.) 365 days, each of which has a similar possibility of one and only one birthday, so that mean number (expected number of people with no one matching their birthday) will be $\mu=365 P=1000(364/365)^{999}$ . My arithmetic with a log table (I don't have a calculator handy) is $\mu=64$. I didn't account either for any cross correlations, but these should be insignificant.

 

[PeroK]

On problem 6, prompted by MM's observation, I see that my summand (54-k) is incorrect. Since the previous ace was in position k, there are only 52-(k+1) =51-k remaining valid places for the last ace.

The calc using that summand instead gives N=211,876.
That would give the probabiity as $\frac{24N}{52\cdot 51\cdot 50\cdot 49}$ which is 78%.

There's a neat solution to this:

Take the $48$ other cards and place them in a row with a space between each (and a space at either end), so there are $49$ spaces. Now, each arrangement of the cards where no two Aces are adjacent corresponds to an arrangment of the cards where each of the $4$ aces occupies one of the $49$ spaces.

Hence, there are $\binom{49}{4}$ valid arrangements, out of the total of $\binom{52}{4}$ possible arrangements for the 52 cards.

This simply generalises. If there are $n$ cards and $k$ aces, then the probability that no two aces are adjacent is:

$\binom{n-k+1}{k} / \binom{n}{k}$

 

[PeroK]

For number 9. Note: solution ignores leap years.

Imagine you conduct this experiment many times with $999$ other people. How often do you find yourself without a birthday partner?

$p = (\frac{364}{365})^{999} = 0.0645$

This is the same for everyone else. So, everyone is without a birthday partner with this probability. Overall, therefore, the expected number in any $1000$ is:

$1000p = 64.5$

Just saw @Charles Link beat me to it!

So, taking 1 leap year every 4 years, we have 1461 days every 4 years:

$p_x = 1/1461$ is the probability of being born on 29th Feb. And

$p_y = 1460/1461$ is the probability otherwise.

For those born on 29th Feb, the probability no one shares their birthday is:

$q_x = (1460/1461)^{999}$

For those not born on 29th Feb:

$q_y = (1457/1461)^{999}$

This gives a revised calculation:

$p = p_xq_x + p_yq_y = 0.0649$

Hence the expected number in 1000 is $64.9$.

 

[thephystudent]

On problem 8, I see from a brute force calc that my answer appears to be three times what I think it should be. It looks like I should have multiplied R by 2 rather than by 6, but I can't immediately see why. I must have done something silly in working out the different orders the lengths could be and how that affects the probability. I'll think about that later.

But I have a method that avoids assuming an order, in which the probability of an obtuse triangle is as follows:

$$\int_0^{\frac12}\int_{\frac12}^{x+\frac12} \chi_A\ dy\ dx$$

the integration limits collectively ensure that no side is longer than 1/2, and hence that a triangle can be formed. The indicator function $\chi_A$ requires the triangle to be obtuse.

The answer I get from a numerical integration on that is about 2.9%. That's the same as for my brute force calc and one third of my erroneous answer above.

I get the same result now for the numerator when I use the triangular inequality I forgot about last time.

The total probability, however is(in my notation)

$$P(\text{obtuse triangle})=\langle\Theta(c^2-a^2-b^2)\Theta(1/2-c)\rangle=\frac{\int_0^1dc\int_0^1db\int_0^1da \Theta(c^2-a^2-b^2)\Theta(1/2-c)\delta(1-a-b-c) }{\int_0^1dc\int_0^1db\int_0^1da\delta(1-a-b-c)\Theta(c-a)\Theta(c-b)}\approx 0.17
$$

Note that demand that $c$ is the biggest one is automatically included in the numerator by the pythagoras inequality.
If I'm correct this permutation counting doesn't matter in the end as long as you're consistent in numerator and denominator. In my way of doing, I for example first pick the longest part and call it $c$, and than $a$ and $b$ are the other two parts as you find them from the left to the right.

 

[andrewkirk]

Here's my corrected attempt at Q8. I think the probability will be:

$$
2\times \int_0^{\frac12}\int_{\frac12}^{x+\frac12} \chi_B\ dy\ dx
$$

where B is the subset of $\mathbb R^2$ (where the two coordinates denote the distances from the left end of the stick where the first and second cuts are made respectively) such that $a^2>b^2+c^2$, where $a,b,c$ are the lengths of the three stick components arranged from longest to shortest (so $a$ is the longest).

That is, if the cut locations are $x$ and $y$ then the stick lengths are $\min(x,y),1-\max(x,y)$ and $|x-y|$ and $a,b,c$ is those three numbers sorted from largest to smallest.

The integral gives the probability of an obtuse triangle if the first cut is closer to the left hand end of the stick. We then double it to get the total probability, as the prob if the second cut is closest to the left hand end is the same as that one, and the overlap of the two events has measure zero.

The integration limits are necessary and sufficient conditions for the three sticks to form a triangle, given that the first cut is closer to the left-hand end.

The result I get from a numerical integration of this is approximately 17%.

 

[thephystudent]

Here's my corrected attempt at Q8. I think the probability will be:

$$
2\times \int_0^{\frac12}\int_{\frac12}^{x+\frac12} \chi_B\ dy\ dx
$$

where B is the subset of $\mathbb R^2$ (where the two coordinates denote the distances from the left end of the stick where the first and second cuts are made respectively) such that $a^2>b^2+c^2$, where $a,b,c$ are the lengths of the three stick components arranged from longest to shortest (so $a$ is the longest).

That is, if the cut locations are $x$ and $y$ then the stick lengths are $\min(x,y),1-\max(x,y)$ and $|x-y|$ and $a,b,c$ is those three numbers sorted from largest to smallest.

The integral gives the probability of an obtuse triangle if the first cut is closer to the left hand end of the stick. We then double it to get the total probability, as the prob if the second cut is closest to the left hand end is the same as that one, and the overlap of the two events has measure zero.

The integration limits are necessary and sufficient conditions for the three sticks to form a triangle, given that the first cut is closer to the left-hand end.

The result I get from a numerical integration of this is approximately 17%.

Nice to have results that agree

 

[micromass]

I would like to try #9. For the probability that the first person has a Jan 1 birthday and all others different, that is $p=(1/365)(364/365)^{999}$. There are 1000 different people who can have this Jan.1 birthday, so that probability of one and only one Jan.1 birthday is $P=(1000/365)(364/365)^{999}$. (Not going to try to account for leap years.) 365 days, each of which has a similar possibility of one and only one birthday, so that mean number (expected number of people with no one matching their birthday) will be $\mu=365 P=1000(364/365)^{999}$ . My arithmetic with a log table (I don't have a calculator handy) is $\mu=64$. I didn't account either for any cross correlations, but these should be insignificant.

For number 9. Note: solution ignores leap years.

Imagine you conduct this experiment many times with $999$ other people. How often do you find yourself without a birthday partner?

$p = (\frac{364}{365})^{999} = 0.0645$

This is the same for everyone else. So, everyone is without a birthday partner with this probability. Overall, therefore, the expected number in any $1000$ is:

$1000p = 64.5$

Just saw @Charles Link beat me to it!

So, taking 1 leap year every 4 years, we have 1461 days every 4 years:

$p_x = 1/1461$ is the probability of being born on 29th Feb. And

$p_y = 1460/1461$ is the probability otherwise.

For those born on 29th Feb, the probability no one shares their birthday is:

$q_x = (1460/1461)^{999}$

For those not born on 29th Feb:

$q_y = (1457/1461)^{999}$

This gives a revised calculation:

$p = p_xq_x + p_yq_y = 0.0649$

Hence the expected number in 1000 is $64.9$.

Very good. I'll credit you both since PeroK also did it for leap years.

I get the same result now for the numerator when I use the triangular inequality I forgot about last time.

The total probability, however is(in my notation)

$$P(\text{obtuse triangle})=\langle\Theta(c^2-a^2-b^2)\Theta(1/2-c)\rangle=\frac{\int_0^1dc\int_0^1db\int_0^1da \Theta(c^2-a^2-b^2)\Theta(1/2-c)\delta(1-a-b-c) }{\int_0^1dc\int_0^1db\int_0^1da\delta(1-a-b-c)\Theta(c-a)\Theta(c-b)}\approx 0.17
$$

Note that demand that $c$ is the biggest one is automatically included in the numerator by the pythagoras inequality.
If I'm correct this permutation counting doesn't matter in the end as long as you're consistent in numerator and denominator. In my way of doing, I for example first pick the longest part and call it $c$, and than $a$ and $b$ are the other two parts as you find them from the left to the right.

Here's my corrected attempt at Q8. I think the probability will be:

$$
2\times \int_0^{\frac12}\int_{\frac12}^{x+\frac12} \chi_B\ dy\ dx
$$

where B is the subset of $\mathbb R^2$ (where the two coordinates denote the distances from the left end of the stick where the first and second cuts are made respectively) such that $a^2>b^2+c^2$, where $a,b,c$ are the lengths of the three stick components arranged from longest to shortest (so $a$ is the longest).

That is, if the cut locations are $x$ and $y$ then the stick lengths are $\min(x,y),1-\max(x,y)$ and $|x-y|$ and $a,b,c$ is those three numbers sorted from largest to smallest.

The integral gives the probability of an obtuse triangle if the first cut is closer to the left hand end of the stick. We then double it to get the total probability, as the prob if the second cut is closest to the left hand end is the same as that one, and the overlap of the two events has measure zero.

The integration limits are necessary and sufficient conditions for the three sticks to form a triangle, given that the first cut is closer to the left-hand end.

The result I get from a numerical integration of this is approximately 17%.

That is correct, but sadly thephystudent was first. I will credit anybody else who gives an exact solution as opposed to the approximate one.

 

[QuantumQuest]

Those replies are both correct. I'm afraid for QuantumQuest that PeroK was first though, so he gets credited

Yes indeed. I had worked for some time on the problem and when I was ready to post, PeroK had already done. But anyway, such is life...;)

 

[Redbelly98]

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

Can you clarify something. If each person chooses "two people at random without regard to the past development" to repeat the rumor to, then they could repeat the rumor to the same person who told them. That doesn't seem to follow common sense, but is a literal interpretation of the problem statement.

Thanks for putting these together, btw!

 

[micromass]

Can you clarify something. If each person chooses "two people at random without regard to the past development" to repeat the rumor to, then they could repeat the rumor to the same person who told them. That doesn't seem to follow common sense, but is a literal interpretation of the problem statement.

Thanks for putting these together, btw!

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.

 

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