Efficient and Reliable Computation of Birth-Death Process Performance Measures

We present an efficient, reliable, and easy-to-implement algorithm to compute steady-state probabilities for birth-death processes whose upper-tail probabilities decay geometrically or faster. The algorithm can provide any required accuracy and avoids over- and underflow. In addition to steady-state probabilities, the algorithm can compute any performance measure that can be expressed as the expected value of a function of the population size, for nonnegative functions that are bounded by a constant, linear, or quadratic function of population size. The algorithm works with conditional steady-state probabilities, given that the population is in a range that is extended up and down as the algorithm progresses. These conditional probabilities facilitate the derivation of truncation error bounds. We illustrate the application of the algorithm to the Erlang B, C, and A queueing systems.