# How many socks do I have to pull

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

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)!}.$$

-
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
@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

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.

-
+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