Expected Time for All Ants to Fall Off a Stick

Worked Solution

How to Think About It: This is the classic ants-on-a-stick puzzle, and the whole thing hinges on one beautiful observation: when two ants collide and reverse, it is indistinguishable from the ants passing through each other. Think about it -- two identical ants approaching each other, colliding, and turning around looks exactly the same as two ants walking right through each other. Once you internalize this, the problem collapses from something that seems horribly complicated (tracking all the collisions) into something trivial (each ant just walks in a straight line to the edge).

Quick Estimate: Say $L = 100$ and we have 5 ants scattered across the stick. Each ant's time to fall off is either $p_i$ (if it goes left) or $L - p_i$ (if it goes right). The worst-case ant is the one closest to the center -- say at position 55. Its maximum possible time is $\max(55, 45) = 55$. For the expected max, consider the simplest case: one ant at position $p$. Its time is $p$ or $L - p$ each with probability $1/2$, so $E[T] = \max(p, L-p)$. For the single-ant case that settles it, but with multiple ants we need $E[\max_i T_i]$, which is harder. But the answer is always between $\max_i \min(p_i, L - p_i)$ and $\max_i \max(p_i, L - p_i)$.

Approach: Use the collision-symmetry principle, then compute $E[\max]$ over independent binary random variables.

Formal Solution:

*Step 1: The symmetry argument.*

Label the ants $1, \ldots, n$ by position. When two ants collide, they reverse direction. But since all ants are identical, we can equivalently say the ants pass through each other. Under this "pass-through" model, ant $i$ simply walks in its chosen direction at speed 1 until it falls off the edge. No collisions to track.

So ant $i$'s time to fall off is:

$$T_i = \begin{cases} p_i & \text{with probability } 1/2 \text{ (walks left)} \\ L - p_i & \text{with probability } 1/2 \text{ (walks right)} \end{cases}$$

The $T_i$ are independent (each ant chooses its direction independently).

*Step 2: Worst-case time.*

The maximum possible time for any single ant is $\max(p_i, L - p_i)$. So the worst case over all ants is:

$$T_{\max} = \max_{1 \le i \le n} \max(p_i, L - p_i)$$

This is achieved when every ant walks toward the farther end. In particular, the ant closest to the center of the stick determines this value. The absolute worst case is $L$ (an ant at one end walking to the other), but for given positions, it is $\max_i \max(p_i, L - p_i)$.

*Step 3: Expected time.*

We need $E[T] = E[\max_i T_i]$ where the $T_i$ are independent binary random variables. For each ant $i$, define $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\}$ each with probability $1/2$.

The total time $T = \max_i T_i$. We can compute this via the CDF:

$$P(T \le t) = \prod_{i=1}^n P(T_i \le t)$$

Since each $T_i$ takes only two values, $P(T_i \le t)$ is 0 for $t < a_i$, $1/2$ for $a_i \le t < b_i$, and 1 for $t \ge b_i$.

For concreteness, consider $n = 2$ ants at positions $p_1$ and $p_2$ on a stick of length $L$. We have four equally likely direction assignments, each with probability $1/4$. The expected time is:

$$E[T] = \frac{1}{4}\bigl(\max(p_1, p_2) + \max(p_1, L - p_2) + \max(L - p_1, p_2) + \max(L - p_1, L - p_2)\bigr)$$

For general $n$, there are $2^n$ equally likely direction vectors. The expected time is:

$$E[T] = \frac{1}{2^n} \sum_{\mathbf{d} \in \{L, R\}^n} \max_{1 \le i \le n} T_i(d_i)$$

where $T_i(L) = p_i$ and $T_i(R) = L - p_i$.

Answer: By the collision-symmetry principle, collisions are equivalent to pass-through, so each ant independently walks to one end in time $p_i$ or $L - p_i$. The worst-case time is $\max_i \max(p_i, L - p_i)$. The expected time is $E[T] = 2^{-n} \sum_{\mathbf{d}} \max_i T_i(d_i)$, computed by enumerating $2^n$ direction assignments. For large $n$, $E[T]$ concentrates near $\max_i \max(p_i, L - p_i)$ because it becomes increasingly likely that at least one ant walks toward the far end.