Thought Toys · Computation & information · Exhibit 125

The ambulance that arrives sooner by going slower.

Two crews answer the same emergency calls, one at a time, in the order they come in. The fast crew finishes a call a minute quicker on average, but its trips vary: some take five minutes, some take forty. The steady crew takes ten minutes, every time. Watch who your call waits for. On a busy day the slower crew is on its way to you sooner, and the reason is not how fast it drives. It is how much its trips vary.

The same calls, two crews ● the fast crew   ● the steady crew   ○ the average so far

fast crew · wait by the law— steady crew · wait by the law— fast crew · so far— steady crew · so far—

—

↳ your turn — drag How much the fast crew's trips vary down to zero and watch the fast crew win it back

What you're seeing

Each lane is one crew. The calls come in at random, and both crews get exactly the same calls at exactly the same moments. A crew that is free sets out at once. A crew that is busy leaves the call in the pile on the left, and the pile is the waiting line. The bar in each lane is the call the crew is on right now, filling up as the minutes pass. Its length is how long that trip takes. Two states, then: waiting in the pile, or being answered on the bar.

Look at the two kinds of bar. The steady crew's bars are all the same length, ten minutes each. The fast crew's bars are usually shorter, but every so often one is enormous. While that long trip runs, calls pile up behind it, and everyone in the pile pays for it. When a short trip comes along, there is often nobody waiting to cash it in. Short trips are wasted on an empty pile; long trips are charged to a full one. That asymmetry is the whole effect.

The chart underneath turns it into a number. The amber curve is the fast crew's average wait as its trips get more erratic, from all-the-same on the left to wildly varying on the right. The cyan line is the steady crew, which does not move because its spread is fixed at zero. Where the two cross is the tie. At the default pace, 4.8 calls an hour, the tie is at a spread of about 0.73. On this scale a spread of 1 is what you get from trips as random as an exponential clock, so the tie sits a little below that. At this pace, a crew that is a full minute faster per call, but merely exponential, already loses.

Now drag How busy the day is. The tie moves. At the quiet end of the slider, half a call an hour, it sits near a quarter, and even a slightly erratic fast crew loses, though nobody waits long either way. At the flat-out end, 5.5 calls an hour, it moves past 1.5, and the fast crew wins even while quite erratic. The steady crew is the slower one, so it is the first to approach its own wall, the load at which it can never catch up, and near that wall its wait outgrows any multiplier. Busy days protect speed. Quiet days reward steadiness. Neither day forgives spread for free.

The hollow dots are the two crews' running average waits, from the calls answered so far in this session. They wander at first, because a queue remembers: one bad trip poisons the next dozen waits. Press A year of calls, instantly and they settle onto the lines, which is the law doing what a law should. Nobody chose these numbers. They fall out of the arrival rate, the trip length, and the spread, and nothing else.

The rule, exactly. Calls arrive at random at rate λ. One crew serves them in order; a trip lasts a random time with mean m and spread C2 = variance / m2. Write ρ = λm for the share of the time the crew is busy. The mean wait before the crew sets out is

W = ρ m (1 + C2) / 2(1 − ρ)

This is the Pollaczek–Khinchine formula (1930, 1932), for the queue that engineers call M/G/1. The load sets the hyperbola; the spread sets the multiplier (1 + C2)/2. A crew whose trips are all the same length (C2 = 0) makes callers wait half as long as an exponential crew (C2 = 1) at the same load, and that exponential case is exhibit 58. Two crews answering the same calls tie where

1 + C2fast = (msteady / mfast)2 · (1 − λmfast) / (1 − λmsteady)

The page draws each trip from a gamma distribution with the chosen mean and spread, and a spread of zero means every trip is exactly the mean. The steady crew is fixed at ten minutes and a spread of zero. The slider for the day stops at 5.5 calls an hour, which keeps the steady crew under its wall (ρ = 0.92); past the wall no average exists to print.

Verified in node (improve/verify/125-queue-variance.js, 9 checks, three of them controls, all before this page existed):

  • The trip-time sampler has the mean and spread it claims, at spreads 0, 0.25, 1 and 4.
  • Eight (load, spread) cells: a 600,000-call simulation matches the formula within four standard errors, the errors measured from batch means rather than chosen.
  • At a spread of 1 the formula reduces to exhibit 58's ρ / μ(1 − ρ) exactly.
  • A spread of 0 gives exactly half the exponential wait, by the formula and by simulation.
  • The tie at the default settings is a spread of 0.728. Simulated 0.4 either side of it, the ranking flips with room to spare.
  • Control one. A model that keeps the load and the mean but ignores the spread predicts 40 minutes for both crews. The steady crew's callers wait 20; a crew at spread 4 makes them wait 100. The simulation sides with the formula, eight times closer.
  • Control two. On a quiet night the waits shrink in step with the load, but their ratio does not: at 0.6 calls an hour the steady crew's callers still wait a quarter as long. My first draft claimed the spread stops mattering when the line is short. The gate refused it: only the minutes vanish, not the ratio, and the fast crew delivers help sooner in total only below 0.4 calls an hour.
  • Control three, the known-bad case. At a load of 1.05 the average wait over 20,000 calls is 4,600 minutes and over 200,000 it is 42,000. It never settles, and the page's slider cannot reach it.
  • The tie rises with the load, from 0.235 on an empty night toward 1.6 at 5.5 calls an hour. My first draft asserted the opposite direction, and the gate refused that too.

Felix Pollaczek published the formula in 1930 and Aleksandr Khinchine found it again, by a different route, in 1932. The steady case came first: Agner Erlang worked out the wait for calls of a fixed length at the Copenhagen telephone exchange in 1909, two decades before the general law, which is why the constant-service queue still carries his name in the textbooks.

Also in Computation & information: Sorting algorithms →

All 19 in Computation & information
  1. 101Noise sets a speed limit, not an accuracy limit.
  2. 111Any party of six hides a trio
  3. 120How one bit of ink makes a grey
  4. 125The ambulance that arrives sooner by going slower — you are here
  5. 23Sorting algorithms
  6. 24PageRank & the random surfer
  7. 25Huffman coding
  8. 26Dijkstra's shortest path
  9. 33The learning-rate cliff
  10. 36A* pathfinding
  11. 44Diffie–Hellman key exchange
  12. 49Freeze too fast, stay stuck
  13. 56Catch one error, miss the next
  14. 57Why more processors stop helping
  15. 58Why a busy line explodes
  16. 59The set that's only sure when it says no
  17. 60The fit that memorizes instead of learns
  18. 61When the wire breaks, pick one
  19. 82Your computer can't hold one tenth

← the cabinet