{"id":3601,"date":"2023-02-04T00:43:54","date_gmt":"2023-02-04T06:43:54","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=3601"},"modified":"2023-02-04T10:12:52","modified_gmt":"2023-02-04T16:12:52","slug":"n-bottles-of-beer","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/n-bottles-of-beer\/","title":{"rendered":"N Bottles of Beer"},"content":{"rendered":"

This week’s Riddler Classic<\/a> is puzzle about the world’s most annoying song.<\/p>\n

\nYou and your friends are singing the traditional song, \u201c99 Bottles of Beer.\u201d With each verse, you count down the number of bottles. The first verse contains the lyrics \u201c99 bottles of beer,\u201d the second verse contains the lyrics \u201c98 bottles of beer,\u201d and so on. The last verse contains the lyrics \u201c1 bottle of beer.\u201d There\u2019s just one problem. When completing any given verse, your group of friends has a tendency to forget which verse they\u2019re 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?<\/p>\n

Extra credit:<\/em> Instead of \u201c99 Bottles of Beer,\u201d suppose you and your friends are singing \u201cN Bottles of Beer,\u201d 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?\n<\/p><\/blockquote>\n

My solution:
\n[Show Solution]<\/a><\/p>\n

\n

Let’s solve a more general version of the problem. Suppose there are $n$ bottles of beer, and there is a probability $p$ of forgetting at every verse. Define $E_k$ to be the expected number of additional verses we will sing assuming we are currently singing verse $k$. Our task is to solve for $E_1$. Since at each verse, we have a probability $p$ of returning to verse $1$, and a probability $1-p$ of moving to the next verse, we can write:<\/p>\n

\\begin{align}
\nE_1 &= 1 + p E_1 + (1-p) E_2 \\\\
\nE_2 &= 1 + p E_1 + (1-p) E_3 \\\\
\n&\\;\\vdots \\\\
\nE_{n-2} &= 1 + p E_1 + (1-p) E_{n-1} \\\\
\nE_{n-1} &= 1 + p E_1 + (1-p)
\n\\end{align}In the last equation, we substituted $E_n=1$, since if we start on the last verse, we will sing that verse and the song will end. We have a system of $n-1$ equations in the unknowns $E_1,E_2,\\dots,E_{n-1}$ and our task is to solve for $E_1$.<\/p>\n

The obvious approach is to use back-substitution<\/em>: solve for $E_{n-1}$ in the last equation, substitute into the previous equation to solve for $E_{n-2}$, and continue in this fashion until we reach the first equation. However this leads to a complicated formula. A more efficient approach is to multiply the $k^\\text{th}$ equation by $(1-p)^{k-1}$, and obtain:<\/p>\n

\\begin{align}
\nE_1 &= 1 + p E_1 + (1-p) E_2 \\\\
\n(1-p)E_2 &= (1-p)(1 + p E_1) + (1-p)^2 E_3 \\\\
\n(1-p)^2E_3 &= (1-p)^2(1 + p E_1) + (1-p)^3 E_4 \\\\
\n&\\;\\vdots \\\\
\n(1-p)^{n-3}E_{n-2} &= (1-p)^{n-3}(1 + p E_1) + (1-p)^{n-2} E_{n-1} \\\\
\n(1-p)^{n-2}E_{n-1} &= (1-p)^{n-2}(1 + p E_1) + (1-p)^{n-1} E_n
\n\\end{align}We can get all the terms involving $E_2,\\dots,E_{n-1}$ to cancel if we add all these equations together. This yields:<\/p>\n

\\begin{align}
\nE_1 &= (1 + p E_1)\\sum_{k=0}^{n-2} (1-p)^{k} + (1-p)^{n-1} \\\\
\n&= (1+ p E_1) \\frac{1-(1-p)^{n-1}}{p} + (1-p)^{n-1} \\\\
\n&= \\frac{1-(1-p)^{n-1}+p(1-p)^{n-1}}{p} + \\bigl(1-(1-p)^{n-1}\\bigr)E_1 \\\\
\n&= \\frac{1-(1-p)^{n}}{p} + \\bigl(1-(1-p)^{n-1}\\bigr)E_1
\n\\end{align}Now solve for $E_1$ and obtain<\/p>\n

$\\displaystyle
\nE_1 = \\frac{1-(1-p)^{n}}{p(1-p)^{n-1}}
\n$<\/span><\/p>\n

As a simple sanity check, if $n=1$, we obtain $E_1=1$ as we should. It’s also possible to check that if $p\\to 0$, we get $E_1\\to n$. The problem asks what happens to the ratio $E_1\/n$ if we set $p=1\/n$ and $n$ is very large. We can write this as<\/p>\n

\\begin{align}
\n\\lim_{n\\to\\infty}\\left.\\frac{E_1}{n}\\right|_{p=\\frac{1}{n}} &= \\lim_{n\\to\\infty} \\frac{1}{n}\\frac{1-\\left(1-\\tfrac{1}{n}\\right)^{n}}{\\tfrac{1}{n}\\left(1-\\tfrac{1}{n}\\right)^{n-1}} \\\\
\n&= \\lim_{n\\to\\infty} \\frac{1-\\left(1-\\tfrac{1}{n}\\right)^{n}}{\\left(1-\\tfrac{1}{n}\\right)^{n-1}} \\\\
\n&= \\frac{1-e^{-1}}{e^{-1}} \\\\
\n&= e-1 \\\\
\n&\\approx 1.71828
\n\\end{align}In the second-last step, we used the well-known fact<\/a> that $\\lim_{n\\to\\infty} \\left(1+\\frac{x}{n}\\right)^{n} = e^x$, which implies that $\\lim_{n\\to\\infty} \\left(1-\\frac{1}{n}\\right)^{n} = e^{-1}$.<\/p>\n

We can verify this limit by plotting $\\frac{1}{n}E_1$ with $p=\\frac{1}{n}$, which yields<\/p>\n

\"\"\n<\/div>\n","protected":false},"excerpt":{"rendered":"

This week’s Riddler Classic is puzzle about the world’s most annoying song. You and your friends are singing the traditional song, \u201c99 Bottles of Beer.\u201d With each verse, you count down the number of bottles. The first verse contains the lyrics \u201c99 bottles of beer,\u201d the second verse contains the lyrics \u201c98 bottles of beer,\u201d … Continue reading “N Bottles of Beer”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"_uf_show_specific_survey":0,"_uf_disable_surveys":false,"footnotes":""},"categories":[7],"tags":[8,2],"class_list":["post-3601","post","type-post","status-publish","format-standard","hentry","category-riddler","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3601","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/comments?post=3601"}],"version-history":[{"count":5,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3601\/revisions"}],"predecessor-version":[{"id":3608,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3601\/revisions\/3608"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=3601"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=3601"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=3601"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}