A server busy four fifths of the time has a fifth of itself spare, and yet work waits. It waits because arrivals bunch: run clockwork arrivals and clockwork service at ρ = 4/5 and nothing ever queues, then run random ones at exactly the same ρ and the mean number in the system triples. Bunching, not overload.
Core ideas
The comparison is the lesson. Both arms have identical rates, identical utilisation and identical mean service time, and one of them never queues.
One arrival every five slots, served in exactly four: the server is busy 4/5 of the time and no second customer ever exists. The mean number in the system is exactly 4/5 — the one in service, counted for the fraction of time it is there — and the largest the system ever holds is one.
Keep ρ = 4/5 and make the arrivals random and the service random. Now the mean number in the system is 12/5, three times the clockwork answer. The server is idle exactly as often as before; it is idle at the wrong moments, and the work that arrives while it is busy is what waits.
“I ran a simulation” is not a measurement of anything until the model is stated. This one is a Bernoulli arrival per slot, a geometric service, and a rule about what happens when both land in the same slot. Change any of the three and the number changes.
The material
What clockwork does, what randomness does, exactly which model the simulation is, and which number in it is exact.
“We are only at 70% — nobody should be waiting.” The sentence assumes that a server with headroom is a server with no queue, and it is true of exactly one system: the one where work arrives on a timetable and takes the same time every time.
One arrival every five slots; each takes exactly four slots to serve. The server finishes a slot before the next arrival appears, so the system holds one customer four slots in five and none in the fifth. L = 4/5, and the largest number ever present is 1. Nothing queues, ever, at any utilisation below one.
Time advances in slots. In each slot one arrival occurs with probability p, independently of everything else. A customer in service completes with probability q in each slot, so service times are geometric with mean 1/q slots. Within a slot the departure is resolved first and the arrival second — the late-arrival convention — so a customer arriving in slot t cannot leave before slot t + 1.
That is a discrete-time chain, written Geo/Geo/1. It is not M/M/1, and the convention in the last sentence is part of the model: change it and the exact answer changes.
The utilisation of that chain is ρ = p/q: arrivals come at p per slot, each takes 1/q slots of the server, so the server is busy p/q of the time. At p = 2/5 and q = 1/2 that is ρ = 4/5 — the same utilisation as the clockwork run, the same mean service time of two slots, and the same throughput.
The 12/5 is exact, and it is not this lesson's to derive. The chain above is solved in closed form in Operations Research, markov-chains-decisions-and-queues/queues-in-discrete-time, which gives the stationary distribution and the mean L = p(1 − p)/(q − p) — equivalently ρ(1 − p)/(1 − ρ) — for any p and q under this convention. What belongs here is the phenomenon: waiting appears well below ρ = 1, and the lab shows it happening.
Note what the third line of the table does not say. ρ/(1 − ρ) is 4 at this utilisation, and 4 is not the slotted system's answer: it overstates the exact 12/5 by a factor of 5/3. The continuous formula describes the limit of this chain as the slot shrinks, not the chain at a slot of one. “The M/M/1 Queue” states that limit precisely and shows the convergence; treating the two as the same model is the error that comparison is designed to prevent.
A run begins with nothing in the system, which is a state the settled chain visits only a fifth of the time. Averaging from t = 0 therefore includes a stretch that is unrepresentatively quiet, and the mean comes out biased low. The lab prints the mean twice — from t = 0 and after discarding a warm-up — and draws the ensemble occupancy rising from zero so that the bias is visible rather than argued about. The general treatment is Operations Research, simulation/warm-up-and-the-initial-transient.
Neither printed mean is the exact answer. One run is a sample: the same seed gives the same run and a different seed gives a different number, and with a few thousand slots the sampling error is larger than the difference between many wrong formulas. What is stable across seeds is the comparison — the random arm above the clockwork arm, by a factor near three — and that comparison is what the lesson claims.
So the honest version of the opening sentence is: at 70% utilisation the server is idle 30% of the time, and whether anyone waits depends entirely on how that idleness is distributed. Randomness guarantees it is distributed badly.
Interactive
A seeded slotted run against a clockwork one, at exactly the same ρ
Method
The comparison is only worth anything if the two arms differ in exactly one respect.
ρ = p/q for the random arm. Choose p and q first, compute ρ, and give the clockwork arm the same one. A comparison at two different ρ values measures nothing.
It is exact and it is small: at ρ = 4/5 the mean number in system is 4/5, and the maximum is 1. This arm has no sampling error because there is nothing random in it.
Take the mean from t = 0 and the mean after the warm-up and note the gap between them. The run starts empty, so the first is the biased one.
Whatever moves between seeds is sampling error, not signal. The factor of about three does not move; the third decimal place does.
The exact answer for this model is 12/5. ρ/(1 − ρ) = 4 is the answer for a different model and is 5/3 too large here, so a run landing near 2.4 is agreement and a run landing near 4 would be a bug.
Both columns have the same utilisation and the same mean service time. Only the pattern differs, and that is the entire cause of the third number.
The clockwork column is the intuition being corrected: it really is true that a deterministic system with headroom never queues. Every real system fails its assumption, and the cost of failing it is the factor of three.
The last block is worth reading twice. ρ/(1 − ρ) is the right formula for a different model, and reaching for it here would overstate the queue by 5/3. The two agree only in the limit of a vanishing slot, which is the subject of “The M/M/1 Queue”.
For a faded rehearsal, set p = 1/4 and q = 1/2. The supplied first move is ρ = 1/2. Predict whether the gap between the random and clockwork arms is larger or smaller than it was at ρ = 4/5, then run it and see.
You should be able to compute ρ = p/q for the slotted model, say what the clockwork arm does at that ρ, name the model a simulation is running, and say why ρ/(1 − ρ) is not the number to compare a slotted run against.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.