Taking down all the bottles of beer
Probability, Calculus; Difficulty: medium
Can you take down all the bottles of beer?
This week’s Riddler Classic is a probability question based on the popular reverse cumulative song 99 bottles of beer on the wall. The extra credit requires a bit of calculus. The Classic reproduced:
You and your friends are singing the traditional song, “99 Bottles of Beer.” With each verse, you count down the number of bottles. The first verse contains the lyrics “99 bottles of beer,” the second verse contains the lyrics “98 bottles of beer,” and so on. The last verse contains the lyrics “1 bottle of beer.”
There’s just one problem. When completing any given verse, your group of friends has a tendency to forget which verse they’re on. When this happens, you finish the verse you are currently singing and then go back to the beginning of the song (with 99 bottles) on the next verse.
For each verse, suppose you have a 1 percent chance of forgetting which verse you are currently singing. On average, how many total verses will you sing in the song?
Extra credit: Instead of “99 Bottles of Beer,” suppose you and your friends are singing “N Bottles of Beer,” where N is some very, very large number. And suppose your collective probability of forgetting where you are in the song is 1/N for each verse. If it takes you an average of K verses to finish the song, what value does the ratio of K/N approach?
*spoiler alert* solution and answer follow below
Solution
Let \(E_n\) represent the expected number of verses sung once the group is at the beginning of verse \(n\). At the end of any verse, the group either goes back to the top of the song—verse \(N\) (\(= 99\) in the traditional song) with probability \(q\) or moves ahead to the next verse with probability \(p\), where \(p+q = 1\).
Conditioning the expectation on the next verse, we have the following recursive relationship:
\begin{align*}
E_n &= (E_n | \ \textit{move to next verse})p \ + \ (E_n | \ \textit{move to first verse})q \\
E_n &= (1+E_{n-1})p + (1 + E_N)q \qquad (2 \leq n \leq N)\\
& \textit{(since there is one verse added at the completion of verse n)} \\
&= p + q + pE_{n-1} + qE_N \\
E_n &= 1 + pE_{n-1} + qE_N \\ \\
& \textit{and} \\ \\
E_1 &= 1\cdot p + (1 + E_N)q \\
E_1 &= 1 + qE_N
\end{align*}
Note: It is assumed that even when on verse number 1, there is the same \(q\) probability that the group forgets they are on the final verse and goes back to the start.
Using the above equations and working back it is easy to see that:
\begin{align*}
E_2 &= 1 + p +pqE_N + qE_N \\
&= (1+p) + qE_N(1+p) \\ \\
& \textit{and in general} \\ \\
E_n &= (1 + p +p^2 + …+p^{n-1}) + qE_N(1 + p +p^2 + …+p^{n-1}) \qquad (2 \leq n \leq N) \\
E_n &= (1 + qE_N) \left (\frac{1 – p^N}{1-p} \right ) \qquad \textit{(summing the gemetric series)} \\
\Rightarrow \ E_N &= (1+qE_N)\left ( \frac{1 – p^N}{1-p} \right ) \qquad \textit{(applying above for n = N)} \\
\Rightarrow \ E_N &=\frac{1-p^N}{qp^N}
\end{align*}
For the main question, substituting \(N=99, \ p = 0.99 \ q = 0.01 \) gives us the required expected number of verses as 170.47. This group is going to sound like a broken record!
Extra credit
We are asked to calculate the limiting value of \(\displaystyle \frac{E_N}{N}\) as \(N\rightarrow \infty \) with \(q = \displaystyle \frac{1}{N} \) and \(p = 1 – \displaystyle \frac{1}{N} \)
\begin{align*}
\lim_{N\to \infty }\frac{E_N}{N} &= \lim_{N\to \infty } \frac{1-p^N}{Nqp^N} \\
&= \lim_{N\to \infty } \frac{1-p^N}{p^N} \\
&= \lim_{N\to \infty } \frac{1- \left (1-\displaystyle\frac{1}{N} \right)^N}{\left (1-\displaystyle\frac{1}{N} \right)^N} \\
&= \frac{\lim_{N\to \infty }1-\left ( 1-\displaystyle \frac{1}{N}\right )^N}{\lim_{N\to \infty } \left (1-\displaystyle \frac{1}{N}\right )^N} \\ & \textit{(can split num and denom limits, since denom limit is not zero)} \\
& = \frac{1 – \displaystyle \frac{1}{e}}{\displaystyle \frac{1}{e}} \\
& = \mathbf{{\color{Red} {e – 1}}} \\
& \approx \mathbf{{\color{Red} {1.71828}}}
\end{align*}
As seen below, the convergence is fairly rapid.
2 thoughts on “Taking down all the bottles of beer”
I just want to point out: the group sounding like a broken record has a lot less to do with their forgetfulness, and more to do with the chosen song. Even if they weren’t forgetful, they’d still be singing 99 verses of the same song – over half the expected value.
😀 That’s true!