Skip to content

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:

  1. Derive \(P_n=(1-\rho)\rho^n\) for the \(M/M/1\) queue from the birth–death equations.
  2. Derive \(L_s\), \(L_q\), \(W_s\) and \(W_q\) and connect them by Little's law.
  3. Derive the waiting-time distributions and compute percentiles.
  4. Explain why congestion grows non-linearly as \(\rho\to1\), and quantify it.
  5. 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:

  1. Arrivals form a Poisson process of rate \(\lambda\).
  2. Service times are exponential with mean \(1/\mu\); the service rate is \(\mu\).
  3. One server; the queue may grow without limit; nobody balks or reneges.
  4. Arrivals and service times are independent of each other and of the state.

The traffic intensity (or utilisation factor) is

\[\rho = \frac{\lambda}{\mu} = \frac{\text{mean service time}}{\text{mean inter-arrival time}}.\]

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

\[\lambda P_n = \mu P_{n+1} \ \Longrightarrow\ P_{n+1} = \rho P_n \ \Longrightarrow\ P_n = \rho^{\,n}P_0.\]

Normalising, and using the geometric series (which converges only if \(\rho<1\)):

\[\sum_{n=0}^{\infty}\rho^nP_0 = \frac{P_0}{1-\rho}=1 \ \Longrightarrow\ P_0 = 1-\rho.\]

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:

\[P_0 = 1-\rho = \Pr[\text{system empty}] = \Pr[\text{server idle}],\]
\[\Pr[n\ge k]=\sum_{n\ge k}(1-\rho)\rho^n = \rho^{\,k}. \tag{2.2}\]

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

\[L_s=\sum_{n=0}^{\infty}nP_n=(1-\rho)\sum_{n=1}^{\infty}n\rho^n =(1-\rho)\rho\sum_{n=1}^{\infty}n\rho^{\,n-1}.\]

Using \(\displaystyle\sum_{n\ge1}n x^{n-1}=\frac{d}{dx}\frac{1}{1-x}=\frac{1}{(1-x)^2}\),

\[L_s=(1-\rho)\rho\cdot\frac{1}{(1-\rho)^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\):

\[L_q=\sum_{n=1}^{\infty}(n-1)P_n=L_s-\sum_{n\ge1}P_n=L_s-(1-P_0)=L_s-\rho.\]

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.

\[\rho=\frac{\lambda}{\mu}=\frac{8}{10}=0.8 <1 \ \checkmark\ \text{(stable)}\]
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:

\[\Pr[W_s>t]=e^{-2(1/3)}=e^{-0.6667}=\mathbf{0.5134}\]

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\):

\[t=\frac{\ln 10}{2}=\frac{2.3026}{2}=1.1513\text{ h}=\mathbf{69.1\text{ minutes}}\]

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\).

\[L_s=\frac{0.75}{0.25}=3\text{ cars},\qquad L_q=\frac{0.75^2}{0.25}=2.25\text{ cars}\]
\[W_s=\frac{1}{20-15}=0.2\text{ h}=12\text{ min},\qquad W_q=\frac{15}{20(5)}=0.15\text{ h}=9\text{ min}\]

Verification.

\[\lambda W_s=15(0.2)=3=L_s\ \checkmark \qquad \lambda W_q=15(0.15)=2.25=L_q\ \checkmark\]
\[L_s-L_q=0.75=\rho\ \checkmark\qquad W_s-W_q=0.05\text{ h}=3\text{ min}=1/\mu\ \checkmark\]

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\):

\[L_s=\frac{0.6667}{0.3333}=2,\qquad L_q=1.333,\qquad W_s=\frac{1}{6-4}=0.5\text{ h}=30\text{ min}\]
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

  1. \(\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)
  2. 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\))
  3. 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)
  4. 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)
  5. 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.