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.
Nicely done! One possible correction: “So, curiously, with a very large number of dwarfs, each dwarf’s probability of sleeping in their own bed is roughly one half!” Isn’t it only the eldest’s probability that tends towards 1/2? The second youngest’s, for instance, tends to one, the second eldest’s tends towards 2/3, the third eldest’s towards 3/4, . . . (The divergence from these values is entirely due to our prohibiting the youngest from randomly landing in his own bed.
https://hectorpefo.github.io/2018-01-06-Strange-Beds/ )
Yes, you’re right. What I was thinking in my head was that the kth eldest dwarf’s probability also tends to 1/2, so in a sense “all dwarfs” have a probability that tends to 1/2. It depends on how you track dwarfs as you increase their number. e.g. if you increase the number of dwarfs by adding more younger ones then every dwarf has a probability that tends to 1/2. I’ll change the text to clarify.
Thanks for sharing your write-up as well!
I’m not sure we’re on the same page yet. One (to me) surprising thing about this puzzle is that, even for large n, the probabilities for the eldest and the second-eldest remain quite different (tending towards 1/2 and 2/3, respectively). Nearly all of the decay in probability from near 1 to near 1/2 happens in the last few dwarfs.
You’re absolutely right. I made a careless error simplifying fractions… I updated my solution yet again. I agree, it’s quite interesting that things change so dramatically when it comes to the last few dwarfs!
Interesting problem. I need a little bit to think about this.
Part 2 looks suspiciously like a coupon collecting result, though superficially I don’t really see the linkage — i.e. this one is expected number of ‘hits’ while the coupon result is expected time until absorption.
Interesting that the problem includes an $\frac{n}{n-1}$ ‘correction’ though, which is reminiscent of the two different ways to calculate Variance — population or sample, and of course doesn’t matter asymptotically (or, for that matter, for moderately large n).
Suppose that the youngest dwarf chooses one of the $n$ beds (including his own bed) at random (the lost boarding pass case). Then Part 2 of the problem has as answer $\sum_{j=1}^{n-1} 1/j$ and the problem looks very much like the following birthday-candle problem. It’s your birthday and you are now $n$ years old. You get a birthday cake with $n$ burning candles. If you blow when there are still $k$ candles burning, then $j$ burning candles will remain, each with probability $1/(k+1)$ for $j=0,1,\ldots, k-1$. What is the expected number of times you must below until there are no burning candles anymore? The answer is $\sum_{k=1}^{n} 1/k$. How to make the ‘translation’ to the problem of the dwarfs?
The probability that the oldest dwarf sleeps in his own bed is (n-2)/(2n-2), n = number of dwarfs.
The result of the formula for 3 dwarfs is (3-2)/(2*3-2)=1/4.
The list of all possibilities for 3 dwarfs looks like:
2 1 3, 3 1 2, 3 2 1.
According to this the probability amounts to 1/3 .
Can you please help me and clarify the situation.
Kind regards,
Walter
Hi Walter,
Your list of all possible sleeping arrangements is correct, but your error is in assuming that each of these sleeping arrangements is equally likely to occur. That’s not the case! In fact, we have:
2 1 3 occurs 1/4 of the time
3 1 2 occurs 1/4 of the time
3 2 1 occurs 1/2 of the time
The reason is that the first dwarf picks bed 3 half the time (? ? 1), but whenever the first dwarf does this, the second dwarf always picks bed 2 and so we always end up with (3 2 1). This means this arrangement occurs 1/2 of the time.
If the first dwarf picks bed 2 instead (? 1 ?), then the other two cases, (2 1 3) and (3 1 2) are equally likely to occur, so they each have probability 1/4.