Given n different pair of shoes,a total of 2n shoes,we put these 2n shoes together and randomly divided into n groups,with each group having 2 shoes.If 2 shoes in a group are just a pair,them we call this group the "pair group".Let X be the number of "pair groups".Calculate the expectation of x.
For this problem,I figured out that 2n shoes divided into n groups that has $C{2 \choose 2n}$ * $C{2 \choose 2n-2}$*… * $C{2 \choose 2}$ and the probability of X = n is $ \frac{2^n*n!}{2n!} $
X can be 0,1,2,…,n.So what is the probability of X = 0,X = 1,…,X=n-1,and how to calculate the E(X)?
Best Answer
Approaching the problem by Linearity of Expectation -
First to find, probability of a group of two shoes be a pair -
The number of ways to arrange $2n$ shoes into $n$ groups of two $= \displaystyle \frac{(2n)!}{2^n} \times \frac{1}{n!}$
(which comes from ${2n \choose 2} {2n-2 \choose 2} ...{4 \choose 2}$ and we divide by $n!$ to account for overcounting).
If a group is a pair, the number of ways to arrange $(2n-2)$ remaining shoes into $(n-1)$ groups of two
$= \displaystyle \frac{(2n-2)!}{2^{(n-1)}} \times \frac{1}{(n-1)!}$
So the probability of a group being a pair $P(X_1) = \displaystyle \frac{ 1}{2n-1}$ (which makes sense as we are choosing one particular shoe from $(2n-1)$ to make a pair).
To find expected number of pairs, we will sum their individual expected values.
So expected number of pairs, $E(\mathbb{X}) = P(X_1) \times 1 + P(X_2) \times 1 + ... + P(X_n) \times 1 = \displaystyle \frac{n}{2n-1}$