Hold λ and μ still and every cut gives the same ratio ρ = λ/μ, so the product telescopes and πₙ = π₀ρⁿ. The geometric distribution is a consequence of the cut equations rather than a separate result: nothing was assumed about the shape of π. But this kit works on a finite chain and an M/M/1 queue does not, so every figure here is an approximation and the page prints the size of it — the exact tail mass ρ^(N+1) the truncation redistributed, and the gap between the chain's L and the closed form's. The closed form is sysdesign_core's, called rather than rewritten, so the two Subjects cannot disagree about M/M/1.
Core ideas
Three ideas. The first is where the geometric shape comes from, the second is what the truncation costs, and the third is why the closed form on the page is borrowed rather than written here.
With λₙ = λ and μₙ = μ for every n, each cut ratio is λ/μ = ρ, so the running product from π₀ is 1, ρ, ρ², … and normalising gives πₙ = π₀ρⁿ. On an unbounded chain the total is 1/(1 − ρ) and π₀ = 1 − ρ. Nothing was postulated about the shape of π; it fell out of one equation applied repeatedly.
birthDeath truncates, and an M/M/1 queue has infinitely many states. The exact mass the untruncated chain puts above state N is ρ^(N+1), and the truncation redistributes it over the states kept. At ρ = 4/5 and forty states that is 0.000106; at ρ = 19/20 and sixty states it is 0.043766, which is not small. The page prints it rather than choosing a state count at which to stop mentioning it.
mm1 comes from sysdesign_core, the same function “The M/M/1 Queue” is built on. This page calls it and labels the column with its name. Writing a second implementation would be inviting exactly the disagreement that is hardest to find: two pages in one library quoting different numbers for the same model, each internally consistent.
The material
Where the geometric shape comes from, what the finite chain costs, the tail probabilities against their closed forms, and what ρ ≥ 1 does.
A birth-death chain with λₙ = λ for every n and μₙ = μ for every n ≥ 1. Write ρ = λ/μ, the utilisation.
μ is a rate, not a duration: a service taking 1/5 of a unit of time has μ = 5. That confusion is the single commonest way to get a queueing answer exactly upside down, and it is worth checking in the units before anything else.
Everything about this model follows from feeding two constant lists to the same function the preceding material used. The lab does not switch algorithms; it switches the rate lists. That is the claim “one chain, five readings” being kept rather than asserted.
For the M/M/1 chain with ρ < 1 on states 0, 1, 2, …, πₙ = (1 − ρ)ρⁿ, L = ρ/(1 − ρ), and P(N > k) = ρ^(k+1).
Each cut gives πₙ₊₁ = πₙ · λ/μ = πₙρ, so πₙ = π₀ρⁿ by induction.
The weights sum to Σₙ ρⁿ = 1/(1 − ρ) for ρ < 1, so π₀ = 1 − ρ. Then P(N > k) = Σ_{n>k} (1 − ρ)ρⁿ = ρ^(k+1), and L = Σ n(1 − ρ)ρⁿ is the standard geometric mean ρ/(1 − ρ). The ρ ≥ 1 case has no distribution at all, because the weights do not sum to anything finite.
□
Read the two L columns together. They are close at ρ = 4/5 and they are not close at ρ = 19/20, and the reason is entirely in the tail: at four fifths loaded the untruncated chain puts about one part in ten thousand above state 40, and at nineteen twentieths it puts four per cent above state 60. The mean is sensitive to that mass because the mass sits at large n, so a four-per-cent tail moves L from 19 to 16.2.
The chain's π₀ comes out as 0.2000212699 rather than 0.2 for the same reason: the truncation redistributes the lost tail over the states kept, and state 0 gets the largest share of it. That is not error in the arithmetic sense — the fraction is exact, twenty-eight digits over twenty-nine — it is the exact answer to a slightly different question. Pulling the state slider down and watching the two L columns separate is the fastest way to see the difference stop being negligible.
P(N > k) on the truncated chain is a finite sum of exact fractions; on the untruncated chain it is ρ^(k+1). The page prints both and their difference. At ρ = 4/5 and forty states: 0.79997873 against 0.8 at k = 0, 0.40953721 against 0.4096 at k = 3, 0.00911800 against 0.00922337 at k = 20. The discrepancy grows with k, which is exactly where the missing tail is.
Set λ = 5 and μ = 4. The page reports ρ = 5/4 ≥ 1 in red: there is no untruncated M/M/1 queue here at all, and the backlog grows without bound at rate 1 per unit time.
The finite chain still has a distribution, because it cannot grow past the last state. But that distribution belongs to a different model — one with a buffer — and reporting it as an M/M/1 answer would be reporting a number for a queue that has none. “Finite Buffers, Blocking and the Admitted Rate” is where the buffered model belongs, and there ρ ≥ 1 is not a problem at all.
At λ = 1, μ = 2 and thirty states, ρ = 1/2 and ρ³¹ is about 5 × 10⁻¹⁰. The chain's L is 0.99999999 against the closed form's 1, and π₀ is 0.5000000002 against 1/2.
This is the case people generalise from, and generalising from it is the mistake. The tail mass falls like ρ^N, so halving the load does not halve the error, it changes its exponent; and at ρ = 19/20 the same thirty states would be useless. The page prints the number so that you never have to reason about which case you are in.
One more thing the exact column buys. At sixty states and ρ = 19/20, π₀ is a fraction of seventy-nine digits over eighty, and at ninety states its denominator runs to a hundred and nineteen. Those are carried whole. A double could not hold them, so a decimal implementation would be storing the nearest number it had and calling it π₀ — and it would have no way to tell you that the difference between its L and the closed form's was truncation rather than rounding.
Interactive
a geometric distribution derived rather than quoted, and the price of a finite chain
Method
Four steps, and the last one is what separates a number from a number you can defend.
μ is completions per unit time. If what you have is a service duration, invert it. A model built with a duration where a rate belongs gives ρ upside down and every subsequent figure with it, and the numbers will look entirely plausible.
At ρ ≥ 1 there is no M/M/1 distribution: the weights do not sum to anything finite. Any finite answer you see is an answer about a bounded model, and you should say which bound.
Each ratio is ρ, so πₙ = π₀ρⁿ and π₀ = 1 − ρ. Two lines, no memorised formula, and the derivation survives the moment one of the rates stops being constant — which is the next thing that will happen to it.
ρ^(N+1) is the exact probability the untruncated chain puts above your last state. If it is 0.000106 your L is good to three decimals; if it is 0.043766 your L is out by nearly three. Printing the number costs one power and removes the judgement call entirely.
The same arithmetic at two loads. Only the two rates and the state count change, and the point of the pair is how differently the truncation behaves.
The P(N > k) block is the clearest picture of where the missing mass went. At k = 0 the two agree to five decimals; by k = 20 the difference has grown to 0.000105, which is almost the whole truncation mass 0.000106. That is not a coincidence: the mass the truncation threw away was all above state 40, so it is missing from every tail probability and the shortfall converges on the full ρ⁴¹.
The second block is the same computation at a load a designer would actually worry about, and it is where the habit of printing the error pays. L = 16.2 against a true 19 is not a rounding; it is a sixty-state model being asked a question about an unbounded one. Nothing about the left-hand column looks suspicious on its own.
For a rehearsal, take the four-fifths case and drag the state count from 40 down to 10. The supplied first move is that ρ¹¹ is about 0.086, so roughly nine per cent of the mass is being redistributed. Predict which way π₀ moves and by how much before you look, and then say why L moves further in relative terms than π₀ does.
You should be able to get πₙ = (1 − ρ)ρⁿ from the cut equations rather than from memory, compute L, Lq, W and P(N > k) from it, quote ρ^(N+1) as the truncation mass beside any finite-chain figure, and recognise ρ ≥ 1 as the absence of a model rather than as a large answer.
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.