Birth-and-Death Process Steady-State Probabilities

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 \lambda_n is the birth rate for state n, \mu_n is the death rate for state n, and P_n is the probability of being in state n in steady-state, then we have the set of equations

\displaystyle \lambda_0 P_0 = \mu_1 P_1,
\displaystyle (\lambda_n + \mu_n)P_1 = \lambda_{n-1} P_{n-1} + \mu_{n+1} P_{n+1}, for n \geq 1.

The first equation gives us \displaystyle P_1 = \frac{\lambda_0}{\mu_1} P_0.  Substituting into the second equation when n =1 yields

\displaystyle P_2 = \frac{(\lambda_1 + \mu_1)P_1 - \lambda_0 P_0}{\mu_2} = \frac{(\lambda_1 + \mu_1)P_1 - \mu_1 P_1}{\mu_2} = \frac{\lambda_1}{\mu_2}P_1 = \frac{\lambda_1 \lambda_0}{\mu_2 \mu_1} P_0.

This suggests that we might have \displaystyle P_n = \frac{\lambda_{n-1}}{\mu_n} P_{n-1} for n \geq 1.  Assuming this, we have

\displaystyle P_{n+1} = \frac{(\lambda_n + \mu_n)P_n - \lambda_{n-1} P_{n-1}}{\mu_{n+1}} = \frac{(\lambda_n + \mu_n)P_n - \mu_n P_n}{\mu_{n+1}} = \frac{\lambda_n}{\mu_{n+1}} P_n.

Therefore, \displaystyle P_n = \frac{\prod_{i=0}^{n-1} \lambda_i}{\prod_{i=1}^n \mu_i} P_0.

Assuming that the birth and death rates are such that we actually have well-defined steady state probabilities, \displaystyle \sum_{n=0}^{\infty} P_n = 1, and so

\displaystyle \sum_{n=0}^{\infty} \frac{\prod_{i=0}^{n-1} \lambda_i}{\prod_{i=1}^n \mu_i} P_0 = 1,

which implies

\displaystyle P_0 = \left( \sum_{n=0}^{\infty} \frac{\prod_{i=0}^{n-1} \lambda_i}{\prod_{i=1}^n \mu_i} \right)^{-1}.

In general, then,

\displaystyle P_n = \left(\prod_{i=1}^n \frac{\lambda_{i-1}}{\mu_i} \right) \left(\sum_{n=0}^{\infty} \frac{\prod_{i=0}^{n-1} \lambda_i}{\prod_{i=1}^n \mu_i} \right)^{-1}.

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 \lambda_i = \lambda and \mu_i = \mu for each i.  In this case, the formula for P_0 simplifies nicely.  We get

\displaystyle P_0 = \left( \sum_{n=0}^{\infty} \frac{\lambda^n}{\mu^n} \right)^{-1} = \left( \sum_{n=0}^{\infty} \left(\frac{\lambda}{\mu} \right)^n \right)^{-1} = \left( \frac{1}{1 - \lambda/\mu} \right)^{-1} = 1 - \frac{\lambda}{\mu}.

In the second-to-last step we use the formula for a geometric series.  This step requires \lambda < \mu; 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 \displaystyle P_n = \frac{\lambda^n}{\mu^n} \left(1 - \frac{\lambda}{\mu} \right).

Advertisements
This entry was posted in probability, queuing. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s