A small café has one barista and room for three customers inside, counting the one being served. Customers arrive at random, about one every two minutes, and an order takes a minute on average. How many people are inside on average? How long does a customer spend there? How often is someone turned away at the door? The number of customers inside goes up and down by one at a time, and with the right assumptions its future depends only on its present value. That makes it a Markov chain, and every question becomes a question about its stationary distribution.
By the end you can
- Use the Poisson process to get the chance of an arrival in a short interval.
- Explain why exponential service lets the state be just the number of customers.
- Build the transition matrix of a queue in discrete time, including the empty and full states.
- Solve a birth–death chain by detailed balance.
- Compute L, Lq, W and Wq, using Little's law with the arrivals that get in.
"Arrivals form a Poisson process with rate λ" means: the numbers of arrivals in separate stretches of time are independent, and the number in any stretch of length t is Poisson with mean λt. Equivalently, the gaps between arrivals are independent exponential times with mean 1/λ (the Common Distributions chapter connects the two). To turn this into a chain we cut time into short intervals of length h and ask what happens in each one.
Services are assumed exponential with rate μ (mean 1/μ). The exponential is memoryless: a service that has already lasted s minutes has the same chance of ending in the next h minutes as one that has just started. That is why the state can be the number of customers alone. Nobody needs to remember how long the current service has been running. With k servers busy at once, the next completion is the first of k independent exponential times:
Let Xₖ be the number of customers in the system (waiting or being served) after k intervals, from 0 to the capacity K. In each interval an arrival happens with chance a and a completion with chance dₙ, independently. One arrival and no completion: up by one. One completion and no arrival: down by one. Both or neither: the count stays.
The café: λ = 0.5, mean service 1 minute, K = 3, h = 0.1
a = 1 − e^(−0.05) = 0.04877 and, with one barista, d = 1 − e^(−0.1) = 0.09516 whenever someone is inside. Rounded to five decimals:
| from ↓ to → | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0.95123 | 0.04877 | 0 | 0 |
| 1 | 0.09052 | 0.86535 | 0.04413 | 0 |
| 2 | 0 | 0.09052 | 0.86535 | 0.04413 |
| 3 | 0 | 0 | 0.09052 | 0.90948 |
Row 0: an arrival (0.04877) is the only way out. Row 1: up needs an arrival and no completion, 0.04877 × 0.90484 = 0.04413; down needs a completion and no arrival, 0.95123 × 0.09516 = 0.09052. Row 3: a lone arrival is turned away, so the stay probability gets that 0.04413 as well.
A chain that only moves up or down by one is a birth–death chain, and for it detailed balance holds: in the long run the flow up across the edge between n and n + 1 equals the flow down. That gives each π(n + 1) from π(n) with one multiplication, with no system to solve, even for K = 150.
Why Little's law holds: watch the café for a long time T and add up everyone's time inside. Counted customer by customer, that is about λ_ef·T customers × W minutes each. Counted minute by minute, it is the number inside at each moment added over the T minutes, about L × T. The two counts are the same total, so L·T = λ_ef·T·W and L = λ_ef W. Nothing in the argument used exponential times; Little's law holds for almost any queue.
As h → 0, a ≈ λh and dₙ ≈ min(n, c)μh, so each ratio up/down tends to λ/(min(n + 1, c)μ): the h cancels. That gives the exact distribution of the continuous-time queue, written M/M/c/K (Markovian arrivals, Markovian services, c servers, capacity K):
| L | Lq | W | Wq | π(3) | |
|---|---|---|---|---|---|
| chain, h = 0.1 | 0.7506 | 0.2689 | 1.6079 | 0.5759 | 0.0664 |
| exact (h → 0) | 0.7333 | 0.2667 | 1.5714 | 0.5714 | 0.0667 |
Bars: the stationary distribution of the chain, π(n) = probability of n customers in the system. Dots: the exact continuous-time answer. W and Wq come from Little's law with the arrivals that get in, λ(1 − π(K)). Make h smaller and the bars move onto the dots. The choice under the sliders is the one convention the discretisation leaves open: when the system is full and an arrival and a departure fall in the same interval, does the newcomer take the freed place or was it already turned away? It matters less and less as h shrinks. Press play to watch the chain run, one simulated minute per second.
Nothing changes with c servers except dₙ, which grows with the number busy until all c are working. A large capacity K is no harder either: the product formula has one factor per level. When K is large and λ < cμ (fewer arrivals than the servers can handle), the probabilities of the top levels are tiny, the loss π(K) is practically 0, and the queue behaves like one with unlimited room. If λ ≥ cμ, the line grows without limit in an unlimited queue, and in a limited one it stays close to full.
| Step | What to do |
|---|---|
| 1 | States: the number in the system, 0 to K (K counts those being served). |
| 2 | Per interval: a = 1 − e^(−λh), and dₙ = 1 − e^(−min(n, c)μh) for each n (d₀ = 0). |
| 3 | Rows of P: up a(1 − dₙ), down (1 − a)dₙ, stay the rest; at K the lone arrival is lost (and pick the convention for arrival + departure). |
| 4 | π by detailed balance: π(n + 1) = π(n)·up(n)/down(n + 1), then divide by the total. |
| 5 | L = Σ nπ(n), Lq = Σ (n − c)π(n) for n > c. |
| 6 | λ_ef = λ(1 − π(K)), W = L/λ_ef, Wq = Lq/λ_ef. Check: W − Wq ≈ 1/μ. |
| 7 | Compare with the continuous M/M/c/K answer; a big gap means h is too large or a row is wrong. |
A round of 10 questions
Answer as many as you can. Mistakes come back at the end for a review round.
Every exercise is made on the spot, so a new round is never the same. The computer picks the answer first and builds the question around it, working with exact fractions, so the answer key is always right. Answers are read exactly: 0.75, 3/4 and 6/8 count as the same number (where lowest terms are asked for, 6/8 just gets a reminder). A wrong answer shows the worked solution line by line, in the order the lesson does it; the new number in each line is coloured.
| Wrong | Right | Why |
|---|---|---|
| completion chance μh with 2 servers busy | 1 − e^(−2μh) | the first of two exponentials ends at rate 2μ |
| a completion from state 0 | d₀ = 0 | an empty system has no service to finish |
| an arrival from K goes to K + 1 | it is turned away: the count stays K | the capacity includes the customers being served |
| W = L/λ | W = L/(λ(1 − π(K))) | only the arrivals that get in spend time inside |
| Lq = Σ n π(n) for n > c | Σ (n − c) π(n) | c of the n customers are being served, not waiting |
| state = number + time served so far | the number alone | exponential services are memoryless |
Key ideas
- Poisson arrivals: an arrival in an interval h with chance a = 1 − e^(−λh) ≈ λh; two in one interval have chance ≈ (λh)²/2.
- Exponential services are memoryless, so the state is just the number in the system; k busy servers finish at rate kμ.
- Per interval: up = a(1 − dₙ), down = (1 − a)dₙ, stay = the rest; d₀ = 0; at K a lone arrival is lost.
- Moves of ±1 only: detailed balance gives π(n + 1) = π(n)·P(n→n+1)/P(n+1→n).
- L = Σ nπ(n), Lq = Σ (n − c)π(n); W = L/λ_ef and Wq = Lq/λ_ef with λ_ef = λ(1 − π(K)).
- As h → 0 the chain tends to the continuous M/M/c/K queue, π(n) ∝ Π λ/(min(k, c)μ).