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 the case of 2 birds, consider the wire to be one decameter long so we can use a unit length, and the expected value will come out naturally as a fraction. Let bird 1 be at location w and bird 2 at location x. We need to integrate abs(w-x) over the double integral of each of w and x from 0 to 1.

Integ{0 to 1} Integ{0 to 1} abs(w-x) dw dx = Integ{0 to 1} ( Integ{0 to x}(x-w)dw + Integ{x to 1} (w-x) dw ) dx

= Integ{0 to 1} ([xw-(w^2)/2]{w=0 to x} + [(w^2)/2-x1]{w=x to 1} ) dx

= Integ{0 to 1} (x^2 - (x^2)/2 + 1/2 - x^2) dx

= [x/2 - (x^3)/6]{x=0 to 1}

= 1/2 - 1/6 = 1/3

(or 3.3333... measured in meters for a 10-meter wire)

I'm afraid 12 or 1000 birds would be a bit too complicated to handle, but the limit as the number of birds gets larger is the same as using an infinite wire instead of a finite one.  Let's assume an average of one bird per unit of distance on an indefinitely long wire.

In this case the probability of no birds in a given stretch of wire is e^-r where r is the length of the stretch (a particular example of a Poisson distribution, looking for zero occurrences). We want to know what fraction of randomly chosen points are colored, that is, that at least one of the two birds on either side of it has the other as its nearest neighbor.  By inclusion-exclusion, that is the probability that the right-hand bird is the left-hand bird's nearest neighbor plus the probability that the left-hand bird is the right-hand bird's nearest neighbor minus the probability that they are both each other's nearest neighbor.

In each case "left-hand bird" refers to the bird to the left of a randomly chosen point, and similarly for "right-hand bird" (they are not end birds, as in fact we are treating an infinite wire where there are no end birds, or infinitely many birds, where the two end birds count vanishingly small).

For a given distance r1 that the left-hand bird is from the randomly chosen point and distance r2 that the right-hand bird is from the point, that right-hand bird is the left-hand bird's nearest neighbor if there are no other birds within r1+r2 (that is, the distance between these two birds) units on the other side of the left-hand bird. Note: we already know that there are no other birds between the two, so we don't have to examine that amount of span on the side toward the random point and the right-hand bird.  Likewise, the left-hand bird is the right-hand bird's nearest neighbor if there are no other birds within r1+r2 units on the other side of the right-hand bird.  Since the intevals are equal, the probability of finding no bird within either span is the same, which is e^(-r1-r2), adding up to 2*e^(-r1-r2).  But we have to subtract the probability that they are mutually nearest neighbor, as that has been counted twice.  That probability is the probability that both these areas of the same size are devoid of other birds, which is e^(-2*r1-2*r2).  These have to be multiplied by the probability distributions for r1 and r2, so the double integral is

Integ{0 to inf} Integ{0 to inf} (e^-r1)*(e^-r2)*(2*e^(-r1-r2) - 2*e^(-2*r1-2*r2)) dr1 dr2

= Integ{0 to inf} (e^-r2)*[2*(e^-r2)*(e^(-2*r1))/(-2) - (e^-2*r2)*(e^(-3*r1))/(-3)]{r1 = 0 to inf}  dr2

= Integ{0 to inf} (e^-r2)*(e^(-r2) - (e^(-2*r2))/3)  dr2

= Integ{0 to inf} (e^(-3*r2) - (e^(-3*r2))/3) dr2

= [(e^(-2*r2))/9 - (e^(-3*r2))/2]{r2=0 to inf}

= -1/9 + 1/2 = 7/18

(or 70/18 measured in meters for a 10-meter wire- with infinitely many birds--ok, it's the limit as the number of birds increases without limit)

Posted by Charlie on 2004-06-07 15:44:05