Martha has to put on socks before leaving her house in the morning. She has a drawer in her bedroom which contains \(N\) different pairs of socks. Martha starts pulling socks from the drawer one by one, and a soon as she gets a matching pair, she stops and departs for work. Find the expected value \( \mathbb{E}\left( X \right) \) of the number of socks she has to pull every day from her drawer before she can leave her house.

**The Ugly One**

Let’s bruteforce the expected value:

$$ \mathbb{E}\left( X \right) = \sum_i^N i \cdot p_i = 2 \cdot p_2 + 3 \cdot p_3 + … + (N + 1) \cdot p_{N + 1} $$ Where \( p_i \) is the probability of her going to work after pulling out \( i \) number of socks. It is obvious that \( p_1 = 0 \) since she will have only one sock at that moment, and that she is guaranteed to stop and have a matching pair after pulling \( N + 1 \) socks from the drawer.

Probability \( p_i \) is conditional on survival \(1-p_{i-1}\), i.e. reaching step \( i \): $$ p_i = (1 – p_{i-1}) \cdot r_i $$ Where \( r_i \) is a probability of a match after pulling \( i \)-th sock: $$r_i = \frac{i – 1}{2N – (i – 1)}$$