{"id":2371,"date":"2018-08-04T14:14:45","date_gmt":"2018-08-04T19:14:45","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2371"},"modified":"2018-08-04T14:48:46","modified_gmt":"2018-08-04T19:48:46","slug":"a-coin-flipping-game","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/a-coin-flipping-game\/","title":{"rendered":"A coin-flipping game"},"content":{"rendered":"

This Riddler puzzle<\/a> involves a particular coin-flipping game. Here is the problem:<\/p>\n

\nI flip a coin. If it\u2019s heads, I\u2019ve won the game. If it\u2019s tails, then I have to flip again, now needing to get two heads in a row to win. If, on my second toss, I get another tails instead of a heads, then I now need three heads in a row to win. If, instead, I get a heads on my second toss (having flipped a tails on the first toss) then I still need to get a second heads to have two heads in a row and win, but if my next toss is a tails (having thus tossed tails-heads-tails), I now need to flip three heads in a row to win, and so on. The more tails you\u2019ve tossed, the more heads in a row you\u2019ll need to win this game.<\/p>\n

I may flip a potentially infinite number of times, always needing to flip a series of N heads in a row to win, where N is T + 1 and T is the number of cumulative tails tossed. I win when I flip the required number of heads in a row.<\/p>\n

What are my chances of winning this game? (A computer program could calculate the probability to any degree of precision, but is there a more elegant mathematical expression for the probability of winning?)\n<\/p><\/blockquote>\n

Here is my solution:
\n[Show Solution]<\/a><\/p>\n

\n

The solution is short but sweet. It turns out it’s easier to think about the probability of losing<\/em> rather than the probability of winning. Let’s define:
\n\\[
\nP(t) = \\text{Probability of losing given we have just flipped the }t^\\text{th}\\text{ Tail}.
\n\\]If we have just flipped our $t^\\text{th}$ Tail, then we’ll win if we flip $t+1$ Heads in a row (probability $\\frac{1}{2^{t+1}}$). Otherwise, we’ll flip our $(t+1)^\\text{st}$ Tail and we’ll have a chance $P(t+1)$ of losing from that point forward. Mathematically,
\n\\[
\nP(t) = \\left(1-\\frac{1}{2^{t+1}}\\right) P(t+1)
\n\\]Our goal is to find the initial probability of winning, which is $1-P(0)$. It’s clear that $\\lim_{t\\to\\infty}P(t) = 1$, because it becomes progressively less likely we’ll win as the number of Tails flipped accrues. Iterating the above recursion, we have<\/p>\n

$\\displaystyle
\n\\text{Probability of winning} = 1-\\prod_{t=1}^\\infty \\left(1-\\frac{1}{2^t}\\right)
\n$<\/span><\/p>\n

This expression occurs often enough that it was given its own name! It’s a special case of the Euler function<\/a> (just one of many things named after Euler), which is itself a special case of the q-Pochhammer symbol<\/a>.<\/p>\n

There is no way to further simplify the infinite product, unfortunately, but it’s rather easy to approximate it. The probability of winning is approximately $0.711211904913…$, so about $71\\%$.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

This Riddler puzzle involves a particular coin-flipping game. Here is the problem: I flip a coin. If it\u2019s heads, I\u2019ve won the game. If it\u2019s tails, then I have to flip again, now needing to get two heads in a row to win. If, on my second toss, I get another tails instead of a … Continue reading “A coin-flipping game”<\/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,15,2],"class_list":["post-2371","post","type-post","status-publish","format-standard","hentry","category-riddler","tag-probability","tag-recursion","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2371","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=2371"}],"version-history":[{"count":7,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2371\/revisions"}],"predecessor-version":[{"id":2373,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2371\/revisions\/2373"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2371"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2371"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2371"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}