Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 8 down vote accepted

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.$$

share|cite|improve this answer
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$. – David Mitra Nov 14 '11 at 10:15
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. – Michael Hardy Nov 14 '11 at 11:45
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.) – David Mitra Nov 14 '11 at 11:52

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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