The Distribution of Customers Waiting in Queue

From Number in System to Number Waiting

In an M/M/1 queue, the number of customers in the system and the number waiting in line are not the same quantity. The system count includes a customer receiving service; the waiting count does not. This difference matters especially at zero: there is no one-to-one correspondence between a system count of zero or one and a waiting count of zero. Both system states produce an empty waiting line.

Consider an M/M/1 queue on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with a Poisson arrival process of rate $\lambda>0$, independent exponential service times of rate $\mu>0$, one server, and an unlimited waiting area. Let $X_t\in S=\{0,1,2,\ldots\}$ be the number of customers in the system at time $t\ge0$, and let $(\mathcal{F}_t)_{t\ge0}$ be the filtration generated by the queue history up to time $t$. Define the traffic intensity by $\rho=\lambda/\mu$. We assume $\rho<1$, the condition under which this queue has a stationary probability distribution.

The earlier result on stationary probabilities for the number in system gives, under these assumptions, the stationary law $\mathbb{P}(X_t=n)=\pi_n=(1-\rho)\rho^n$ for $n\ge0$. This is a probability distribution because $0<\rho<1$ and $\sum_{n=0}^{\infty}(1-\rho)\rho^n=1$. We use this established system-count law to derive the distribution of the number waiting; we do not need to analyze arrival observations or waiting times.

Definition: The number waiting at time $t$, excluding any customer in service, is $W_t=(X_t-1)^+=\max\{X_t-1,0\}$. Thus $W_t=0$ when $X_t=0$ or $X_t=1$, and $W_t=k$ exactly when $X_t=k+1$ for each integer $k\ge1$.

In stationarity, write $W$ for a random variable with the stationary distribution of $W_t$. The zero probability must combine two disjoint possibilities: the system is empty, or exactly one customer is present and is receiving service. For a positive waiting count $k$, there must be $k$ customers waiting and one more in service, so the system count is $k+1$.

The Stationary Distribution of the Waiting Count

Theorem: For an M/M/1 queue with $\lambda>0$, $\mu>0$, and $\rho=\lambda/\mu<1$, the stationary number $W$ of customers waiting, excluding any customer in service, has distribution $$ \mathbb{P}(W=0)=1-\rho^2,\qquad \mathbb{P}(W=k)=(1-\rho)\rho^{k+1},\quad k\ge1. $$ In particular, the probability of a nonempty waiting line is $\mathbb{P}(W\ge1)=\rho^2$.

Proof. The map $g(n)=(n-1)^+$ takes the system count $X_t$ to the waiting count $W_t$. Since $g(0)=g(1)=0$, the event $W=0$ is the disjoint union of $X=0$ and $X=1$. Therefore $$ \mathbb{P}(W=0)=\pi_0+\pi_1=(1-\rho)+(1-\rho)\rho=(1-\rho)(1+\rho)=1-\rho^2. $$ For any integer $k\ge1$, the event $W=k$ is exactly the event $X=k+1$, so $$ \mathbb{P}(W=k)=\pi_{k+1}=(1-\rho)\rho^{k+1}. $$ The events $W=0,W=1,\ldots$ partition the possible values of $W$. Their probabilities sum to $$ 1-\rho^2+\sum_{k=1}^{\infty}(1-\rho)\rho^{k+1} =1-\rho^2+(1-\rho)\frac{\rho^2}{1-\rho} =1. $$ Finally, summing the positive-count probabilities gives $\mathbb{P}(W\ge1)=\rho^2$. Because $W_t=g(X_t)$ is a fixed function of the system count, applying $g$ at each time to a stationary process preserves stationarity: the joint distribution at any collection of times remains unchanged by a common time shift, and applying the same function to each coordinate preserves that equality. Thus these probabilities are the stationary distribution of the waiting-count process. $\square$

The atom at zero is larger than the probability that the whole system is empty. In fact, $\mathbb{P}(W=0)=\mathbb{P}(X=0)+\mathbb{P}(X=1)$. The first term describes an idle server; the second describes a busy server with nobody waiting. The positive probabilities start at $\pi_2$, not at $\pi_1$, because a queue with one person in line also has one person in service.

Worked Example: Arrival Rate Half the Service Rate

Suppose $\lambda=2$ and $\mu=4$, in the same time units. Then $\rho=\lambda/\mu=2/4=1/2$, which satisfies $0<\rho<1$. Find the probability of no one waiting and the probabilities of one and two customers waiting.

The stationary system probabilities needed are $\pi_0=1-\rho=1/2$, $\pi_1=(1-\rho)\rho=(1/2)(1/2)=1/4$, $\pi_2=(1-\rho)\rho^2=(1/2)(1/4)=1/8$, and $\pi_3=(1-\rho)\rho^3=(1/2)(1/8)=1/16$. Hence $$ \mathbb{P}(W=0)=\pi_0+\pi_1=\frac12+\frac14=\frac34,\quad \mathbb{P}(W=1)=\pi_2=\frac18,\quad \mathbb{P}(W=2)=\pi_3=\frac1{16}. $$ The remaining positive waiting probabilities sum to $$ \sum_{k=3}^{\infty}\mathbb{P}(W=k) =\frac12\sum_{k=3}^{\infty}\left(\frac12\right)^{k+1} =\frac12\cdot\frac{(1/2)^4}{1-1/2} =\frac1{16}. $$ Check: $\frac34+\frac18+\frac1{16}+\frac1{16}=1$. Also, $\mathbb{P}(W\ge1)=1/8+1/16+1/16=1/4=(1/2)^2=\rho^2$.

Tail Probabilities and the Nonempty Queue

The same state-count correspondence gives useful tail probabilities without summing every individual mass. For an integer $k\ge1$, having at least $k$ people waiting requires at least $k+1$ in the system. The geometric system-count law therefore gives $$ \mathbb{P}(W\ge k)=\mathbb{P}(X\ge k+1) =\sum_{n=k+1}^{\infty}(1-\rho)\rho^n =\rho^{k+1}. $$ The final equality follows by summing the geometric series: $\sum_{n=k+1}^{\infty}\rho^n=\rho^{k+1}/(1-\rho)$. In particular, setting $k=1$ recovers $\mathbb{P}(W\ge1)=\rho^2$. The event $W\ge0$, by contrast, has probability $1$; the displayed tail formula is stated for $k\ge1$.

Result: Conditional on there being at least one customer waiting, the number waiting has probabilities $$ \mathbb{P}(W=k\mid W\ge1)=(1-\rho)\rho^{k-1},\quad k\ge1. $$ This conditional distribution is geometric on the positive integers. The conditioning event has positive probability $\rho^2>0$ under the standing assumption $\lambda>0$.

Proof. For each $k\ge1$, the definition of conditional probability applies because $\mathbb{P}(W\ge1)=\rho^2>0$. Using the stationary mass and the theorem, $$ \mathbb{P}(W=k\mid W\ge1) =\frac{\mathbb{P}(W=k)}{\mathbb{P}(W\ge1)} =\frac{(1-\rho)\rho^{k+1}}{\rho^2} =(1-\rho)\rho^{k-1}. $$ These conditional probabilities sum to one, since $$ \sum_{k=1}^{\infty}(1-\rho)\rho^{k-1} =(1-\rho)\frac{1}{1-\rho}=1. $$ Thus the formula gives the full conditional distribution. $\square$

Worked Example: A Nonempty Queue at Traffic Intensity Two-Thirds

Suppose $\lambda=4$ and $\mu=6$. Then $\rho=4/6=2/3<1$. Compute the probability of an empty waiting line, the probability of exactly two waiting, and the conditional probability of exactly two waiting given that someone is waiting.

The atom at zero is $$ \mathbb{P}(W=0)=1-\left(\frac23\right)^2=1-\frac49=\frac59. $$ Exactly two customers waiting means three customers in the system, so $$ \mathbb{P}(W=2)=(1-\rho)\rho^3 =\frac13\left(\frac23\right)^3 =\frac13\cdot\frac8{27} =\frac8{81}. $$ The probability of at least one waiting is $$ \mathbb{P}(W\ge1)=\rho^2=\left(\frac23\right)^2=\frac49. $$ Consequently, $$ \mathbb{P}(W=2\mid W\ge1) =\frac{8/81}{4/9} =\frac8{81}\cdot\frac94 =\frac29. $$ Check: The conditional formula gives $(1-\rho)\rho^{2-1}=(1/3)(2/3)=2/9$, agreeing with the ratio. The positive waiting probabilities sum to $(1-\rho)\sum_{k=1}^{\infty}\rho^{k+1}=\rho^2=4/9$, and adding the zero mass $5/9$ gives $1$.

Worked Example: A Heavily Utilized but Stable Queue

Suppose $\lambda=9$ and $\mu=12$, so $\rho=9/12=3/4<1$. Find the probability that nobody is waiting, and verify the conditional probability of exactly one waiting when the line is nonempty.

First, the stationary probability of an empty waiting line is $$ \mathbb{P}(W=0)=1-\left(\frac34\right)^2=1-\frac9{16}=\frac7{16}. $$ The probability of at least one waiting is $\mathbb{P}(W\ge1)=(3/4)^2=9/16$. Exactly one waiting requires two in the system, so $$ \mathbb{P}(W=1)=(1-\rho)\rho^2 =\frac14\left(\frac34\right)^2 =\frac14\cdot\frac9{16} =\frac9{64}. $$ Therefore $$ \mathbb{P}(W=1\mid W\ge1) =\frac{9/64}{9/16} =\frac{9}{64}\cdot\frac{16}{9} =\frac14. $$ Check: The conditional formula at $k=1$ gives $(1-\rho)\rho^0=(1/4)\cdot1=1/4$. The nonempty probability $9/16$ equals $1-7/16$, as required.

Interpretation, Limits, and a Common Mistake

The waiting-count distribution is stationary because it is obtained by applying a fixed function to the stationary number in system. It describes the queue at a stationary time. It does not, by itself, assert what an arriving customer observes; that is a different question. In particular, no arrival-observation result is needed for this derivation.

The stability condition is also essential. When $\rho\ge1$, the infinite-capacity M/M/1 queue has no stationary probability distribution for the number in system, so the stationary waiting-count distribution derived here is not available. The formula should not be extended into that regime by substitution. Under the assumptions $0<\lambda<\mu$, all displayed probabilities are nonnegative and the geometric series used in the proof converges.

Common mistake: shifting the zero probability incorrectly. One might incorrectly identify “no one waiting” with “no one in the system” and set $\mathbb{P}(W=0)=\pi_0=1-\rho$. For the rates $\lambda=2,\mu=4$, that wrong calculation gives $1-1/2=1/2$. But $W=0$ occurs for both $X=0$ and $X=1$, so the correct calculation is $\pi_0+\pi_1=1/2+1/4=3/4$. The probabilities for positive waiting counts also begin at $\pi_2$, not $\pi_1$.

Keep the state mapping in view when changing between queue quantities: zero waiting combines two system states, while every positive waiting count corresponds to exactly one system count, one larger. That mapping determines both the extra mass at zero and the one-place shift in the positive probabilities.

Check Your Understanding

Use the stationary M/M/1 assumptions and verify each answer from the system-count interpretation.

For $\rho=1/3$, calculate $\mathbb{P}(W=0)$ and $\mathbb{P}(W=1)$. Which system-count states contribute to each?
For general $0<\rho<1$, derive $\mathbb{P}(W\ge2)$ from the event involving the number in system.
For $\rho=1/2$, calculate $\mathbb{P}(W=3\mid W\ge1)$ and verify it using both the conditional formula and a ratio of probabilities.
Why is it incorrect to set the probability of an empty waiting line equal to $\pi_0$?
What fails in this derivation when $\rho\ge1$?

The Distribution of Customers Waiting in Queue

What You'll Learn