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!

For just 2 birds, a simulation finds in one million trials an average of  3.33394 and standard error of the mean of  0.00236.

The same number of trials for 12 birds finds a mean of 3.65490 and std error of 0.00115.

For 1000 birds with 10,000 trials we get a mean of  3.88462  and std err of 0.00122.

The program below measures results in decameters (that is, in this case, the fraction of the wire covered, as that is the length of the wire), but I've converted the measures reported above to meters.

The program is:

DECLARE SUB sort (n1#, n2#)
CLEAR , , 4000
DEFDBL A-Z
n = 1000
DIM SHARED bird(n)
RANDOMIZE TIMER

FOR trial = 1 TO 10000
 FOR b = 1 TO n
   bird(b) = RND(1)  ' measured in decameters
 NEXT
 sort 1, n
 t = bird(2) - bird(1)
 counted = 1
 FOR b = 2 TO n - 1
  IF bird(b + 1) - bird(b) < bird(b) - bird(b - 1) THEN
   t = t + bird(b + 1) - bird(b)
   counted = 1
  ELSE
   IF counted THEN
    counted = 0
   ELSE
    t = t + bird(b) - bird(b - 1)
   END IF
  END IF
 NEXT b
 tot = tot + t: totSq = totSq + t * t
 numTr = numTr + 1
 IF numTr MOD 100 = 0 THEN
   PRINT numTr,
   avg = tot / numTr
   v = ((totSq) - numTr * (avg * avg)) / (numTr - 1)
   PRINT USING "  #.######"; avg; SQR(v / numTr)
 END IF
NEXT trial

avg = tot / numTr
v = ((numTr * totSq) - (tot * tot)) / (numTr * (numTr - 1))
PRINT USING "  #.######"; avg; SQR(v / numTr)

SUB sort (n1, n2)
  IF n1 = n2 THEN EXIT SUB
  pvt = bird(n1)
  IF bird(n2) < pvt THEN pvt = bird(n2)
  DO
    i = n1 - 1: lower = 0
    DO
      i = i + 1
      IF i <= n2 THEN IF bird(i) < pvt THEN lower = i
    LOOP WHILE bird(i) <= pvt AND i <= n2
    IF i > n2 AND lower = 0 THEN EXIT SUB
    IF i > n2 THEN pvt = bird(lower)
  LOOP WHILE i > n2
  sw1 = i
  i = n2 + 1
  DO
    i = i - 1
  LOOP WHILE bird(i) > pvt AND i >= n1
  sw2 = i
  DO
    IF sw2 < sw1 THEN
      sort n1, sw1 - 1
      sort sw2 + 1, n2
      EXIT SUB
    END IF
    IF bird(sw1) > bird(sw2) THEN
        SWAP bird(sw1), bird(sw2)
    END IF
    DO
      sw1 = sw1 + 1
    LOOP UNTIL bird(sw1) > pvt OR sw1 > sw2
    DO WHILE sw2 >= sw1 AND bird(sw2) > pvt
      sw2 = sw2 - 1
    LOOP
  LOOP
END SUB

The result is reported in decameters (so as to give fraction of the wire covered), but I've multiplied by 10 in the above reporting, to match the meters that are asked for.

The subroutine sort is a quick sort of the bird array from starting and ending points passed as a parameter so it could recurse.

The first and last birds are treated separately as they always paint toward the main part of the crowd. A check is made to assure we don't count the same stretch twice for mutually nearest birds.

Posted by Charlie on 2004-06-07 13:56:29