$n$ pairs of socks are hanging to dry in a random order (as taken out of the washing machine). There are no two identical pairs. The socks are hanging behind a drying sheet, so the Absent-Minded Scientist takes one sock at a time by feel and compares each new sock with all the previous ones. Find the expected number of socks removed by the time the Scientist ends up with any pair.
Let $\xi_{n}$ be a random variable equal to the number of socks removed under the condition that $n$ pairs of socks are hanging on the line. Obviously, $\mathrm{E} \xi_{1}=2$.

Let $n>1$. We will number the socks in the order in which the Absent-Minded Scientist removes them from the line. (Obviously, the method of numbering does not matter.) In this numbering, some sock is the last one (its number is $2n$, and it will never be removed, since the sock with number $n+1$ will definitely form a pair with some previous one). Let's distinguish this last sock somehow: let it be white.

Denote by $p_{j, n}$ the probability of the event $\xi_{n}=j$. Obviously, $p_{1, n}=0$.

Let's find $p_{2, n}$. It all depends on where the other white sock is hanging. If it is hanging in the first or second place (the probability of this is $2 / 2n-1$), then the first two socks do not form a pair. If it is hanging in the third or subsequent places (the probability of this is $2n-3 / 2n-1$), then the conditional probability that the first two socks form a pair is $p_{2, n-1}$ - this is the probability of getting a pair on the second attempt, discarding both white socks from the sequence. By the formula of total probability, we get: $p_{2, n}=\frac{2n-3}{2n-1} p_{2, n-1}$. Similarly, we will find $p_{3, n}$. If the white sock is hanging in one of the first two places (with probability ${ }^{2} / 2n-1$), then the conditional probability that the third sock will form a pair is the probability that the second sock will form a pair in the sequence without white socks. If the white sock is in the third place (probability $1 / 2n-1$), then the conditional probability that the third sock will form a pair is 0, since it is white, and its pair is hanging at the end. If the white sock is hanging further than the third place (probability ${ }^{2n-4} / 2n-1$), then the conditional probability that the first two socks form a pair is $p_{3, n-1}$, since in this case the presence of white socks does not matter. The formula of total probability gives: $p_{3, n}=\frac{2}{2n-1} p_{2, n-1}+\frac{2n-4}{2n-1} p_{3, n-1}$.

Reasoning similarly further, we get: $p_{k, n}=\frac{k-1}{2n-1} p_{k-1, n-1}+\frac{2n-1-k}{2n-1} p_{k, n-1}$ for all $k$ from 2 to $n$.

![](https://cdn.mathpix.com/cropped/2024_05_08_293b4772a418c01a5915g-29.jpg?height=320&width=1309&top_left_y=0&top_left_x=392)

Here, the $k$-th sock has the number $k-1$ in the sequence from which the white socks have been removed. Therefore, in this case $p_{k, n}=p_{k-1, n-1}$.

2

![](https://cdn.mathpix.com/cropped/2024_05_08_293b4772a418c01a5915g-29.jpg?height=315&width=1312&top_left_y=460&top_left_x=384)

Here, the $k$-th sock is white, so it cannot form a pair with any of the previous ones: $p_{k, n}=0$.

![](https://cdn.mathpix.com/cropped/2024_05_08_293b4772a418c01a5915g-29.jpg?height=309&width=1318&top_left_y=969&top_left_x=373)

Here, the white sock is hanging further than the $k$-th one, so the white socks can be ignored altogether: $p_{k, n}=p_{k, n-1}$.

If there are $n-1$ pairs in total, then the probability that the first pair will be formed on the $(n+1)$-th sock is zero: $p_{n+1, n-1}=0$. Therefore, for $k=n+1$ we get: $p_{n+1, n}=\frac{n}{2n+1} p_{n, n-1}$.

Now let's find the expected value:

$$
\begin{gathered}
\mathrm{E} \xi_{n}=2 p_{2, n}+3 p_{3, n}+4 p_{5, n}+\ldots+n p_{n, n}+(n+1) p_{n+1, n}= \\
=2 \cdot \frac{2n-3}{2n-1} p_{2, n-1}+3 \cdot \frac{2}{2n-1} p_{2, n-1}+3 \frac{2n-4}{2n-1} p_{3, n-1}+ \\
+4 \cdot \frac{3}{2n-1} p_{3, n-1}+4 \frac{2n-5}{2n-1} p_{4, n-1}+\ldots \\
\ldots+n \cdot \frac{n-1}{2n-1} p_{n-1, n-1}+n \frac{n-1}{2n-1} p_{n, n-1}+(n+1) \frac{n}{2n-1} p_{n, n-1} .
\end{gathered}
$$

Grouping the terms with $p_{k, n-1}$, we get:

$$
\begin{aligned}
\mathrm{E} \xi_{n} & =\frac{4n}{2n-1} p_{2, n-1}+\frac{6n}{2n-1} p_{3, n-1}+\frac{8n}{2n-1} p_{4, n-1}+\ldots+\frac{2n^2}{2n-1} p_{n, n-1}= \\
& =\frac{2n}{2n-1}\left(2 p_{2, n-1}+3 p_{3, n-1}+4 p_{4, n-1}+\ldots+n p_{n, n-1}\right)=\frac{2n}{2n-1} \cdot \mathrm{E} \xi_{n-1} .
\end{aligned}
$$

The obtained relation allows us to compute $\mathrm{E} \xi_{n}$, knowing that $\mathrm{E} \xi_{1}=2$:

$$
E \xi_{n}=\frac{2n(2n-2) \ldots \cdot 4}{(2n-1)(2n-3) \ldots \cdot 3} E \xi_{1}=\frac{(2n)!!}{(2n-1)!!}=\frac{((2n)!!)^2}{(2n-1)!!(2n)!!}=\frac{(2^n n!)^2}{(2n)!}=\frac{4^n}{C_{2n}^n}
$$

To obtain an approximation for large $n$, we will use Stirling's formula: $n! \approx \sqrt{2 \pi n} \cdot n^n e^{-n}$. We get: $\quad \mathrm{E} \xi_{n}=\frac{4^n (n!)^2}{(2n)!} \approx \frac{4^n 2 \pi n \cdot n^{2n} \cdot e^{-2n}}{e^{-2n} \sqrt{2 \pi \cdot 2n}(2n)^{2n}}=\sqrt{\pi n}$

## Answer

## Problem