3

Suppose you have N pairs of socks in a drawer and you pick out K socks. What is the average number of pairs of socks that you will have if you repeat this experiment a large number of times? I know the answer is $\frac{K \choose 2}{2N-1}$ but I am unsure of the proof. This question is different from Expected value of sock pairs because the proof I am looking for is taken as a given in that question.

playfuljog
  • 33
  • Hint: use linearity. What's the probability that the $i^{th}$ pair is chosen? – lulu Sep 26 '19 at 13:48
  • @lulu I understand that there are $2N \choose K$ possible selections, but am unsure where to go from there. Are there $K \choose 2i$ ways of placing the $i^{th}$ pair? – playfuljog Sep 26 '19 at 14:14
  • Placing into what? Can you compute the probability that a given pair will be selected? How many selections contain the pair? How many selections in total are there? – lulu Sep 26 '19 at 14:20
  • @lulu I am having an issue figuring out "how many selections contain the pair". There are $2N \choose K$ total selections. What I was trying to say before was that you have $K \choose 2i$ ways of placing i pairs into K possible slots, although I do not think this helps much. – playfuljog Sep 26 '19 at 15:07
  • I don't see how that's relevant. Just pick a pair. What is the probability that this particular pair is amongst the $k$ chosen socks? – lulu Sep 26 '19 at 15:09
  • The probability of a particular pair being among K socks is $K \choose 2$, but this changes the total selection since you can no longer choose from K socks if 2 were already taken out of the pool – playfuljog Sep 26 '19 at 15:30
  • @playfuljog the probability of a particular pair being among $K$ socks is still a probability and as such is always between $0$ and $1$. $\binom{K}{2}$ on the other hand is larger than one and could not be a probability. Try again. – JMoravitz Sep 26 '19 at 17:27
  • This is true, I did not mean for the final answer to be $K \choose 2$, it should be $\frac{K \choose 2}{X}$ but I was unsure of how to find X, the total number of possible selections. I initially thought $X = {2N \choose K}$ but does that change now that we removed two socks? – playfuljog Sep 26 '19 at 18:02

1 Answers1

1

Let $A_i$ be the random variable that takes the value $1$ if the $i$th pair is selected, and $0$ otherwise (i.e. if only one sock or no socks of this pair are selected).

Then what you want is:

\begin{align} \sum_i^{N} \mathbb{E}[A_i] &= N\mathbb{E}[A_i] \\ &= N \times P(\text{pair $i$ is chosen}) \\ &= N \times \frac{{K\choose 2}}{{K\choose 2} + K(2N-K) + {2N-K \choose 2}} \\ &= N \times \frac{\frac{K(K-1)}{2} } {\frac{K(K-1)}{2} + K(2N-K) + \frac{(2N-K)(2N-K-1)}{2}} \\ &= N \times \frac{K(K-1)}{K(K-1) + 2K(2N-K) + (2N-K)(2N-K-1)} \\ &= N \times \frac{K(K-1)}{K^2 - K + 4KN - 2K^2 + 4N^2 -4KN + K^2 - 2N + K}\\ &= N \times \frac{K(K-1)}{4N^2 - 2N } \\ &= \frac{K(K-1)}{2(2N - 1) } \\ &= \frac{K \choose 2}{2N - 1} \end{align}

The third line is obtained from counting cases (i.e. 2 socks in $K$ socks, 1 sock in $K$ socks and 1 sock in $2N-K$ socks, 2 socks in $2N-K$ socks).

Sean Lee
  • 1,295
  • Can you please explain the first two lines? I understand that we are looking for the expected value, but why are we summing the expected value of each pair being chosen? – playfuljog Sep 26 '19 at 16:04
  • 1
    @playfuljog because the total number of pairs chosen is the sum of the number of times we answer yes to the question "is the $i$'th pair chosen?" and we remember that expectation is linear, so $\Bbb E[X+Y]=\Bbb E[X]+\Bbb E[Y]$ – JMoravitz Sep 26 '19 at 17:29
  • For the third line I think we can say the denominator is actually $2N(2N-1)$ and the sum is going from $i=1$ to $2N$ since the pool of socks is twice the pairs. This gives the same answer you received but with much less algebra involved – playfuljog Sep 26 '19 at 22:12