{"id":3361,"date":"2022-06-11T15:00:27","date_gmt":"2022-06-11T20:00:27","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=3361"},"modified":"2022-06-12T00:41:13","modified_gmt":"2022-06-12T05:41:13","slug":"catch-the-grasshopper","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/catch-the-grasshopper\/","title":{"rendered":"Catch the grasshopper"},"content":{"rendered":"

This week’s Riddler classic<\/a> is a probability problem about a grasshopper!<\/p>\n

\nYou are trying to catch a grasshopper on a balance beam that is 1 meter long. Every time you try to catch it, it jumps to a random point along the interval between 20 centimeters left of its current position and 20 centimeters right of its current position. If the grasshopper is within 20 centimeters of one of the edges, it will not jump off the edge. For example, if it is 10 centimeters from the left edge of the beam, then it will randomly jump to anywhere within 30 centimeters of that edge with equal probability (meaning it will be twice as likely to jump right as it is to jump left). After many, many failed attempts to catch the grasshopper, where is it most likely to be on the beam? Where is it least likely? And what is the ratio between these respective probabilities?\n<\/p><\/blockquote>\n

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

\n

Let’s suppose the beam has length $L$ and the grasshopper can jump a maximum distance $\\frac{M}{2}$. Define $p(x)$ to be the probability density function describing how likely the grasshopper is to be at any given location $x\\in\\left[-\\frac{L}{2},\\frac{L}{2}\\right]$.<\/p>\n

We can arrive at $p(x)$ via a sequential process. Suppose that at time $k$, the grasshopper has distribution $p_k(x)$. When the grasshopper jumps, its probability distribution becomes $p_{k+1}(x)$. Our goal is to find the limiting distribution $p = \\lim_{k\\to\\infty} p_k$.<\/p>\n

At each step, the grasshopper’s density function gets convolved with an appropriate uniform distribution corresponding with where it might land. We can write this as:
\n\\[
\np_{k+1}(x) = \\int_{-L\/2}^{L\/2} \\Psi(x,y) p_k(y) \\,\\mathrm{d}y.
\n\\]Here, for each $y$, the kernel $\\Psi(x,y)$ is the density function (of $x$) corresponding to a uniform distribution between $\\max\\bigl(-\\frac{L}{2},y-\\frac{M}{2}\\bigr)$ and $\\min\\bigl(\\frac{L}{2},y+\\frac{M}{2}\\bigr)$, since this corresponds to the range of locations a grasshopper at location $y$ can jump to. Putting all this together, we get the formula:
\n\\[
\np_{k+1}(x) = \\int_{\\max\\bigl(-\\frac{L}{2},x-\\frac{M}{2}\\bigr)}^{\\min\\bigl(\\frac{L}{2},x+\\frac{M}{2}\\bigr)} \\frac{p_k(y)\\,\\mathrm{d}y}{\\min\\bigl(\\frac{L}{2},y+\\frac{M}{2}\\bigr)-\\max\\bigl(-\\frac{L}{2},y-\\frac{M}{2}\\bigr)}.
\n\\]Yuck! To get a better handle on what this might look like, we can simulate it using the given problem parameters ($L=1$ and $M=0.4$) using units of meters. Here is what we obtain when recursively apply the above formula, assuming $p_0$ is a uniform distribution:<\/p>\n

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

The steady-state distribution is the same no matter what we use as the starting distribution. Here is what it looks like when we start the grasshopper on the left edge of the beam. I had to use different axis scaling to make the transient behavior fit in the plot, but the limiting distribution in the same:<\/p>\n

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

These simulations give us a big hint: The limiting distribution appears to be piecewise-linear! We already expected a symmetric distribution due to the symmetry in the problem, but now we can posit a density function of the form:
\n\\[
\np(x) = \\begin{cases}
\nax+b & -\\frac{L}{2}\\leq x \\leq -\\left|\\frac{L-M}{2}\\right| \\\\
\nc & -\\left|\\frac{L-M}{2}\\right| < x < \\left|\\frac{L-M}{2}\\right| \\\\\n-ax+b & \\left|\\frac{L-M}{2}\\right| \\leq x \\leq \\frac{L}{2}\n\\end{cases}\n\\]We have three unknown parameters $(a,b,c)$, so we need three equations. First, $p$ is a probability density, so $\\int_{-L\/2}^{L\/2}p(x)\\,\\mathrm{d}x=1$. Second, $p$ is continuous at the boundaries $x=\\pm \\left|\\frac{L-M}{2}\\right|$. Finally, we must satisfy $p(x) = p_{k+1}(x) = p_k(x)$ in the original recursion in our original recursion. Solving these equations, we find three cases:\n\\[\np(x) =\n\\begin{cases}\n\\begin{cases}\n\\frac{2 (L+M+2 x)}{M (4 L-M)} & -\\frac{L}{2}\\leq x \\leq \\frac{-L+M}{2} \\\\\n\\frac{4}{4 L-M} & \\frac{-L+M}{2} < x < \\frac{L-M}{2} \\\\\n\\frac{2 (L+M-2 x)}{M (4 L-M)} & \\frac{L-M}{2} \\leq x \\leq \\frac{L}{2}\n\\end{cases} & 0 < M < L \\\\[3mm]\n\\begin{cases}\n\\frac{2 (L+M+2 x)}{M (4 L-M)} & -\\frac{L}{2}\\leq x \\leq \\frac{-M+L}{2} \\\\\n\\frac{4 L}{M (4 L-M)} & \\frac{-M+L}{2} < x < \\frac{M-L}{2} \\\\\n\\frac{2 (L+M-2 x)}{M (4 L-M)} & \\frac{M-L}{2} \\leq x \\leq \\frac{L}{2}\n\\end{cases} & L < M < 2L \\\\[3mm]\n\\quad\\frac{1}{L} & 2L < M\n\\end{cases}\n\\]\n\nWe can also calculate the ratio of largest to smallest likelihood in all three cases. The largest likelihood occurs in the center ($x=0$) while the smallest occurs at an edge ($x=\\pm\\frac{L}{2}$). We then obtain:\n\\[\n\\frac{p_\\text{max}}{p_\\text{min}} = \n\\begin{cases}\n2 & 0 < M < L \\\\[1mm]\n\\frac{2L}{M} & L < M < 2L \\\\[1mm]\n1 & 2L < M\n\\end{cases}\n\\]\nSo, amazingly, the ratio of largest likelihood to the smallest likelihood is 2, a constant indepedent of the length $L$ or the grasshopper range $M$, so long as $M < L$. In particular, the likelihood ratio is $2$ for the setting given in the problem statement ($L=1$ and $M=0.4$).\n<\/div>\n","protected":false},"excerpt":{"rendered":"

This week’s Riddler classic is a probability problem about a grasshopper! You are trying to catch a grasshopper on a balance beam that is 1 meter long. Every time you try to catch it, it jumps to a random point along the interval between 20 centimeters left of its current position and 20 centimeters right … Continue reading “Catch the grasshopper”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":3365,"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":[28,20,8,15,2],"class_list":["post-3361","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-riddler","tag-calculus","tag-markov-chains","tag-probability","tag-recursion","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3361","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=3361"}],"version-history":[{"count":13,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3361\/revisions"}],"predecessor-version":[{"id":3378,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3361\/revisions\/3378"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media\/3365"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=3361"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=3361"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=3361"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}