The Stationary Workload Distribution

Workload at an Arbitrary Time

Queue length counts customers, while workload measures the service still required to clear them. In an M/M/1 queue, the workload at an arbitrary time includes the remaining service of the customer in service and the full service requirements of customers waiting. It is zero exactly when the server is idle. Its stationary distribution therefore reflects both the stationary number of customers and the exponential service-time assumption.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Consider a single-server, first-come-first-served queue with Poisson arrivals of rate \(\lambda>0\), independent service times with exponential distribution of rate \(\mu>0\), and an infinite waiting room. Write \((N_t)_{t\ge0}\) for the number of customers in the system and \((V_t)_{t\ge0}\) for the workload, both in continuous time. Thus \(V_t\) is measured in units of service time. Let \(\rho=\lambda/\mu\). We consider the stationary regime, which exists for this M/M/1 queue when \(\rho<1\).

We use the stationary queue-length probabilities established for the M/M/1 model: \(\mathbb{P}(N_t=n)=(1-\rho)\rho^n\) for \(n=0,1,\ldots\). These probabilities sum to one because \(\sum_{n=0}^{\infty}(1-\rho)\rho^n=1\) when \(0<\rho<1\). The key step is to determine the workload conditional on \(N_t=n\).

Proof. If \(n=1\), the customer in service has an exponential service requirement. Conditional on its service age and on the history determining that it is still in service, the memoryless property gives an exponential remaining service time of rate \(\mu\), independent of that age. If \(n>1\), the other \(n-1\) customers are waiting and each has an independent, not-yet-started service requirement with the original exponential distribution. Those service requirements are independent of the remaining service time in progress. Thus the workload conditional on \(N_t=n\) is a sum of \(n\) independent rate-\(\mu\) exponential variables. For \(n=1\), its density is \(\mu e^{-\mu x}\). If the sum of \(n\) such variables has density \(g_n(y)=\mu^n y^{n-1}e^{-\mu y}/(n-1)!\), convolution with one more exponential density gives, for \(x>0\), $$ g_{n+1}(x)=\int_0^x g_n(y)\mu e^{-\mu(x-y)}\,dy =\frac{\mu^{n+1}e^{-\mu x}}{(n-1)!}\int_0^x y^{n-1}\,dy =\frac{\mu^{n+1}x^n e^{-\mu x}}{n!}. $$ This proves the density formula by induction. \(\square\)

The Stationary Workload Law

Proof. Write \(V\) for a workload at an arbitrary stationary time. Since the workload is zero exactly when \(N_t=0\), \(\mathbb{P}(V=0)=\mathbb{P}(N_t=0)=1-\rho\). For \(n\ge1\), the proposition gives the conditional density of \(V\) given \(N_t=n\). Therefore, for \(x>0\), the density of the positive part of the workload is the mixture $$ f_V(x)=\sum_{n=1}^{\infty}(1-\rho)\rho^n \frac{\mu^n x^{n-1}e^{-\mu x}}{(n-1)!}. $$ All summands are nonnegative, so the series can be evaluated term by term. Factoring out the terms that do not depend on \(n\) gives $$ f_V(x)=(1-\rho)\rho\mu e^{-\mu x} \sum_{k=0}^{\infty}\frac{(\rho\mu x)^k}{k!} =(1-\rho)\rho\mu e^{-\mu x}e^{\rho\mu x}. $$ Since \(\rho\mu=\lambda\) and \((1-\rho)\mu=\mu-\lambda\), this is \(f_V(x)=\rho(\mu-\lambda)e^{-(\mu-\lambda)x}\). Integrating this density from \(x\) to infinity gives \(\mathbb{P}(V>x)=\rho e^{-(\mu-\lambda)x}\) for \(x\ge0\). At \(x=0\), this tail is \(\rho\), which agrees with \(\mathbb{P}(V>0)=1-\mathbb{P}(V=0)=\rho\). Finally, for \(x\ge0\), $$ \mathbb{P}(V>x\mid V>0)=\frac{\mathbb{P}(V>x)}{\mathbb{P}(V>0)} =\frac{\rho e^{-(\mu-\lambda)x}}{\rho} =e^{-(\mu-\lambda)x}. $$ The conditioning is meaningful because \(\rho>0\). This is the survival function of an exponential random variable with rate \(\mu-\lambda\). \(\square\)

The distribution has two parts: an atom of size \(1-\rho\) at zero and a continuous exponential component on positive workloads. Equivalently, for \(x\ge0\), its cumulative distribution function is \(1-\rho e^{-(\mu-\lambda)x}\). At \(x=0\) this gives \(1-\rho\), not one: the jump there is exactly the idle probability.

Why the Tail Rate Is Not the Service Rate

A frequent error is to treat positive workload as only the remaining service time of the customer currently in service. That residual time is exponential with rate \(\mu\), but a busy system can also have customers waiting, whose service requirements add to the workload. Mixing over the stationary number in the system changes the tail rate from \(\mu\) to \(\mu-\lambda\).

Common mistake. In the first example, using \(\mathbb{P}(V>1)=\rho e^{-\mu}\) would give \(\frac25e^{-5}\). This calculation incorrectly assumes that, whenever the server is busy, there is no additional queued work. The correct calculation mixes over all positive queue lengths and gives \(\frac25e^{-(5-2)}=\frac25e^{-3}\). The discrepancy is not a change in the service-time distribution; it comes from including work waiting behind the customer in service.

The stability condition matters as well. The formula requires \(0<\lambda<\mu\). At \(\lambda=\mu\), substituting into the displayed tail expression would give a tail equal to one for every \(x\ge0\), which cannot be the tail of a finite-valued stationary workload: it would imply \(\mathbb{P}(V>0)=1\) and no decrease in the tail as \(x\) grows. There is no stationary M/M/1 workload distribution in that case, so the formula must not be extended to the boundary.

The key interpretation is that the positive workload, conditional on being nonzero, has an exponential distribution with rate \(\mu-\lambda\), while the probability of a positive workload is \(\rho\). The atom at zero records idle time; the exponential component accounts for the remaining service and all work waiting. Keeping these two parts separate prevents confusion between workload, an individual service time, and queue length.