Problem Statement

From The Riddler on FiveThirtyEight, comes the following challenging probability problem from 6/3/2022:

In the Great Riddlerian Desert, there is a single oasis that is straight and narrow. There are N travelers who are trapped at the oasis, and one day, they agree that they will all leave. They independently pick a random location in the oasis from which to start and a random direction in which to travel. Once their supplies are packed, they all head out.

What is the probability that none of their paths will intersect, in terms of N? (For the purposes of this puzzle, assume the oasis is a line segment, while the desert is an infinite Cartesian plane.)

Solution

Let’s think of the line segment as the x-axis between -1 and 1. Each traveler can choose to go north (into quadrants I or II) or south (into quadrants III or IV). Travelers going north will not have to worry about crossing paths with those going south.

If there are N travelers, and they all pick a random point on the segment and a random direction, let’s work out the probability that M will choose to go north (and therefore N-M go south) and that all the travelers do not intersect. Then, we will sum over all M.

The probability that M will choose to go north and N-M will go south is a quick binomial problem and is \(\binom{N}{M}\left(\frac12\right)^N\).

To find the probability that none of the M traveler’s going north nor the N-M travler’s going south intersect, one can standardize the angles 0 to \(\pi\) to 0 to 1, and analyze the travelers going right to left in terms of the angles of their chosen paths from the line segment and look at, say for the case of 3 travelers, \(\int_0^1\int_x^1\int_y^1 \,\, dz\,dy\,dx\). Generalizing to M travelers will lead to \(\frac{1}{M!}\). Hence, for both the north and southbound travelers, the probability there are no intersections is \(\frac{1}{M!}\frac{1}{(N-M)!}\).

The final probability for this case is \(\binom{N}{M}\left(\frac12\right)^N\frac{1}{M!}\frac{1}{(N-M)!}\). Summing this from \(M=0\) to \(M=N\) will provide our answer: \(\sum_{M=0}^{N} \binom{N}{M} \left(\frac12\right)^N \frac{1}{M!} \frac{1}{(N-M)!}\)

## A function to provide the probabilty that N traveler's paths do not cross. 
Travelers <- function(N){
   S <- 0
   for(M in 0:N){
      S <- S + choose(N,M)*(0.5)^N/factorial(M)/factorial(N-M)
   }
   return(S)
}

## The first 6 probabilities: 
Travelers(2)
## [1] 0.75
Travelers(3)
## [1] 0.4166667
Travelers(4)
## [1] 0.1822917
Travelers(5)
## [1] 0.065625
Travelers(6)
## [1] 0.02005208