Deadline Probabilities in a Stable M/M/1 Queue
A service target often asks for the probability that a customer waits no longer than a specified deadline. In an M/M/1 queue, the answer depends on whether the deadline applies to waiting in the queue or to the customer’s entire time in the system. Both probabilities can be calculated from the arrival rate \(\lambda\), the service rate \(\mu\), and the deadline, but their formulas are different.
Consider a queue on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Its continuous-time state is \(X_t\in S=\{0,1,2,\ldots\}\), the number of customers in the system at time \(t\). Arrivals follow a Poisson process of rate \(\lambda>0\), service times are independent exponential random variables with rate \(\mu>\lambda\), and customers are served first come, first served. The condition \(\lambda<\mu\) is the stability condition, so the queue has stationary probabilities \(\pi_n=(1-\rho)\rho^n\), where \(\rho=\lambda/\mu\). We consider a customer arriving in stationarity. By PASTA, such an arrival sees the stationary distribution of \(X_t\); PASTA is a standard result from the earlier material on queueing systems.
The waiting time \(W_q\) can equal zero: this happens when the arriving customer finds the system empty. In contrast, \(W\) includes the customer’s own service time, so it has no mass at zero. This distinction leads to different tail probabilities.
Deriving the Two Tails
Proof. Let \(N\) be the number of customers an arrival sees in the system. By PASTA and stationarity, \(\mathbb{P}(N=n)=(1-\rho)\rho^n\) for \(n\ge0\). If \(N=0\), then \(W_q=0\). If \(N=n\ge1\), the arriving customer waits for \(n\) service completions before their own service begins. The remaining service time of the customer in service is exponential with rate \(\mu\), by the memoryless property. It is independent of the \(n-1\) subsequent service times. Thus, conditional on \(N=n\ge1\), \(W_q\) is a sum of \(n\) independent exponential random variables with rate \(\mu\), with density \(\mu^n t^{n-1}e^{-\mu t}/(n-1)!\) for \(t>0\).
For \(t>0\), mixing these densities over \(n\ge1\) gives the density of the positive part of \(W_q\): $$ \begin{aligned} f_{W_q}(t) &=\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_{k=0}^{\infty}\frac{(\rho\mu t)^k}{k!}\\ &=(1-\rho)\rho\mu e^{-(\mu-\rho\mu)t} =\rho\delta e^{-\delta t}. \end{aligned} $$ Here \(k=n-1\), \(\rho\mu=\lambda\), and \((1-\rho)\mu=\delta\). Integrating this density from \(t\) to infinity yields \(\rho e^{-\delta t}\) for \(t>0\). At \(t=0\), the probability of a strictly positive wait is \(\mathbb{P}(N\ge1)=\rho\), which is also the stated tail formula. The remaining probability \(1-\rho\) is the mass at \(W_q=0\).
If \(N=n\ge0\), the time in the system consists of the \(n\) service completions ahead of the arrival and the arriving customer’s own service. These are \(n+1\) independent exponential service times, including the memoryless residual service time if \(n\ge1\). Thus, conditional on \(N=n\), \(W\) has the Erlang density \(\mu^{n+1}t^n e^{-\mu t}/n!\) for \(t>0\). Mixing over \(n\ge0\) gives $$ \begin{aligned} f_W(t) &=\sum_{n=0}^{\infty}(1-\rho)\rho^n \frac{\mu^{n+1}t^n e^{-\mu t}}{n!}\\ &=(1-\rho)\mu e^{-\mu t} \sum_{n=0}^{\infty}\frac{(\rho\mu t)^n}{n!} =\delta e^{-\delta t}. \end{aligned} $$ Integrating from \(t\) to infinity gives \(\mathbb{P}(W>t)=e^{-\delta t}\). This holds also at \(t=0\), since \(W>0\) almost surely. Taking complements gives both deadline probabilities, including at \(d=0\). \(\square\)
The formulas show why the two notions of delay cannot be substituted for one another. The waiting-time tail has the extra factor \(\rho\), reflecting the probability that the arriving customer finds at least one customer in the system. The system-time tail does not: the arriving customer always has their own service to complete.
Worked Example: Calculating Both Probabilities at a Deadline
Suppose \(\lambda=2\), \(\mu=5\), and the deadline is \(d=(\ln 2)/3\). The stability check is \(2<5\), and the stationary traffic intensity is \(\rho=\lambda/\mu=2/5\). The rate difference is \(\delta=\mu-\lambda=3\), so $$ e^{-\delta d}=e^{-3(\ln 2)/3}=e^{-\ln 2}=\frac12. $$
The probability of waiting longer than the deadline is $$ \mathbb{P}(W_q>d)=\frac25\cdot\frac12=\frac15, $$ so the probability of meeting the waiting deadline is \(1-\frac15=\frac45\). The probability of spending longer than the deadline in the system is $$ \mathbb{P}(W>d)=\frac12, $$ so the probability of meeting the system-time deadline is \(1-\frac12=\frac12\).
Check: The positive-wait probability is \(\rho=2/5\), and the computed tail \(1/5\) is smaller, as it must be for a positive deadline. The two tail probabilities at the deadline are \(1/5\) for queue waiting and \(1/2\) for time in the system; their difference reflects the own-service time included in \(W\).
Turning Service Targets into Rate Inequalities
Suppose the requirement is that a customer meet a deadline \(d\) with probability at least \(\alpha\). Equivalently, the failure probability must be at most \(1-\alpha\). The tail formulas give the target conditions directly.
For a positive deadline \(d>0\), the system-time condition can be written as $$ (\mu-\lambda)d\ge \ln\!\left(\frac{1}{1-\alpha}\right). $$ The waiting-time condition can equivalently be written as $$ \ln\!\left(\frac{\mu}{\lambda}\right)+(\mu-\lambda)d \ge \ln\!\left(\frac{1}{1-\alpha}\right). $$ These are inequalities in the two rates, not just in their difference: for the waiting target, the prefactor \(\lambda/\mu\) matters as well as \(\mu-\lambda\).
To verify the equivalences, the waiting target is, by the theorem, \(1-(\lambda/\mu)e^{-(\mu-\lambda)d}\ge\alpha\). Subtracting \(1\) and multiplying by \(-1\) gives \((\lambda/\mu)e^{-(\mu-\lambda)d}\le1-\alpha\). Both sides are positive, so taking logarithms preserves the inequality. Rearranging then gives the stated logarithmic form. For the system target, the same steps give \(e^{-(\mu-\lambda)d}\le1-\alpha\); taking logarithms and multiplying by \(-1\) gives \((\mu-\lambda)d\ge\ln(1/(1-\alpha))\). Each step is reversible, so the conditions are equivalent to the original targets.
The logarithmic rearrangements use \(d>0\) only when one later divides by \(d\) to express a threshold for \(\mu-\lambda\). The probability inequalities themselves also apply at \(d=0\). At zero deadline, the waiting target reduces to \(1-\lambda/\mu\ge\alpha\), or \(\lambda/\mu\le1-\alpha\). The system-time target cannot hold at zero for any \(\alpha>0\), since \(\mathbb{P}(W\le0)=0\).
Worked Example: Testing Two Targets at the Same Rates
Let \(\lambda=3\), \(\mu=5\), and \(d=(\ln 2)/2\). Stability holds because \(3<5\). Substitution gives \(\rho=3/5\), \(\delta=2\), and \(e^{-\delta d}=e^{-\ln 2}=1/2\). The waiting failure probability is $$ \mathbb{P}(W_q>d)=\frac35\cdot\frac12=\frac3{10}, $$ so the waiting success probability is \(1-\frac3{10}=\frac7{10}\). For a waiting target of \(\alpha=2/3\), the required failure probability is at most \(1-\frac23=\frac13\). Since \(3/10\le1/3\), the target is met.
For the system-time target \(\alpha=1/2\), the failure probability is $$ \mathbb{P}(W>d)=\frac12=1-\frac12. $$ Thus this target is met exactly. The rate inequalities verify both conclusions: for waiting, \(\ln(5/3)+(\ln 2)=\ln(10/3)\ge\ln 3\), because \(10/3\ge3\); for system time, \((\mu-\lambda)d=2(\ln 2)/2=\ln 2=\ln(1/(1-1/2))\).
Check: The waiting success probability is \(7/10\), which is at least \(2/3\) because \(21/30\ge20/30\). The system success probability is \(1/2\), equal to its target. The results agree with the two rate inequalities.
Worked Example: One Queue Target Passes While the Other Fails
Take \(\lambda=1\), \(\mu=3\), \(d=(\ln 2)/2\), and target \(\alpha=3/4\) for each kind of delay. Stability holds, with \(\rho=1/3\), \(\delta=2\), and \(e^{-\delta d}=e^{-\ln 2}=1/2\). The waiting failure probability is $$ \mathbb{P}(W_q>d)=\frac13\cdot\frac12=\frac16, $$ so the waiting success probability is \(1-\frac16=\frac56\). Since \(5/6\ge3/4\), the waiting target passes.
The system failure probability is \(\mathbb{P}(W>d)=1/2\), so the system success probability is \(1/2\), which is less than \(3/4\). The system target fails. In inequality form, the waiting condition holds because $$ \ln(3/1)+2\frac{\ln 2}{2}=\ln 6\ge\ln 4, $$ whereas the system condition fails because $$ 2\frac{\ln 2}{2}=\ln 2<\ln 4. $$
Check: The target failure probability is \(1-3/4=1/4\). The waiting failure probability \(1/6\) is at most \(1/4\), while the system failure probability \(1/2\) is greater than \(1/4\), confirming the opposite pass/fail outcomes.
A Common Tail-Probability Error
A frequent mistake is to use \(e^{-(\mu-\lambda)t}\) for the probability that queue waiting exceeds \(t\). That is the system-time tail, not the queue-waiting tail. For example, with \(\lambda=2\), \(\mu=5\), and \(t=(\ln2)/3\), this incorrect calculation gives \(e^{-3t}=1/2\) as the probability of waiting longer than \(t\). The correct calculation includes the probability of finding the system occupied: $$ \mathbb{P}(W_q>t)=\frac25 e^{-3t}=\frac25\cdot\frac12=\frac15. $$ The missing factor \(2/5\) is not a minor adjustment: it accounts for the probability that waiting in the queue is positive at all.
For a target calculation, first identify which random time the deadline measures. Then calculate its tail, compare that tail with \(1-\alpha\), and check the stability condition \(\lambda<\mu\). In particular, an algebraic inequality is not a substitute for checking that the queue is stable and the stationary formulas apply.
Check Your Understanding
Use the stable M/M/1 assumptions and verify each answer by substituting into the appropriate tail formula.
- If \(\lambda=1\) and \(\mu=4\), what is \(\mathbb{P}(W_q>0)\)? What is \(\mathbb{P}(W>0)\)?
- For a positive deadline \(d\), write the system-time target \(\mathbb{P}(W\le d)\ge\alpha\) as an inequality involving \(\mu-\lambda\).
- At deadline zero, express the waiting-time target \(\mathbb{P}(W_q\le0)\ge\alpha\) as a condition on \(\lambda/\mu\).
- For \(\lambda=2\), \(\mu=4\), and \(d=(\ln2)/2\), calculate both tail probabilities and explain why they differ.
- When is it valid to take logarithms of the waiting-tail target and rearrange it into the stated rate inequality?