Birds on a Wire
By Stuart Anderson
I was recently looking at the solutions posted here to the bird on the wire problem, and was particularly struck by the third solution, which did not involve the notion of an exponential distribution at all. I found it somewhat hard to follow, so I started looking at the assumptions behind the other solutions, to see why you could solve the problem without the exponential distribution.
Here is the surprising result: part of the solution REALLY IS independent of the distribution, although the final answer does depend on the distrbution.
Let L be the length of an interval between adjacent birds. Suppose that the
A given interval will be painted twice if it is "small" i.e. shorter that both its neighbors, once if "medium", i.e. shorter than one and longer than the other neighbor, and not painted if "big", i.e. longer than both neighbors. What is the probability of each case and its expected length?
For the interval that is longer than its neighbors, the probability is
|integral_0^infinity(F(x)·F(x)·f(x))dx = integral_0^1(F^2)dF = 1/3.|
Similar calculations for the other two cases, using 1-F(x) in place of F(x) when we want the neighboring interval to be longer instead of shorter, give the same result. This is rather surprising in itself: regardless of the distribution, the probabilities P(big), P(medium), and P(small), are all exactly 1/3.
The expected length of an interval that is longer than both neighbors is
which we integrate by parts (very carefully!): let u=x, and
|eval_0^infinity(x·(F^3 - 1)) - integral_0^infinity(F^3-1)dx = integral_0^infinity(1-F^3)dx|
if F(x) approaches 1 sufficiently quickly for the eval term to vanish and the integral to converge. Let's call this number B (for "Big interval).
A similar but simpler calculation shows that the expected length of an arbitrary interval (no conditions as to its size relative to its neighbors) gives integral_0^infinity(1-F)dx. Let's call this number A (for "Average interval).
Since all but the "big" intervals are painted, the expected fraction painted is
|B = integral_0^infinity(3exp(-kx) - 3exp(-2kx) + exp(-3kx))dx = (3 - 3/2 + 1/3)/k = 11/(6k),|
A more detailed calculation shows that 2/18 if the length is painted twice (small intervals), 5/18 is painted once (medium) and 11/18 is unpainted (big intervals). Since these types of intervals occur with equal probability, this also shows that the ratio of mean sizes of small, medium, and big intervals is 2:5:11. Of course, if we took 1/3 of the intervals completely at random, we would expect them to cover 1/3 = 6/18 of the wire, so we can extend the ratio to include the overall average length: S:M:B:A = 2:5:11:6. Therefore, medium intervals are slightly shorter than the average length.
- Geometric Probabilities
- Are Most Triangles Obtuse?
- Barycentric Coordinates and Geometric Probability
- Bertrand's Paradox
- Birds On a Wire (Problem and Interactive Simulation)
- Birds on a Wire: Solution by Nathan Bowler
- Birds on a Wire. Solution by Mark Huber
- Birds on a Wire: a probabilistic simulation. Solution by Moshe Eliner
- Birds on a Wire. Solution by Stuart Anderson
- Buffon's Noodle Simulation
- Averaging Raindrops - an exercise in geometric probability
- Rectangle on a Chessboard: an Introduction
- Marking And Breaking Sticks
- Random Points on a Segment
Copyright © 1996-2017 Alexander Bogomolny