Can You Find a Matching Pair of Socks (Again)?

Your drawer holds five distinct pairs of socks, ten socks in all, none paired up, and the room is pitch black. You pull socks out one at a time at random, and you want to stop as soon as you hold a matching pair. If you decide in advance how many socks to draw, how many should that be to maximise the chance that the last sock you draw is the one that first completes a pair?

The Fiddler, Zach Wissner-Gross, June 28, 2024(original post)

Solution

Drawing $k$ socks succeeds when the first $k-1$ are all different colours and the $k$-th matches one of them. The chance the first $k-1$ are all distinct shrinks as $k$ grows, while the chance the next sock then finds a match grows, so the product peaks in the middle. For five pairs, $$P(k)=\underbrace{\frac{8}{9}\cdot\frac{6}{8}\cdots}_{\text{first }k-1\text{ distinct}}\ \times\ \frac{k-1}{10-(k-1)},$$ giving $\tfrac19,\tfrac29,\tfrac27,\tfrac{16}{63},\tfrac{8}{63}$ for $k=2,3,4,5,6$. The largest is $\tfrac27$ at $k=4$, so you should draw $$\boxed{4}$$ socks; the fourth completes the first pair with probability $\tfrac27\approx28.6\%$, the best of any choice.

The computation

Play it out: draw the ten socks in a random order, find the position at which a colour first repeats, and tally how often that position is each $k$. The peak of the tally is at $k=4$, with frequency $\tfrac27$.

import numpy as np
rng = np.random.default_rng(0)
socks = np.repeat(np.arange(5), 2)                 # five colours, two each
counts = np.zeros(11); trials = 1_000_000
for _ in range(trials):
    perm = socks[rng.permutation(10)]
    seen = set()
    for i, col in enumerate(perm, start=1):
        if col in seen: counts[i] += 1; break       # first completed pair
        seen.add(col)
P = counts / trials
print(int(P.argmax()), round(P[4], 3))             # 4  0.286

Extra Credit

With $N$ pairs and $N$ very large, how many socks should you draw?

Solution

The same expression governs it for $N$ pairs: $P(k)$ climbs and then falls, and its peak drifts upward with $N$ exactly like a birthday-problem threshold. The first matching pair tends to arrive after about $\sqrt{2N}$ draws, the familiar square-root scaling of collisions, so the optimal number to commit to is $$\boxed{k^\star\approx\sqrt{2N}.}$$ The ratio $k^\star/\sqrt N$ falls steadily toward $\sqrt2\approx1.414$ as $N$ grows: it is $1.50$ at $N=100$, $1.46$ at $N=500$, and $1.455$ at $N=1000$.

The computation

Evaluate the exact probability of completing the first pair on draw $k$ and maximise it over $k$; the optimum tracks $\sqrt{2N}$.

import math
from fractions import Fraction as F
def P(k, N):                                       # P(first pair completes exactly on draw k)
    dist = F(1)
    for i in range(k - 1): dist *= F(2 * (N - i), 2 * N - i)   # first k-1 distinct colours
    return dist * F(k - 1, 2 * N - (k - 1))                    # k-th matches one of them
for N in (100, 500, 1000):
    k = max(range(2, 2 * N + 1), key=lambda k: P(k, N))
    print(N, k, round(k / math.sqrt(N), 3))        # k* ~ sqrt(2N)