CS5239 Chap.6 Birth-Death Processes and the M/M/1 Queue
Birth-Death Processes and the M/M/1 Queue
What this chapter sets out to do
Earlier chapters described a queue in words and in Kendall notation. This one makes a queue computable. The lecture for Week 4 introduces the continuous-time Markov chain as the engine behind every M-labelled model, then narrows to the birth-death case because it is the simplest structure that still captures jobs arriving and leaving one at a time.
By the end you should be able to take a verbal description of a single-server system, decide whether the M/M/1 assumptions hold, and produce its idle probability, mean population, mean response time and tail probabilities without reaching for a reference.
The modelling assumptions you are buying
Memorylessness is the price of tractability.
A Markov model assumes the future depends on the present state alone, which forces every holding time to be exponential, since no other continuous distribution forgets its own past. In practice that means arrivals form a Poisson stream and service demands vary a lot: an exponential has a coefficient of variation of one.
Poisson streams also behave well when combined or divided: splitting one stream at random by probability p yields two Poisson streams with rates p times lambda and the remainder, and pooling two independent streams yields one whose rate is the sum. Checking those assumptions before solving is part of a good answer, not an optional remark.
From a diagram to numbers
The method has a fixed shape.
You enumerate states, draw arrows labelled with rates, write one equation per state equating probability flow in with flow out, and normalise so the probabilities total one. For birth-death chains the algebra telescopes: each state probability is the idle probability multiplied by a ratio of upward rates over downward rates.
That single product formula covers M/M/1 now and the multi-server and finite-capacity variants in the next chapter, so learning to read it as a ratio of rates pays off twice.
The derivation itself rests on one observation about very short intervals: the chance of two events landing in the same instant vanishes, which is why only neighbouring states are ever linked.
The single-server results and their limits
Setting every arrival rate to lambda and every service rate to mu turns the ratio into a power of the traffic intensity, and the state distribution becomes geometric.
From there come utilisation equal to rho, throughput equal to the arrival rate, a mean population of rho over one minus rho, and a mean response time of one over the gap between service and arrival rates. Every one of these depends on rho staying strictly below one; at or above it the geometric series diverges and no steady state exists.
Tail probabilities follow from the same series and drive buffer sizing decisions.
How to use it on the tests
Both in-person tests are open book, so the formulas themselves are not the bottleneck. Marks are lost on unit conversion, on confusing a service time with a service rate, and on reading a percentage rise in load as a matching rise in delay.
Practise stating the steady-state condition first, converting every rate to the same time unit, and then checking that throughput equals arrival rate as a sanity test. The response-time curve is the other recurring theme: be ready to explain, with numbers, why a modest load increase near saturation produces a disproportionate delay, and why a proportionally smaller speed-up can absorb it.
What this chapter covers
- 01
Markov chains and the memoryless property
- 02
Poisson counts versus exponential times
- 03
Birth-death state-transition diagrams
- 04
Balance equations and the product formula
- 05
M/M/1 state probabilities and stability
- 06
Utilisation, mean jobs and mean response time
- 07
Response-time sensitivity near saturation
Worked example · free
A print server at three-quarters load
- 1Convert the mean printing time to a rate: mu = 60/2.5 = 24 jobs per minute.
- 1Compute rho = 18/24 = 0.75 and confirm rho < 1, so a steady state exists.
- 1Idle probability P0 = 1 - rho = 0.25.
- 1Mean jobs present E[n] = rho/(1 - rho) = 3.
- 1Mean response time E[r] = 1/(mu - lambda) = 1/6 minute = 10 s; subtract the 2.5 s of service to get a mean wait of 7.5 s.
- 1Tail probability P(n >= 3) = rho^3 = 0.421875.
Key terms
- Markov Chain
- A stochastic model of a sequence of events in which the probability of the next event depends only on the most recent state, not on the path taken to reach it.
- Memoryless Property
- A property of a waiting time whereby the remaining wait has the same distribution however long one has already waited; among continuous distributions only the exponential has it.
- Birth-Death Process
- A continuous-time Markov process whose only transitions are births, which raise the state by one, and deaths, which lower it by one.
- Balance Equation
- An equation stating that, at steady state, the probability flow rate into a state equals the flow rate out of it.
- Steady State
- A regime in which the probability of having n jobs in the system no longer depends on time; a system whose probabilities still change with time is transient.
- Traffic Intensity
- A dimensionless measure, rho = lambda/mu, of the rate at which work enters a system, quoted in Erlangs and equal to utilisation for a single lossless server.
- Mean Response Time
- The average time a job spends in the system, waiting plus its own service; for M/M/1 it equals 1/(mu - lambda).
Birth-Death Processes and the M/M/1 Queue FAQ
Why does the M/M/1 model need the utilisation to be strictly below one?
The state probabilities form a geometric series in rho, and that series only sums to a finite value when rho is less than one. At rho equal to or above one, work arrives at least as fast as it can be served, the queue grows without bound, and no steady-state probabilities or averages exist to report.
Is the number of arrivals or the time between arrivals exponential?
The time between arrivals is exponential, and so is each service time. The count of arrivals in a fixed interval is Poisson with mean and variance both equal to lambda times the interval length. The two descriptions are of the same random process, but writing that arrivals are exponentially distributed mixes up a count with a duration.
How do I get mean response time without memorising another formula?
Compute the mean number in the system, rho over one minus rho, and divide it by throughput, which at steady state equals the arrival rate because flow in equals flow out. The result simplifies to one over mu minus lambda, so the two routes double-check each other.
How many buffers does an M/M/1 device need for a target loss rate?
With B buffers, overflow happens when B plus one or more jobs are present, which has probability rho to the power B plus one. Set that below the target, take logarithms, and round up. Remember that dividing by the logarithm of rho, a negative number, flips the inequality direction.
Why does response time grow so much faster than load?
Response time is proportional to one over one minus rho, so each step toward full utilisation removes a shrinking slice of idle capacity and the delay multiplies. Moving from 80% to 90% utilisation doubles the mean response time even though throughput rises by only one eighth.
Assessment move
Draw the birth-death chain for an M/M/1 queue from memory, write the balance equation for states 0, 1 and 2, and derive P2 = rho squared times P0 by hand once. Then take three made-up loads, at rho of 0.5, 0.8 and 0.9, and compute E[n] and E[r] for each to feel the curve before the test.
Working through Birth-Death Processes and the M/M/1 Queue in CS5239? Sia is AskSia’s AI Computer Science tutor — ask any CS5239 Birth-Death Processes and the M/M/1 Queue question and get a clear, step-by-step explanation grounded in how CS5239 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.
