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?

  • 4
    Have you tried using the pigeonhole principle2012-11-03
  • 1
    That is funny!!2012-11-03
  • 2
    Have you considered the analogous problem on the line segment [0, 1]?2012-11-03
  • 0
    @MaoYiyi : Its a problem on continuous space, therefore Pigeon hole principle doesn't make sense here, I think.2012-11-03
  • 0
    @B.D : I can understand the analogy, but I don't know how to solve that either. Any references?2012-11-03
  • 0
    @damned, I think the idea works because you are splitting up the continuous circle into sections. Each section is either smaller than the left or right, nor not. You have n birds, so how many sections of the circle do you have? *plus, it was humorous2012-11-03
  • 0
    @B.D. Losing on purpose the stochastic invariance by rotations? Hmmm... this might not be the best move.2012-11-03

1 Answers 1

2

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.

  • 0
    OK. You first...2012-11-03
  • 0
    @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.)2012-11-03
  • 0
    The question is about the fraction of the circle that gets painted, not of the number of segments.2012-11-03
  • 0
    @WimC: So it is. Thanks!2012-11-03
  • 0
    @WimC: I've updated the answer to address the actual question.2012-11-03
  • 0
    @joriki: I got the same answer but in a slightly different way. I computed that the expected length of a single painted segment is $$ 2(n-1)\int_0^{1/2} x(1-2 x)^{n-2} dx - (n-1)\int_0^{1/3}x(1-3 x)^{n-2} dx = \frac{7}{18 n}. $$2012-11-03
  • 0
    @WimC: Interesting! So you're saying there are $2$ options for which adjacent segment is longer, $n-1$ options for the second point forming it at distance $x$ on that side, and measure $(1-2x)^{n-2}$ for the remaining $n-2$ points, and then we have to subtract the cases where both adjacent segments are longer?2012-11-03
  • 0
    @joriki: exactly.2012-11-03
  • 0
    @joriki: Err, actually I started with the pdf of the length of a single segment: it is $(n-1)(1-x)^{n-2}$. That's where the factor $(n-1)$ comes from. The other probabilities for a given length $x$ are then as you described: $$ \frac{2(1-2x)^{n-2} - (1-3x)^{n-2}}{(1-x)^{n-2}} $$ for $x \in [0, \tfrac{1}{3}]$ and $$ \frac{2(1-2x)^{n-2}}{(1-x)^{n-2}} $$ for $x \in [\tfrac{1}{3}, \tfrac{1}{2}]$ and $0$ for $x \geq \tfrac{1}{2}$.2012-11-03
  • 0
    @WimC: I'm getting math processing errors in this part of the page since you added that comment -- is it being formatted correctly for you?2012-11-03
  • 0
    @joriki: it is.2012-11-03
  • 0
    Could you post your previous answer.2012-11-05
  • 0
    @MaoYiyi: You can access earlier versions of the post by clicking on the timestamp (currently "yesterday") next to "edited" underneath the post. You can unfold any collapsed version by clicking on the corresponding number (in this case $1$). I don't want to repost my earlier answer because it doesn't answer the question. Feel free to ask a different question and post my earlier answer as an answer to that.2012-11-05