500 ants are randomly put on a 1-foot string (independent uniform distribution for each ant between 0 and 1). Each ant randomly moves toward on end of the string (equal probability to the left or the right) at constant speed of 1 foot/minute until it falls of a t one end of the string. Also assume that the size of the ant is infinitely small. When two ants collide head-on, they both immediately change directions and keep on moving at 1 foot/min. What is the expected time for all ants to fall off the string?

I realize this question has been asked here. However, I am trying to understand the answer that is given for this question in my book:

It says the ants labels are randomly assigned and hence the labels of the ants can be changed with no difference to the result. So when the ants collide, they effectively continue in the same direction. This makes sense.

However, I am unclear about this part: If an ant is put on the x-th foot, the expected value for it to fall off is just x min. If it goes in the other direction, simply set it to 1-x. So, the original problem just becomes what is the expected value of the maximum of 500 IID random variables with a Uniform Distribution between 0 and 1. I don't understand how the difference in direction that it goes in is being accounted for.

  • $\begingroup$ The difference in direction doesn't matter overall, because it doesn't matter which way the ants are going. The whole thing is symmetric. The expected value is the maximum distance of an ant to the end it is walking towards. $\endgroup$ – Colm Bhandal Sep 2 '15 at 13:42
  • 1
    $\begingroup$ "If an ant is put on the x-th foot, the expected value for it to fall off is just x min. If it goes in the other direction, simply set it to 1-x" If $U$ is uniform on $(0,1)$ and if $V=U$ or $V=1-U$ with probabilities $p$ and $1-p$ respectively, independently on $U$, then $V$ is uniform on $(0,1)$. The ants problem uses this for $p=\frac12$. $\endgroup$ – Did Jun 30 '18 at 7:03

The distance of each ant from the end that it's moving towards is uniformly distributed over $[0,1]$. It's unnecessarily confusing to talk about the "$x$-th foot" and then calculate $1-x$; that introduces an arbitrary origin from which a coordinate is measured and then transforms that arbitrary coordinate to the non-arbitrary quantity that's actually of interest. Instead, just think directly of the ant's distance from the end it's moving towards.


The difference in direction doesn't matter. To see why, split the ants into two sets $S_l$ travelling left and $S_r$ travelling right. Because the overall distribution is random, so is the distribution within each of these sets. But now, in each set, the time until the last ant falls off is just the maximum value in the set. And so the overall maximum is the maximum of these two maximums. But this is equivalently just the maximum of $S = S_l \cup S_r$, which is exactly the maximum of the 500 random variables as mentioned in the question.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.