All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Bird on a Wire (Posted on 2004-06-07) Difficulty: 5 of 5
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!

No Solution Yet Submitted by Sam    
Rating: 3.7000 (10 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Full solution | Comment 32 of 42 |

Suppose the length of the wire is L, and let X[1], ... X[n] be the location of the i'th bird, where X[i]~U[0, L].  Then the total length being painted is X(n)-X(1), where X(i) denote the ordered statistic of X[i].  That is, X(1) is the shortest position from the left, X(2) is the 2nd, ..., X(n) is the furthest position.  Then the expected value of the total length is given by E[X(n)-X(1)] = E[X(n)] - E[X(n)].

It's easy to find the distribution for X(n) and X(1)

P(X(n)<x) = P(X[1]<x, ..., X[n]<x) = product(P(X[i]<x)) = (x/L)^n.

P(X(1)<x) = 1-P(X(1)>x) = 1-[(L-x)/L]^n

So by taking the derivative of the cdf w.r.t x,
pdf for X(n) = (n/L)(x/L)^(n-1) = n*x^(n-1)/L^n
pdf for X(1) = (n/L)[(L-x)/L]^(n-1) = n*(L-x)^(n-1)/L^n

So E[X(n)] = x*f(X(n), x)dx, x=0..L
= L*n/(n+1)
and E[X(1)] =x*f(X(1), x)dx, x=0..L
= L/(n+1)

Therefore, the expected length = L*n/(n+1)-L/(n+1) = L*(n-1)/(n+1)


  Posted by Bon on 2004-07-12 17:52:56
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information