Desert escape

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.

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!}$.

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.

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). 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$:
\begin{align}
P_n &= \frac{1}{2^n} \sum_{k=0}^n \binom{n}{k} \frac{1}{k!(n-k)!} \\
&= \frac{1}{2^n \cdot n!} \sum_{k=0}^n \binom{n}{k} \frac{n!}{k!(n-k)!} \\
&= \frac{1}{2^n \cdot n!} \sum_{k=0}^n \binom{n}{k} \binom{n}{n-k} \\
&= \frac{1}{2^n \cdot n!}\binom{2n}{n} \\
&= \frac{(2n)!}{2^n \cdot (n!)^3}
\end{align}The last step is a result of Vandermonde’s identity. 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 and part 2). So when the dust settles, the probability of the paths not intersecting is:

$\displaystyle
P_n = \frac{(2n)!}{2^n \cdot (n!)^3}
$

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:

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