Arrival and Service Rates in the Birth-Death Model

From Queue Events to Transition Rates

In an M/M/1 queue, the state records how many customers are in the system, including any customer in service. Arrivals increase that count by one. A service completion decreases it by one only when the system is nonempty. Turning these event descriptions into transition rates gives a continuous-time birth-death model: births are arrivals, and deaths are service completions.

Assume throughout that the arrival rate \(\lambda\) and service rate \(\mu\) are finite and strictly positive. Arrivals form a Poisson process of rate \(\lambda\). Service times are independent exponential random variables of rate \(\mu\), independent of arrivals, and one customer is served at a time whenever the system is nonempty. The exponential memoryless property ensures that, conditional on the current queue length, the remaining service time of a customer in service is again exponential with rate \(\mu\).

Let \((\Omega,\mathcal F,\mathbb P)\) be a probability space supporting the arrival and service randomness, and let \((X_t)_{t\ge0}\) be the queue length at time \(t\). Its state space is \(S=\{0,1,2,\ldots\}\), and time is continuous. We use the filtration \((\mathcal F_t)_{t\ge0}\) generated by the queue history and the arrival and service information observed up to time \(t\). The memoryless and independence assumptions imply that, given \(X_t\), the future evolution has the same transition law as a new queue started in state \(X_t\).

The word “rate” describes the probability of a transition over a short interval: if the rate from \(i\) to \(j\) is \(r\), then the conditional transition probability over an interval of length \(h\) is \(rh+o(h)\) as \(h\downarrow0\). Here \(o(h)\) denotes a quantity whose ratio to \(h\) tends to zero. The transition rates are not themselves probabilities and need not sum to one. It is the generator row, including its negative diagonal entry, that sums to zero.

The Generator and the Boundary at Zero

Proof. Fix a state \(n\). If \(n=0\), an arrival is the only event that can change the queue length. The probability of an arrival during an interval of length \(h\) is \(1-e^{-\lambda h}=\lambda h+o(h)\), so \(q_{0,1}=\lambda\). There is no customer in service, hence no service completion can decrease the state. For \(n\ge1\), the time to the next arrival is exponential with rate \(\lambda\), and the time to the next service completion is exponential with rate \(\mu\); these times are independent. The probability of exactly one arrival and no service completion during an interval of length \(h\) is \(\lambda h e^{-(\lambda+\mu)h}=\lambda h+o(h)\). The probability of exactly one service completion and no arrival is \(\mu h e^{-(\lambda+\mu)h}=\mu h+o(h)\). The probability of two or more potential events in the interval is \(O(h^2)\), so it contributes zero after division by \(h\) and passage to the limit. Thus the upward and downward rates are \(\lambda\) and \(\mu\). A row of a generator sums to zero by its definition, so the diagonal entry is the negative of the sum of the rates to distinct states. No other state can be reached by a single event, so its rate is zero. \(\square\)

This calculation also explains the boundary condition. At a positive queue length, one arrival and one service completion are possible types of state-changing event. At zero, only an arrival is possible. The service rate \(\mu\) does not disappear from the model; rather, it is inactive when there is no customer to serve.

Proof. At zero, the next change occurs at the next arrival, whose waiting time is exponential with rate \(\lambda\), and that arrival moves the chain to one. At \(n\ge1\), let \(A\) and \(C\) be the independent waiting times to the next arrival and service completion. For \(s\ge0\), the chance that neither event occurs by time \(s\) is \(\mathbb P(A>s,C>s)=e^{-\lambda s}e^{-\mu s}=e^{-(\lambda+\mu)s}\). Thus the minimum of the two waiting times is exponential with rate \(\lambda+\mu\). The probability that the arrival occurs first is \(\int_0^\infty \lambda e^{-\lambda s}e^{-\mu s}\,ds=\lambda/(\lambda+\mu)\); the probability that the service completion occurs first is \(\int_0^\infty \mu e^{-\mu s}e^{-\lambda s}\,ds=\mu/(\lambda+\mu)\). These probabilities sum to one, and the corresponding events move the chain up or down by one. \(\square\)

The holding-time description and the generator describe the same local behavior in two forms. In particular, the total rate of leaving state \(n\) is \(-q_{nn}\): it is \(\lambda\) at zero and \(\lambda+\mu\) in every positive state. The jump probabilities are obtained by dividing each possible outgoing rate by this total rate.

Worked Examples

A Common Boundary Error

A frequent mistake is to give state zero the same diagonal entry as a positive state, namely \(-(\lambda+\mu)\). For example, with \(\lambda=2\) and \(\mu=3\), this would put \(-5\) on the diagonal at zero. If the only listed outgoing transition is the arrival to state one at rate \(2\), the proposed row sum is \(-5+2=-3\), not zero. The row is not a generator row, and the calculation has incorrectly included a service event when no customer is present.

The correction is to count only events that can change the state from the state in question. At zero, the only such event is an arrival, so the row is \((-2,2,0,\ldots)\), with sum \(-2+2=0\). At a positive state, both events are possible, so the diagonal entry is \(-(2+3)=-5\), and the row sum is \(3-5+2=0\). The two diagonal formulas differ because the set of possible events differs at the boundary.

The rates specify local transitions, holding times, and the behavior at an empty system. They do not by themselves assert that a stationary distribution exists or describe long-run queue behavior. Those questions require separate analysis; for constructing the birth-death model, the essential checks are that each listed rate corresponds to a possible event and that every generator row sums to zero.