Utilization and the Probability of an Idle Server

Utilization as a Stationary Probability

In an M/M/1 queue, the server alternates between idle periods and periods of work. Its utilization is the fraction of time it is occupied serving customers. When the queue is stable, this time fraction has a simple expression: it is the ratio of the arrival rate to the service rate. The stationary distribution makes that expression precise, while regenerative cycles give a useful second interpretation.

Consider a probability space \((\Omega,\mathcal{F},\mathbb{P})\) carrying a continuous-time Markov chain \((X_t)_{t\ge0}\), with filtration \((\mathcal{F}_t)_{t\ge0}\). The state \(X_t=n\) means that \(n\) customers are in the system at time \(t\), so the state space is \(S=\{0,1,2,\ldots\}\). Arrivals occur at rate \(\lambda>0\), and service completions occur at rate \(\mu>0\) whenever the system is nonempty. Thus the generator \(Q=(q_{ij})\) has \(q_{0,1}=\lambda\), \(q_{0,0}=-\lambda\), and, for \(n\ge1\), \(q_{n,n+1}=\lambda\), \(q_{n,n-1}=\mu\), and \(q_{n,n}=-(\lambda+\mu)\). All other entries are zero. Each row sums to zero: at state \(0\), \(-\lambda+\lambda=0\); at each \(n\ge1\), \(\lambda+\mu-(\lambda+\mu)=0\).

The traffic intensity or utilization parameter is \(\rho=\lambda/\mu\). The queue is stable when \(\rho<1\), equivalently \(\lambda<\mu\). The server is idle exactly when \(X_t=0\), and busy exactly when \(X_t\ge1\). We will find the stationary probability of state \(0\), then take its complement to obtain the busy probability.

Finding the Idle Probability

For a stationary distribution, the balance equations are \(\pi Q=0\). In this model, the total exit rates are bounded by \(\lambda+\mu\), so these equations characterize stationarity. To see the sufficiency directly, choose \(c\ge\lambda+\mu\) and set \(R=I+Q/c\). The rows of \(R\) sum to one and have nonnegative entries. Uniformization gives \(P(t)=e^{-ct}\sum_{k=0}^{\infty}(ct)^kR^k/k!\). If \(\pi Q=0\), then \(\pi R=\pi\), hence \(\pi R^k=\pi\) for every \(k\), and the displayed series gives \(\pi P(t)=\pi\). Conversely, differentiating \(\pi P(t)=\pi\) at \(t=0\) gives \(\pi Q=0\).

For each \(n\ge0\), add the balance equations for states \(0,1,\ldots,n\). Transitions within this set cancel in pairs. The only transition out is an arrival from \(n\) to \(n+1\), with stationary flow \(\pi_n\lambda\); the only transition in is a service completion from \(n+1\) to \(n\), with flow \(\pi_{n+1}\mu\). Therefore \(\pi_n\lambda=\pi_{n+1}\mu\). These equations are the local balance relations for this birth-death chain.

Proof. The balance relation gives \(\pi_{n+1}=\rho\pi_n\) for every \(n\ge0\). Repeated substitution yields \(\pi_n=\pi_0\rho^n\). If \(\rho<1\), then \(\sum_{n=0}^{\infty}\rho^n=1/(1-\rho)\), and normalization requires \(1=\sum_{n=0}^{\infty}\pi_n=\pi_0/(1-\rho)\). Thus \(\pi_0=1-\rho\), and the resulting probabilities sum to one. They satisfy the balance equations: at state \(0\), \(-\lambda\pi_0+\mu\pi_1=0\); at \(n\ge1\), \(\lambda\pi_{n-1}-(\lambda+\mu)\pi_n+\mu\pi_{n+1}=0\), by the adjacent balance relations. The bounded-rate argument above shows this distribution is stationary. If \(\rho\ge1\), then \(\sum_{n\ge0}\pi_0\rho^n\) is infinite for every \(\pi_0>0\), so it cannot be normalized. If \(\pi_0=0\), the balance relation forces every \(\pi_n=0\), also impossible for a probability distribution. Thus no stationary probability distribution exists in that case. Finally, when \(\rho<1\), the probability of being busy is \(1-\pi_0=\rho\). \(\square\)

This calculation identifies the stationary chance of finding the server busy when the system is in equilibrium. It does not say that an arrival sees a busy server with this probability; that is a different sampling question. Here, the probabilities refer to time in the stationary process.

Why These Probabilities Are Long-Run Time Fractions

For an irreducible positive recurrent continuous-time Markov chain, the ergodic theorem identifies stationary probabilities with long-run proportions of time. In this queue, positive recurrence holds under \(\lambda<\mu\). The same interpretation can be seen through regenerative cycles, which begin whenever the system becomes empty. A cycle consists of an idle period followed by the ensuing busy period and ends at the next return to state \(0\).

Here is the cycle calculation. The idle period has mean \(1/\lambda\). Let \(B\) be the length of a busy period that starts with one customer. During a customer's service, the expected number of arrivals is \(\lambda/\mu=\rho\), because the service time has mean \(1/\mu\). Each such arrival initiates further service within the same busy period. For \(\rho<1\), the expected number of customers served in successive generations is \(1+\rho+\rho^2+\cdots=1/(1-\rho)\): the initial customer is generation zero, and each customer has mean \(\rho\) arrivals during service. Each customer's mean service time is \(1/\mu\), so linearity of expectation gives \(\mathbb{E}[B]=1/(\mu(1-\rho))=1/(\mu-\lambda)\).

The renewal-reward theorem says that for independent, identically distributed regenerative cycles with finite mean length and finite mean reward, the long-run reward per unit time is the expected reward in a cycle divided by its expected length. Its hypotheses hold here: the idle and busy portions regenerate at state \(0\), and the cycle mean is finite when \(\lambda<\mu\). Taking busy time as the reward, and idle time as a second reward, gives the following fractions.

Thus, when the queue is stable, the stationary probabilities agree with the long-run time fractions: over a long observation period, the server spends a fraction \(\rho\) of time busy and a fraction \(1-\rho\) idle, almost surely. This is a time average, not a claim about what an arriving customer observes.

When Utilization Is Not a Probability

Common mistake. It is incorrect to call \(\lambda/\mu\) the stationary busy probability without checking stability. For example, if \(\lambda=4\) and \(\mu=3\), then \(\rho=4/3\). Substituting mechanically would give an “idle probability” \(1-\rho=-1/3\), which is impossible for a probability. The correction is that \(\lambda\ge\mu\) gives no stationary probability distribution for the infinite-capacity M/M/1 queue. The busy-probability formula applies only when \(0<\lambda<\mu\).

Also distinguish a stationary probability from a long-run fraction. The stationary probability refers to the distribution at a fixed time when the process is initialized in equilibrium. The long-run fraction is a limit of time averages. In this stable irreducible queue, the ergodic theorem and the regenerative-cycle calculation connect them; the two concepts are not identical by definition. Neither quantity is the probability seen by an arriving customer, which requires a separate argument.