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!

{[0,5 + ln(4/3)] [N-5]  + 2} / [N+1]

gives the expected portion of the line painted for N>=4 birds.

This works out to a tad under 0,79 for very large N.

Reasoning:

We want to compute the probability that the middle interval between four consecutive bird positions is painted. For convenience, we take the two outside bird positions to be located at 0 and 1. I.e., with 1 > b > a > 0 we want to compute the probability P that [a,b] will is painted.

We distinguish three cases:

1) If a < 1/3 then [a,b] will be painted iff b is closer to a than to 1. Thus the probability of being painted in this case is 0,5.

2) If a > 1/2 then the probability of being painted is 1.

3) If 1/2 > a > 1/3 then [a,b] will be painted unless both of the following conditions hold:

* b has to be closer to 1 than to a, so  b - a > 1 - b

* a has to be closer to 0 than to b, so   b - a > a

I.e. [a,b] will be painted unless b > Max (2a, .5 + .5a)

The range available for b is the interval b > a, so that the probability, P(a), that the [a,b] is painted is conforms with

1 - P(a) = 1 - [1 - M(a)] / [1 - a]   , i.e.,

P(a) = [ M(a) - a ] / [1 - a ]   where

M(a) = Max(2a, .5 + .5a)  so that

P(a) = a/[1-a]   for 1/3 < a < 1/2

This completes the examination of the 3 cases.

To determine P = probability that the middle interval is painted, we have to compute a weighted average of the probabilities for all cases.

P = 1/3 * (1/2) + 1/2 * (1) + �� a da / (1 - a)

where the integral (corresponding to the third case) runs from 1/3 to 1/2. This gives

P = ,5 + ln(4/3), or about ,7876

Next, we have to consider a couple of special cases. Let 0<x1<....<xN<1 be the positions of the N birds. The intervals [0,x1] and [xN,1] will never be painted. The average length of each of these two intervals is 1/[N+1]. This can be viewed as an extension of the result for the two bird case, where the average separation between birds was 1/3. Perhaps a simpler way of seeing it though, would be to consider that, on average, the birds will be distributed evenly about the centre point with equal separation between each other and with the endpoints.

In addition, the interval [x1,x2] will only be painted if [x2,x3] is not painted, with a similar condition holding for [xN-1,xN]. Hence, these two intevals contribute an amount (1-P) 2 / (N+1)  to the painted length expectation value.

The average length which remains (i.e. the average distance between x2 and xN-1) is [N-3]/[N+1]. The portion of that interval we would expect to be painted is P. This completes the demonstration.

For 12 birds, you would expect close to ,578 of the interval to be painted. For 1000 birds, the value is 78,5%.

Edited on March 28, 2008, 6:46 am

Posted by FrankM on 2008-02-03 22:01:06