3
$\begingroup$

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?

$\endgroup$
1
  • 3
    $\begingroup$ "This means the time it takes for all the ants to fall off should be determined by the middle ant" is incorrect. Say the ants land at points $70$, $80$ and $90$cm from the left end of the metre stick, and are moving (respectively) left, right and right. The longest time is not taken by the middle ant in this case. $\endgroup$
    – Chris Lewis
    Commented Jul 8 at 19:57

1 Answer 1

Reset to default
5
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Independent and identically distributed is crucial here, which follows by the view of ants passing through each other, and the assumption that initial locations are uniform and independent. Remarkably, it seems to me that the initial directions do not need to be independent of each other as long as the initial direction of each ant is independent of its initial location. Overall, there are several unstated assumptions in the statement of this question. $\endgroup$
    – Michael
    Commented Jul 8 at 22:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .