3
$\begingroup$

We've got $10$ different pairs of shoes. Now we mix them up and randomly regroup them into $10$ "pairs". Of course some "pairs" are not matched and maybe some of them are. So what's the expect number of pairs that are matched?

By "randomly group", I mean you can randomly pick one from the $20$, then choose one from the remaining $19$ to pair it up, and so on.

1 Answers 1

9

Let $X$ be the number of pairs of shoes that are matched. It is somewhat complicated to work with $X$ directly, so we think of $X$ as a sum of simpler variables:

For $i=1,2,\ldots10$, let $X_i=\cases{1 & \text{if the }i\text{th pair is matched},\\ 0 & \text{otherwise}.}$

Then each $X_i$ is a Bernoulli variable and $X=\sum_{i=1}^{10}X_i$.

Expectation is linear, so $$ \Bbb E(X)=\sum_{i=1}^{10}\,\Bbb E(X_i). $$

Now we fix $i$ and find $\Bbb E(X_i) $:

Since $X_i$ is a Bernoulli variable, $\Bbb E(X_i)=P[X_i=1]$. But the probability that $X_i=1$ is the probability that the $i$th pair was matched. Since it is equally likely that any one of the other 19 shoes is paired with the left shoe of the $i$th pair, $P[X_i=1]={1\over19}$.

So $\Bbb E(X_i)={1\over19}$.

Finally, we have:

$$\Bbb E(X)=\sum_{i=1}^{10}\Bbb E(X_i)=\sum_{i=1}^{10}{1\over19}=10/19.$$

  • 1
    I should mention why $P[X_i=1]={1\over19}$ without "hand waving": there are ${20!\over2^{10}}\cdot{1\over10!}$ ways to divide the 20 shoes into pairs and there are ${18!\over2^9}\cdot{1\over9!}$ ways to divide them into pairs with the $i$th pair matched. $P[X_i=1]$ is the ratio of these quantities, which is $1/19$.2011-11-14
  • 0
    Interesting that you're allowed to pair a right shoe with another right shoe. I might have stated the problem differently---maybe using socks, since with those you can't tell left from right.2011-11-14
  • 0
    I'm thinking of the problem as the same as "10 married couples are split into 10 groups, each of size 2". Find the expected number of groups consisting of a married couple. (That is, a pair of shoes consists of two distinct objects.)2011-11-14