This problem was originally posted on the Riddler blog. Here it goes:
In a building’s lobby, some number (N) of people get on an elevator that goes to some number (M) of floors. There may be more people than floors, or more floors than people. Each person is equally likely to choose any floor, independently of one another. When a floor button is pushed, it will light up.
What is the expected number of lit buttons when the elevator begins its ascent?
My solution:
[Show Solution]
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:
- $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}$.
- $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%.
A much more elegant solution, courtesy of Ross Boczar
[Show Solution]
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)
$
From the person who submitted the puzzle to The Riddler, congratulations on your clear and elegant solutions!
Great post! Could you elaborate more on how you obtain the 4th line in the derivation of theta(n + 1) = (1 – 1/M) theta(n): how do we know that k (k + 1) P(k + 1, n) = (k – 1) k P(k, n)?
Also minor typo: it should be “This means one of the (M – k) on-lights was pressed” instead of “This means one of the (k-M) on-lights was pressed”
Apologies for the delayed response; my spam filter misclassified your comment!
In the 4th line of the derivation, I replaced $k \mapsto k-1$, which does not change the expression because I am summing over all $k$ and first term in the new sum is zero anyway.
Fixed the typo. Thanks!
If the number of buttons/floors (M) goes to infinity, then doesn’t the solution need to go to N (the number of people who boarded the elevator)? With an infinite number of floors, the odds any one elevator rider will want to duplicate a selection become infinitesimally small. So, it will approach a situation where each rider will almost definitely select their own button. When you check for infinite N, you get the solution M, which you expect, from the given equation. It’s the sanity check for infinite M the doesn’t seem to work here. You should get closer and closer to N for a solution, and this equation yields zero buttons pushed as we approach infinite M. Right?
I like to check at the extremes and zero to confirm for myself that the solution I arrived at could possibly be the solution. (With zero floors, you get zero buttons. Check. With zero people, you get zero buttons. Check.)
Great question — the limit of infinite $M$ does in fact work. To see why, expand the $(1-\tfrac{1}{M})^N$ term using the binomial theorem, which leads to $1-\tfrac{N}{M} + {N \choose 2}\tfrac{1}{M^2}-{N \choose 3}\tfrac{1}{M^3} + \dots + (-1)^N {N \choose N} \tfrac{1}{M^N}.$ Substituting this into the solution, you’re left with:
\[
N-{N \choose 2} \frac{1}{M} + \text{(higher powers of }\tfrac{1}{M}\text{)}
\]
So as $M\to\infty$, you do recover $N$, as expected. In fact, for very large $M$, the formula above tells you that the solution will be slightly smaller than $N$, which also makes sense.
Thanks. I guess sanity checks aren’t always the “easy part”! Smart guys like you come in handy.
Thanks for the two different solutions. Actually, this is just a very classic “coupon collection” problem.
Care to elaborate? I don’t see how this is a coupon collector problem…
Sure. One coupon collector problem asks: given M different coupons, each time you collect one coupon, randomly, with replacement, what is the expected time to collect all M different coupons. The other coupon collector problem asks: also M different coupons, each time you collect one coupon, randomly, with replacement; you collect N times, what is the expected number of different coupons you would get? For both problems, we can use the trick of decomposing the expectation into summations. The latter one corresponds this elevator button problem (view M buttons as coupons and N people as collecting N times).
Very nice, thanks!