Running from Samsquanch - Part 2 [SOLUTION]
Did Samsquanch get stuck? Or did I?
Our problem from 9/8/24 was
You’re thinking about doing a backpacking trip through Rainier National Park but there’s one big concern; that’s Samsquanch territory! After thinking it over for a moment you realize you have one big advantage; Samsquanch’s broad shoulders make it more difficult to navigate dense trees while your small, nerdy frame can fit quite easily. In order to make sure you have a chance to escape, you want to make sure the forest you’re hiking through has sufficient tree density.
Let’s model our forest as a 10x10 square. The top will be the entrance and the bottom will be the exit. For simplicity, we will assume the sides are impassable barriers. Each tree will be modeled by a point and Samsquanch will be modeled by a circle of radius 1. Trees will be distributed uniformly in the 10x10 square. Let’s further assume that Samsquanch can’t fit between any two trees that are less than 2R apart. We need to figure out what density the trees need to be in order for you to evade Samsquanch.This week, we will do another related but simpler problem (a warmup if you will). Instead of navigating through a 2D forest, Image you just have to determine if Samsquanch can fit through a particular line of trees. The trees are uniformly distributed on a line of length 10. In other words, you need to identify if there are any gaps in this line of length at least 2. Assume there are 7 trees on this line. What is the probability that Samsquanch can fit through this barrier of trees?
Still no submissions but that’s ok! I’ll start advertising this blog once I have a little bit of a backlog for folks to look at :)
And honestly, I wouldn’t blame someone for not submitting! This problem ended up being trickier than I realized! I thought we could use order statistics in a relatively straightforward manner but I was wrong!
I posted my incomplete solution here. To summarize, I tried to model the gaps between trees using order statistics. I started by looking at how tree positions would be distributed along a line and then computed the distribution of the gaps between each tree However, ventured down this approach thinking I could compute the probability of none of the gaps being greater than 2 by naively computing
Of course this assumes the gaps between the trees were independent, which is pretty obviously not the case (facepalm). By the time I realized this, I did not have enough time to correct my solution so I’ll have to update this post with the correct solution when I get there.
Updated Solution
My updated solution is posted here. As you may recall (or see above) I naively thought I could find the gap between consecutive order statistics and multiply the probability of the gap being less than 2 for each order statistic. This, of course, fails to account for the dependence between the gaps. Instead, I needed to recognize that a different distribution was at play—the Dirichlet distribution. In fact, when it’s parameterized with with the same alpha=1 for every alpha_i, it describes the distribution of the length of the gaps between consecutive order statistics generated from uniform random variables—just what we need. Now how do we constrain this distribution such that no gap is greater than 2? The full details are in the solution I posted but essentially, we need to recognize the dirichlet distribution domain can be represented as a simplex and the value of the distribution is uniform over this simplex. With this, we can employ some geometric techniques and recognize that constraining each gap to be less than 2 is equivalent to finding the intersection of the simplex with a hypercube with side lengths [0,2]. Interestingly (and quite counter-intuitively) this quantity can be computed using the Irwin-Hall distribution. Putting all of this together with some not-so-obvious change of variables, we get that the probability that there’s at least 1 gap with length greater than 2 is 98.5%. Uhh oh! sounds like you’re in trouble!
I hope you found this problem fun! Well, maybe fun is a stretch. Perhaps educational or challenging would be more likely. As always, feel free to leave comments, thoughts, etc in the comments. Hope to see you for the next one!