{"id":1684,"date":"2016-12-23T23:15:37","date_gmt":"2016-12-24T05:15:37","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=1684"},"modified":"2016-12-30T13:51:00","modified_gmt":"2016-12-30T19:51:00","slug":"fighting-stormtroopers","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/fighting-stormtroopers\/","title":{"rendered":"Fighting stormtroopers"},"content":{"rendered":"<p>This <a href=\"http:\/\/fivethirtyeight.com\/features\/build-your-own-death-star-and-defeat-the-stormtroopers\/\">Riddler<\/a> puzzle is about fighting a group of stormtroopers. Why <em>are<\/em> they so inaccurate anyway?<\/p>\n<blockquote><p>\nIn Star Wars battles, sometimes a severely outnumbered force emerges victorious through superior skill. You panic when you see a group of nine stormtroopers coming at you from very far away in the distance. Fortunately, they are notoriously inaccurate with their blaster fire, with only a 0.1 percent chance of hitting you with each of their shots. You and each stormtrooper fire blasters at the same rate, but you are $K$ times as likely to hit your target with each shot. Furthermore, the stormtroopers walk in a tight formation, and can therefore create a larger target area. Specifically, if there are $N$ stormtroopers left, your chance of hitting one of them is $(K\\sqrt{N})\/1000$. Each shot has an independent probability of hitting and immediately taking out its target. For approximately what value of $K$ is this a fair match between you and the stormtroopers (where you have 50 percent chance of blasting all of them)?\n<\/p><\/blockquote>\n<p>Here is my solution.<br \/>\n<a href=\"javascript:Solution('soln_stormtrooper','toggle_stormtrooper')\" id=\"toggle_stormtrooper\">[Show Solution]<\/a><\/p>\n<div id=\"soln_stormtrooper\" style=\"display: none\">\n<p>Let&#8217;s call $q$ the probability that a stormtrooper blasts us. In the problem, $q=\\tfrac{1}{1000}$. Let&#8217;s call $P(N)$ the probability that we will blast all of the $N$ stormtroopers and survive to tell the tale. Each round, several things can happen. We can blast a stormtrooper (or not) and we can get blasted ourselves (or not). One thing for sure is that we can only advance if we don&#8217;t get blasted.<\/p>\n<ul>\n<li> The probability that we blast a stormtrooper is given as $q K\\sqrt{N}$.\n<li> The probability that one stormtrooper doesn&#8217;t blast us is $1-q$ so the probability that we don&#8217;t get blasted by any of the $N$ stormtroopers is $\\left(1-q\\right)^N$.\n<\/ul>\n<p>Assembling these probabilities, we can write the following recursion:<br \/>\n\\begin{align}<br \/>\nP(0) &#038;= 1 \\\\<br \/>\nP(N) &#038;= \\left(1-q\\right)^N\\left[ \\left(1-q K\\sqrt{N}\\right)P(N) + q K\\sqrt{N}\\, P(N-1) \\right]<br \/>\n\\end{align}The initial condition is that when there are no stormtroopers left, we have a 100% chance of blasting them all so $P(0)=1$. This recursion can be rearranged so that it&#8217;s in a bit easier to work with:<br \/>\n\\[<br \/>\nP(N) = \\left( \\frac{\\left(1-q\\right)^N\\left(q K\\sqrt{N}\\right)}{1-\\left(1-q\\right)^N\\left(1-q K\\sqrt{N}\\right)}\\right) \\, P(N-1)<br \/>\n\\]Now it&#8217;s clear that we can substitute $P(0)$ and solve for $P(1)$, and then solve for $P(2)$, and so on. So the probability is given by the formula<br \/>\n\\[<br \/>\nP(N) = \\prod_{n=1}^N \\frac{\\left(1-q\\right)^n q K\\sqrt{n}}{1-\\left(1-q\\right)^n\\left(1-q K\\sqrt{n}\\right)}<br \/>\n\\]<\/p>\n<h3>Exact formula<\/h3>\n<p>There doesn&#8217;t appear to be any way to simplify the product above, so we resort to a numerical solution. Here is a plot that shows the probability of blasting all the stormtroopers as a function of the number of stormtroopers $N$ and the blasting efficiency ratio $K$.<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_kvar.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_kvar.png\" alt=\"\" width=\"1444\" height=\"864\" class=\"aligncenter size-full wp-image-1700\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_kvar.png 1444w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_kvar-300x180.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_kvar-768x460.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_kvar-1024x613.png 1024w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_kvar-1200x718.png 1200w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>The plot above makes sense; our chances of blasting all the stormtroopers increases as $K$ increases (we get better at shooting them) or as $N$ decreases (there are fewer stormtroopers). We can also estimate that to blast 9 stormtroopers 50% of the time (without getting blasted ourselves!) we should have $K\\approx 25$. In order to get a more precise estimate of $K$, we must do a bit more work.<\/p>\n<p>Expanding the recursion as a function of $K$, the solution for $P(9)$ turns out to be the following rational function:<br \/>\n\\[<br \/>\nP(9) \\approx<br \/>\n\\tfrac{K^9}{K^9+19.37 K^8+165 K^7+810 K^6+2524 K^5+5176 K^4+6972 K^3+5943 K^2+2904 K+619}<br \/>\n\\]The only approximation I used here was in rounding the coefficients in the denominator. This function starts at zero when $K=0$ and increases monotonically and asymptotically to 1 as $K\\to\\infty$. This makes sense; the better we shoot, the likelier we are to blast all the stormtroopers! Here is a plot of $P(9)$ as a function of $K$:<\/p>\n<p><a href=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_exact.png\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_exact.png\" alt=\"\" width=\"1287\" height=\"854\" class=\"aligncenter size-full wp-image-1701\" srcset=\"https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_exact.png 1287w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_exact-300x199.png 300w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_exact-768x510.png 768w, https:\/\/laurentlessard.com\/bookproofs\/wp-content\/uploads\/2016\/12\/storm_trooper_exact-1024x679.png 1024w\" sizes=\"auto, (max-width: 709px) 85vw, (max-width: 909px) 67vw, (max-width: 1362px) 62vw, 840px\" \/><\/a><\/p>\n<p>Solving $P(9)=0.5$ numerically for $K$, we obtain $K\\approx 26.797$. So in order to have a 50% chance of surviving an encounter with 9 stormtroopers, we should be roughly 27 times more accurate.<\/p>\n<p><strong>Note:<\/strong> It&#8217;s also possible that we blast all the stormtroopers but on our last shot, we also get blasted. I did not account for this possibility because I assumed that &#8220;blasting all the stormtroopers&#8221; meant that we also survived the encounter!<\/p>\n<h3>Approximate solution<\/h3>\n<p>In this scenario, $q$ is very close to zero and $N$ is small as well. So we can approximate $q^2 \\approx 0$. This is effectively a first order <a href=\"https:\/\/en.wikipedia.org\/wiki\/Taylor_series\">Taylor expansion<\/a>. This allows us to write $(1-q)^n \\approx 1-nq$, for example. By applying $q^2 \\approx 0$ in the original formula, we obtain the simpler product:<br \/>\n\\[<br \/>\nP(N) = \\prod_{n=1}^N \\frac{K}{K + \\sqrt{n}}<br \/>\n\\]Note that $q$ actually cancels! The formula above represents the limit as $q\\to 0$, which we&#8217;re assuming is a good enough approximation given that $q = \\tfrac{1}{1000}$ is so small. Solving it numerically, we obtain $K \\approx 26.707$, which is pretty close to the true solution of $K=26.797$. Unfortunately, this is still a problematic expression and there doesn&#8217;t appear to be a closed-form solution, but we can approximate further&#8230; Taking logs of both sides, we obtain:<br \/>\n\\[<br \/>\n-\\log P(N) = \\sum_{n=1}^N \\log\\left( 1 + \\tfrac{\\sqrt{n}}{K} \\right) \\approx \\frac{1}{K}\\left(\\sum_{n=1}^N \\sqrt{n}\\right)<br \/>\n\\]The approximation we made stems from the fact that the expression on the right is of the form $\\log(1+x)$ and $x$ is relatively small (we expect $K\\approx 25$ and $n < 10$, therefore $x = \\tfrac{\\sqrt{n}}{K} < 0.12$). The approximation we used is a first order Taylor approximation $\\log(1+x) \\approx x$. If we want to find the $K$ such that $P(9) = 0.5$, we can solve this easily and obtain:\n\\[\nK = \\frac{1}{\\log 2} \\sum_{n=1}^9 \\sqrt{n} \\approx 27.85\n\\]This is reasonably close to the $K\\approx 26.707$ we were looking for and a lot easier to work with! The reason our approximation isn't better is because $x$ isn't actually <em>that<\/em> close to zero. To get a better approximation, we can use the second order Taylor approximation $\\log(1+x)\\approx x-\\tfrac{1}{2}x^2$ and we obtain the equation:<br \/>\n\\[<br \/>\n-\\log P(N) \\approx \\frac{1}{K} \\left( \\sum_{n=1}^N \\sqrt{n} \\right)-\\frac{1}{2K^2} \\left( \\sum_{n=1}^N n \\right)<br \/>\n\\]This is a simple quadratic equation in $K$ and solving it with $N=9$ and $P(9)=0.5$ yields the solution $K\\approx 26.63$, which is much closer to the $K\\approx 26.707$ we were approximating and still pretty close to the true solution $K=26.797$.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>This Riddler puzzle is about fighting a group of stormtroopers. Why are they so inaccurate anyway? In Star Wars battles, sometimes a severely outnumbered force emerges victorious through superior skill. You panic when you see a group of nine stormtroopers coming at you from very far away in the distance. Fortunately, they are notoriously inaccurate &hellip; <a href=\"https:\/\/laurentlessard.com\/bookproofs\/fighting-stormtroopers\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Fighting stormtroopers&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":1700,"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-1684","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-probability","tag-recursion","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1684","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=1684"}],"version-history":[{"count":18,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1684\/revisions"}],"predecessor-version":[{"id":1723,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/1684\/revisions\/1723"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/1700"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=1684"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=1684"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=1684"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}