A telephone wire stretched tight between two poles placed ten meters apart is a favorite resting spot for a flock of crows.

Suppose one morning two crows land on the wire, each at a random spot (the probability is uniformly distributed). With a bucket of paint and a brush you mark the stretch of wire between them. A certain length of wire will have been painted.

On average, what length of wire would you expect to have painted? Assume that each bird is a single point along the line, and so has no width.

Suppose instead that a dozen crows landed on the wire, each at an independent, random location, and you painted the stretch of wire between each bird and its nearest neighbor. On average, what total length of wire would you expect to have painted now?

And if a thousand crows landed?

A computer-generated solution could be found, but bonus points will be awarded for a formal proof!

This is a very complicated problem, not a simple problem.

If it were simple it would be asking:  What is the average length between the first and last bird?  This question does indeed have solution (n-1)/(n+1).

The problem as written allows more unpainted sections as n increases.  For example, with 4 crows at positions {1,2,8,9} only the intervals (1,2) and (8,9) are painted.  Only the portion from each crow to its nearest neighbor is painted.

The simple and complicated versions are identical only when n=2 or n=3.

When there are n crows, the wire has n+1 intervals of average size 1/(n+1) of the total wire.  The first and last are unpainted and the second and second-from last are painted.  What is needed for a formal proof is the average length and number of the intervening n-3 intervals.

If the probablility of an interval being painted is p and painted intevals have average length l the solution is (2+(n-3)pl)/(n+1)

My wild guess is that as n increases p may approach 1/2 and l may approach 1/(n-1) but I certainly have no proof of this.  I'll try looking at Charlie's solutions to see if I can get a better estimate.

-Jer

Posted by Jer on 2004-06-09 09:17:35