Generalization of this question about ants bumping into each other on the real number line:
"There are n ants on a meter stick [real number line $\mathbb{R}^1$], each walking at $1cm/s$ in some direction. If two ants collide, they both reverse direction. Given the starting positions and directions of all the ants, how long will it take until the last ant falls off?" Also, the way the ants positions are initialized is: uniformly spaced, $1$ ant every $1$ cm. (So for example you will not have all ants on top of each other at the end of the stick for a finish time of $\sim0$ seconds)
- the lower bound on the time will be $50$ seconds if the ants all face outward at the start and walk to the nearest edge.
- the upper bound is described in the linked questions and is $100$ seconds.
- so for any random instantiation of the ants, it will take between $50$ seconds to $100$ seconds to all exit
-So, my question is, over all $2^{100}$ possible initializations of ants [each of the $100$ ants can point in $1$ of $2$ directions] what is the expected time for the ants to all walk off the stick? Or more general, what is the probability distribution, for the completion time $t$, $p(t=T)$? Where the support of $t$ is nonzero only for $T=50$ seconds to $T=100$ seconds.
above question comes from $2$ places
First, as the Quora answer makes clear, you can think of this problem simply as the ants moving without colliding at all, since whether they collide or not, the end effect is still having two ants moving in the two different directions.
Second, with $100$ ants spread out and having $1$ cm between them, the two outmost ants start $0.5$ cm from the ends, and so the upper bound is $99.5$ seconds, while the two most inside ants start $49.5$ cm from the ends, and so the lower bound is $49.5$ seconds.
Third, the probability distribution for the possible outcomes will be a geometric distribution. Indeed, the expected time will be very close to the upper bound.
To see this, consider: if at least one of the outer ants start by walking inward, it'll take $99.5$ seconds, and the chance of that is pretty good: $\frac{3}{4}$.
And even if both outside ants immediately walk off (with a chance of $\frac{1}{4}$), then there is a $\frac{3}{4}$ chance that at least one of the second to the most outer ants start walking inward, in which case it'll take $98.5$ seconds. So, there is a $\frac{3}{16}$ chance it will take $98.5$ seconds.
And we get exponentially smaller chances for that time to go down, e.g. there is a $\frac{3}{64}$ chance it will take $97.5$ seconds, a $\frac{3}{256}$ chance it will take $96.5$ seconds, etc. Like I said, you get a geometric distribution with smaller and smaller probabilities. As you found yourself, the probability of getting the lower bound is $1$ in $2^{100}$. ut even getting something below $90$ is highly improbable, as you'd need all of the $20$ outmost ants face the right way, so that only happens $1$ in $2^{20}$ times.
Finally, here is my rough calculation for the expected time ... someone who is better with series (especially partial sums) should be able to give a more precise answer ...
$$E = \sum_{i=0}^{49} (\frac{3}{4})\cdot (\frac{1}{4})^{i} \cdot (99.5-i) + (\frac{1}{4})^{50} \cdot 49.5 \approx$$
$$\sum_{i=0}^{\infty} (\frac{3}{4})\cdot (\frac{1}{4})^{i} \cdot (99.5-i) = $$
$$\frac{3}{4}\cdot \big(99.5 \cdot \sum_{i=0}^{\infty} (\frac{1}{4})^{i} -\sum_{i=0}^{\infty} (\frac{1}{4})^{i} \cdot i \big) = $$
$$\frac{3}{4}\cdot \big(99.5 \cdot \frac{1}{1-\frac{1}{4}} -\frac{1}{4} \cdot \sum_{i=1}^{\infty} (\frac{1}{4})^{i-1} \cdot i \big) = $$
$$\frac{3}{4}\cdot \big(99.5 \cdot \frac{1}{\frac{3}{4}} -\frac{1}{4} \cdot \frac{1}{(1-\frac{1}{4})^2}\big) = $$
$$\frac{3}{4}\cdot \big(99.5 \cdot \frac{4}{3} -\frac{1}{4} \cdot \frac{16}{9}\big) = $$
$$99.5 -\frac{3}{9} \approx 98.8333 $$
Note that if you use $101$ ants, so that the two outer ants are at the very end of the stick, and the middle ant is in the middle, you get an upper bound of $100$ seconds, a lower bound of $50$ seconds, and an expected time of a little over $99$ seconds.