Category: The Riddler

Computing the expectation

Define $T$ to be number of turns that the game lasts (this is a random variable). Define $q_k = \textbf{P}(T > k)$ to be the probability that the game has still not ended after $k$ draws. We can compute this explicitly. There are $\binom{2n}{k}$ possible (equally likely) ways of choosing $k$ socks among the $2n$ socks in the drawer. If there is no match, we must have drawn $k$ socks of different colors. There are $\binom{n}{k}$ ways to choose the $k$ colors and $2^k$ ways to pick the socks once the colors are chosen. Putting everything together and performing some algebraic manipulations, we obtain:
\[
q_k = \frac{\binom{n}{k} 2^k}{\binom{2n}{k}}
= \frac{n! \cdot (2n-k)! \cdot 2^k}{(2n)! \cdot (n-k)!}
= \frac{ \binom{2n-k}{n} 2^k }{\binom{2n}{n}}
\]Let’s also define $p_k = \textbf{P}(T=k)$ to be the probability that the game ends on precisely the $k^\text{th}$ draw. Note that $q_{k} = p_{k+1}+p_{k+2}+\cdots+p_{n+1}$, or alternatively, $p_k = q_{k-1}-q_k$. From the definition of expected value:
\[
\textbf{E}(T) = \sum_{k=1}^{n+1} k\,p_k = \sum_{k=1}^{n+1}k(q_{k-1}-q_k) = \sum_{k=0}^n q_k
\]This is a manifestation of the general fact that $\textbf{E}(T) = \sum_{k\ge 0}\textbf{P}(T > k)$. Make the change $k\mapsto n-k$ in the expectation:
\[
\textbf{E}(T) = \frac{\sum_{k=0}^n \binom{2n-k}{n} 2^k}{\binom{2n}{n}}
= \frac{2^n \sum_{k=0}^n \binom{n+k}{k} 2^{-k}}{\binom{2n}{n}}
\]Consider the sum in the numerator. Define:
\[
S_n = \sum_{k=0}^n \binom{n+k}{k} 2^{-k}
\]We can evaluate this sum recursively:
\begin{align}
S_{n+1} &= \sum_{k=0}^{n+1} \binom{n+k+1}{k} 2^{-k} \\
&= \sum_{k=0}^{n+1}\left[ \binom{n+k}{k} + \binom{n+k}{k-1} \right] 2^{-k} \\
&= \sum_{k=0}^{n+1} \binom{n+k}{k}2^{-k} + \sum_{k=0}^{n+1} \binom{n+k}{k-1} 2^{-k} \\
&= S_n + \binom{2n+1}{n+1}2^{-n-1} + \sum_{k=0}^{n} \binom{n+k+1}{k} 2^{-k-1} \\
&= S_n + \tfrac{1}{2}S_{n+1}
\end{align}Solving, we obtain $S_{n+1} = 2S_n$, and therefore conclude that $S_n = 2^n$. Substituting this result back into the formula we had above, we obtain:

$\displaystyle
\textbf{E}(T) = \frac{4^n}{\binom{2n}{n}}
$

To get a feel for how this expression varies with $n$, we can use Stirling’s approximation, which leads us to the approximation:
\[
\textbf{E}(T) \approx \sqrt{\pi n}
\]So the expected number of socks we’ll have to draw grows as the square root of the number of pairs. For example, when we have $n=10$ pairs of socks, $\textbf{E}(T) = \frac{262144}{46189}\approx 5.67546$. Meanwhile, the approximation yields $\sqrt{10\pi} \approx 5.60499$. The approximation gets better as $n$ gets larger. Here is a plot showing the true expected value and the approximation:

Computing the distribution

We have the expectation $\textbf{E}(T) = \frac{4^n}{\binom{2n}{n}} \approx \sqrt{\pi n}$. But what about the distribution of $T$ itself? Does it approach anything interesting as $n$ gets large? First, we need to compute the exact probability mass function, which is nothing other than $p_k$. We can do this from the recursion we derived earlier: $p_k = q_{k-1}-q_k$. This simplifies to:
\[
p_k = \frac{k-1}{n-k+1} \frac{\binom{2n-k}{n} 2^{k-1} }{\binom{2n}{n}}\qquad\text{for }k=1,2,\dots,n+1
\]We can plot these distributions along with their means to see what it looks like. Here are the distributions of $T$ for $n=\{10,20,50,100\}$.

To understand what this distribution looks like as $n$ gets very large, we have to do a bit of asymptotic analysis. This part is a little rough around the edges (read: not particularly rigorous), but it seems to give a reasonable answer. My reasoning was that as $n\to\infty$, $k$ is small compared to $n$ because the mean grows like $\sqrt{n}$. Therefore, we will assume $k \sim \sqrt{n}$.

Using Mathematica, we can look at how $\frac{p_k}{k-1}$ varies for small $k$. Using a series approximation about $k=0$ and $n=\infty$, we find that:
\[
\log\left( \frac{p_k}{k-1} \right) \approx \log(\tfrac{1}{2n}) + O(\tfrac{1}{n}) + \tfrac{5}{4n} k-\tfrac{1}{4n}k^2+O(k^3)
\]Therefore, we conclude that:
\[
p_k \approx \frac{k}{2n} e^{-\tfrac{k^2}{4n}}
\]This means that as $n\to\infty$, the distribution of stopping time $T$ approaches a Rayleigh distribution with parameter $\sigma = \sqrt{2n}$. This also gives the correct mean for large $n$, as the mean of the Rayleigh distribution is $\sigma\sqrt{\frac{\pi}{2}} = \sqrt{\pi n}$. For a comparison, here is the plot for $n=500$ along with the Rayleigh approximation:

Let’s suppose each card starts with $n$ drinks. There are three ways the sequence of buying drinks can end:

1. The first card gets maxed out and the second card has $k$ drinks remaining with $k\ge 1$. This means we purchased a total of $2n-k$ drinks and $n$ of them ended up on the first card. Then, we tried to purchase one additional drink on the first card and the buying stopped. The probability of this occurring is: $(\tfrac{1}{2})^{2n-k+1}\binom{2n-k}{n}$.
2. both cards get maxed out and then we try to buy one more drink on either card. This means we purchased a total of $2n$ drinks and $n$ of them ended up on the first card. The probability of this occurring is $(\tfrac{1}{2})^{2n}\binom{2n}{n}$.
3. The second card gets maxed out and the first card has $k$ drinks remaining with $k\ge 1$. This is exactly analogous to the first case, and the probability of this occurring is again: $(\tfrac{1}{2})^{2n-k+1}\binom{2n-k}{n}$.

Putting all of this together, we end up with a tidy formula for $p(n,k)$, the probability that when the game ends, the other card has exactly $k$ drinks remaining on it:

$\displaystyle
p(n,k) = \frac{1}{2^{2n-k}} \binom{2n-k}{n}
$

To double-check that this is a valid probability mass function, we should have $\sum_{k=0}^n p(n,k) = 1$. This is indeed the case, but it’s rather challenging to verify. Here is a link to the WolframAlpha computation. Here is plot of the probability mass function for $n=50$.

We can now answer the first question: the probability that the other card still has drinks on it is one minus the probability that there are no drinks left, i.e. $1-p(n,0)$. This evaluates to:

$\displaystyle
\mathrm{Prob}\Bigl(\begin{smallmatrix}\text{there are drinks left}\\\text{on the other card}\end{smallmatrix}\Bigr)
= 1-\frac{1}{4^n} \binom{2n}{n} \approx 1-\frac{1}{\sqrt{\pi n}}
$

This makes sense; the only way there can be no drinks left is if we purchased $2n$ drinks, and we were lucky to use each card exactly $n$ times. We would expect this probability to get smaller as $n$ gets larger. The approximation I used above comes from Stirling-like approximations for binomial coefficients (see here). When $n=50$ as in the problem statement, the probability evaluates to $92.04\%$. Here is a plot showing how the probability of there being drinks on the other card slowly tends to $1$ as $n$ gets larger:

Now let’s address the second question: what is the expected number of drinks on the other card? We will compute the expected value directly from the probability mass function: $E_n = \sum_{k=0}^n k\, p(n,k)$. We find:

$\displaystyle
\mathbb{E}\Bigl(\begin{smallmatrix}\text{number of drinks left}\\\text{on the other card}\end{smallmatrix}\Bigr)
= \frac{2n+1}{4^n}\binom{2n}{n}-1 \approx \frac{2n+1}{\sqrt{\pi n}}-1
$

Again, the derivation is challenging so I omitted it, but here is the WolframAlpha link. Here is a plot of this function as it changes with $n$ along with the approximation (which is quite good!)

When $n=50$ as in the problem statement, the expected number of drinks remaining on the other card is $7.0385$. This corresponds to the expected value of the probability distribution plotted in the first image.

This problem is short and sweet. The probability in question seems complicated, because there are so many different ways in which a song (or several songs) could repeat. This is made much easier by using complementarity. Namely:
\[
\mathrm{Prob}(\text{at least one song repeats}) = 1-\mathrm{Prob}(\text{no songs repeat})
\]And the probability that no songs repeat is simply the probability that all songs are different. This is much easier to calculate! Let’s call $p$ the probability that at least one song gets played twice and let’s say there are $n$ different songs on the playlist. Then we have:
\begin{align}
p &= 1-\mathrm{Prob}(\text{all }100\text{ songs are different})\\
&= 1-\frac{(\text{number of ways of picking }100\text{ different songs})}{(\text{number of ways of picking }100\text{ songs})}\\
&= 1-\frac{n(n-1)(n-2)\cdots(n-99)}{n^{100}} \\
&= 1-\binom{n}{100}\frac{100!}{n^{100}}
\end{align}Of course, this formula is only valid if $n\ge 100$. If there aren’t at least $100$ songs, then by the Pigeonhole Principle, a song getting picked twice is inevitable. The formula for the probability $p$ of hearing at least one repeated song as a function of the number of different songs $n$ is therefore:

$\displaystyle
p = \begin{cases}
1 & \text{if }1 \le n \le 99\\
1-\binom{n}{100}\frac{100!}{n^{100}} & \text{if }n \ge 100
\end{cases}
$

We can make a plot of this function to see how it changes as a function of $n$:

As expected, the probability remains at or near $1$ for awhile, and then drops once the number of songs on the playlist gets very large. Searching near $p=0.5$ as stated in the problem, the closest candidate $n$ values are:
\begin{align}
n=7174\quad&\implies\quad p=0.50002836 \\
n=7175\quad&\implies\quad p=0.49997983
\end{align}The closest to $p=0.5$ is attained by $n=7175$, so we’ll go with that!