online advertising

Saturday, February 13, 2016

Duck Pond Chance (3)

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.

No comments:

Post a Comment