Vasya bought $n$ pairs of identical socks. For $n$ days, Vasya had no problems: every morning he took a new pair from the closet and wore it all day. After $n$ days, Vasya's mother washed all the socks in the washing machine and paired them up as they came out, since, to reiterate, the socks are identical. Let's call a pair of socks successful if both socks in this pair were worn by Vasya on the same day.

a) Find the probability that all the resulting pairs are successful.

b) Prove that the expected number of successful pairs is greater than 0.5.
a) The probability that the first pair is a match is $1 / 2n-1$, since when the mother picked up the first sock, $2n-1$ socks remained, and only one of them forms a matching pair with the first. Similarly, the probability that the second pair is a match (given that the first pair is a match) is $1 / 2n-3$, and so on. The probability that all pairs are matches is obtained as the product $\frac{1}{2n-1} \cdot \frac{1}{2n-3} \cdot \ldots \cdot \frac{1}{3}=\frac{1}{(2n-1)!!}=\frac{(2n)!!}{(2n)!}=\frac{2^n n!}{(2n)!}$.

To find an approximate expression, we apply Stirling's formula: $m! \approx \sqrt{2 \pi m} \cdot m^m e^{-m}:$

$$
\frac{2^n n!}{(2n)!} \approx \frac{2^n \sqrt{2 \pi n} \cdot n^n e^{-n}}{\sqrt{4 \pi n} \cdot (2n)^{2n} e^{-2n}} = \frac{1}{\sqrt{2}} \left( \frac{e}{2n} \right)^n
$$

b) The probability that a specific pair is a match, found in part a), is $1 / 2n-1$. Let's number the pairs from 1 to $n$. We introduce indicators:

$\xi_k=1$ if the $k$-th pair is a match, $\xi_k=0$ if the $k$-th pair is not a match. Then $E \xi_k = 1 / 2n-1$.

The random variable $X$ "number of matching pairs" is equal to the sum of the indicators: $X = \xi_1 + \xi_2 + \ldots + \xi_n$.

Therefore, $\mathrm{E} X = n \mathrm{E} \bar{\zeta}_1 = n / 2n-1 > 0.5$.

## Answer

a) $\frac{2^n n!}{(2n)!} \approx \frac{1}{\sqrt{2}} \left( \frac{e}{2n} \right)^n$

Submit a comment