# Puzzle : Birds on a circular wire

The problem is taken from my course on randomized algorithms :

There is a circle made of wire. n birds (assume n>2) occupy uniformly random position over it (visualize each bird occupying a point on the circumference of the circle). This will lead to partitioning of circle into n segments. We follow the following rule for painting these segments. A segment is painted if it is smaller than at least one of its neighboring segments. What is the expected fraction of the circle which gets painted?

I am not able to frame it mathematically. Any hints?

• Have you tried using the pigeonhole principle – yiyi Nov 3 '12 at 6:43
• That is funny!! – copper.hat Nov 3 '12 at 6:47
• Have you considered the analogous problem on the line segment [0, 1]? – Benjamin Dickman Nov 3 '12 at 7:17
• @MaoYiyi : Its a problem on continuous space, therefore Pigeon hole principle doesn't make sense here, I think. – damned Nov 3 '12 at 7:53
• @B.D : I can understand the analogy, but I don't know how to solve that either. Any references? – damned Nov 3 '12 at 7:54

Let an $(n+1)$-th bird perch randomly uniformly on the wire. Now the circle is divided into $n+1$ segments, and we're looking for the probability that the two segments next to the additional bird together are smaller than at least one of the segments adjacent to them. Let $a\le b\le c$ be an ordered triple uniformly randomly drawn from $[0,1]^3$; then with $x:=c-a$ the measure of the set in which $x\lt a$ or $x\lt1-c$ is

$$\int_0^{1/3}x(1-x)\mathrm dx+2\int_{1/3}^{1/2}x(1-2x)\mathrm dx=\left[\frac12x^2-\frac13x^3\right]_0^{1/3}+2\left[\frac12x^2-\frac23x^3\right]_{1/3}^{1/2}=\frac7{108}\;,$$

where the first factor $x$ measures the possibilities for $b$ and the second factor measures the possibilities for $a$ that satisfy the inequalities. The measure of all ordered triples is $1/3!$, so the desired fraction is $7/18$.

P.S.: I tested the result numerically; here's the code.

• OK. You first... – Did Nov 3 '12 at 9:16
• @did: You didn't need to delete your answer... saying the same thing in multiple ways is often helpful. (And usually it isn't even exactly the same thing either.) – ShreevatsaR Nov 3 '12 at 9:18
• The question is about the fraction of the circle that gets painted, not of the number of segments. – WimC Nov 3 '12 at 9:22
• @WimC: So it is. Thanks! – joriki Nov 3 '12 at 9:24
• @WimC: I've updated the answer to address the actual question. – joriki Nov 3 '12 at 11:58