A birth-and-death process is a special kind of continuous-time Markov chain that has applications in queuing. If we assume that arrivals to a queuing system follow a Poisson process and that service times are exponentially distributed, then the resulting queuing system is a birth-and-death process. In this post we’ll derive the steady-state probabilities for a general birth-and-death process. At the end we’ll take the special case in which the arrival rates are the same and the service rates are the same. This will give us the steady-state probabilities for the basic M/M/1 queuing system.
Derivation of the steady-state probabilities.
In steady-state for a continuous-time Markov chain the rate at which individuals transition into a particular state must be equal to the rate at which individuals transition out of that state. If is the birth rate for state n, is the death rate for state n, and is the probability of being in state n in steady-state, then we have the set of equations
, for .
The first equation gives us . Substituting into the second equation when yields
This suggests that we might have for . Assuming this, we have
Assuming that the birth and death rates are such that we actually have well-defined steady state probabilities, , and so
In general, then,
Application to the M/M/1 queuing system.
For an M/M/1 queuing system (i.e., a system with Markovian, or exponential, interarrival and service times, plus a single server), we have and for each i. In this case, the formula for simplifies nicely. We get
In the second-to-last step we use the formula for a geometric series. This step requires ; otherwise, the infinite series fails to converge. This should make sense: If the arrival rate is larger than the service rate then over time the queue will get longer and longer and so will never approach steady-state. (It is perhaps harder to see intuitively that we do not get a steady state if the arrival and service rates are equal, but that falls out of the mathematics here.)
In general, then, for the M/M/1 queuing system, the probability that there are exactly n customers in the system in steady-state is given by