{"id":4149,"date":"2024-10-27T16:55:25","date_gmt":"2024-10-27T21:55:25","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=4149"},"modified":"2024-10-29T11:14:47","modified_gmt":"2024-10-29T16:14:47","slug":"halloween-puzzle","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/halloween-puzzle\/","title":{"rendered":"Halloween Puzzle"},"content":{"rendered":"<p>This week&#8217;s <a href=\"https:\/\/thefiddler.substack.com\/p\/can-you-solve-the-tricky-mathematical\">Fiddler<\/a> is about rounding!<\/p>\n<blockquote><p>\nYou are presented with a bag of treats, which contains $n \\geq 3$ peanut butter cups and some unknown quantity of candy corn kernels (with any amount being equally likely). You reach into the bag $k$ times, with $3 \\leq k \\leq n$, and pull out a candy at random. Each time, it\u2019s a peanut butter cup! How many candy kernels do you expect to be in the bag?\n<\/p><\/blockquote>\n<p>My solution:<br \/>\n<a href=\"javascript:Solution('soln_hallpuzz','toggle_hallpuzz')\" id=\"toggle_hallpuzz\">[Show Solution]<\/a><\/p>\n<div id=\"soln_hallpuzz\" style=\"display: none\">\n<p>Define the following random variables:<\/p>\n<ul>\n<li> $m$: number of candy corn kernels in the bag\n<li> $K$: whether we draw $k$ peanut butter cups in a row (true\/false)\n<\/ul>\n<p>We are asked to calculate the expected number of corn kernels in the bag given that we draw $k$ peanut butter cups in a row. In other words, we want to find $\\mathbb{E}(m\\mid K)$.<\/p>\n<p>An easier quantity to calculate is the probability that we draw $k$ peanut butter cups in a row given that there are $m$ candy corn kernels in the bag. This is given by:<br \/>\n\\begin{align*}<br \/>\n\\mathbb{P}(K\\mid m)<br \/>\n&#038;= \\frac{n}{n+m}\\cdot \\frac{n-1}{n+m-1}\\cdots\\frac{n-k+1}{n+m-k+1} \\\\<br \/>\n&#038;= \\frac{n!(n+m-k)!}{(n-k)!(n+m)!} \\\\<br \/>\n&#038;= \\binom{n}{k}\\binom{n+m}{k}^{-1}<br \/>\n\\end{align*}Using <a href=\"https:\/\/en.wikipedia.org\/wiki\/Bayes%27_theorem\">Bayes&#8217; rule<\/a>, we can express the desired expectation in terms of the conditional probability above:<br \/>\n\\begin{align*}<br \/>\n\\mathbb{E}(m\\mid K)<br \/>\n&#038;= \\sum_{m=0}^\\infty m\\cdot \\mathbb{P}(m\\mid K)<br \/>\n= \\sum_{m=0}^\\infty m\\cdot \\frac{\\mathbb{P}(K \\mid m)\\mathbb{P}(m)}{\\mathbb{P}(K)}<br \/>\n\\end{align*} Now substitute: $\\mathbb{P}(K) = \\sum_{m=0}^\\infty \\mathbb{P}(K\\mid m)\\mathbb{P}(m)$ and obtain:<br \/>\n\\begin{align*}<br \/>\n\\mathbb{E}(m\\mid K)<br \/>\n&#038;= \\frac{\\sum_{m=0}^\\infty m\\cdot \\mathbb{P}(K \\mid m)\\mathbb{P}(m)}{\\sum_{m=0}^\\infty \\mathbb{P}(K \\mid m)\\mathbb{P}(m)} \\\\<br \/>\n&#038;= \\frac{\\sum_{m=0}^\\infty m\\cdot \\mathbb{P}(K \\mid m)}{\\sum_{m=0}^\\infty \\mathbb{P}(K \\mid m)}<br \/>\n\\end{align*}where in the last step, we used the fact that $\\mathbb{P}(m)$ is the same for all $m$ so we canceled it from the numerator and denominator. Substituting our expression for $\\mathbb{P}(K\\mid m)$, we obtain:<br \/>\n\\begin{align*}<br \/>\n\\mathbb{E}(m\\mid K)<br \/>\n&#038;= \\frac{\\sum_{m=0}^\\infty m\\binom{n}{k}\\binom{n+m}{k}^{-1}}{\\sum_{m=0}^\\infty \\binom{n}{k}\\binom{n+m}{k}^{-1}}<br \/>\n= \\frac{\\sum_{m=0}^\\infty m\\binom{n+m}{k}^{-1}}{\\sum_{m=0}^\\infty \\binom{n+m}{k}^{-1}}<br \/>\n%= \\frac{n-k+1}{k-2}<br \/>\n\\end{align*}<br \/>\nTo simplify this, define the following quantity:<br \/>\n\\[<br \/>\nf(k,a,b) := \\sum_{i=a}^b \\binom{i}{k}^{-1}<br \/>\n\\]and observe that we have:<br \/>\n\\[<br \/>\n\\mathbb{E}(m\\mid K) = \\frac{\\sum_{j=1}^\\infty f(k,n+j,\\infty)}{f(k,n,\\infty)}<br \/>\n\\]It turns out we can evaluate $f$, and that it has the nice closed-form expression:<br \/>\n\\[<br \/>\nf(k,a,b) = \\frac{k}{k-1}\\left( \\binom{a-1}{k-1}^{-1}-\\binom{b}{k-1}^{-1}\\right)<br \/>\n\\]This formula can be proved by induction and is related to something called the <a href=\"https:\/\/en.wikipedia.org\/wiki\/Binomial_coefficient#Partial_sums\">German tank problem<\/a>.<\/p>\n<p>With this formula in hand, we can take the limit $b\\to\\infty$ and see that:<br \/>\n\\[<br \/>\nf(k,a,\\infty) = \\frac{k}{k-1}\\binom{a-1}{k-1}^{-1}<br \/>\n\\]Substituting into our expression for the desired expectation, we obtain:<br \/>\n\\begin{align*}<br \/>\n\\mathbb{E}(m\\mid K)<br \/>\n&#038;= \\frac{\\sum_{j=1}^\\infty f(k,n+i,\\infty)}{f(k,n,\\infty)} \\\\<br \/>\n&#038;= \\frac{\\sum_{j=1}^\\infty \\frac{k}{k-1}\\binom{n+j-1}{k-1}^{-1}}{\\frac{k}{k-1}\\binom{n-1}{k-1}^{-1}} \\\\<br \/>\n&#038;= \\binom{n-1}{k-1}\\sum_{j=1}^\\infty \\binom{n+j-1}{k-1}^{-1} \\\\<br \/>\n&#038;= \\binom{n-1}{k-1} f(k-1,n,\\infty) \\\\<br \/>\n&#038;= \\binom{n-1}{k-1} \\frac{k-1}{k-2} \\binom{n-1}{k-2}^{-1} \\\\<br \/>\n&#038;= \\frac{(n-1)!}{(n-k)!(k-1)!} \\frac{k-1}{k-2} \\frac{(n-k+1)!(k-2)!}{(n-1)!} \\\\<br \/>\n&#038;= \\frac{n-k+1}{k-2}<br \/>\n\\end{align*}<\/p>\n<p>Therefore, our final answer is:<\/p>\n<p style=\"text-align: center;\"><span style=\"background-color: #AFC8E6; padding: 25px 10px 25px 10px;\">$\\displaystyle<br \/>\n\\mathbb{E}(m\\mid K) = \\frac{n-k+1}{k-2}<br \/>\n$<\/span><\/p>\n<p>I undoubtedly found the most complicated possible solution for this problem&#8230; So if somebody can show me a more elegant solution (perhaps a counting argument?) then I would be much obliged!\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"<p>This week&#8217;s Fiddler is about rounding! You are presented with a bag of treats, which contains $n \\geq 3$ peanut butter cups and some unknown quantity of candy corn kernels (with any amount being equally likely). You reach into the bag $k$ times, with $3 \\leq k \\leq n$, and pull out a candy at &hellip; <a href=\"https:\/\/laurentlessard.com\/bookproofs\/halloween-puzzle\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Halloween Puzzle&#8221;<\/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":[42],"tags":[6,43,8],"class_list":["post-4149","post","type-post","status-publish","format-standard","hentry","category-the-fiddler","tag-counting","tag-fiddler","tag-probability"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/4149","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=4149"}],"version-history":[{"count":6,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/4149\/revisions"}],"predecessor-version":[{"id":4156,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/4149\/revisions\/4156"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=4149"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=4149"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=4149"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}