Book Proofs

A natural first step is to find the probability that one button will be lit, that two buttons will be lit, and so on. Using all these probabilities, we can then compute the expected number of lit buttons. While it’s possible to solve the problem this way, it turns out to be the path of most resistance. For a single lit button, it’s not too difficult to see that the probability is $ 1/M^{N-1}$. But as we try to count the number of ways that exactly two, or three, or more buttons can be lit, it becomes increasingly difficult to keep track of all the possibilities while avoiding double-counting.

Since the riddle doesn’t ask for individual probabilities, is it possible to calculate the expected number of lit buttons without calculating the individual probabilities? Yes!

Let $P(k,n)$ be the probability that $ k$ lights are off after $ n$ people have pressed a button (we’re counting the number of lights off rather than the number of lights on because it makes the math a little simpler). As mentioned above, these are difficult to compute. As we’ll see, we can solve the problem without ever computing them! Suppose that the $(n+1)$st person now comes along, presses their desired button, and there are now $ k$ lights off. This could have happened in two ways:

1. $k$ lights were off prior, and the $(n+1)$st button press didn’t change anything. This means one of the $(M-k)$ on-lights was pressed, which would have happened with probability $\frac{M-k}{M}$.
2. $k+1$ lights were off prior, and the $(n+1)$st button press turned on a light that was previously off. This means one of the $ (k+1)$ off-lights was pressed, which would have happened with probability $\frac{k+1}{M}$.

Therefore, we can write a recursion that describes how the probability changes as more people press a button:

\[
P(k,n+1) = \frac{M-k}{M} P(k,n) + \frac{k+1}{M} P(k+1,n)
\]

What we’re really after is the expected number of lights that are off after $ n$ people have made their selection. We’ll call this quantity $ \theta(n)$. The expected value is obtained by summing up each possible number of lights off, weighed by its corresponding probability. Applying this definition together with the recursion from above, we obtain:

\begin{align}
\theta(n+1) &= \sum_k k P(k,n+1) \\
&= \sum_k k \left( \frac{M-k}{M} P(k,n) + \frac{k+1}{M} P(k+1,n) \right) \\
&= \sum_k \left( k \frac{M-k}{M} P(k,n) + k \frac{k+1}{M} P(k+1,n) \right) \\
&= \sum_k \left( k \frac{M-k}{M} P(k,n) + (k-1) \frac{k}{M} P(k,n) \right) \\
&= \sum_k k \frac{M-1}{M} P(k,n)\\&= \left(1-\frac{1}{M}\right)\theta(n)\\
\end{align}

This recursion tells us how the expected number of lights off changes as more people are added but, amazingly, it does not depend on the individual $ P(k,n)$ probabilities! All lights are off when the elevator is empty, so $ \theta(0) = M$. We conclude that:

\[
\theta(N) = \left( 1-\frac{1}{M} \right) \theta(N-1)
= \dots = \left( 1-\frac{1}{M} \right)^N \theta(0)
= M \left( 1-\frac{1}{M} \right)^N
\]

Finally, the riddle asks for the expected number of lights on, which is $ M$ minus the expected number of lights off. Putting everything together, we obtain the final solution: the expected number of lit buttons is:

$\displaystyle
M\left( 1-\left( 1-\frac{1}{M} \right)^N \right)
$

As a sanity check, note that the formula simplifies to 0 when $ N=0$ and to 1 when $ N=1$, which are the answers we expect. Also, as $ N\to\infty$, the formula asymptotically approaches $ M$, which also makes sense. The formula is valid regardless of whether there are more people than floors or more floors than people.

An interesting fact is that if $ M=N$ (as many people as floors) and we take the limit as the number of floors goes to infinity, the fraction of lit buttons will tend to $ 1-1/e$, which is approximately 63.2%.

Define the random variable $X_k$ as:

\[
X_k = \begin{cases}
1 & \text{if button }k\text{ is lit} \\
0 & \text{otherwise}
\end{cases}
\]

We are interested in the expected number of lit buttons, which is:

\[
\mathbb{E}\left[ \sum_k X_k\right] = M \mathbb{E}\left[ X_1 \right]
\]

This follows because each $ X_k$ has an identical distribution so we only need to compute the expected value for one of the buttons and multiply the result by the total number of buttons. Now we can compute:

\begin{align}
\mathbb{E}[X_1] &= \mathrm{Prob}(\text{first button is pressed at least once}) \\
&= 1-\mathrm{Prob}(\text{first button is never pressed})\\
&= 1-\left(\frac{M-1}{M}\right)^N
\end{align}

Therefore, the expected number of lit buttons is:

$\displaystyle
M\left( 1-\left( 1-\frac{1}{M} \right)^N \right)
$