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.


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
    $\begingroup$ 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$. $\endgroup$ Nov 14 '11 at 10:15
  • $\begingroup$ 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. $\endgroup$ Nov 14 '11 at 11:45
  • $\begingroup$ 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.) $\endgroup$ Nov 14 '11 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.