The following problem appeared in The Riddler. It’s an interesting recursive problem.
Each of the seven dwarfs sleeps in his own bed in a shared dormitory. Every night, they retire to bed one at a time, always in the same sequential order, with the youngest dwarf retiring first and the oldest retiring last. On a particular evening, the youngest dwarf is in a jolly mood. He decides not to go to his own bed but rather to choose one at random from among the other six beds. As each of the other dwarfs retires, he chooses his own bed if it is not occupied, and otherwise chooses another unoccupied bed at random.
- What is the probability that the oldest dwarf sleeps in his own bed?
- What is the expected number of dwarfs who do not sleep in their own beds?
Here is my solution.
[Show Solution]
We’ll solve the problem in full generality and suppose $n$ is the total number of dwarfs (dwarves?). Let’s begin by numbering the dwarfs and their corresponding beds $1,2,\dots,n$, where dwarf $1$ is the first to go bed and dwarf $n$ is the last. Let’s also define:
\begin{align}
a\to b &= \text{The event that dwarf }a\text{ sleeps in bed }b.\\
\neg k &= \text{The event that dwarf }k\text{ does not sleep in their own bed.} \\
&= \text{The event that bed }k\text{ is occupied when dwarf }k\text{ goes to bed.}
\end{align}Note the two equivalent definitions for $\neg k$, since the dwarfs always prefer to sleep in their own beds. A dwarf does not sleep in their own bed precisely when their bed is occupied at bedtime.
If any dwarf except the first dwarf does not sleep in their own bed, it must be that another dwarf is already sleeping there. Therefore, we have:
\begin{align*}
\mathbb{P}(\neg k) &= \mathbb{P}(1\to k \text{ or } 2\to k \text{ or } \dots \text{ or } k-1\to k) \\
&= \sum_{i=1}^{k-1} \mathbb{P}(i\to k)\qquad\text{for }k=2,\dots,n
\end{align*}The probabilities simply sum together because they represent mutually exclusive events; two dwarfs can’t both be sleeping in the same bed. Next, observe that:
\begin{align*}
\mathbb{P}(a \to b) &= \mathbb{P}( a \to b \,\vert\, \neg a )\, \mathbb{P}( \neg a )\\
&= \frac{1}{n-a+1}\mathbb{P}(\neg a) \qquad\text{for }a=2,\dots,b-1
\end{align*}This follows because when a dwarf doesn’t sleep in their own bed, it’s always because their bed is occupied. The conditional probability evaluates to $\frac{1}{n-a+1}$ because by the time dwarf $a$ goes to bed, there are already $a-1$ dwarfs in bed, so there are only $n-a+1$ beds left to choose from.
It remains to set the initial condition. According to the problem statement, the first dwarf always sleeps in the wrong bed. Therefore, $\mathbb{P}(\neg 1) = 1$ and $\mathbb{P}(1\to b) = \frac{1}{n-1}$ for $b=2,\dots,n$. Substituting into the above, we can write a clean expression for the recursion and its initial condition:
\begin{align}
\mathbb{P}(\neg 1) &= 1 \\
\mathbb{P}(\neg k) &= \frac{1}{n-1} + \sum_{i=2}^{k-1} \frac{1}{n-i+1}\mathbb{P}(\neg i) \qquad\text{for }k=2,\dots,n
\end{align}This isn’t bad, but we can do better! By taking a second difference, we can formulate an equivalent recursion that doesn’t require a sum over all terms. For convenience, let’s define $p(k) = \mathbb{P}(\neg k)$. Substituting the above equations into $p(k+1)-p(k)$ and simplifying, we obtain:
\begin{align}
p(1) &= 1,\quad p(2) = \tfrac{1}{n-1}\\
p(k+1) &= \left(1+\tfrac{1}{n-k+1}\right)p(k)\qquad\text{for }k=2,\dots,n
\end{align}The recurrence is a telescoping product that we can solve explicitly:
\begin{align}
p(1) &= 1\\
p(k) &= \frac{n}{(n-1)(n-k+2)}\qquad\text{for }k=2,\dots,n
\end{align}Now that we have a closed-form expression for $p(k)$, we can answer just about any question about the dwarfs and their sleeping situation.
Problem 1
Back to the problems! The first question was to find the probability that the oldest dwarf sleeps in his own bed. This is simply $1-p(n)$. Therefore, the probability that the oldest dwarf sleeps in his own bed is $\frac{n-2}{2(n-1)}$, or $\frac{5}{12}\approx 41.67\%$ in the case where $n=7$.
This gets interesting if we look at other values of $n$. When $n=1$, the quantity is rightfully undefined. When $n=2$, the probability is zero. This makes sense because with only two dwarfs, the first dwarf always sleeps in the oldest dwarf’s bed, so the oldest dwarf never sleeps in his own bed. As $n\to\infty$, the probability tends to $\frac{1}{2}$. With a bit more algebra, we can deduce that with a large number of dwarfs, the $(n-p)^\text{th}$ dwarf sleeps in his own bed with a probability of $\frac{p+1}{p+2}$. i.e. the second oldest sleeps in his own bed with probability $\frac{2}{3}$, the third oldest with probability $\frac{3}{4}$, and so on.
Problem 2
The second problem asks for the expected number of dwarfs that do not sleep in their own beds. Let’s call this quantity $E_n$. Define
\[
Y_k = \begin{cases}1 & \text{if }\neg k\\0 & \text{otherwise}\end{cases}
\]In other words, $Y_k$ counts whether the $k^\text{th}$ dwarf doesn’t sleep in their own bed. The total number of dwarfs that do not sleep in their own bed is $Y_1+\dots+Y_n$. Therefore, by linearity of expectation, we have:
\begin{align}
E_n &= \mathbb{E}(Y_1+\dots+Y_n) \\
&= \sum_{k=1}^n \mathbb{E}(Y_k) \\
&= \sum_{k=1}^n \mathbb{P}(\neg k) \\
&= 1+\sum_{k=2}^n \frac{n}{(n-1)(n-k+2)} \\
&= 1+\frac{n}{n-1} \left( \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n} \right)
\end{align}Therefore, when $n=7$, the expected number of dwarfs that do not sleep in their own beds is $E_7 = \frac{343}{120}\approx 2.8583$.
Looking at extremes once again, when $n=2$, we have $E_2=2$. This makes sense because with two dwarfs, both always sleep in the wrong bed, so the number of dwarfs not sleeping in their own bed is always exactly $2$. As $n\to\infty$, we can obtain lower and upper bounds for $E_n$ by using the logarithmic approximation to the harmonic series:
\[
\tfrac{n}{n-1}\log(n+1)-\tfrac{1}{n-1} < E_n < \tfrac{n}{n-1}\log(n)+1
\]Therefore $E_n$ grows like $\log(n)$ as $n\to\infty$. If we want an asymptotically tight approximation instead, we can write:
\[
E_n \approx \log(n)+\gamma
\]Where $\gamma \approx 0.5772$ is the Euler–Mascheroni constant.
