Book Proofs

A simpler problem: coin flips

A popular (and simpler) version of this problem is the following: “I have a coin that comes up heads with probability $p$ and tails with probability $1-p.$ If I flip the coin until I get heads, how many flips will I make, on average?”. The standard approach to solving this problem is to enumerate all the possibilities:

• “H” (one flip), probability $p$.
• “T,H” (two flips), probability $(1-p)p$.
• “T,T,H” (three flips), probability $(1-p)^2p$.
• … (and so on)

To get the expected number of flips, you then multiply each number of flips with its associated probability and sum them:

\[
\sum_{k=1}^\infty k (1-p)^{k-1}p
= -p\,\frac{\mathrm{d}}{\mathrm{d}p} \sum_{k=1}^\infty (1-p)^k
= -p\,\frac{\mathrm{d}}{\mathrm{d}p} \left(\frac{1}{p}\right)
= \frac{1}{p}
\]

This is a pretty standard summation, and there are many ways of evaluating it. One particularly nice approach is to use recursion. Let $X$ be the expected number of flips. After we flipped our first coin, if our first flip was H (probability $p$), we stop flipping so there is no additional length added. If our first flip was a $T$ (probability $1-p$), then we will add $X$ more flips on average. Therefore: $X = 1 + p \cdot 0 + (1-p)\cdot X$. Solving for $X$, we find $X = \frac{1}{p}$, as before. This recursive approach works because the stopping criterion (flipping H) does not depend on what our previous flips were.

Back to monster slaying

We’ll use the recursive approach from the coin-flipping problem to solve the monster slaying problem. What makes this version more difficult is that the coin flips are not all independent. In other words, whether we should stop flipping coins (slaying monsters) depends on which types of gems we have accumulated so far. Let’s say the three types of gems are $p, q, r$. I’ll use the same variable names to denote the respective probability of each gem occurring. The first thing to realize is that to count the expected number of $p$’s that occur, it’s equivalent to count the total number of gems that occur and multiply the result by $p$. This follows from linearity of expectation. Specifically, if the sequence of gems has length $n$ and $X_i$ tells us whether gem $i$ is a $p$ or not, we have:

\begin{multline}
\mathbb{E}\left[\sum_{i=1}^n X_i\right]
= \mathbb{E}\left[ \mathbb{E}\left[ \sum_{i=1}^n X_i \,\middle|\, n \right] \right]
= \mathbb{E}\left[\sum_{i=1}^n \mathbb{E}\left[ X_i\,\middle|\, n \right] \right]\\
= \mathbb{E}\left[\sum_{i=1}^n \mathbb{E}\left[ X_i \right]\right]
= \mathbb{E}\left[ np \right]
= p\, \mathbb{E}[ n ]
\end{multline}

We stop collecting gems once we have at least one of each type of gem. We’ll need several variables to properly characterize our current state of gem accumulation. Define the following:

• $X$: the expected number gems we’ll collect from now on, assuming we haven’t collected any gems yet (this is $\mathbb{E}[n]$).
• $X_p$ (similarly $X_q, X_r$): the expected number gems we’ll collect from now on, assuming our current collection includes at least one $p$ gem.
• $X_{pq}$ (similarly $X_{pr}, X_{qr}$): the expected number gems we’ll collect from now on, assuming our current collection includes at least one $p$ gem and at least one $q$ gem.

The expected number of gems we expect to collect in the future depends on type of gem we get first. We can write the following recursion:

\[
X = 1 + p X_p + q X_q + r X_r
\]

In other words, if our first gem was $p$, we can expect $X_p$ subsequent $p$ gems, plus the first one we just collected. In the other cases, for example if the first gem is $q$, then we can expect $X_q$ subsequent $p$ gems. We can write similar recursions for when we’ve collected our first gem:

\begin{align}
X_p &= 1 + p X_p + q X_{pq} + r X_{pr} \\
X_q &= 1 + p X_{pq} + q X_q + r X_{qr} \\
X_r &= 1 + p X_{pr} + q X_{qr} + r X_r
\end{align}

And, recursions for when we’ve collected two different gems:

\begin{align}
X_{pq} &= 1 + p X_{pq} + q X_{pq} + r \cdot 0 \\
X_{pr} &= 1 + p X_{pr} + q \cdot 0 + r X_{pr} \\
X_{qr} &= 1 + p \cdot 0 + q X_{qr} + r X_{qr}
\end{align}

The last three recursions are decoupled. Solving them, we obtain:

\begin{gather}
X_{pq} = \frac{1}{1-p-q} = \frac{1}{r},\quad
X_{pr}=\frac{1}{1-p-r} = \frac{1}{q},\\
X_{qr}= \frac{1}{1-q-r} = \frac{1}{p}
\end{gather}

In the final equalities, we used the fact that $p + q + r = 1$. These results shouldn’t be surprising — once you’ve already obtained at least one $p$ and one $q$, the problem it simply to count how many more flips until you obtain $r$, and this is precisely the coin-flipping problem! Substituting into the previous set of recursions, we obtain:

\begin{gather}
X_p = \frac{1}{1-p}\left( 1 + \frac{q}{r} + \frac{r}{q}\right),\quad
X_q = \frac{1}{1-q}\left( 1 + \frac{p}{r} + \frac{r}{p}\right),\\
X_r = \frac{1}{1-r}\left( 1 + \frac{p}{q} + \frac{q}{p}\right)
\end{gather}

Finally, substitute these findings into the recursion for $X$, and obtain:

\begin{multline}
X = 1 + \frac{p}{1-p}\left( 1 + \frac{q}{r} + \frac{r}{q}\right)
+ \frac{q}{1-q}\left( 1 + \frac{p}{r} + \frac{r}{p}\right) \\
+ \frac{r}{1-r}\left( 1 + \frac{p}{q} + \frac{q}{p}\right)
\end{multline}

We can now substitute the values $p = \frac{1}{2}$, $q = \frac{1}{3}$, and $r = \frac{1}{6}$ and we obtain that the sequence will have expected length $\mathbb{E}[n] = X = \frac{73}{10}$. Therefore, the expected number of common gems is simply $p \,\mathbb{E}[n] = \frac{73}{20}.$

$\displaystyle
(\text{Expected number of common gems}) = \frac{73}{20} = 3.65
$

As in the previous solution, we’ll label the gems $p$, $q$, $r$ and use this notation for the respective probabilities as well. Moreover, we’ll work on computing the expected sequence length. Let $\mathbb{P}(n,k)$ be the probability that a sequence of gems has length $n$ and terminates with gem $k$. What we’d like to find is:

\[
\mathbb{E}[n] = \sum_{n=3}^\infty n \left( \mathbb{P}(n,p) + \mathbb{P}(n,q) + \mathbb{P}(n,r) \right)
\]

Taking a closer look at $\mathbb{P}(n,p)$, for example, we see that $\mathbb{P}(n,p)$ is the probability of the sequence consisting of $(n-1)$ $q$’s and $r$’s (at least one of each), and terminating with $p$. The probability of this happening is:

\[
\mathbb{P}(n,p) = p\left( (q+r)^{n-1} – q^{n-1} – r^{n-1} \right)
\]

since we must exclude the sequences consisting of all $q$’s or all $r$’s. Define: $f(x) = \sum_{n=3}^\infty n x^{n-1}$. Then we can write:

\begin{multline}
\mathbb{E}[n] = p\left( f(q+r)-f(q)-f(r) \right) \\
+ q\left( f(p+r)-f(p)-f(r) \right) \\
+ r\left( f(p+q)-f(p)-f(q) \right)
\end{multline}

So it remains to evaluate $f$. Notice that:

\[
f(x) = \sum_{n=3}^\infty n x^{n-1} = \frac{\mathrm{d}}{\mathrm{d}x} \sum_{n=3}^\infty x^n = \frac{\mathrm{d}}{\mathrm{d}x} \frac{x^3}{1-x} = \frac{3x^2-2x^3}{(1-x)^2}
\]

So that’s it! It remains to substitute $p=\tfrac12$, $q=\tfrac13$, $r=\tfrac16$, and to evaluate $\mathbb{E}[n]$. Doing so, we find $\mathbb{E}[n]=\tfrac{73}{10}$. Therefore, the expected number of common gems is $\mathbb{E}[p n]=\tfrac{73}{20}$.

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