From a pile of 25 different pairs of socks, how many socks must you pull out on average before you get a...

probability/sock.drawer New

New entry, edited from material collected for the archive and not yet in a released version.

Problem

From a pile of 25 different pairs of socks, how many socks must you
pull out on average before you get a matching pair?

I have a pile of laundry with socks evenly distributed throughout.  In
this pile, I have 25 pairs of socks, each of which is different.  How
many socks (on average) should I expect to have to pull out before I
get ONE pair?

This is a real life situation, and it seems like I can pull out sock
after sock and they are all different.  It takes forever to get a pair.

-- Geoff Hazel <geoffh@eskimo.com>

Show solution

This is easy. After you have pulled the first sock, only one of the
remaining 49 socks will match. So the chance of picking a pair after
two pulls will be 1/49. The chance of needing exactly three pulls is
48/49 times 2/48 = 2/49, as now two of the remaining socks will match.
The chance of needing 2 or 3 pulls is 1/49+2/49 = 3/49. The chance of
needing exactly 4 pulls is 46/49*3/47 = 138/2303.

This generalizes to the recursive formulae

        p=(2)  = 1/49
        p<=(2) = 1/49

        p=(n+1)  = (1-p<=(n))*n/(50-n)
        p<=(n+1) = p<=(n)+p=(n+1)

Which yields the following table

         n  p=(n)        p<=(n)
        -----------------------
         2  1/49         1/49
         3  2/49         3/49
         4  138/2303     279/2303 [Editor: was 93/2303]
         5  176/2303 [Editor: was 4420/52964]
                         455/2303 [Editor: was 937/7567]
         6  .0891590679  .2867274569
         7  .0972644377  .3839918946
         .  .            .
         .  .            .

To find the average number of pulls we calculate the sum of n*p=(n) for
n = 2 to 26 (as after pulling 26 socks, you are sure to get a pair).
This gives 8.906688597.

So the average number of socks you have to pull is a little under 9.

-- Torben AEgidius Mogensen <torbenm@diku.dk>

[ Editor: the corrected fractions follow from the formulae:
3/49 + 138/2303 = 141/2303 + 138/2303 = 279/2303; then
p=(5) = (2024/2303)*4/46 = 176/2303 and p<=(5) = 455/2303.  The
decimal entries for n = 6 and 7 agree with these corrected values. ]