There are $n$ socks in a drawer, of $m$ different colours. Initially, the probability of picking a sock of colour $c_i$ at random is $\mathbb{P}(c_i) \cdot 2r$ socks are picked at random, without replacement.

What is the probability, $\mathbb{P}(pairs)$, that $r$ pairs of socks are picked? (i.e. all socks are paired)

If $r = 1$ (2 socks are chosen):

$\mathbb{P}(pairs)$ = $\mathbb{P}$(2 are $c_1$ or 2 are $c_2$ or ... or 2 are $c_m$) ~ $\sum_{k}^{m} {\left[\mathbb{P}(c_k)\right]^2}$

How can this be generalized for r?

  • $\begingroup$ Your calculation seems to assume that the socks are picked with replacement. If so, you should add that to the question, since this is not how one would spontaneously tend to think about picking socks from a drawer :-). If not, you may be considering the limit $n\to\infty$. If so, that should be noted in the question. In either case, the number $n$ of socks doesn't enter into the calculation. (Also please don't put tags in the title. That's what the tags are for -- the title should be more specific to the question.) $\endgroup$ – joriki Jun 19 '16 at 18:07
  • $\begingroup$ Now you're specifying that you're drawing without replacement. Then the sum of squares is just an approximation. Is your question how this approximation can be generalised? That would essentially be equivalent to asking for the exact probability with replacement. $\endgroup$ – joriki Jun 19 '16 at 18:22
  • $\begingroup$ The probability to pick $n_i$ socks of colour $i$ can be described by the exponential generating function $\prod_i\exp(p_ix_i)$. If only even numbers of each colour are allowed, this becomes $\prod_i\cosh(p_ix_i)$. The probability to pick an even number of each colour when picking a total of $2r$ socks can then be read off the coefficient of $x^{2r}$ in $\prod_i\cosh(p_ix)$. $\endgroup$ – joriki Jun 19 '16 at 18:27
  • $\begingroup$ Thank you for your replies. If $n_i$ is the number of socks of colour $i$, the probability to pick $k$ socks of colour $i$ is the following: $\frac{n_i}{n}.\frac{n_i - 1}{n - 1}.\frac{n_i - 2}{n-2}. ... . \frac{n_i - k}{n - k}$. How do you then arrive at the exponential notation? $\endgroup$ – Jack Smith Jun 19 '16 at 19:05
  • $\begingroup$ I was building on my previous comment that the relation you want to generalise approximates the case without replacement by the case with replacement, so I provided the generating function for the case with replacement. $\endgroup$ – joriki Jun 20 '16 at 18:03

I think some clarification is necessary.

$\mathbb{S}$ is the set of socks in the drawer. (Where elements appear more than once, consider them to have some ordinal to satisfy uniqueness, but are still the 'same' element and can therefore be paired).
$n_i$ is the initial number of socks of colour $i$ in the draw.
$m$ is the number of different colours the socks may have.
$n$ is the initial number of socks in the draw. $n = \sum_{j}^{m}n_j$
$p_i$ is the initial probability of drawing a sock of colour $i$ from the draw $p_i = \frac{n_i}{n}$.
$n_i$ may or may not be equal to $n_j$ may or may not be equal to $n_k$ ...
(There may be odd socks in the draw (i.e. socks that cannot be paired), no socks of a given colour etc.)

If $2a$ socks are picked at random and not replaced (i.e. choose a subset of $\mathbb{S}$), what is the probability, $\mathbb{P}$, that these socks can all be paired up? The order in which the socks are picked does not matter. When they have all been picked, they are then paired.

Case 1:
$\mathbb{S} = \{r, r, g, g, b, b\}$
(properly $\mathbb{S} = \{r_1, r_2, g_1, g_2, b_1, b_2\}$ etc.)
$a = 1$
possible selections: $\{rr, rg, rb, gr, gg, gb, br, bg, bb\}$
valid selections: $\{rr, gg, bb\}$
$\mathbb{P} = \frac{1}{3}$

Case 2:
$\mathbb{S} = \{r, r, g, g, b, b\}$
$a = 2$
possible selections: $\{rrgg, rrgb, rrbg, rrbb, ... , bbgg\}$
valid selections: $\{rrgg, rgrg, rggr, rrbb, rbrb, rbbr, ..., bggb\}$
$\mathbb{P} = \frac{1}{5}$

Case 3:
$\mathbb{S} = \{r, r, r, r, r, r, g, g, g, b, y, y, y, ...\}$
is a lot more complex...
If $a = 3$, three pairs of red socks could be chosen, or a pair of red a pair of yellow and a pair of green.

(The real question I am trying to answer is for an edge matching puzzle. If I choose $n$ pieces with $m$ edges each from $o$ possible pieces what is the probability that the chosen pieces are able to match completely (i.e. there must be even multiples of each edge type in the chosen pieces for a solution to be possible)).

(Thank you for replies so far. My apologies for posting this as an answer. I do not have access to the unregistered account I posted the question under, and cannot post a comment until I have 50 reputation).


In short, although I can write a solution to your problem, I think that simplifying it may be quite intractible.

Say you choose $i_j$ socks of colour $j$. Then $\sum_{j=1}^Mi_j=2r$, $i_j\leq n_j$ for all $j$ and the probability that you get pairs in this particular way is $\left(\begin{array}{c} 2r \\ i_1\;i_2\;\ldots\;i_m\end{array}\right)\frac{n_1(n_1-1)\ldots(n_1-i_1+1)}{n^{i_1}}\frac{n_2(n_2-1)\ldots(n_2-i_2+1)}{n^{i_2}}\ldots\frac{n_m(n_m-1)\ldots(n_m-i_m+1)}{n^{i_m}}$, where in the case $i_j=0$ the corresponding term is equal to 1. The multinomial coefficient is there because you can choose the socks in different orders. Therefore $\mathbb{P}[\text{Pairs}]=\sum_{(i_j)_j:\begin{array}{c} \sum_{j=1}^Mi_j=2r \\ i_j\leq n_j \\ i_j \text{ even}\end{array}}\left(\begin{array}{c} 2r \\ i_1\;i_2\;\ldots\;i_m\end{array}\right)\frac{n_1(n_1-1)\ldots(n_1-i_1+1)n_2(n_2-1)\ldots(n_2-i_2+1)}{n^{i_2}}\ldots\frac{n_m(n_m-1)\ldots(n_m-i_m+1)}{n^{i_m}}=\\\sum_{(i_j)_j:\begin{array}{c} \sum_{j=1}^Mi_j=2r \\ i_j\leq n_j \\ i_j \text{ even}\end{array}}\left(\begin{array}{c} 2r \\ i_1\;i_2\;\ldots\;i_m\end{array}\right)\frac{n_1(n_1-1)\ldots(n_1-i_1+1)n_2(n_2-1)\ldots(n_2-i_2+1)\ldots n_m(n_m-1)\ldots(n_m-i_m+1)}{n^{2r}}$

To be clear the summation notation means we are summing over all vectors $(i_1,\ldots,i_M)$ that satisfy the given constraints. In the limit as $n_j\rightarrow\infty$ for all $j$ but $r$ stays constant we get the approximation $\sum_{(i_j)_j:\sum_{j=1}^Mi_j=2r, i_j \text{ even}}\left(\begin{array}{c} 2r \\ i_1\;i_2\;\ldots\;i_m\end{array}\right)\frac{n_1^{i_1}n_2^{i_2}\ldots n_m^{i_m}}{n^{2r}}$.

This is well studied, it is the probability that a multinomial distribution has all terms even. As far as I know there is no clean answer to this, which means I doubt there is a clear simplification of the exact answer, although it can be calculated in the case of specific values of $r$, $n_i$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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