6

Suppose that $N$ pairs of socks are put in a washing machine, with each sock having one mate. If the washing machine randomly eats socks, and at the end of the wash returns a random number $K$ of socks where $0 \leq K \leq 2N$, where each $K$ is equally probable, what is the expected number of complete pairs of returned socks?

Just from working out the first few values of $N$, I conjecture that the answer is $N/3$, but I am not sure how to prove it for all values of $N$.

Just to be clear, this is the expected value for an infinite number of trials where each $K$ is equally probable, not the expected value for an infinite number of trials where $K$ is fixed, whereupon the answer is $\displaystyle{K \choose 2}/(2N-1)$.

Clarinetist
  • 19,519
stumped
  • 61

2 Answers2

1

Let $X$ be the number of pairs of socks that get returned.

You already know that $\mathbb{E}[X|K] = \dfrac{1}{2N-1}\dbinom{K}{2}$ and that $K \sim \text{Uniform} \ \overline{0,2N}$

Thus, $\mathbb{E}[X] = \mathbb{E}[\mathbb{E}[X|K]] = \mathbb{E}\left[\dfrac{1}{2N-1}\dbinom{K}{2} \right] = \dfrac{1}{2N-1}\displaystyle\sum_{k = 0}^{2N}\dfrac{1}{2N+1}\dbinom{k}{2}$ $= \dfrac{1}{(2N-1)(2N+1)}\dbinom{2N+1}{3} = \dfrac{1}{(2N-1)(2N+1)}\dfrac{(2N+1)(2N)(2N-1)}{6} = \dfrac{N}{3}$.

JimmyK4542
  • 54,331
1

Let random variable $X_i$ be $1$ if the $i$-th pair survives the washing machine, and let $X_i=0$ otherwise. Then the number $Y$ of surviving pairs is given by $Y=X_1+X_2+\cdots+X_N$. By the linearity of expectation we have $E(Y)=E(X_1)+E(X_2)+\cdots +E(X_N)$.

We need to find $E(X_i)$. By a conditional expectation argument, this is $$\frac{1}{2N+1}\sum_0^{2N} E(X_i|K=k).\tag{1}$$ If $k\ge 2$ socks survive, the probability the pair $i$ does is the probability the left sock does, times the probability the right does given the left does, that is, $\frac{k(k-1)}{2N(2N-1)}$.

Add up, $k=2$ to $N$. By a standard result, the sum (1) is equal to $$\frac{1}{2N+1}\cdot \frac{1}{2N(2N-1)}\cdot 2\binom{2N+1}{3}.$$ Multiply by $N$ for the expectation.

Simplify. There is nice cancellation, and we get $\dfrac{N}{3}$.

André Nicolas
  • 507,029