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).