The Waiting-Time Paradox, math that surprises you lesson

Buses on a route come every 10 minutes on average. A passenger who turns up at a random moment might expect to wait 5 minutes, half the average gap. If the timetable alternates gaps of 2 and 18 minutes, the average wait is in fact 8.2 minutes. This page explains why a random moment is more likely to fall in a long gap than in a short one, computes the expected wait exactly, and states the assumptions the result depends on.

Key terms

Waiting-time paradox

Definition Buses stop at a station on a timetable that repeats every $T$ minutes. In each cycle there are $k$ gaps between consecutive buses, of lengths $L_1, \dots, L_k$ minutes, all positive, with $L_1 + \cdots + L_k = T$ . A passenger arrives at a time chosen uniformly at random over one cycle, without regard to the timetable, and boards the first bus that comes, which always has room and leaves at once. An arrival at the exact moment a bus is there waits $0$ , which happens with probability $0$ and does not change any average. The average gap is $T/k$ , and a natural guess is that the passenger waits half of it on average. The waiting-time paradox is that the expected wait is

E[W] = \frac{L_1^2 + \cdots + L_k^2}{2T},

which is at least half the average gap, $T/(2k)$ , with equality exactly when all the gaps are equal. The resolution is that a random moment falls in a gap with probability proportional to the length of the gap, and the long gaps, which are caught more often, are also the ones that leave long waits.

In plain words The timetable lists each gap once, but the clock spends more time inside the long gaps. A passenger who turns up at a random moment is therefore usually inside a long gap, and a long gap usually leaves a long wait.

Example Take gaps of $2$ and $18$ minutes, so $T = 20$ , the average gap is $10$ minutes and half of it is $5$ . The arrival falls in the short gap with probability $2/20 = 0.1$ , and then the remaining wait is between $0$ and $2$ minutes, $1$ minute on average. It falls in the long gap with probability $18/20 = 0.9$ , and then the remaining wait is $9$ minutes on average. So

\begin{aligned} E[W] &= 0.1 \cdot 1 + 0.9 \cdot 9 \\[0.4em] &= 8.2 \text{ minutes}. \end{aligned}

The formula agrees, since $(2^2 + 18^2)/(2 \cdot 20) = 328/40 = 8.2$ . The expected wait is less than the average gap of $10$ minutes, but well above $5$ .

Length-biased sampling

Definition Suppose a stretch of time of length $T$ is cut into consecutive intervals of lengths $L_1, \dots, L_k$ , and a moment is chosen uniformly at random in the stretch. The interval that contains it is interval $i$ with probability $L_i / T$ , and the moment lands exactly on a boundary with probability $0$ . This is called length-biased sampling. It is a case of size-biased sampling, in which each item is chosen with probability proportional to its size, and here the size of an interval is its length. It differs from choosing one of the $k$ intervals from a list, which gives each of them probability $1/k$ . The expected length of the interval that contains the moment is

\frac{L_1^2 + \cdots + L_k^2}{T},

which is at least the average length $T/k$ , with equality exactly when all the lengths are equal.

In plain words Throw a dart at a timeline, and the gap it hits is chosen in proportion to its length. Long gaps are easier targets.

Example In the timetable with gaps of $2$ and $18$ minutes, the passenger’s gap is the short one with probability $1/10$ and the long one with probability $9/10$ . The long gap is nine times as likely to be the one experienced, although the timetable lists each gap once. The expected length of the gap that contains the arrival is

\begin{aligned} &0.1 \cdot 2 + 0.9 \cdot 18 \\[0.4em] &\quad = 16.4 \text{ minutes}, \end{aligned}

not $10$ . The expected wait of $8.2$ minutes is exactly half of $16.4$ , because inside whichever gap contains the arrival, the remaining wait is on average half the length of that gap.

Expected waiting time

Definition The expected waiting time is the average of the wait $W$ over the random arrival time. For an arrival time uniform over a cycle of length $T$ , it is the area under the graph of the wait divided by $T$ . The wait at time $t$ is the time from $t$ until the next bus. Across a gap of length $L$ it falls at a rate of one minute per minute from $L$ down to $0$ , and it jumps back up when a bus leaves. Over each gap the region under the graph is therefore a right triangle whose two legs have length $L$ , with area $L^2/2$ , measured in square minutes. Adding the triangles and dividing by $T$ minutes gives the formula $E[W] = (L_1^2 + \cdots + L_k^2)/(2T)$ in minutes. The same formula follows from weighting the average remaining wait $L_i/2$ in gap $i$ by the probability $L_i/T$ of being in that gap. It needs the arrival time to be uniform over the cycle and chosen without regard to the timetable. A passenger who reads the timetable and times the arrival has a different arrival distribution and a different expected wait, and a fixed repeating timetable says nothing about how real buses spread out or bunch together.

In plain words Draw the wait as a sawtooth. It shrinks to zero as each bus approaches and jumps back up when the bus leaves. The expected wait is the average height of the sawtooth, and each gap contributes a triangle whose area grows with the square of the gap’s length, so a few long gaps weigh heavily.

Example For gaps of $2$ and $18$ minutes the triangles have areas $\tfrac12 \cdot 2^2 = 2$ and $\tfrac12 \cdot 18^2 = 162$ square minutes. Their total is $164$ , and $164/20 = 8.2$ minutes. Keeping the cycle at $20$ minutes with two buses, gaps of $4$ and $16$ minutes give

\frac{4^2 + 16^2}{2 \cdot 20} = \frac{272}{40} = 6.8

minutes, and gaps of $10$ and $10$ give $200/40 = 5$ minutes. The number of buses and the average gap are the same in all three timetables, and only the regularity changes.

Inspection paradox

Definition Suppose a whole is divided into $k$ parts of sizes $s_1, \dots, s_k$ , all positive, with total $S$ , and one unit of the whole, such as a moment of time or a member of a group, is chosen uniformly at random. The part that contains it is part $i$ with probability $s_i / S$ , so its expected size is

\frac{s_1^2 + \cdots + s_k^2}{S},

which is at least the average part size $S/k$ , with equality exactly when all the sizes are equal. The inspection paradox is this gap between the average size of the parts and the average size of the part found by inspecting a random unit. Both averages are correct, and they answer different questions.

In plain words Ask the people inside groups how big their group is, and the answers are larger on average than the average group size, because big groups contain more people to ask.

Example A school has two classes, one of $10$ students and one of $50$ , so the average class size is $30$ . A student chosen at random is in the small class with probability $10/60$ and in the large class with probability $50/60$ . The expected size of that student’s class is

\begin{aligned} \frac{10^2 + 50^2}{60} &= \frac{2600}{60} \\[0.4em] &\approx 43.3. \end{aligned}

The waiting-time paradox is the same effect with gaps as the parts and moments as the units. The friendship paradox is another case, with people as the parts and the entries on all friend lists as the units, since each person is named on as many lists as they have friends.

Check yourself

A timetable repeats every 20 minutes with gaps of 5 and 15 minutes. Find the probability that a passenger arriving at a uniformly random time lands in each gap, and the expected wait.

Show the answer

The arrival lands in the short gap with probability $5/20 = 0.25$ and in the long gap with probability $15/20 = 0.75$ . The average remaining waits are $2.5$ and $7.5$ minutes, so

\begin{aligned} E[W] &= 0.25 \cdot 2.5 + 0.75 \cdot 7.5 \\[0.4em] &= 0.625 + 5.625 \\[0.4em] &= 6.25 \text{ minutes}. \end{aligned}

The formula gives the same value, since $(5^2 + 15^2)/(2 \cdot 20) = 250/40 = 6.25$ . It lies between the $5$ minutes of the regular timetable and the $6.8$ minutes of the timetable with gaps of $4$ and $16$ .

For the timetable with gaps of 2 and 18 minutes, someone argues that half the gaps are short and half are long, so the average wait is $(1 + 9)/2 = 5$ minutes. Which random experiment does give 5 minutes, and why is it not the experiment of a passenger who arrives at a uniformly random time?

Show the answer

The value $5$ is the expected wait if a gap is chosen first, each with probability $\tfrac12$ , and then the arrival time is chosen uniformly inside that gap. In general this experiment gives

\frac{1}{k} \left( \frac{L_1}{2} + \cdots + \frac{L_k}{2} \right) = \frac{T}{2k},

exactly half the average gap. A passenger arriving at a uniformly random time does not choose a gap first. The arrival lands in a gap with probability proportional to its length, $0.1$ for the short gap and $0.9$ for the long one, and these weights give $0.1 \cdot 1 + 0.9 \cdot 9 = 8.2$ minutes.

The answer $8.2$ also needs the arrival to be chosen without regard to the timetable. A passenger who reads the timetable and always arrives one minute before a bus waits one minute every time.

A timetable repeats every 20 minutes with gaps of 1, 1, 1 and 17 minutes. Find the average gap and the expected wait. Then show that a timetable with only two gaps per cycle always has an expected wait shorter than its average gap.

Show the answer

There are $4$ gaps in $20$ minutes, so the average gap is $5$ minutes. The expected wait is

\begin{aligned} \frac{1 + 1 + 1 + 17^2}{2 \cdot 20} &= \frac{292}{40} \\[0.4em] &= 7.3 \end{aligned}

minutes, longer than the whole average gap. The single long gap holds $17/20$ of the time and leaves an average wait of $8.5$ minutes.

With two gaps $a$ and $b$ , the average gap is $(a + b)/2$ and the expected wait is $(a^2 + b^2)/(2(a + b))$ . Their difference is

\begin{aligned} &\frac{a + b}{2} - \frac{a^2 + b^2}{2(a + b)} \\[0.4em] &\quad = \frac{(a + b)^2 - a^2 - b^2}{2(a + b)} \\[0.4em] &\quad = \frac{ab}{a + b}, \end{aligned}

which is positive because $a$ and $b$ are positive. So with two gaps the expected wait is always less than the average gap, and by the general result it is at least half of it. For gaps of $2$ and $18$ the difference is $36/20 = 1.8$ , and $10 - 1.8 = 8.2$ as before. With more gaps, as the timetable above shows, the expected wait can exceed the average gap.

The Waiting-Time Paradox

Video 1, chapter 12

Key terms

Waiting-time paradox

Length-biased sampling

Expected waiting time

Inspection paradox

Check yourself