B A Little Probability Puzzle

[bob012345]

TL;DR Summary

Here is a little probability puzzle concerning numbered balls randomly picked in pairs. Please only do this for a fun diversion.

Suppose you have ten ping pong balls labeled one through ten. You pull two balls at a time out of a random mixer and record the pairings. Now repeat. What are the odds of getting at least one pairing the same as before? What are the odds of getting only one pairing as before? What are the odds of getting all the pairings as before? Finally, how many repeats to have a 90% chance of getting the same set of five pairings as the initial pairings? Does that last question even make sense?

 

[DaveC426913]

I'm a bit confused about your scenario.


"pull two balls at a time out of a random mixer and record the pairings. Now repeat"
Do you put the two balls back before repeating?

If not, the answer is zero - you will not pick that same combination again since they are not in the mix.

If yes, then this just a straight combination:


OK. So there are 45 possible combinations in the first selection.
1+2,3,4,5,6,7,8,9,10 = 9
2+3,4,5,6,7,8,9,10 = 8
3+4,5,6,7,8,9,10 =7
etc.
10 = 0

S = n(n+1)/2
where n=9, a=0
S=45

In the second pick, there are also 45 possible combinations.
So, the chance of pulling the same pair the second time are ... 1 in 45. I think.

It seems the problem may need some clarification.

1. Put ten balls in the mixer.
2. Take a pair out, record their numbers.
3. Put them back in the mix.
4. Take out another pair, record their numbers.
5. Do not put these ones back (Otherwise the game has no end condition and, given enough time, you will eventually pull every combination.)
6. Repeat steps 4 and 5 until all ten balls are gone ... ? (Otherwise the last few questions, eg. "What are the odds of getting only one pairing as before?" make no sense)

 

[bob012345]

Sorry, I meant pull two at a time till all are out. Then throw them all in again and repeat so steps 1,2,4,5,6.

 

[Hornbein]

Please show us your work so far.

 

[bob012345]

Please show us your work so far.

Below are my answers. But please try it on your own. It’s a puzzle, not a homework problem.

Spoiler

My answers (which could always be wrong):



What are the odds of getting at least one pairing the same as before?

There are 45 possible combinations and 5 happened in the first round so

the odds are 5/45 or 1/9. (EDIT: that is wrong!)



What are the odds of getting only one pairing as before?

I think this is the probability above for one times the probability of not getting the next nor the next and so forth. The probability of not getting a second pairing is

(1-4/28)which is 24/28 or 6/7. The 28 comes from the fact that the combinations are less after the first pairing. They are 8!/(6!2!)=28 and there are 4 possible pairings from before. Applying that to the others I get P= 1/9 x6/7 x4/5 x2/3x1/1=48/945 (EDIT: this is wrong too)



What are the odds of getting all the pairings as before?

That would be 1/9x 1/7x 1/5x 1/3x1/1=1/945



Finally, how many repeats to have a 90% chance of getting the same set of five pairings as the initial pairings? The chance of not getting any pairings from the first round is 1-1/945=944/945. We can say 1-(944/945)^n>=0.9. About 2175 times.
[\Spoiler]

 

[PeroK]

I get the following. There are 945 possibilities for the 5 pairs. The probability of getting 0-5 pairs the same, given as a numerator over 945 are:
$$p(0) = 544, p(1) = 300, p(2) = 80, p(3) = 20 p(4)=0, p(5)= 1$$

 

[bob012345]

I get the following. There are 945 possibilities for the 5 pairs. The probability of getting 0-5 pairs the same, given as a numerator over 945 are:
$$p(0) = 544, p(1) = 300, p(2) = 80, p(3) = 20 p(4)=0, p(5)= 1$$

Is p(4)=0 a typo?

 

[PeroK]

Is p(4)=0 a typo?

No! It's not a typo.

 

[Ibix]

Is p(4)=0 a typo?

If you get four pairs the same, what are you left with for the fifth pair?

 

[bob012345]

No! It's not a typo.

Ok, I see.

 

[bob012345]

I get the following. There are 945 possibilities for the 5 pairs. The probability of getting 0-5 pairs the same, given as a numerator over 945 are:
$$p(0) = 544, p(1) = 300, p(2) = 80, p(3) = 20 p(4)=0, p(5)= 1$$

I interpret these to be your answers for the case of exactly matching 0,1,2,3,4 and 5 pairings. Why isn’t p(0)/945=(945-p(5))/945 making p(0)=944 in your system?

Also, what is your probability for the case of at least one pairing? Thanks.

 

[PeroK]

I interpret these to be your answers for the case of exactly matching 0,1,2,3,4 and 5 pairings. Why isn’t p(0)/945=(945-p(5))/945 making p(0)=944 in your system?

Also, what is your probability for the case of at least one pairing? Thanks.

I don't understand the question. The figures I gave are for the exact number of matches. Those probabilities must add to 1.

 

[bob012345]

I don't understand the question. The figures I gave are for the exact number of matches. Those probabilities must add to 1.

How did you derive those values? Thanks.

 

[PeroK]

How did you derive those values? Thanks.

Without loss of generality, we can assume that the first set of pairings is (1,2), (3,4) ... (9,10).

The number of ways of getting exactly one duplicate pair can be identified uniquely by the common pair. This is equally likely to be any of the five. We can count the number of ways to get (1,2) as one pair, but none of the others, and then multiply this by 5.

For two duplicate pairs it's $\binom 5 2$ times the number of ways we can get (1,2) and (3,4) but none of the others. Etc.

Generally, the higher number of duplicate pairings is easier to calculate. P(0) is the hardest, but it's a good exercise to check that it agrees with the others. Although, once you have p(1) thru p(5), you can subtract these from 945 to get p(0).

 

[Gavran]

$$ P(A_n)=(2!)^n(10-2n)!\frac{5!}{(5-n)!n!}n!\frac{1}{10!} $$
$A_n$ - the n particular pairs are pulled out in one repeat
$n\in\{1,2,3,4,5\}$

$$ P(B_n)=\frac{5!}{(5-n)!n!}P(A_n) $$
$B_n$ - n pairs in one repeat belong to the set of the initial pairs

$P(B_1)=(5\cdot2^1\cdot8!\cdot5\cdot1!)/(10!)=5/9$
$P(B_2)=(10\cdot2^2\cdot6!\cdot10\cdot2!)/(10!)=10/(9\cdot7)$
$P(C_1)=P(B_1)-P(B_2)=25/(9\cdot7)$
$C_1$ - only one pair in one repeat belongs to the set of the initial pairs

$P(B_5)=(1\cdot2^5\cdot0!\cdot1\cdot5!)/(10!)=1/(9\cdot7\cdot5\cdot3)$

The repeats are independent events.
$m\cdot P(B_5)=0,9$
$m=0,9/P(B_5)$
The chance of getting the same set of five pairs as the initial set of pairs will be $90\%$ for $850,5$ repeats.

 

[PeroK]

That last answer is not right. The correct answer is 2175.

Also, does your formula give p(4)=0?

 

[bob012345]

So the answer to my first question in the OP (the probability of having at least one of the original pairings) can be answered by using the case for P(0) worked out by @PeroK giving (945-544)/945=401/945. This problem was harder than I originally thought!

 

[Gavran]

That last answer is not right. The correct answer is 2175.

You are right.
$1-(1-P(B_5))^m=0,9$
$m=\ln(0,1)/\ln(1-P(B_5))\approx2175$
where $P(B_5)=1/(9\cdot7\cdot5\cdot3\cdot1)$ is the probability of getting the same set of five pairs as the initial set of pairs in one repeat.

Also, does your formula give p(4)=0?

No, it does not. There is something wrong with my formula in the post #15.

 

[Gavran]

$$ \begin{align}
\{\{1,2\}\}\,\,\,\,\,\,\,\,\,\,&n_{1,1}=1\nonumber\\
&n_{1,0}=1-1=0\nonumber\\
\{\{1,2\},\{3,4\}\}\,\,\,\,\,\,\,\,\,\,&n_{2,2}=1\nonumber\\
&n_{2,1}=2\cdot0=0\nonumber\\
&n_{2,0}=3-0-1=2\nonumber\\
\{\{1,2\},\{3,4\},\{5,6\}\}\,\,\,\,\,\,\,\,\,\,&n_{3,3}=1\nonumber\\
&n_{3,2}=3\cdot0=0\nonumber\\
&n_{3,1}=3\cdot2=6\nonumber\\
&n_{3,0}=15-6-0-1=8\nonumber\\
\{\{1,2\},\{3,4\},\{5,6\},\{7,8\}\}\,\,\,\,\,\,\,\,\,\,&n_{4,4}=1\nonumber\\
&n_{4,3}=4\cdot0=0\nonumber\\
&n_{4,2}=6\cdot2=12\nonumber\\
&n_{4,1}=4\cdot8=32\nonumber\\
&n_{4,0}=105-32-12-0-1=60\nonumber\\
\{\{1,2\},\{3,4\},\{5,6\},\{7,8\},\{9,10\}\}\,\,\,\,\,\,\,\,\,\,&n_{5,5}=1\nonumber\\
&n_{5,4}=5\cdot0=0\nonumber\\
&n_{5,3}=10\cdot2=20\nonumber\\
&n_{5,2}=10\cdot8=80\nonumber\\
&n_{5,1}=5\cdot60=300\nonumber\\
&n_{5,0}=945-300-80-20-0-1=544\nonumber\\
\end{align} $$
The formula is:
$$ n_{m,k}=\begin{cases}
1&k=m\\
\binom mk\cdot n_{m-k,0}&0\lt k\lt m\\
(2m-1)!!-\sum_{i=1}^{m}n_{m,i}&k=0
\end{cases} $$
where $n_{m,k}$ is the number of all $m$-pairing sets whose $k$ pairings belong to the initial set of pairings.

The formula for the probability of getting the $m$-pairing set with $k$ pairings belong to the initial set of pairings is:
$$ P(K=k)=\frac{n_{m,k}}{(2m-1)!!} $$.

The probabilities are:
$(945-544)/945$ at least one pairing in a set belongs to the initial set of pairings
$300/945$ one pairing in a set belongs to the initial set of pairings
$1/945$ five pairings in a set belong to the initial set of pairings.

 

[bob012345]

Thanks all! I originally came up with this while pulling identical pairs of socks out of my dryer. What are the odds? If I do laundry once a week, there is a 99% chance that I will match a pair in just over 8 weeks (m≈8.4) or about two months.

 

[sophiecentaur]

TL;DR Summary: Here is a little probability puzzle concerning numbered balls randomly picked in pairs. Please only do this for a fun diversion.

Suppose you have ten ping pong balls labeled one through ten. You pull two balls at a time out of a random mixer and record the pairings. Now repeat. What are the odds of getting at least one pairing the same as before? What are the odds of getting only one pairing as before? What are the odds of getting all the pairings as before? Finally, how many repeats to have a 90% chance of getting the same set of five pairings as the initial pairings? Does that last question even make sense?

There is a similar thing about Birthdays. The Birthday Problem :

"in probability theory, the birthday problem asks for the probability that, in a set of n randomly chosen people, at least two will share the same birthday. The birthday paradox is the counterintuitive fact that only 23 people are needed for that probability to exceed 50%."
That Wiki article discusses it fully.