Duck Pond

Duck Pond

Here's a neat probability problem that I was working on last summer. I was having a sort out of my old files and I came across my written explanation that I did for a Facebook discussion so I thought I'd turn it into an article for here. If you were my student last year then you might remember it.

OK let's go. There is a circular pond with n ducks randomly distributed across the top. Each duck can be modelled as a point, so these are infinitely small ducks. What is the probability that all of the ducks are in the same half of the circle. Note here that we can draw the half way line on any diameter; they can go at any angle.

A good way to get a grip on these sort of problems is to investigate the smaller cases and then see if you can build up some sort of pattern. For one duck the probability is quite clearly 1, but what about n=2? Have a go.

Well for two ducks we can always draw a line which either has both ducks on the same side or, at worst, has both ducks actually on the line. You'll notice that I haven't told you what happens with these edge cases. Do we count it as both ducks on the same side? It actually doesn't matter because the chance that the two ducks are exactly opposite on the circle is infinitely small ie it happens with a probability of 0. Ok. 2 ducks always fit into half the pond.

For 3 ducks it looks like this: duck 1 is in black. We can put it arbitrarily at the top of the pond because the whole thing is rotationally symmetric. On average duck 2 is 90 degrees away. This splits the pond into regions. If the duck 3 is in any of the 3 regions next to the first two then you can draw a diameter with all 3 on oneside. However if it is opposite then you can’t. So the probability of 3 ducks being in half the pond is 3/4.

 Duck 1 black, average duck 2 red

Duck 1 black, average duck 2 red

4 ducks carries on this logic but with more regions. Scenario 1 is that the 3rd duck (green) is between the previous 2 like this:

 Same as before, but with duck 3 in the same quadrant, so it doesn't affect the answer

Same as before, but with duck 3 in the same quadrant, so it doesn't affect the answer

This happens 1/ 4 of the time and if it is true then it works just like the 3 duck case, with a probability of 3/ 4 of being able to place duck 4.

Scenario 2 is when the 3rd duck is somewhere in the regions either side of scenario 1. On average that is 45 degrees away (if this wasn’t a uniform distribution we’d have to go through the whole integration route, but surprisingly taking the average value here works). I’ve drawn in the average duck 3 in this case. This gives you 135 degrees where you already have 3 ducks. This is 3/ 8 of the whole circle. In total you get 5/ 8 where the 4th duck can land giving you 4 on the same side.

 Average duck 3 added in green for when it is in either of the 2 side quadrants

Average duck 3 added in green for when it is in either of the 2 side quadrants

Putting this together you get 1/ 4 * 3/ 4 + 1/ 2 * 5/ 8 = 8/ 16 = 1/ 2 (how satisfying is that?)

5 ducks works similarly, but with more cases. Essentially you do a big probability tree. It works out as 5/ 16. So for n=1, 2, 3, 4, 5 we get p=1, 1, 3/ 4. 1/ 2. 5/ 16. This gets a lot nicer if you write it as 1/ 1, 2/ 2, 3/ 4, 4/ 8, 5/ 16, .... The numerators increase by 1, the denominators double. For the general case it appears that p=n/2^(n-1). I haven’t been able to prove this (I suspect at this point the integration method is going to be the way, but it requires stats that I can’t remember. Maybe there is a neat induction?

P vs NP

P vs NP

Plans and Elevations

Plans and Elevations