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 P(L < x) = F(x) for an arbitrary cumulative probability function F. Then the density function f(x) = F'(x) gives the probability density for the interval to have length x.

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

integral_0^infinity(x·F(x)·F(x)·f(x))dx/(1/3),

which we integrate by parts (very carefully!): let u=x, and dv = (F(x))^2·f(x)dx = d((F(x))^3 - 1)/3. (We can choose any antiderivative we like when integrating by parts, and this one allows the u·v term to vanish at infinity.) Then we get

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 1 - (B·P(Big))/A = 1 - B/(3A). When F(x) = 1- exp(-kx) is the exponential distribution,

B = integral_0^infinity(3exp(-kx) - 3exp(-2kx) + exp(-3kx))dx = (3 - 3/2 + 1/3)/k = 11/(6k),

while A = integral_0^infinity(exp(-kx))dx = 1/k. Therefore, the expected fraction painted is 1-(11/6k)/(3/k) = 1 - 11/18 = 7/18.

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 Probability

40618086