Now, let try another approach. We construct the distribution for the smallest enclosing angle incrementally. The case for the smallest enclosing angle for 2 duck is just the uniform distribution in $ [0, \pi] $.
Solving the distribution function for 3 ducks is key, because the same approach is likely useful for 4 ducks, or even $ n $ ducks.
Let $ 2a $ be the smallest enclosing angle for the first 2 ducks
Let $ b $ be the smallest enclosing angle for the first 3 ducks.
For simplicity, we let duck 1 has polar angle $ a $ , duck 2 has polar angle $ -a $.
For duck 3, let it polar angle be $ t $.
If $ t \in [a, -a] $, then $ b = 2a $, in other words, $ P(b = 2a) = \frac{2a}{2\pi} = \frac{a}{\pi} $.
Now suppose $ t \in [a, \pi] $, we need to compare all choices:
(Option 1) duck 2 -> duck 1 -> duck 3 will have angle $ t + a $
(Option 2) duck 1 -> duck 3 -> duck 2 will have angle $ 2\pi - 2a $
(Option 3) duck 3 -> duck 2 -> duck 1 will have angle $ 2\pi - (t - a) = 2\pi + a - t $
We know (option 1) is always as good as than (option 3) because (option 3) - (option 1) = $ (2\pi + a - t) - (t + a) = 2\pi - 2t \ge 0 $ (Remember the maximum of $ t $ is $ \pi $). So we can simply ignore option 3.
It is not so simple for (option 2), we see
(option 1) - (option 2) = $ (t + a) - (2\pi - 2a) = t + 3a - 2\pi $
We know if the difference is greater than 0, then (option 2) is better. The condition for that to be true is $ t \ge 2\pi - 3a $, which means if the range of $ t = [a, \pi] $ contains $ 2\pi - 3a $, then we need to worry about splitting it so that we choose the options wisely.
For that to happen, $ a \le 2\pi - 3a \implies 4a \le 2\pi \implies a \le \frac{\pi}{2} $, which is automatically true, we also need $ 2\pi - 3a \le \pi \implies \pi \le 3a \implies a \ge \frac{\pi}{3} $
So we have 4 cases to worry about for positive $ t $.
Case 1: $ t \le a $ - in that case $ b = 2a $.
Case 2: $ t \ge a $ and $ a \le \frac{\pi}{3} $ - in that case $ b = t + a $.
Case 3: $ t \ge a $, $ a \ge \frac{\pi}{3} $ and $ t \le 2\pi - 3a $ - in that case $ b = t + a $, and at last
Case 4: $ t \ge a $, $ a \ge \frac{\pi}{3} $ and $ t > 2\pi - 3a $ - in that case $ b = 2\pi - 2a $.
The cases for negative $ t $ is completely symmetric so we can skip it. Now, if we are given $ a $ and $ t $, we can calculate $ b $.
But, that's not our goal. We wanted to know the distribution of $ b $, To get there, the plan is to compute $ F(b|a) $, the conditional cumulative density function (conditional CDF) for b first.
Case 1 is easy to encode, $ P(b \le t|a) = 0 $ if $ t \in [0, 2a) $.
Case 2 means $ P(b \le t + a|a) = \frac{2t}{2\pi} = \frac{t}{\pi} $, $ a \le \frac{\pi}{3} $ and $ t \ge a $, as the diagram would indicate.
An algebraic manipulation of the above is to let $ s = t + a $, that would give $ P(b \le s) = \frac{s - a}{\pi} $, $ a \le \frac{\pi}{3} $ and $ s \ge 2a $.
Case 1 and Case 2 form the complete distribution for b (condition on a), in this case, we get a curve like this:
Case 3 is getting complicated, as long as we stay within the $ 2\pi - 3a $ region, the probability is pretty much the same as it was for case 2.
$ P(b \le s) = \frac{s - a}{\pi} $, $ a \ge \frac{\pi}{3} $,$ s \ge 2a $ and $ t \le 2\pi - 3a \implies s \le 2\pi - 2a $
Case 4 seems complicated but in fact it is not. It merely says that the $ s $ is capped above by $ 2\pi - 2a $, so the final CDF look like this in that case.
It is too late at night for me now, so I will stop here with the conditional CDF. If time allows I will continue and work on the PDFs.
Solving the distribution function for 3 ducks is key, because the same approach is likely useful for 4 ducks, or even $ n $ ducks.
Let $ 2a $ be the smallest enclosing angle for the first 2 ducks
Let $ b $ be the smallest enclosing angle for the first 3 ducks.
For simplicity, we let duck 1 has polar angle $ a $ , duck 2 has polar angle $ -a $.
For duck 3, let it polar angle be $ t $.
If $ t \in [a, -a] $, then $ b = 2a $, in other words, $ P(b = 2a) = \frac{2a}{2\pi} = \frac{a}{\pi} $.
Now suppose $ t \in [a, \pi] $, we need to compare all choices:
(Option 1) duck 2 -> duck 1 -> duck 3 will have angle $ t + a $
(Option 2) duck 1 -> duck 3 -> duck 2 will have angle $ 2\pi - 2a $
(Option 3) duck 3 -> duck 2 -> duck 1 will have angle $ 2\pi - (t - a) = 2\pi + a - t $
We know (option 1) is always as good as than (option 3) because (option 3) - (option 1) = $ (2\pi + a - t) - (t + a) = 2\pi - 2t \ge 0 $ (Remember the maximum of $ t $ is $ \pi $). So we can simply ignore option 3.
It is not so simple for (option 2), we see
(option 1) - (option 2) = $ (t + a) - (2\pi - 2a) = t + 3a - 2\pi $
We know if the difference is greater than 0, then (option 2) is better. The condition for that to be true is $ t \ge 2\pi - 3a $, which means if the range of $ t = [a, \pi] $ contains $ 2\pi - 3a $, then we need to worry about splitting it so that we choose the options wisely.
For that to happen, $ a \le 2\pi - 3a \implies 4a \le 2\pi \implies a \le \frac{\pi}{2} $, which is automatically true, we also need $ 2\pi - 3a \le \pi \implies \pi \le 3a \implies a \ge \frac{\pi}{3} $
So we have 4 cases to worry about for positive $ t $.
Case 1: $ t \le a $ - in that case $ b = 2a $.
Case 2: $ t \ge a $ and $ a \le \frac{\pi}{3} $ - in that case $ b = t + a $.
Case 3: $ t \ge a $, $ a \ge \frac{\pi}{3} $ and $ t \le 2\pi - 3a $ - in that case $ b = t + a $, and at last
Case 4: $ t \ge a $, $ a \ge \frac{\pi}{3} $ and $ t > 2\pi - 3a $ - in that case $ b = 2\pi - 2a $.
The cases for negative $ t $ is completely symmetric so we can skip it. Now, if we are given $ a $ and $ t $, we can calculate $ b $.
But, that's not our goal. We wanted to know the distribution of $ b $, To get there, the plan is to compute $ F(b|a) $, the conditional cumulative density function (conditional CDF) for b first.
Case 1 is easy to encode, $ P(b \le t|a) = 0 $ if $ t \in [0, 2a) $.
Case 2 means $ P(b \le t + a|a) = \frac{2t}{2\pi} = \frac{t}{\pi} $, $ a \le \frac{\pi}{3} $ and $ t \ge a $, as the diagram would indicate.
An algebraic manipulation of the above is to let $ s = t + a $, that would give $ P(b \le s) = \frac{s - a}{\pi} $, $ a \le \frac{\pi}{3} $ and $ s \ge 2a $.
Case 1 and Case 2 form the complete distribution for b (condition on a), in this case, we get a curve like this:
Case 3 is getting complicated, as long as we stay within the $ 2\pi - 3a $ region, the probability is pretty much the same as it was for case 2.
$ P(b \le s) = \frac{s - a}{\pi} $, $ a \ge \frac{\pi}{3} $,$ s \ge 2a $ and $ t \le 2\pi - 3a \implies s \le 2\pi - 2a $
Case 4 seems complicated but in fact it is not. It merely says that the $ s $ is capped above by $ 2\pi - 2a $, so the final CDF look like this in that case.
It is too late at night for me now, so I will stop here with the conditional CDF. If time allows I will continue and work on the PDFs.
No comments:
Post a Comment