4
$\begingroup$

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?

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ OK. You first... $\endgroup$ – Did Nov 3 '12 at 9:16
  • $\begingroup$ @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.) $\endgroup$ – ShreevatsaR Nov 3 '12 at 9:18
  • $\begingroup$ The question is about the fraction of the circle that gets painted, not of the number of segments. $\endgroup$ – WimC Nov 3 '12 at 9:22
  • $\begingroup$ @WimC: So it is. Thanks! $\endgroup$ – joriki Nov 3 '12 at 9:24
  • $\begingroup$ @WimC: I've updated the answer to address the actual question. $\endgroup$ – joriki Nov 3 '12 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.