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!

(In reply to re(3): Computer simulation by Charlie)

You must have an error in your simulation. Three birds gives the maximum expected value over a long run of trials - this is exactly one half of the overall length. There are two segments that are always counted - rather, the difference between max(1,2,3) and min(1,2,3) is the amount of wire painted.

According to my simulations, over many trials, the expected value of three birds in this case is 5 meters. In general, it is half the overall length of the wire. Once we introduce a fourth bird, the length of painted wire decreases. This is because with high probability, one of the birds has a newer nearest neighbor. Each bird introduced has this effect with high probability, thus decreasing the overall length of painted wire. So, in general from three birds to infinity, the average length of painted wire is decreasing.

Nonetheless, you've already got the solution, so this doesn't much matter. Well done.

Posted by Eric on 2004-06-07 17:23:36