A Worked M/M/1 Performance Calculation

From Rates to Performance Measures

An M/M/1 performance calculation starts with two rates: arrivals occur at rate \(\lambda\), and service completions occur at rate \(\mu\) whenever the server is busy. These rates describe a single-server queue with Poisson arrivals, independent exponential service times, an unlimited waiting room, and first-come, first-served (FCFS) service. The first question is whether the queue has a stationary distribution. If it does, a small set of formulas gives occupancy probabilities, utilization, mean queue length, and delay. A waiting-time tail then answers a probability question about an individual arriving customer.

Let \((X_t)_{t\ge0}\) be the number of customers in the system at time \(t\), on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with state space \(S=\{0,1,2,\ldots\}\) and continuous time \(t\ge0\). From state \(0\), the process jumps to \(1\) at rate \(\lambda\). From state \(n\ge1\), it jumps to \(n+1\) at rate \(\lambda\) and to \(n-1\) at rate \(\mu\). Assume \(\lambda>0\) and \(\mu>0\). The generator has \(q_{00}=-\lambda\), and for \(n\ge1\), \(q_{nn}=-(\lambda+\mu)\), with the off-diagonal rates just specified; each generator row sums to zero.

Rates must be expressed in the same time units before they are compared or used in a formula. A stationary calculation also requires \(\rho<1\), equivalently \(\lambda<\mu\). Under that condition, the stationary probabilities and performance measures are

and, by flow balance or Little's law,

Here \(\pi_n\) is the stationary probability of \(n\) customers in the system. The distinction between \(W_q\) and \(W\) matters: \(W_q\) excludes service, whereas \(W\) includes it. In a stable system, the long-run throughput equals \(\lambda\), so these mean-time identities use the arrival rate \(\lambda\).

Why the Stationary Formulas Apply

Proof. Suppose first that \(\pi=(\pi_0,\pi_1,\ldots)\) is a stationary probability distribution. For any \(n\ge0\), consider the set of states \(\{0,\ldots,n\}\). The only transition out of this set is an arrival from state \(n\), at rate \(\lambda\); the only transition into it from outside is a service completion from state \(n+1\), at rate \(\mu\). Stationarity makes the net flow across this boundary zero. Thus \(\lambda\pi_n=\mu\pi_{n+1}\), or \(\pi_{n+1}=\rho\pi_n\). Repeated substitution gives \(\pi_n=\pi_0\rho^n\) for every \(n\ge0\). If \(\rho\ge1\), these terms do not have a finite sum, so they cannot be the probabilities of a stationary distribution. If \(\rho<1\), normalization requires \(1=\sum_{n=0}^{\infty}\pi_n=\pi_0\sum_{n=0}^{\infty}\rho^n=\pi_0/(1-\rho)\), so \(\pi_0=1-\rho\). This produces a probability distribution, and its adjacent-state flow equations hold. For each state, those equations balance all incoming and outgoing stationary rates, so \(\pi Q=0\); hence the distribution is stationary. The recurrence \(\pi_{n+1}=\rho\pi_n\) and normalization also show it is unique. \(\square\)

The formulas for \(L\) and \(L_q\) follow from this distribution. For \(0\le\rho<1\), the geometric series gives \(\sum_{n\ge0}\pi_n=1\). Differentiating \(\sum_{n\ge0}\rho^n=1/(1-\rho)\) for \(\rho<1\) gives \(\sum_{n\ge0}n\rho^n=\rho/(1-\rho)^2\). Therefore \(L=\sum_{n\ge0}n\pi_n=\rho/(1-\rho)\). The queue excludes one customer when the system is nonempty, so \(L_q=L-\mathbb{P}(X_t\ge1)=L-\rho=\rho^2/(1-\rho)\). For a stable queue, Poisson arrivals see the stationary time-average occupancy (PASTA), and Little's law gives \(L_q=\lambda\mathbb{E}[W_q]\) and \(L=\lambda\mathbb{E}[W]\). These are the standard PASTA and Little's law results; their general proofs are not repeated here.

Proof. By PASTA, an arriving customer sees \(n\) customers in the system with probability \(\pi_n=(1-\rho)\rho^n\). If \(n=0\), the customer waits zero time. If \(n\ge1\), FCFS service and the memoryless property of exponential service imply that the customer's waiting time is the sum of \(n\) independent exponential service times of rate \(\mu\). Its density at \(t>0\) is \(\mu^n t^{n-1}e^{-\mu t}/(n-1)!\). Mixing over \(n\ge1\), the density of the positive part of \(W_q\) is $$ \sum_{n=1}^{\infty}(1-\rho)\rho^n \frac{\mu^n t^{n-1}e^{-\mu t}}{(n-1)!} =(1-\rho)\rho\mu e^{-\mu t} \sum_{r=0}^{\infty}\frac{(\rho\mu t)^r}{r!} =\rho(\mu-\lambda)e^{-(\mu-\lambda)t}. $$ The equality uses the exponential series and \((1-\rho)\mu=\mu-\lambda\). Integrating this density from \(t\) to infinity gives \(\mathbb{P}(W_q>t)=\rho e^{-(\mu-\lambda)t}\) for \(t\ge0\). At \(t=0\), this gives \(\mathbb{P}(W_q>0)=\rho\), which also follows because a customer waits exactly when the system is nonempty. \(\square\)

Worked Performance Calculations

Interpretation and Common Pitfalls

These calculations describe a stationary queue, not every possible initial condition at every time. In particular, an arrival rate larger than or equal to the service rate invalidates the stationary formulas; inserting \(\rho\ge1\) into a geometric-series expression does not produce a probability distribution. The waiting-time tail also has a specific interpretation: it is the time until service begins, under stationary arrivals and FCFS, not the time until service is completed.

A common error is to call \(L\) the mean queue length and then use it to calculate the mean waiting time before service. For the first example, that mistake would give \(L/\lambda=2/2=1\) hour as the mean queue wait. But \(L\) counts the customer in service as well as those waiting. The correction is \(L_q/\lambda=(4/3)/2=2/3\) hour; the one-hour value is the mean total time in the system. A second check is \(\mathbb{E}[W]=\mathbb{E}[W_q]+1/\mu=2/3+1/3=1\) hour, where \(1/\mu=1/3\) hour is the mean service time.

For a reliable calculation, keep the quantities distinct: \(\rho\) is utilization, \(L_q\) counts those waiting, \(L\) counts everyone in the system, \(W_q\) excludes service, and \(W\) includes service. Check stability before computing stationary measures, and use the strict tail event \(W_q>t\) when applying the waiting-time formula.