One hundred ants are dropped on a
meter stick. Each ant is traveling either to the left or the right with constant
speed 1 meter per minute. When two
ants meet, they bounce off each other
and reverse direction. When an ant
reaches an end of the stick, it falls off.
At some point all the ants will have fallen off. The time at which this happens
will depend on the initial configuration of the ants.
Question:
Calculate the average time it takes for arbitrary
initial number of ants N to fall off the stick.
I understand the solution that yields $\frac{N}{N+1}$ as the answer, however, I don't get why my approach is wrong. Suppose N=3 and T be the time it takes for 3 ants to fall off the stick. I model the starting positions of the 3 ants as 3 i.i.d. Uniform (0,1) rvs. 1/4 of the time, the outermost ants (leftmost and rightmost) both start moving towards the ends of the stick. This means the time it takes for all the ants to fall off should be determined by the middle ant. On average, the middle ant is located at position 1/2 so the average time in this case is 1/2. The other 3/4 of the time, at least one of the outermost ants starts by moving inwards. This means the time it takes for all the ants to fall off should be determined by an outermost ant. Using order statistics, the max of 3 Uniform (0,1) rvs should be 3/ (3+1) = 3/4 so the average time in this case is 3/4. I'm making the assumption here that we can treat collisions of ants as if ants passed through each other. The approach yields the average time of 1/4 * 1/2 + 3/4 * 3/4 = 11/16 which is not the same as 12/16 = 3/4. What's wrong with my approach of conditioning on the starting directions of the outermost ants?
Best Answer
The problem with your solution is that the longest time is not determined by the middle ant.
You are correct about treating ants bouncing off each other as passing through each other. Thus, if you think about it that way, the time for an ant to fall off is the time it takes to get to the end as if there were no other ants, which is simply a uniformly distributed random variable from 0 to 1. It is well known that given $N$ of those variables, the expected value of the largest is $\frac{N}{N+1}$. If you don't know that, it's not hard to prove it.