{"id":2809,"date":"2020-05-01T10:21:10","date_gmt":"2020-05-01T15:21:10","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=2809"},"modified":"2020-05-01T12:10:59","modified_gmt":"2020-05-01T17:10:59","slug":"flip-to-freedom","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/flip-to-freedom\/","title":{"rendered":"Flip to freedom"},"content":{"rendered":"

This week’s Riddler Classic<\/a> is a problem about coin flipping. The text of the original problem is quite long, so I will paraphrase it here:<\/p>\n

\nThere are $n$ prisoners, each with access to a random number generator (generates uniform random numbers in $[0,1]$) and a fair coin. Each prisoner is given the opportunity to flip their coin once if they so choose. If all of the flipped<\/em> coins come up Heads, all prisoners are released. But if any of the flipped coins come up Tails, or if no coins are flipped at all, the prisoners are not released. If the prisoners cannot communicate in any way and do not know who is flipping their coin or not, how can they maximize their chances of being released?\n<\/p><\/blockquote>\n

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

\n

This problem is a balancing act. If $k$ of the prisoners flip their coins, the chance of being released is
\n\\[
\n\\mathrm{Prob}(\\text{win if }k\\text{ coins are flipped})=\\begin{cases} 0 & k=0\\\\ \\frac{1}{2^k} & k=1,2,\\dots,n\\end{cases}
\n\\]The best-case scenario is if $k=1$ prisoner flips their coin and the others do not, ensuring the maximum probability of release of $1\/2$. But how should the prisoners decide who flips their coin? If they were allowed to communicate ahead of time, they could elect somebody to flip their coin. But since the prisoners cannot communicate so there is no way to plan ahead!<\/p>\n

Since each prisoner has access to a random number generator, they can use it to decide whether they should be flipping their coin or not. Here is the strategy. We must decide on a threshold $t$. Each prisoner queries their random number generator and if the number they obtain is less than $t$, they flip their coin. The larger $t$ is, the more likely prisoners are to flip coins. So there is a trade-off between ensuring at least one prisoner flips a coin and ensuring not too many prisoners flip coins. Let’s figure out the best choice of $t$.<\/p>\n

Let’s call the probability the prisoners are released $f_n(t)$. It depends on the threshold they choose. Now,
\n\\begin{align*}
\nf_n(t) &= \\sum_{k=1}^n \\frac{1}{2^k} \\mathrm{Prob}(\\text{there are }k\\text{ flips}) \\\\
\n&= \\sum_{k=1}^n \\frac{1}{2^k} \\binom{n}{k}t^k(1-t)^{n-k} \\\\
\n&= \\sum_{k=1}^n \\binom{n}{k}\\left(\\frac{t}{2}\\right)^k (1-t)^{n-k} \\\\
\n&= ( 1-\\tfrac{1}{2}t)^n-(1-t)^n
\n\\end{align*} In the last step, we used the Binomial Theorem<\/a> to evaluate the sum. So our goal is to find $t\\in[0,1]$ that minimizes $f_n(t)$. Here is what the function looks like for different values of $n$:<\/p>\n

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

As anticipated, there is an ideal value of the threshold $t$ that maximizes the probability of winning. However, the maximum depends on $n$, the number of prisoners. To find the maximum, we can use calculus: set the derivative of $f_n(t)$ equal to zero:
\n\\[
\n\\frac{\\mathrm{d}f_n(t)}{\\mathrm{d}t}=n(1-t)^{n-1}-\\tfrac{1}{2}n(1-\\tfrac{1}{2}t)^{n-1}=0
\n\\]Solving for the optimal threshold $t$, we obtain:<\/p>\n

$\\displaystyle
\nt_\\text{opt}=1-\\frac{1}{2^{n\/(n-1)}-1}
\n$<\/span><\/p>\n

As a function of $n$, $t_\\text{opt}$ is the threshold each prisoner should use. If their random number generator produces a value less than the threshold, they should flip their coin. Otherwise, they should not. As anticipated, in the limit $n\\to\\infty$, $t_\\text{opt}\\to 0$ because as the number of prisoners increases, we want each prisoner to be less likely to flip their coin. As an approximation, the first order asymptotic expansion of $t_\\text{opt}$ is
\n\\[
\nt_\\text{opt} = \\frac{2\\log(2)}{n} + O\\left(\\frac{1}{n^2}\\right)\\approx\\frac{1.386}{n}
\n\\]So this can be used as a quick way to approximate the threshold (in case the prisoners don’t have access to a calculator!).<\/p>\n

How about the probability of winning assuming the prisoners use this strategy? This simply amounts to evaluating $f_n(t_\\text{opt})$. Doing so, we obtain:<\/p>\n

$\\displaystyle
\n\\textrm{Prob}(\\text{win}) = \\frac{1}{\\left(2^{n\/(n-1)}-1\\right)^{n-1}}
\n$<\/span><\/p>\n

Here is a table comparing the optimal threshold and corresponding probability of winning for different values of $n$:<\/p>\n\n\n\n\n\n\n\n\n\n\n
Number of prisoners<\/th>\nthreshold $t_\\text{opt}$<\/th>\nProbability of freedom<\/th>\n<\/tr>\n
1<\/td>\n1<\/td>\n0.5<\/td>\n<\/tr>\n
2<\/td>\n0.666667<\/td>\n0.333333<\/td>\n<\/tr>\n
3<\/td>\n0.453082<\/span><\/td>\n0.299119<\/td>\n<\/tr>\n
4<\/td>\n0.342037<\/td>\n0.284842<\/td>\n<\/tr>\n
5<\/td>\n0.274529<\/td>\n0.277001<\/td>\n<\/tr>\n
10<\/td>\n0.13802<\/td>\n0.262709<\/td>\n<\/tr>\n
50<\/td>\n0.0277034<\/td>\n0.252429<\/td>\n<\/tr>\n
100<\/td>\n0.0138574<\/td>\n0.251208<\/td>\n<\/tr>\n<\/table>\n

So when $n=1$, the lone prisoner flips every time and the probability of winning is $\\frac{1}{2}$. With two prisoners, each prisoner should flip $\\frac{2}{3}$ of the time, and the probability of winning is $\\frac{1}{3}$. As $n\\to\\infty$, the threshold goes to zero as described above, and we can also verify that the probability of winning tends to $\\frac{1}{4}$ in the limit.<\/p>\n

So this strategy ensures that the probability of all prisoners being released is always at least 25%. The only caveat is that in order to compute which threshold to use, the prisoners must know $n$, the total number of prisoners playing the game.\n<\/p><\/div>\n","protected":false},"excerpt":{"rendered":"

This week’s Riddler Classic is a problem about coin flipping. The text of the original problem is quite long, so I will paraphrase it here: There are $n$ prisoners, each with access to a random number generator (generates uniform random numbers in $[0,1]$) and a fair coin. Each prisoner is given the opportunity to flip … Continue reading “Flip to freedom”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":2820,"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":[9,28,8,2],"class_list":["post-2809","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-binomial","tag-calculus","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2809","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=2809"}],"version-history":[{"count":9,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2809\/revisions"}],"predecessor-version":[{"id":2823,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/2809\/revisions\/2823"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/2820"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=2809"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=2809"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=2809"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}