3
$\begingroup$

Suppose there are $2n$ socks where each of the $n$ pairs are unique. I wish to find the probability that there is at least one matching pair when these socks are paired at random. Suppose, for the clarity of my solution, that the socks are allocated to persons $P_1, P_2, \ldots, P_n$. The probability that person $P_1$ is allocated a matching pair is $$\frac{\binom{n}{1}}{\binom{2n}{2}}$$ So if I consider $$\sum_{k=1}^{n}\frac{\binom{n}{1}}{\binom{2n}{2}}$$ then I will have overcounted for when pairs of persons had a matching pair, when triplets of persons had a matching pair and so on. So this appears to be a doable calculation by the inclusion exclusion principle. Thus the probability is

$$\sum_{k=1}^{n}\binom{n}{k}\times \frac{n(n-1)\cdots(n-k+1)}{\binom{2n}{2}\binom{2n-2}{2}\cdots \binom{2n-2k+2}{2}}\times (-1)^{k+1}$$

The quantity in the denominator is a convenient telescoping product $$\binom{2n}{2}\binom{2n-2}{2}\cdots \binom{2n-2k+2}{2}=\frac{(2n!)\times2^n}{(2n-2k)!}$$

but I am unsure of this answer at this stage. Any ideas?

$\endgroup$
  • $\begingroup$ Find the complement of the probability. $P(\text{getting no socks})$ $\endgroup$ – Aops Vol. 2 Oct 7 at 2:29
  • $\begingroup$ Is that any easier? $\endgroup$ – An Invisible Carrot Oct 7 at 2:35
  • $\begingroup$ @AopsVol.2: I don't think that is easy. If we were matching shoes and each person were given a left and a right we would just be looking for a derangement, but for socks it is not so simple. $\endgroup$ – Ross Millikan Oct 7 at 2:38
  • $\begingroup$ @RossMillikan: for me, when solving with numerical problems, its always easier to find the complement. Although doing the math now im not sure about this case. $\endgroup$ – Aops Vol. 2 Oct 7 at 2:40
  • $\begingroup$ Yes, I wasn't able to come up with anything for the complement that you mentioned. I agree that it is generally easier to find the complement - but as was mentioned, there are problems (such as dearrangements) where this is not the case. $\endgroup$ – Hugh Entwistle Oct 7 at 3:03
0
$\begingroup$

An approximate way to look at it is to realize that each person gets a pair with probability $\frac 1{2n-1}$. If we ignore the correlations, the chance that nobody gets a pair is $\left(1-\frac 1{2n-1}\right)^n$ The limit of this for large $n$ is $\frac 1{\sqrt e}$ The correlations come from the fact that the probability changes if $P_1$ and $P_2$ get opposite halves of two pairs compared to them getting four disparate socks.

The only way I can see to improve on this is to use inclusion-exclusion coupled to a two dimensional recurrence. We would let $Q(n,k)$ be the chance of no pairs when there are $n$ people, $n-k$ pairs of socks, and $2k$ single socks. From $n,k$ we can draw a pair of socks with probability $\frac {n-k}n \cdot \frac1{2n-1}$, two socks that cannot be paired with probability $\frac {2k(2k-1)}{2n(2n-1)}$, two socks that could have been paired with probability $\frac {n-k}n\cdot \frac{2n-2k-2}{2n-1}$ and one sock that could have been paired and one sock that could not with probability $2\frac{n-k}{n}\cdot \frac {2k}{2n-1}$ This gives the recurrence $$Q(n,k)=\frac {2k(2k-1)}{2n(2n-1)}Q(n-1,k-1)+\\ \frac {n-k}n\cdot \frac{2n-2k-2}{2n-1}Q(n-1,k+1)+\\ 2\frac{n-k}{n}\cdot \frac {2k}{2n-1}Q(n-1,k)$$

The other approach is to write a simulation.

$\endgroup$
0
$\begingroup$

Possible alternate approach, partly inspired by the answer by @RossMillikan

  • Let $p_n =$ prob of no match in the original experiment, where we start with $2n$ total socks in $n$ pairs.

  • Let $q_n =$ prob of no match in a modified experiment, where we start with $2n$ total socks in $n-1$ pairs plus $2$ extra socks that don't match any other (but we will call these two as "phantom pair").

Here's my attempt to write a $1$-dimensional recurrence using just the above:

Claim 1: $p_n = {2n-2 \over 2n-1} q_{n-1}$

Reason: Person $1$ has unmatched socks with prob ${2n-2 \over 2n-1}$, and as far as the rest of the people, they have an experiment with $2n-2$ socks in $n-2$ pairs plus $2$ extras (the partners to whatever Person $1$ is holding).

Claim 2: $q_n = p_n + {1 \over 2n-1} p_{n-1}$

Reason: The event of $q_n$ can happen in two (disjoint) cases:

  • The phantom pair is held by the same person: This happens with prob ${1 \over 2n-1}$ and then for the event of $q_n$ to happen the remaining $n-1$ pairs must be mismatched, which happens with prob $p_{n-1}$.

  • The phantom pair is held by two different people: All $n$ pairs, real or phantom, must be mismatched, which happens with prob $p_n$.

If my reasoning above is correct, then:

$$p_n = {2n-2 \over 2n-1} (p_{n-1} + {1 \over 2n-3} p_{n-2})$$

However, I'm not $100\%$ sure of my reasoning above, nor am I sure my answer matches the OP's answer and/or Ross's answer, so critiques are very welcome.

$\endgroup$

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.