Expected Time for All Ants to Fall Off a Stick
A stick has length $L$. There are $n$ ants on the stick at fixed, known positions $p_1, p_2, \ldots, p_n$ (all distinct, with $0 < p_i < L$). Each ant independently and with equal probability chooses to walk left or right, and all ants move at speed 1. When two ants collide, they instantly reverse directions. When an ant reaches either end of the stick, it falls off.
Let $T$ be the time until all ants have fallen off. The only randomness is in the $n$ direction choices.
- For these positions, what is the largest value $T$ can take over all $2^n$ possible direction choices (the worst-case time)?
- For these positions, what is $E[T]$, the expected time for all ants to fall off?
Express your answers in terms of the positions $p_i$ and the stick length $L$.
Hints
- What happens if you imagine the ants passing through each other instead of bouncing? Can you distinguish the two scenarios if the ants are identical?
- Under the pass-through model, each ant's fall-off time is simply $p_i$ or $L - p_i$ with equal probability, and $T$ is the max over all ants. The worst case is every ant heading to its farther end.
- You need $E[\max_i T_i]$ where the $T_i$ are independent two-point random variables. Enumerate all $2^n$ direction assignments, or use $P(T \le t) = \prod_i P(T_i \le t)$ and $E[T] = \int_0^L P(T > t)\,dt$.
Worked Solution
How to Think About It: The heuristic is *relabeling*: when two identical ants collide and both reverse, the picture is indistinguishable from the two ants walking straight through each other. The set of occupied positions at every moment is the same in both stories, so the time until the stick is empty is the same too. That turns a collision-tracking nightmare into $n$ independent walkers, each heading straight to an end.
Quick Estimate: Take $L = 100$ with ants at $30$ and $80$. Pass-through: the ant at $30$ needs $30$ (left) or $70$ (right); the ant at $80$ needs $80$ (left) or $20$ (right). Worst case: both pick the far end, $\max(70, 80) = 80$. Expected: the four equally likely cases give $\max(30,20)=30$, $\max(30,80)=80$, $\max(70,20)=70$, $\max(70,80)=80$, average $(30+80+70+80)/4 = 260/4 = 65$.
Approach: Replace collisions by pass-through, write each ghost ant's exit time as a two-point random variable, then take the max (worst case) and the expected max (via enumeration or the CDF).
Formal Solution:
*Step 1: Pass-through.* Swapping the labels of two ants at each collision turns "both reverse" into "both continue". The set of positions on the stick is unchanged at every time, so $T$ (the moment that set becomes empty) is unchanged. In the pass-through picture, ghost ant $i$ walks straight in its chosen direction, so its exit time is $$T_i = \begin{cases} p_i & \text{if it walks left} \\ L - p_i & \text{if it walks right} \end{cases}$$ each with probability $1/2$, independently across ants, and $T = \max_i T_i$.
Write $a_i = \min(p_i, L - p_i)$ and $b_i = \max(p_i, L - p_i)$, so $T_i \in \{a_i, b_i\}$.
*Part 1: Worst case.* $T_i \le b_i$ for every ant, with equality when ant $i$ heads to its farther end. Choosing that for every ant gives $$\boxed{T_{\text{worst}} = \max_{1 \le i \le n} \max(p_i, L - p_i)}$$ This is set by the ant closest to an end of the stick (farthest from the center), since $\max(p, L-p)$ grows as $p$ moves away from $L/2$. It is always less than $L$ because $0 < p_i < L$.
*Part 2: Expected time.* Enumerating the $2^n$ equally likely direction vectors, $$\boxed{E[T] = \frac{1}{2^n} \sum_{\mathbf{d} \in \{\text{left}, \text{right}\}^n} \max_{1 \le i \le n} T_i(d_i)}$$ with $T_i(\text{left}) = p_i$ and $T_i(\text{right}) = L - p_i$.
An equivalent form that is faster by hand uses independence: $P(T \le t) = \prod_i F_i(t)$, where $F_i(t) = 0$ for $t < a_i$, $1/2$ for $a_i \le t < b_i$, and $1$ for $t \ge b_i$. Since $T \ge 0$, $$E[T] = \int_0^{L} \Bigl(1 - \prod_{i=1}^n F_i(t)\Bigr)\,dt,$$ and the integrand is a step function that changes only at the $a_i$ and $b_i$.
*Check on the example* ($L = 100$, ants at $30, 80$, so $a = (30, 20)$, $b = (70, 80)$): $\prod F_i = 0$ on $[0, 30)$, $1/4$ on $[30, 70)$, $1/2$ on $[70, 80)$, $1$ from $80$ on. So $E[T] = 30 \cdot 1 + 40 \cdot \tfrac34 + 10 \cdot \tfrac12 = 30 + 30 + 5 = 65$, matching the enumeration. A direct simulation with real collisions and reversals gives the same $80$ and $65$.
Note that $P(T = \max_i b_i) \ge 1/2$ always (the ant achieving it just has to head to its far end), and $E[T]$ moves toward the worst case as more ants sit near the ends, because then it is likely that one of them heads the long way.
Answer: (1) The worst-case time is $\max_i \max(p_i, L - p_i)$, set by the ant nearest an end. (2) $E[T] = 2^{-n} \sum_{\mathbf{d}} \max_i T_i(d_i)$, equivalently $\int_0^L \bigl(1 - \prod_i F_i(t)\bigr)\,dt$. For $L = 100$ with ants at $30$ and $80$: worst case $80$, expected $65$.
Intuition
The deep lesson here is that symmetry can obliterate complexity. On the surface, tracking $n$ ants bouncing off each other seems like a nightmare of combinatorial case analysis. But the moment you realize that identical particles bouncing is indistinguishable from particles passing through each other, the entire collision structure becomes irrelevant. Each ant just walks in a straight line. This relabeling trick shows up across quant work: whenever interacting agents are identical, check whether their interactions actually matter or are just an artifact of labeling.
The second insight is about the expected maximum. Each individual ant's expected exit time is $\tfrac12 p_i + \tfrac12 (L - p_i) = L/2$, yet the time for ALL ants to fall off is driven by the slowest one, and the expected maximum of independent random variables grows as you add more of them. With many ants near the ends, it becomes very likely that at least one heads the long way, so $E[T]$ approaches the worst case. The same effect appears in risk management: the expected worst loss across many positions is much larger than the average loss of any single position.