Traffic Intensity and the Stability Threshold

Traffic Intensity and the Queue-Length Process

In an M/M/1 queue, customers arrive at rate \(\lambda\), and a single server completes service at rate \(\mu\) whenever the system is nonempty. The central comparison is between these two rates. Their ratio indicates how much arriving work the server must handle relative to its service capacity, and it determines whether the queue-length balance equations can have a stationary probability distribution.

Assume throughout that \(\lambda>0\) and \(\mu>0\). On a probability space \((\Omega,\mathcal{F},\mathbb{P})\), let \((X_t)_{t\ge0}\) be the continuous-time Markov chain giving the number of customers in the system at time \(t\). Its state space is \(S=\{0,1,2,\ldots\}\), and its natural history is \(\mathcal{F}_t=\sigma(X_s:0\le s\le t)\). An arrival increases the state by one. A service completion decreases it by one when the state is positive; at state \(0\), the server is idle.

The generator \(Q=(q_{ij})\) records the instantaneous transition rates. At state \(0\), the only possible transition is an arrival. At every state \(n\ge1\), arrivals and service completions give transitions to \(n+1\) and \(n-1\), respectively. Thus \(q_{00}=-\lambda\), \(q_{01}=\lambda\), and, for \(n\ge1\), \(q_{n,n-1}=\mu\), \(q_{nn}=-(\lambda+\mu)\), and \(q_{n,n+1}=\lambda\); all other entries are zero. The boundary row sums to \(-\lambda+\lambda=0\), and every interior row sums to \(\mu-(\lambda+\mu)+\lambda=0\), as required for a generator.

A probability row vector \(\pi=(\pi_0,\pi_1,\ldots)\) is a stationary distribution if, when \(X_0\) has distribution \(\pi\), the distribution of \(X_t\) remains \(\pi\) for every \(t\ge0\). In this tutorial, “stationary distribution exists” means that such an invariant probability distribution exists. The balance equations express that, in stationarity, each state's probability mass does not change over time.

What the Stationary Balance Equations Require

For a stationary distribution, the equation for state \(0\) is \(\mu\pi_1=\lambda\pi_0\): the rate of mass leaving state \(0\) must equal the rate entering it. For each \(n\ge1\), the equation is \((\lambda+\mu)\pi_n=\lambda\pi_{n-1}+\mu\pi_{n+1}\). The left side is the rate of mass leaving state \(n\); the right side is the incoming rate from its two neighboring states.

These are the global balance equations. To derive the equations, use the small-time transition rates: over a time interval of length \(h\), a transition along an allowed edge with rate \(r\) has probability \(rh+o(h)\), while two or more jumps have probability \(o(h)\). Because all exit rates are bounded by \(\lambda+\mu\), the stationary forward equations apply to each state. Setting the time derivative of each stationary state probability to zero gives the displayed equations.

Proof. Define \(J_n=\lambda\pi_n-\mu\pi_{n+1}\). The balance equation at state \(0\) gives \(\lambda\pi_0-\mu\pi_1=0\), so \(J_0=0\). For \(n\ge1\), rearranging the balance equation gives \(\lambda\pi_{n-1}-\mu\pi_n=\lambda\pi_n-\mu\pi_{n+1}\), which is \(J_{n-1}=J_n\). Starting from \(J_0=0\), induction gives \(J_n=0\) for every \(n\ge0\). Therefore \(\lambda\pi_n=\mu\pi_{n+1}\) for every \(n\), as claimed. \(\square\)

The proposition turns the balance equations into a simple recurrence. Since \(\mu>0\), it gives \(\pi_{n+1}=\rho\pi_n\), and repeated substitution yields \(\pi_n=\pi_0\rho^n\) for every \(n\ge0\). A stationary distribution must also satisfy \(\pi_n\ge0\) and \(\sum_{n=0}^{\infty}\pi_n=1\). Those requirements impose the threshold.

Proof. First suppose a stationary probability distribution exists. The proposition gives \(\pi_n=\pi_0\rho^n\). If \(\pi_0=0\), the recurrence forces every \(\pi_n=0\), contradicting \(\sum_n\pi_n=1\); hence \(\pi_0>0\). If \(\rho\ge1\), then \(\pi_n=\pi_0\rho^n\ge\pi_0>0\) for every \(n\), so the series \(\sum_n\pi_n\) diverges. This contradicts normalization. Therefore \(\rho<1\), equivalently \(\lambda<\mu\). When \(0<\rho<1\), the geometric series gives \(\sum_{n=0}^{\infty}\rho^n=1/(1-\rho)\), so normalization forces \(\pi_0=1-\rho\).

Conversely, suppose \(\rho<1\) and define \(\pi_n=(1-\rho)\rho^n\). Each term is nonnegative, and \(\sum_n\pi_n=(1-\rho)/(1-\rho)=1\). Also, \(\lambda\pi_n=\mu\pi_{n+1}\) because \(\mu\pi_{n+1}=\mu(1-\rho)\rho^{n+1}=\lambda(1-\rho)\rho^n\). At state \(0\), this equality is exactly the balance equation. For \(n\ge1\), adding \(\lambda\pi_n=\mu\pi_{n+1}\) to \(\mu\pi_n=\lambda\pi_{n-1}\) gives \((\lambda+\mu)\pi_n=\lambda\pi_{n-1}+\mu\pi_{n+1}\). Thus all balance equations hold.

To see that this probability vector is invariant, set \(\nu=\lambda+\mu\) and \(R=I+Q/\nu\). The row at state \(0\) has entries \(R_{00}=\mu/\nu\) and \(R_{01}=\lambda/\nu\), summing to \(1\). For \(n\ge1\), the entries \(R_{n,n-1}=\mu/\nu\), \(R_{nn}=0\), and \(R_{n,n+1}=\lambda/\nu\) also sum to \(1\). The balance equations give \(\pi Q=0\), hence \(\pi R=\pi\). The chain can be represented by potential jump times from a rate-\(\nu\) Poisson process, using \(R\) as the transition matrix at each potential jump; a transition may leave the state unchanged. Conditional on \(k\) potential jumps by time \(t\), its distribution is \(\pi R^k=\pi\). Averaging over the Poisson number of jumps leaves the distribution equal to \(\pi\). Thus \(\pi\) is stationary, proving existence when \(\rho<1\). \(\square\)

Worked Examples Across the Threshold

Why the Threshold Is a Normalization Condition

The balance equations describe how probability mass moves between neighboring queue lengths. They force the stationary weights, if they exist, to have a geometric ratio \(\rho\). The condition \(\lambda<\mu\) is exactly what makes those weights summable. At \(\rho=1\), the weights are constant; above \(1\), they increase. Neither case can be normalized over the unbounded state space.

This conclusion concerns existence of a stationary probability distribution. It does not, by itself, assert a particular convergence rate from every initial state or describe the distribution of waiting times. Those are distinct questions. The calculation here also depends on the M/M/1 assumptions: a single server, Poisson arrivals at rate \(\lambda\), exponential service at rate \(\mu\) while busy, and an unlimited queue capacity.

Common pitfall: treating the critical case as normalizable. At \(\rho=1\), one might truncate the state space at \(N\), assign probability \(1/(N+1)\) to each state \(0,\ldots,N\), and then claim a stationary distribution by letting \(N\) increase. For each fixed \(n\), however, \(1/(N+1)\) tends to \(0\). The pointwise limit assigns zero to every state, whose total mass is \(0\), not \(1\). A sequence of normalized distributions on larger and larger finite sets need not have a normalized limit on the infinite state space. The correct test is whether the infinite series of balance weights sums to \(1\).