Stationary Departure-Queue Distribution by Generating Functions

From Departures to a Stationary Generating Function

In an M/G/1 queue, service times need not be exponential, so the number of customers left behind at a departure is not generally described by the geometric distribution familiar from M/M/1. A useful way to find its stationary law is to observe the queue only at departure epochs. The resulting recursion reduces the stationary distribution to a probability generating function for the number of arrivals during one service.

Consider a single-server queue with an unlimited waiting room, Poisson arrivals of rate $\lambda>0$, and independent, identically distributed service times $S_1,S_2,\ldots$, independent of the arrival process. Assume $0<S<\infty$ almost surely, $0<\mathbb{E}S<\infty$, and $\rho=\lambda\mathbb{E}S<1$. On a probability space $(\Omega,\mathcal{F},\mathbb{P})$, let $X_n$ be the number of customers left in the system immediately after the $n$th departure; its state space is $\mathbb{Z}_{\ge0}$, with discrete time $n\ge0$. Its natural filtration is $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$.

Definition: Let $A_{n+1}$ be the number of arrivals during the service that ends at departure $n+1$. The embedded recursion is $X_{n+1}=(X_n-1)^+ + A_{n+1}$, where $x^+=\max(x,0)$. The variables $A_{n+1}$ have the common distribution of $A$, the arrivals during a generic service, and are independent of $X_n$. Write $\alpha_k=\mathbb{P}(A=k)$, $a(z)=\mathbb{E}[z^A]=\sum_{k\ge0}\alpha_k z^k$, and $\Pi(z)=\mathbb{E}[z^X]=\sum_{k\ge0}\pi_k z^k$ when $X$ has the stationary distribution $(\pi_k)_{k\ge0}$.

The positive-part term handles both cases in the recursion. If the queue is nonempty after a departure, one of the customers already waiting begins service, leaving $X_n-1$ before arrivals during that service are counted. If the queue is empty, the next customer arrives after an idle period and begins service; the number left by the next departure is just the arrivals during that service, as the recursion specifies.

Conditional on $S=s$, the arrival count during service is Poisson with mean $\lambda s$. Consequently, for $0\le z\le1$,

a(z)=\mathbb{E}\!\left[e^{-\lambda S(1-z)}\right], \qquad a(1)=1, \qquad a'(1)=\mathbb{E}[A]=\lambda\mathbb{E}S=\rho.

Under these assumptions and $\rho<1$, the M/G/1 embedded chain is positive recurrent; the stability result for the embedded chain gives a stationary distribution. Since $S>0$ almost surely and $\lambda>0$, every $\alpha_k$ is positive, so the chain is irreducible. The derivation below identifies its stationary probability generating function.

The Stationary Generating-Function Formula

Theorem: Under the queueing assumptions above with $\rho<1$, the stationary post-departure queue-length generating function is, for $0\le z<1$, $$ \Pi(z)=\frac{(1-\rho)a(z)(1-z)}{a(z)-z}. $$ In particular, the stationary probability of an empty system immediately after departure is $\pi_0=1-\rho$.

Proof. Let $X$ have the stationary distribution and let $A$ be an independent arrivals-during-service count. Stationarity and the embedded recursion give $X$ the same distribution as $(X-1)^++A$. For $0<z\le1$, independence therefore gives $\Pi(z)=a(z)\mathbb{E}[z^{(X-1)^+}]$. The term for $X=0$ contributes $\pi_0$; for $X\ge1$, $z^{(X-1)^+}=z^{X-1}$. Thus \[ \mathbb{E}[z^{(X-1)^+}] =\pi_0+\sum_{k\ge1}\pi_k z^{k-1} =\frac{\Pi(z)+(z-1)\pi_0}{z}. \] Substitution and rearrangement yield \[ (z-a(z))\Pi(z)=\pi_0a(z)(z-1). \] For $z<1$, $a(z)>z$: convexity of the probability generating function gives $a(z)\ge 1+\rho(z-1)>z$, where the last inequality follows from $\rho<1$. Hence the denominator is nonzero, and the identity gives \[ \Pi(z)=\frac{\pi_0a(z)(1-z)}{a(z)-z}. \] As $z$ increases to $1$, $\Pi(z)$ tends to $1$, since the stationary probabilities sum to $1$. Also $a(1)=1$ and $a'(1)=\rho$, so \[ \lim_{z\uparrow1}\frac{a(z)(1-z)}{a(z)-z} =\frac{1}{1-\rho}. \] Taking the limit in the formula shows $1=\pi_0/(1-\rho)$, hence $\pi_0=1-\rho$. Substitution proves the stated expression. $\square$

This formula depends on the post-departure convention: the queue length is measured after the customer in service has left. It also separates the service-time model from the stationary calculation. First find $a(z)$, the generating function of arrivals during one service; then substitute it into the formula.

Extracting Stationary Probabilities

The formula can be used directly when it simplifies, or its coefficients can be found recursively. Matching coefficients in the identity $(z-a(z))\Pi(z)=\pi_0a(z)(z-1)$ gives, for $n\ge1$,

Coefficient recurrence: If $\alpha_0>0$, then $$ \alpha_0\pi_n = \pi_{n-1} -\sum_{k=1}^{n-1}\alpha_k\pi_{n-k} -\pi_0\alpha_{n-1}, \qquad n\ge1. $$

Proof. The coefficient of $z^n$ in $z\Pi(z)$ is $\pi_{n-1}$. The coefficient in $a(z)\Pi(z)$ is $\sum_{k=0}^{n}\alpha_k\pi_{n-k}$. On the right side, the coefficient in $\pi_0a(z)(z-1)$ is $\pi_0(\alpha_{n-1}-\alpha_n)$, where $\alpha_{-1}=0$. Equating coefficients and moving terms gives \[ \alpha_0\pi_n =\pi_{n-1}-\sum_{k=1}^{n}\alpha_k\pi_{n-k} -\pi_0\alpha_{n-1}+\pi_0\alpha_n. \] The $k=n$ term in the sum is $\alpha_n\pi_0$, which cancels $+\pi_0\alpha_n$, leaving the displayed recurrence. Since $\alpha_0>0$, it determines each $\pi_n$ from earlier probabilities. $\square$

Worked Example: Exponential Service

Take arrival rate $\lambda=1$ and exponential service rate $\mu=2$. The traffic intensity is $\rho=\lambda/\mu=1/2<1$. Conditional on an exponential service time, the count $A$ has probabilities $\alpha_k=\frac{2}{3}(\frac{1}{3})^k$, for $k\ge0$. These sum to $\frac{2}{3}\sum_{k\ge0}(1/3)^k=1$, so they form a probability distribution. The transition row from any state $i\ge1$ assigns probability $\alpha_k$ to state $i-1+k$; its row sum is $\sum_{k\ge0}\alpha_k=1$. From state $0$, the row assigns probability $\alpha_k$ to state $k$, with the same row sum.

The arrivals-during-service generating function is $a(z)=\frac{2}{3-z}$. Substitution into the stationary formula gives $\Pi(z)=\frac{(1/2)(2/(3-z))(1-z)}{2/(3-z)-z}$. Since $2-z(3-z)=(1-z)(2-z)$, this simplifies to $\Pi(z)=\frac{1}{2-z}=\frac{1/2}{1-z/2}$. Thus $\pi_k=\frac12(\frac12)^k$ for every $k\ge0$.

Check: The probabilities sum to $\frac12\sum_{k\ge0}(1/2)^k=1$, and $\pi_0=1/2=1-\rho$. The coefficient recurrence also gives $\pi_1=\pi_0(1-\alpha_0)/\alpha_0$. Here $\alpha_0=2/3$, so $\pi_1=(1/2)(1/3)/(2/3)=1/4$, which agrees with the generating function.

Worked Example: Deterministic Service

Let every service last $s=2$ time units and set $\lambda=1/4$. Then $\rho=\lambda s=1/2$. The arrivals during service have a Poisson distribution with mean $\lambda s=1/2$, so $\alpha_k=e^{-1/2}(1/2)^k/k!$. These probabilities sum to $e^{-1/2}e^{1/2}=1$; every transition row of the embedded chain sums to this same total, whether the current state is zero or positive.

Set $q=e^{-1/2}$. Then $\alpha_0=q$, $\alpha_1=q/2$, and $\alpha_2=q/8$, while $\pi_0=1-\rho=1/2$. The recurrence at $n=1$ gives \[ \pi_1=\frac{\pi_0(1-\alpha_0)}{\alpha_0} =\frac{1-q}{2q}. \] At $n=2$, it gives \[ \pi_2=\frac{\pi_1(1-\alpha_1)-\pi_0\alpha_1}{\alpha_0} =\frac{\frac{1-q}{2q}(1-\frac q2)-\frac q4}{q}. \] These are exact probabilities; no approximation to the exponential terms is needed.

Check: For $n=1$, the coefficient equation is $\pi_0-\alpha_0\pi_1-\alpha_1\pi_0=\pi_0(\alpha_0-\alpha_1)$. Substituting $\pi_1=\pi_0(1-q)/q$, $\alpha_0=q$, and $\alpha_1=q/2$ gives $ \pi_0-q\pi_1-(q/2)\pi_0=\pi_0(q/2)$ on both sides. The value of $\pi_2$ was obtained from the $n=2$ recurrence itself, so it also satisfies that coefficient equation by construction.

Worked Example: A Two-Point Service-Time Distribution

Suppose $S=1$ or $S=2$, each with probability $1/2$, and let $\lambda=1/4$. The mean service time is $3/2$, so $\rho=3/8$ and $\pi_0=5/8$. Conditional on either service time, arrivals are Poisson. Averaging those two conditional distributions gives \[ \alpha_0=\frac{e^{-1/4}+e^{-1/2}}{2}, \qquad \alpha_1=\frac{e^{-1/4}}{8}+\frac{e^{-1/2}}{4}, \qquad \alpha_2=\frac{e^{-1/4}}{64}+\frac{e^{-1/2}}{16}. \] The full sequence is a probability distribution because each conditional Poisson distribution sums to $1$, and their equal-weight mixture therefore sums to $1$. As in the preceding examples, every transition row uses this distribution with its entries shifted according to the current queue length, so each row sums to $1$.

The first two nonempty probabilities follow from the recurrence: \[ \pi_1=\frac{5}{8}\frac{1-\alpha_0}{\alpha_0}, \qquad \pi_2=\frac{\pi_1(1-\alpha_1)-\frac58\alpha_1}{\alpha_0}. \] These exact expressions show how the service-time mixture affects the coefficients through the arrival-count probabilities $\alpha_k$, rather than through a geometric form imposed in advance.

Check: The $n=1$ recurrence requires $\alpha_0\pi_1=\pi_0(1-\alpha_0)$, which holds after substituting the displayed value of $\pi_1$. The $n=2$ recurrence requires $\alpha_0\pi_2=\pi_1(1-\alpha_1)-\pi_0\alpha_1$, which is exactly the displayed expression after multiplication by $\alpha_0$. The complete generating function, not a partial sum of these first coefficients, ensures $\sum_{k\ge0}\pi_k=1$.

Boundary States and a Common Error

A frequent mistake is to use $\mathbb{E}[z^{(X-1)^+}]=\Pi(z)/z$. That expression treats every state as if a customer were already waiting after the departure. At $X=0$, however, the next service begins only after a new arrival; the exponent contributed by the current post-departure queue is zero, not $-1$. The missing boundary correction is $\pi_0(1-1/z)$, so the correct factor is $[\Pi(z)+(z-1)\pi_0]/z$.

For a concrete check, in the exponential-service example the incorrect factor would imply $\Pi(z)=a(z)\Pi(z)/z$. Since $\Pi(z)>0$, this would require $z=a(z)=2/(3-z)$, or $(1-z)(2-z)=0$. That equality fails for $0<z<1$, contradicting the stationary recursion. Including the empty-state term instead gives the valid generating function $\Pi(z)=1/(2-z)$.

The generating-function method matters because it gives the whole stationary post-departure distribution without solving infinitely many balance equations separately. It also makes the model dependence explicit: service times enter through $a(z)=\mathbb{E}[e^{-\lambda S(1-z)}]$, while the correction for an empty system is determined by $1-\rho$. The departure-epoch distribution is tied to this precise observation convention; it should not be silently identified with a queue length measured at arrival epochs.

Check Your Understanding

Use the recursion and generating-function identity to answer the following questions.

For a stationary post-departure queue length $X$, why is $\mathbb{E}[z^{(X-1)^+}]$ not equal to $\Pi(z)/z$? Write the correct expression.
If $\rho=1/4$, what is the stationary probability that the system is empty immediately after a departure?
For exponential service with $\lambda=1$ and $\mu=3$, find $a(z)$ and simplify the stationary generating function.
State the coefficient recurrence for $\pi_n$ in terms of $\alpha_k$, $\pi_0$, and earlier coefficients.
For deterministic service with $\lambda s=1/2$, write $\alpha_0,\alpha_1,\alpha_2$ and use the recurrence to express $\pi_1$ exactly.

Stationary Departure-Queue Distribution by Generating Functions

What You'll Learn