Random Ants

Five hundred ants are dropped onto a one-foot string, their positions independent and uniform on $[0,1]$ . Each ant independently faces left or right with equal chance and walks at one foot per minute until it falls off an end. The ants are points. When two collide head-on they instantly reverse and keep walking at the same speed. What is the expected time until every ant has fallen off?

Reveal solutionHide solution

#The collision is a disguise

Two ants meeting head-on and bouncing apart trace the very same pair of paths as two ants that walk straight through each other. The ants are identical points, so relabelling them at the instant of contact turns the bounce into a pass-through. Apply that at every collision and the whole jostling crowd becomes five hundred ghosts that ignore one another completely.

A collision that reverses two ants looks exactly like the two passing through, so the crowd behaves like non-interacting walkers. Each walker falls off after travelling its distance to the chosen end, a Uniform[0,1] time, and the last departure is the maximum of the n times.

The bookkeeping changes, but the set of moments at which an ant leaves the string does not. Collisions never alter when the string finally empties.

#One ghost's exit time

A ghost starting at position $x$ and heading left falls off at time $x$ ; heading right, it falls at time $1-x$ . With $x \sim \mathrm{Uniform}[0,1]$ and the direction a fair coin, its exit time $T$ has, for any $t \in [0,1]$ ,

\PP(T \le t) = \tfrac{1}{2}\,\PP(x \le t) + \tfrac{1}{2}\,\PP(1-x \le t) = \tfrac{1}{2}\,t + \tfrac{1}{2}\,t = t. \tag{1}

So each ghost's exit time is itself $\mathrm{Uniform}[0,1]$ , and the five hundred exit times are independent because the positions and directions were drawn independently.

#The last one out

The string is empty the instant the slowest ghost falls, so the total time is the maximum of five hundred independent $\mathrm{Uniform}[0,1]$ times. The maximum of $n$ such draws has

\E\big[\max(T_1,\dots,T_n)\big] = \int_0^1 t \cdot n\,t^{\,n-1}\,dt = \frac{n}{n+1}. \tag{2}

With $n = 500$ ,

\E[\text{time to clear}] = \frac{500}{501} \approx 0.998 \text{ minutes}. \tag{3}

Five hundred ants barely outlast a single one. With so many starting points, almost surely one begins close to an end and marches the wrong way, dragging the finish to within a breath of the full minute.

#A quick check in code

The simulation stays close to the physical picture. Drop each ant at a uniform position, pick an end, and take the distance to that end as its fall time. Batching the trials holds the working set near 80 MB rather than the multi-gigabyte array a single allocation would demand.

import numpy as np

rng = np.random.default_rng()
ants, trials, batch = 500, 1_000_000, 20_000

last_fall = np.empty(trials)
for i in range(0, trials, batch):
    pos = rng.random((batch, ants))             # ant positions in [0, 1]
    end = rng.integers(0, 2, (batch, ants))     # 0 = left end, 1 = right end
    dist = np.abs(pos - end)                     # time to fall off the chosen end
    last_fall[i:i + batch] = dist.max(axis=1)   # the last ant to leave

print(last_fall.mean())

Tracking that mean as the trials accumulate shows it settle onto its limit. Since $\lvert \text{pos} - \text{end}\rvert$ is itself $\mathrm{Uniform}[0,1]$ , the same run confirms the direction never mattered.