Lesson 24: Model I: (M/M/1):(∞/FCFS) Derived in Full¶
24.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- Derive \(P_n=(1-\rho)\rho^n\) for the \(M/M/1\) queue from the birth–death equations.
- Derive \(L_s\), \(L_q\), \(W_s\) and \(W_q\) and connect them by Little's law.
- Derive the waiting-time distributions and compute percentiles.
- Explain why congestion grows non-linearly as \(\rho\to1\), and quantify it.
- Apply the complete formula set to a design problem and interpret each number.
24.2 The Model¶
Kendall notation. \((M/M/1):(\infty/\text{FCFS})\) means: Markovian (Poisson) arrivals, Markovian (exponential) service, 1 server, infinite system capacity, infinite calling population, served first come first served.
Assumptions, stated explicitly so you know what you are trusting:
- Arrivals form a Poisson process of rate \(\lambda\).
- Service times are exponential with mean \(1/\mu\); the service rate is \(\mu\).
- One server; the queue may grow without limit; nobody balks or reneges.
- Arrivals and service times are independent of each other and of the state.
The traffic intensity (or utilisation factor) is
It is dimensionless: it is the fraction of time the server is busy, and for a single server it is also the expected number of customers in service.
24.3 Deriving the State Distribution¶
Apply Lesson 23 with \(\lambda_n=\lambda\) and \(\mu_n=\mu\) for all \(n\). The cut equations give
Normalising, and using the geometric series (which converges only if \(\rho<1\)):
Result 1 (state distribution). $\(\boxed{\ P_n = (1-\rho)\rho^{\,n},\qquad n = 0,1,2,\dots\ }\tag{2.1}\)$ valid if and only if \(\rho<1\).
Two immediate consequences:
Equation (2.2) is worth memorising: the probability of finding at least \(k\) customers is simply \(\rho^k\).
24.4 Deriving the Four Performance Measures¶
Expected number in the system¶
Using \(\displaystyle\sum_{n\ge1}n x^{n-1}=\frac{d}{dx}\frac{1}{1-x}=\frac{1}{(1-x)^2}\),
Result 2. \(\qquad\boxed{\ L_s = \dfrac{\rho}{1-\rho}=\dfrac{\lambda}{\mu-\lambda}\ }\tag{3.1}\)
Expected queue length¶
\(L_q\) counts only those waiting, i.e. \(n-1\) when \(n\ge1\):
Result 3. \(\qquad\boxed{\ L_q = \dfrac{\rho^2}{1-\rho}=\dfrac{\lambda^2}{\mu(\mu-\lambda)}=\rho L_s\ }\tag{3.2}\)
The identity \(L_s-L_q=\rho\) has a clean reading: the average number in service equals the utilisation. It is the fastest check available on any \(M/M/1\) answer.
The waiting times, via Little's law¶
Little's law (\(L=\lambda W\)) applies to any stable system, whatever the distributions:
Result 4. \(\qquad\boxed{\ W_s=\dfrac{L_s}{\lambda}=\dfrac{1}{\mu-\lambda},\qquad W_q=\dfrac{L_q}{\lambda}=\dfrac{\rho}{\mu-\lambda}=\dfrac{\lambda}{\mu(\mu-\lambda)}\ }\tag{3.3}\)
Also \(W_s = W_q + \dfrac1\mu\): total time = waiting + service. Since nothing here is blocked or discouraged, \(\lambda_{\text{eff}}=\lambda\).
The complete formula set¶
| Quantity | Formula | In terms of \(\rho\) |
|---|---|---|
| \(P_0\) | \(1-\lambda/\mu\) | \(1-\rho\) |
| \(P_n\) | \((1-\rho)\rho^n\) | \((1-\rho)\rho^n\) |
| \(\Pr[n\ge k]\) | \(\rho^k\) | \(\rho^k\) |
| \(L_s\) | \(\lambda/(\mu-\lambda)\) | \(\rho/(1-\rho)\) |
| \(L_q\) | \(\lambda^2/[\mu(\mu-\lambda)]\) | \(\rho^2/(1-\rho)\) |
| \(W_s\) | \(1/(\mu-\lambda)\) | \(\dfrac{1}{\mu}\cdot\dfrac{1}{1-\rho}\) |
| \(W_q\) | \(\lambda/[\mu(\mu-\lambda)]\) | \(\dfrac{1}{\mu}\cdot\dfrac{\rho}{1-\rho}\) |
| \(L_q\) of a busy period | \(1/(1-\rho)\) | \(1/(1-\rho)\) |
24.5 The Waiting-Time Distributions¶
The averages above hide the variability. Fortunately the full distributions are simple.
Theorem. For \(M/M/1\) under FCFS, the total time in the system is exponential with rate \(\mu-\lambda\): $\(\Pr[W_s > t] = e^{-(\mu-\lambda)t}. \tag{4.1}\)$ The waiting time in the queue has an atom at zero: $\(\Pr[W_q = 0]=1-\rho,\qquad \Pr[W_q>t]=\rho\,e^{-(\mu-\lambda)t}. \tag{4.2}\)$
Sketch of proof. An arrival who finds \(n\) ahead must wait for \(n+1\) services (its own included), a sum of \(n+1\) i.i.d. exponentials — an Erlang. Averaging that Erlang over the geometric distribution of \(n\) from (2.1) collapses the mixture back to a single exponential of rate \(\mu-\lambda\). ∎
Two practical uses:
- Percentiles. The \(100p\)-th percentile of \(W_s\) is \(t_p = \dfrac{-\ln(1-p)}{\mu-\lambda}\). Service-level agreements are written in percentiles, not means.
- The atom at 0. A fraction \(1-\rho\) of customers wait not at all. Quoting only the mean \(W_q\) misrepresents everyone's experience: most customers either sail through or wait a long time.
24.6 Solved Problems¶
Problem 1 — The complete standard calculation¶
At a single-window bank counter customers arrive in a Poisson stream at \(8\) per hour and service is exponential at a mean rate of \(10\) per hour. Compute every standard measure.
Solution.
| Quantity | Working | Value |
|---|---|---|
| \(P_0\) | \(1-0.8\) | \(0.20\) — idle \(20\,\%\) of the time |
| \(\Pr[n\ge2]\) | \(\rho^2=0.8^2\) | \(0.64\) |
| \(\Pr[n\ge4]\) | \(0.8^4\) | \(0.4096\) |
| \(L_s\) | \(\dfrac{8}{10-8}\) | \(\mathbf{4}\) customers |
| \(L_q\) | \(\dfrac{8^2}{10(2)}=\dfrac{64}{20}\) | \(\mathbf{3.2}\) customers |
| \(W_s\) | \(\dfrac{1}{10-8}=0.5\) h | \(\mathbf{30}\) minutes |
| \(W_q\) | \(\dfrac{8}{10(2)}=0.4\) h | \(\mathbf{24}\) minutes |
Checks. \(L_s-L_q=4-3.2=0.8=\rho\) ✓. \(W_s-W_q=0.1\text{ h}=6\text{ min}=1/\mu\) ✓. \(L_s=\lambda W_s = 8(0.5)=4\) ✓.
Interpretation. The server is idle one hour in five, yet the average customer spends half an hour for six minutes of service — 80 % of the customer's time is pure waiting. Idle servers and long queues coexist; that is not a contradiction but the essence of the phenomenon.
Problem 2 — Waiting-time distribution and percentiles¶
For the counter in Problem 1, find (a) \(\Pr[W_s>20\text{ min}]\), (b) \(\Pr[W_q>20\text{ min}]\), (c) the probability a customer does not wait at all, (d) the time within which \(90\,\%\) of customers are finished.
Solution. Here \(\mu-\lambda=2\) per hour.
(a) With \(t=\tfrac13\) h:
Over half of all customers spend more than \(20\) minutes in the bank.
(b) \(\Pr[W_q>t]=\rho e^{-2/3}=0.8(0.5134)=\mathbf{0.4107}\)
(c) \(\Pr[W_q=0]=1-\rho=\mathbf{0.20}\) — one customer in five walks straight to the window.
(d) Solve \(e^{-2t}=0.10\):
Interpretation. The mean is \(30\) minutes but the 90th percentile is 69 minutes — more than twice the mean. Publishing the average would understate the worst experience badly. Always quote a percentile alongside a mean.
Problem 3 — Verifying Little's law¶
Cars arrive at a service bay at \(15\) per hour; servicing is exponential at \(20\) per hour. Compute all measures and verify \(L=\lambda W\) in both forms.
Solution. \(\rho = 15/20 = 0.75\).
Verification.
Remark. Little's law needed no distributional assumption — only that the system is stable and that we are averaging over the long run. That is why it holds for \(M/G/1\), \(G/G/c\) and every model in this unit, and why it is the right tool for cross-checking any answer.
Problem 4 — Why the last 10 % of capacity is unaffordable¶
Tabulate \(L_s\), \(L_q\) and \(W_s\) (as a multiple of the service time \(1/\mu\)) for \(\rho=0.5,0.8,0.9,0.95,0.99\), and interpret.
Solution.
| \(\rho\) | \(L_s=\dfrac{\rho}{1-\rho}\) | \(L_q=\dfrac{\rho^2}{1-\rho}\) | \(W_s\div(1/\mu)=\dfrac{1}{1-\rho}\) |
|---|---|---|---|
| 0.50 | 1.00 | 0.50 | 2 |
| 0.80 | 4.00 | 3.20 | 5 |
| 0.90 | 9.00 | 8.10 | 10 |
| 0.95 | 19.00 | 18.05 | 20 |
| 0.99 | 99.00 | 98.01 | 100 |
Interpretation. Everything is governed by the factor \(\dfrac{1}{1-\rho}\), which blows up as \(\rho\to1\):
- From \(\rho=0.5\) to \(\rho=0.9\), utilisation rises \(1.8\times\) but the queue grows \(16\times\).
- From \(\rho=0.9\) to \(\rho=0.95\) — a mere five extra percentage points of utilisation — waiting time doubles.
- At \(\rho=0.99\) a customer spends 100 service times in the system.
The central management lesson of queuing theory. Utilisation and responsiveness are in direct conflict, and the trade-off is not linear. Systems that must stay responsive (hospitals, emergency services, data-centre links) are deliberately run at \(60\)–\(80\,\%\) utilisation. A manager who demands \(95\,\%\) utilisation of a single server has, unknowingly, demanded a twenty-fold queue.
Problem 5 — A design problem¶
A one-chair barber shop has Poisson arrivals at \(4\) customers per hour; a haircut takes an average of \(12\) minutes, exponentially distributed. The shop is open \(10\) hours a day. Find: (a) the fraction of the day the barber is idle, (b) the average time a customer spends in the shop, (c) the average number waiting, (d) the probability that a customer must wait, (e) the probability of finding more than \(3\) people in the shop. (f) The barber can train to cut the mean time to \(10\) minutes. What happens?
Solution. Mean service \(12\) min \(\Rightarrow \mu = 60/12 = 5\) per hour; \(\lambda = 4\); \(\rho = 4/5 = 0.8\).
(a) \(P_0=1-\rho=0.2\), so the barber is idle \(0.2\times10 = \mathbf{2\text{ hours per day}}\).
(b) \(W_s = \dfrac{1}{5-4}=1\) hour \(=\mathbf{60\text{ minutes}}\) for a \(12\)-minute haircut.
(c) \(L_q = \dfrac{0.8^2}{0.2}=\mathbf{3.2\text{ customers waiting}}\) on average.
(d) \(\Pr[\text{must wait}]=\Pr[n\ge1]=\rho=\mathbf{0.8}\) — four customers in five must wait.
(e) \(\Pr[n>3]=\Pr[n\ge4]=\rho^4=0.8^4=\mathbf{0.4096}\). The shop needs seating for four or more about \(41\,\%\) of the time.
(f) With \(\mu = 6\) per hour, \(\rho = 4/6 = 0.6667\):
| before | after | change | |
|---|---|---|---|
| Mean service time | 12 min | 10 min | \(-17\,\%\) |
| \(\rho\) | 0.800 | 0.667 | \(-17\,\%\) |
| \(L_q\) | 3.20 | 1.33 | \(\mathbf{-58\,\%}\) |
| \(W_s\) | 60 min | 30 min | \(\mathbf{-50\,\%}\) |
Interpretation. A 17 % cut in service time halves the customer's time in the shop and reduces the queue by 58 %. This leverage — small improvements in the service rate producing large improvements in congestion — is the strongest practical argument in this unit, and it works in reverse too: a small slippage in service speed can produce a spectacular collapse in service level.
24.7 Practice Problems¶
- \(\lambda=10\)/h, \(\mu=15\)/h. Find \(\rho\), \(P_0\), \(L_s\), \(L_q\), \(W_s\), \(W_q\). (Answer: \(0.6667\), \(0.3333\), \(2\), \(1.333\), \(12\) min, \(8\) min)
- For Problem 1's counter, find the probability that the queue (excluding the customer in service) has at least \(2\) people. (Answer: \(\Pr[n\ge3]=\rho^3=0.512\))
- A repair shop has \(\lambda=3\)/day and \(\mu=4\)/day. What fraction of arriving jobs find the shop empty, and what is the mean time a job spends there? (Answer: \(0.25\); \(1\) day)
- If \(W_q\) must not exceed \(5\) minutes when \(\lambda=20\)/h, what is the minimum \(\mu\)? (Answer: solve \(\mu^2-20\mu-240=0\), giving \(\mu\ge 28.44\)/h)
- Show that \(\mathrm{Var}[n]=\dfrac{\rho}{(1-\rho)^2}\) for the geometric distribution (2.1), and evaluate it at \(\rho=0.8\). (Answer: \(20\), so \(\sigma=4.47\) — as large as the mean \(L_s=4\))
24.8 Summary¶
- \(M/M/1\) has \(P_n=(1-\rho)\rho^n\): a geometric distribution, valid only when \(\rho<1\).
- \(\Pr[n\ge k]=\rho^k\) — the single most useful one-line result in the model.
- \(L_s=\dfrac{\rho}{1-\rho}\), \(L_q=\rho L_s\), \(W_s=\dfrac{1}{\mu-\lambda}\), \(W_q=\rho W_s\).
- Two universal checks: \(L_s-L_q=\rho\) and \(W_s-W_q=1/\mu\). Use them on every answer.
- Time in the system is exponential with rate \(\mu-\lambda\); a fraction \(1-\rho\) of customers never wait at all. Report percentiles, not just means.
- Congestion scales as \(\dfrac{1}{1-\rho}\) and therefore explodes near full utilisation. High utilisation and short queues are mutually exclusive goals.
- A modest improvement in service rate delivers a disproportionately large reduction in waiting — the most actionable finding in the whole unit.
Next lesson: L25 — Model I applications: costing, design decisions and extensive practice.
Practise now: unit3-queue-inventory-lab.html → M/M/1 Explorer: drag \(\lambda\) and \(\mu\), watch
\(P_n\), \(L_s\) and \(W_s\) update live, and see the \(1/(1-\rho)\) blow-up on the congestion curve.