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

 A: 
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=\frac{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)!}
$$
A: 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.
