Why is the other line always faster?

You pick a line at the supermarket, and the one next to you moves faster. It happens so often that it feels like a law of nature. Queues really are strange, but the reasons are simple enough to watch happen. We need only three ideas: customers arrive at random, service takes a random amount of time, and nobody can be served before they arrive.

One till

Start with a single till. Customers arrive at random at an average rate we’ll call λ (lambda), say 48 an hour. At random means that an arrival in one minute tells you nothing about the next minute, like raindrops. A busy cashier serves at an average rate μ (mu), say 60 an hour, so one customer takes a minute on average but sometimes much more or much less.

The share of time the till is busy is called its utilisation, ρ (rho) = λ/μ. Here that is 48/60 = 80%. The till has 20% of its time to spare. Surely nobody waits long?

At 80% busy the average customer waits 4 minutes for a 1-minute service. The reason is randomness. Sometimes three people arrive within a minute of each other. The till can’t work ahead and bank the idle time from a quiet spell. Idle time is lost for good, while a burst of arrivals leaves a queue that takes a long time to clear.

If customers arrived exactly every 75 seconds and each took exactly 60 seconds, nobody would ever wait. Randomness alone creates the queue, even when capacity comfortably exceeds demand on average.

For this simplest case, called the M/M/1 queue (random arrivals, random service times, one server), the long-run average wait in line has a tidy formula:

average wait = ρ / (1 − ρ) × average service time

At 50% busy you wait one service time on average. At 80%, 0.8/0.2 = 4 service times. The denominator, 1 − ρ, is the spare capacity. It sits at the bottom of a fraction, and that is where the trouble starts.

The explosion near 100%

Drag along the curve below, or focus it and use the arrow keys. The green dot marks the utilisation at which the wait doubles from wherever you are. Notice how close together those doublings get as you approach the right-hand edge.

Going from 80% to 90% busy doesn’t raise the wait by an eighth. It more than doubles it, from 4 to 9 service times. Going on from 90% to 95% more than doubles it again, to 19. Near the top, every time you halve the spare capacity you roughly double the wait. At 100% there is no steady state at all: the line grows without limit.

This is why systems run “efficiently” close to capacity feel broken: hospital emergency departments, motorway traffic, a web server under load. The last 10% of utilisation costs more waiting than the first 80%. It is also why a small drop in demand, like a school holiday, can make a road feel empty. That drop moves you back down the steep part of the curve.

One line or three?

Now take three tills. Shops arrange them in two ways. Supermarkets usually give each till its own line. Banks, post offices and airport security often use one shared, snaking line that feeds whichever till comes free next.

The figure below runs both at once, with exactly the same customers: the same arrival times and the same service times. On the left, each customer picks one of the three lines at random and stays there, which is roughly what happens when you can’t see how full each trolley is. On the right, everyone joins one line. Each till takes 3 minutes per customer on average.

The shared line wins on the average, and wins clearly on the worst case. With separate lines, one customer with a huge trolley or a price check holds up everyone behind them, while another till may sit idle. A shared line never leaves a till idle while someone is waiting. It is also fair: nobody who arrives after you is served before you.

At 85% busy the shared line (the M/M/3 queue) averages about 4.9 minutes. The textbook result for it is called the Erlang C formula, after the Danish telephone engineer A. K. Erlang. If customers instead picked a line at random, each line would behave like its own M/M/1 queue at 85%, and the average wait would be 17 minutes. Picking the shortest line recovers most of that loss, but not all of it, and it does not stop the worst waits.

And the other line? When you choose at random, each of three equally good lines is equally likely to be the fastest. So yours is the fastest only about a third of the time. Two times out of three, one of the others really did move faster. The simulation confirms it: over many hours, customers who arrive when every till is busy and pick a line at random are in the fastest line 33% of the time. Picking the shortest line helps, but only to about 48%. You notice and remember the times you lose. Your line is not cursed. The odds are simply against you.

It’s the variability, not just the average

The formula above assumed “fully random” arrivals and service. Real queues can be more regular (appointments, a machine with a fixed cycle) or more erratic (a till that sometimes gets a full weekly shop and sometimes a single banana). A useful measure is the coefficient of variation: the standard deviation of a time divided by its average. Clockwork is 0, fully random is 1, erratic is above 1.

In 1961 the mathematician John Kingman found a simple approximation for one server:

average wait ≈ ρ/(1 − ρ) × (c_a² + c_s²)/2 × average service time

Here c_a and c_s are the coefficients of variation of the gaps between arrivals and of the service times. The first factor is the utilisation explosion we have already met. The second is a variability multiplier: it equals 1 when both are fully random, and 0 when both are clockwork.

When arrivals are fully random (c_a = 1), Kingman’s formula is exact. This special case was known earlier as the Pollaczek–Khinchine formula. In other cases it is only an estimate. It is very good when the till is busy, within about 5% above 90% busy, and it gets better the busier the server. But it can be well off when the till is quiet and arrivals are more regular than random: at 50% busy with c_a = 0 and c_s = 1 it gives about twice the true wait, which is why the dot can sit below the curve in Figure 4. Both kinds of variability count equally, and they add.

That is the logic behind many everyday fixes. Express lanes take the small baskets out of the mix, so each lane has less variable service times. Appointments make arrivals regular. Standard procedures make service regular. None of them makes anyone work faster, and all of them shorten the wait.

So when a queue feels broken, ask two questions. How close to 100% busy is it? And how variable is it? A little spare capacity, or a little less randomness, buys far more than you’d guess.