{"id":3350,"date":"2022-06-03T15:12:15","date_gmt":"2022-06-03T20:12:15","guid":{"rendered":"https:\/\/laurentlessard.com\/bookproofs\/?p=3350"},"modified":"2022-06-03T17:42:05","modified_gmt":"2022-06-03T22:42:05","slug":"desert-escape","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/desert-escape\/","title":{"rendered":"Desert escape"},"content":{"rendered":"

This week’s Riddler classic<\/a> is about geometry and probability, and desert escape! Here is the (paraphrased) problem:<\/p>\n

\nThere are $n$ travelers who are trapped on a thin and narrow oasis. They each independently pick a random location in the oasis from which to start and a random direction in which to travel. What is the probability that none of their paths will intersect, in terms of $n$?\n<\/p><\/blockquote>\n

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

\n

First, consider a simpler problem, where all travelers depart from the same side of the oasis. Here is a diagram of what that might look like.<\/p>\n

\"\"<\/p>\n

The paths will not cross precisely if the angles from left-to-right are arranged from smallest to largest. For example, in the diagram above, the paths will not cross because $\\theta_1 \\lt \\theta_2 \\lt \\theta_3$. Once you fix the angles, only one of the $n!$ possible arrangements of the travelers will have the correct ordering. Therefore, the probability that the paths do not intersect is $\\frac{1}{n!}$.<\/p>\n

Now consider the case where travelers can depart from either side of the oasis. Suppose $k$ travelers depart from the top and $n-k$ depart from the bottom, as in the diagram below.<\/p>\n

\"\"<\/p>\n

Since each traveler is equally likely to depart from either side, the probability of this happening is $\\frac{1}{2^n} \\binom{n}{k}$ (it’s a binomial distribution<\/a>). The probability that the paths do not intersect is $\\frac{1}{k!(n-k)!}$, since it is the product of the probability that the $k$ travelers departing from the top do not intersect and the $n-k$ travelers departing from the bottom do not intersect, and both events are independent. To find the total probability $P_n$, we sum over all possible $k$:
\n\\begin{align}
\nP_n &= \\frac{1}{2^n} \\sum_{k=0}^n \\binom{n}{k} \\frac{1}{k!(n-k)!} \\\\
\n&= \\frac{1}{2^n \\cdot n!} \\sum_{k=0}^n \\binom{n}{k} \\frac{n!}{k!(n-k)!} \\\\
\n&= \\frac{1}{2^n \\cdot n!} \\sum_{k=0}^n \\binom{n}{k} \\binom{n}{n-k} \\\\
\n&= \\frac{1}{2^n \\cdot n!}\\binom{2n}{n} \\\\
\n&= \\frac{(2n)!}{2^n \\cdot (n!)^3}
\n\\end{align}The last step is a result of Vandermonde’s identity<\/a>. You can think of it as counting the number of ways of picking $n$ objects from a set of $2n$ objects. We can do this by imagining that our $2n$ objects are split into two groups of $n$, and we are picking $k$ from the first group and $n-k$ from the second group, and then summing over $k$. If you are interested in these sorts of binomial identities, I encourage you to read the two-part blog post I wrote on the topic (part 1<\/a> and part 2<\/a>). So when the dust settles, the probability of the paths not intersecting is:<\/p>\n

$\\displaystyle
\nP_n = \\frac{(2n)!}{2^n \\cdot (n!)^3}
\n$<\/span><\/p>\n

This function decreases rapidly as $n$ increases. To see this, we can plot $P_n$ as a function of $n$. Here is what we obtain:<\/p>\n

\"\"<\/p>\n

To get a better handle on $P_n$, we can use Stirling’s approximation<\/a> to the factorial, $n! \\sim \\sqrt{2\\pi n}\\left(\\frac{n}{e}\\right)^n$, which yields
\n\\[
\nP_n \\sim \\frac{1}{2\\sqrt{2}\\,\\pi\\,e} \\left( \\frac{2e}{n}\\right)^{n+1}
\n\\]This tells us that $\\log(P_n) \\sim -n\\log(n)$, which agrees with the almost linear<\/em> decrease of $P_n$ on a log scale.\n<\/div>\n","protected":false},"excerpt":{"rendered":"

This week’s Riddler classic is about geometry and probability, and desert escape! Here is the (paraphrased) problem: There are $n$ travelers who are trapped on a thin and narrow oasis. They each independently pick a random location in the oasis from which to start and a random direction in which to travel. What is the … Continue reading “Desert escape”<\/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":[9,10,8,2],"class_list":["post-3350","post","type-post","status-publish","format-standard","hentry","category-riddler","tag-binomial","tag-geometry","tag-probability","tag-riddler"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3350","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=3350"}],"version-history":[{"count":3,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3350\/revisions"}],"predecessor-version":[{"id":3358,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/posts\/3350\/revisions\/3358"}],"wp:attachment":[{"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/media?parent=3350"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/categories?post=3350"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/laurentlessard.com\/bookproofs\/wp-json\/wp\/v2\/tags?post=3350"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}