Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We all know the simple puzzle "If you have N pairs of socks in the washing machine, how many socks do you need to pull in order to be sure that you hold at least one matching pair." The answer is trivially N+1.

Today I was confronted with a generalized form of the same problem and I still can't think of a a simple answer:

  • How many socks do I need to pull in order to have P% probability of holding a pair
  • What is the probability of holding a pair if I have pulled M socks

For bonus points:

  • What would be the answer of the questions above if I had N multiple pairs of the same kind (i.e. my sock inventory is described by a vector of even numbers).
share|improve this question
    
Both answers are great, I am picking Didier Piau's because it's simple and instructive and I could understand it easily. Joriki's answer provides some nice practical approximation, but unfortunately the explanation is above my level (I know, I have to study ;-) –  ddimitrov Aug 1 '11 at 23:47
add comment

2 Answers 2

up vote 6 down vote accepted

Consider the complement events.

The probability $q_{n+1}$ of not holding any pair in $n+1$ socks is $q_n$ times the probability $r_n$ that the $(n+1)$th sock is not pairing any of the $n$ first ones. There are $n$ taboo socks amongst the $2N-n$ remaining ones, hence $r_n=(2N-2n)/(2N-n)$.

Thus the probability of holding a pair after $M$ pulls is $$ 1-q_M=1-\prod\limits^{M-1}_{n=1}\frac{2N-2n}{2N-n}. $$ An equivalent formula for $M\le N$ is $$ 1-q_M=1-2^M\,\frac{N!\,\,(2N-M)!}{(N-M)!(2N)!}. $$

share|improve this answer
    
Shouldn't start the productoria at n=0? If you calculate M=1 it must return 1-1 = 0. You can't hold any pair. –  helios Aug 1 '11 at 8:52
    
@helios: for $n=0$, the ratio $(2N-2n)/(2N-n)$ is... :-) –  Did Aug 1 '11 at 9:01
    
Exactly. It's irrelevant for the productoria, but the complete expression 1-productoria (for M=1) should calculate as 1-1=0 (no probabilities of extracting a pair). So it's important to start at n=0 so with M=1 the productoria yields 1. (or it yelds 1 if there's no terms??! oops, maybe I'm not used to productorias) –  helios Aug 1 '11 at 9:03
3  
@helios: Indeed, an empty product is defined to be $1$. –  André Nicolas Aug 1 '11 at 9:16
    
@Didier & André: My mistake... thanks for the clarification! –  helios Aug 1 '11 at 10:20
show 2 more comments

There are $2^M\binom{N}{M}$ ways of pulling $M$ socks without a pair, so the probability for that is

$$p(N,M)=2^M\frac{\binom NM}{\binom{2N}M}\;,$$

where the relationship between $p$ and your $P$ is $1-p=P\;\%$. This can't be solved for $M$ in closed form for arbitrary $p$ and $N$, but asymptotically for $N$ large and $M\ll N$ we have

$$ \begin{eqnarray} p(N,M) &=& 2^M\frac{\binom NM}{\binom{2N}M} \\ &=& 2^M\frac{N!(2N-M)!}{(2N)!(N-M)!} \\ &\approx& 2^M\frac{N^N(2N-M)^{2N-M}}{(2N)^{2N}(N-M)^{N-M}}\sqrt{\frac{N(2N-M)}{2N(N-M)}} \\ &=& \frac{\left(1-\frac M{2N}\right)^{2N-M+1/2}}{\left(1-\frac MN\right)^{N-M+1/2}} \\ &=& \frac{\left(1-\frac M{N}+\left(\frac{M}{2N}\right)^2\right)^{N-M/2+1/4}}{\left(1-\frac MN\right)^{N-M+1/2}} \\ &=& \left(1+\left(\frac{M}{2N}\right)^2/\left(1-\frac MN\right)\right)^{N-M/2+1/4}\left(1-\frac MN\right)^{M/2-1/4} \\ &\approx& \left(1+\frac{M^2}{4N}\right)\left(1-\left(\frac M2-\frac14\right)\frac MN\right) \\ &\approx& 1-\frac{M(M-1)}{4N}\;. \end{eqnarray} $$

So the probability of pulling a sock with a pair is about $M(M-1)/(4N)$. This approximation is good enough for some practical cases; for instance, if you pull $4$ out of $20$ socks, the exact probability of finding a pair is $15.\overline{176715}\%$ and the approximation yields $15\%$.

However, this approximation breaks down if $M$ is of the order of $\sqrt N$, which will be the case if you want a probability near $50\%$. For this case, we need a slightly different approximation. Generalizing $p$ to fractional $M$ by replacing $k!$ by $\Gamma(k+1)$, we have

$$ \begin{eqnarray} \lim_{N\to\infty} p(N,\sqrt{\lambda N}) &=& \lim_{N\to\infty}2^{\sqrt{\lambda N}}\frac{\Gamma(N+1)\Gamma(2N-\sqrt{\lambda N}+1)}{\Gamma(2N+1)\Gamma(N-\sqrt{\lambda N}+1)} \\ &=& \lim_{N\to\infty} \left(1+\left(\frac{\sqrt{\lambda N}}{2N}\right)^2/\left(1-\frac{\sqrt{\lambda N}}N\right)\right)^{N-\sqrt{\lambda N}/2+1/4}\left(1-\frac{\sqrt{\lambda N}}N\right)^{\sqrt{\lambda N}/2-1/4} \\ &=& \lim_{N\to\infty} \left(1+\left(\frac{\sqrt{\lambda N}}{2N}\right)^2\right)^{N}\left(1-\frac{\sqrt{\lambda N}}N\right)^{\sqrt{\lambda N}/2} \\ &=& \lim_{N\to\infty} \left(1+\frac{\lambda}{4N}\right)^{N}\left(1-\frac{\lambda/2}{\sqrt{\lambda N}/2}\right)^{\sqrt{\lambda N}/2} \\ &=& \mathrm e^{\lambda/4}\mathrm e^{-\lambda/2} \\ &=& \mathrm e^{-\lambda/4}\;. \end{eqnarray} $$

So for large $N$, we need to pull $\sqrt{\lambda N}$ socks to get a probability of $\mathrm e^{-\lambda/4}$ not to get a pair. This we can readily solve for $\lambda$ for given limit probability $p$ of not getting a pair:

$$p=\mathrm e^{-\lambda/4} \rightarrow \lambda=-4\log p\;.$$

For instance, for a $50\%$ chance, we get $\lambda =4\log2$, so $\sqrt{\lambda}=2\sqrt{\log2}\approx1.665$. That is, for large $N$, to have a $50\%$ chance of pulling a pair, you need to pull about $1.665\sqrt N$ socks. Since $1/p$ is the average number $n$ of times you need to pull to not get a pair, we can also write this as

$$M=\sqrt{\lambda N}=\sqrt{-4N\log p}=\sqrt{4N\log1/p}=2\sqrt{N\log n}\;.$$

So $M$ is twice the geometric mean of the number of socks and the logarithm of the average number of times you want to be able to do this until the first miss.

share|improve this answer
    
+1: for the approximated closed form approach! –  helios Aug 1 '11 at 10:24
    
@helios: Thanks. I've added another approximation that will probably be more useful in practice. –  joriki Aug 1 '11 at 11:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.