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?

  • 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
    @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