{"id":3468,"date":"2022-09-25T23:02:31","date_gmt":"2022-09-26T04:02:31","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=3468"},"modified":"2022-09-25T23:40:56","modified_gmt":"2022-09-26T04:40:56","slug":"spotting-a-rare-creature","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/spotting-a-rare-creature\/","title":{"rendered":"Spotting a rare creature"},"content":{"rendered":"

This week’s Riddler Classic<\/a> is a question about large numbers of attempts at a very unlikely thing.<\/p>\n

\nGraydon is about to depart on a boating expedition that seeks to catch footage of the rare aquatic creature, F. Riddlerius. Every day he is away, he will send a hand-written letter to his new best friend, David Hacker. But if Graydon still has not spotted the creature after $n$ days (where $n$ is some very, very large number), he will return home.<\/p>\n

Knowing the value of $n$, Graydon confides to David there is only a 50 percent chance of the expedition ending in success before the $n$ days have passed. But as soon as any footage is collected, he will immediately return home (after sending a letter that day, of course).<\/p>\n

On average, for what fraction of the $n$ days should David expect to receive a letter?\n<\/p><\/blockquote>\n

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

\n

We will assume the probability of spotting the creature on any given day is $p$ and is independent one day to the next. We are told the probability the expedition will fail is $\\frac{1}{2}$. This occurs when the creature is not observed for $n$ days. This event has probability $(1-p)^n$. Therefore, we have
\n\\[
\n(1-p)^n = \\frac{1}{2}
\n\\]We can solve this equation for $p$ and we find
\n\\[
\np = 1-2^{-1\/n}
\n\\]<\/p>\n

If Graydon sends $k$ letters (with $1\\leq k \\leq n-1$), this means that the creature was spotted on the $k^\\text{th}$ day, after not being spotted for the first $k-1$ days. The probability of this event is $p(1-p)^{k-1}$. If $n$ letters are sent, then either the creature was spotted on the last day (probability $p(1-p)^{n-1}$), or the creature was not spotted at all (probability $(1-p)^n$). Let the average fraction of days where a letter is received be $A$. This quantity is equal to the expected number of letters received divided by $n$. Therefore, we obtain:
\n\\[
\nA = \\frac{1}{n} \\sum_{k=1}^n k p(1-p)^{k-1} + (1-p)^n
\n\\]We can evaluate this sum<\/a> in closed form, and we obtain
\n\\[
\nA = \\frac{1-(1-p)^n}{n p}
\n\\]Substituting what we found for $p$, we obtain
\n\\[
\nA = \\frac{1}{2n(1-2^{-1\/n})}
\n\\]We are told that “$n$ is very very large”, so it makes sense to examine what happens as $n\\to\\infty$. Doing so, we observe that $A$ tends to a constant:<\/p>\n

\"\"<\/a><\/p>\n

With a bit of work, we can actually evaluate the limit exactly:
\n\\[
\n\\lim_{n\\to\\infty} \\frac{1}{2n(1-2^{-1\/n})}
\n= \\frac{1}{\\log (4)} \\approx 0.721348
\n\\]So, on average, David should expect to receive a letter on approximately 72.1% of the days.<\/p>\n

Alternative approach<\/h5>\n

A slightly faster way to get to the same answer is to realize that if $(1-p)^n=\\frac{1}{2}$ and $n$ is “very very large”, then it must be true that $p$ is “very very small”. Specifically, if we recall the fact that
\n\\[
\n\\lim_{n\\to\\infty} \\left(1+\\frac{x}{n}\\right)^n = e^x
\n\\]Then we can rearrange:
\n\\[
\n(1-p)^n = \\left(1 + \\frac{(-np)}{n}\\right)^n
\n\\]So if $n\\to\\infty$, we conclude that $e^{-np} \\to \\frac{1}{2}$, or that $np \\to \\log(2)$. Therefore, we can return to our original expression for $A$ and substitute $(1-p)^n \\to \\tfrac{1}{2}$ and $np\\to \\log(2)$ and we find:
\n\\[
\nA = \\frac{1-(1-p)^n}{n p} \\to \\frac{1}{\\log(4)}
\n\\]which is the same thing we found using the first approach.\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"

This week’s Riddler Classic is a question about large numbers of attempts at a very unlikely thing. Graydon is about to depart on a boating expedition that seeks to catch footage of the rare aquatic creature, F. Riddlerius. Every day he is away, he will send a hand-written letter to his new best friend, David … Continue reading “Spotting a rare creature”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":3491,"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":[39,8,2],"class_list":["post-3468","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-limits","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3468","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=3468"}],"version-history":[{"count":23,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3468\/revisions"}],"predecessor-version":[{"id":3493,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3468\/revisions\/3493"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/3491"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=3468"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=3468"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=3468"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}