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\u2019s 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\u2019s 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\u2019s 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<\/p><\/div>\n

<\/p>\n<\/body>","protected":false},"excerpt":{"rendered":"

This week\u2019s 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":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t