The M/G/1 Waiting-Time Transform

From Service Times to Waiting Times

In an M/G/1 queue, arrivals form a Poisson process, there is one server, and service times may have any nonnegative distribution. Under first-come, first-served (FCFS) service, the waiting time of an arriving customer is the amount of work already present when that customer arrives. The service-time distribution therefore influences waiting not only through its mean, but also through its variability. A Laplace transform gives a compact way to describe that dependence and, when possible, to recover probabilities and moments.

Let arrivals occur at rate $\lambda>0$, and let $B$ be a nonnegative service time, independent across customers and independent of the Poisson arrival process. Write $b_k=\mathbb{E}[B^k]$ when that moment is finite, and define the service-time Laplace transform by $\beta(s)=\mathbb{E}[e^{-sB}]$ for $s\ge0$. Assume $0<b_1<\infty$ and traffic intensity $\rho=\lambda b_1<1$. The earlier M/G/1 stability result gives a stationary workload under these assumptions. Let $W$ denote the stationary FCFS waiting time of an arrival, excluding that customer's own service, and set $\widetilde W(s)=\mathbb{E}[e^{-sW}]$.

Definition: The Laplace transform of a nonnegative random variable $Y$ is $\mathbb{E}[e^{-sY}]$, $s\ge0$. It equals $1$ at $s=0$. In a stable M/G/1 queue, $W$ is the workload seen by a stationary Poisson arrival immediately before it joins the queue.

Deriving the Waiting-Time Transform

Consider the workload process $V_t$, the total unfinished service in the system at time $t$. Between arrivals it decreases at rate one while positive and stays at zero when empty. At each arrival it jumps upward by an independent service time distributed as $B$. Let $V$ have the stationary workload distribution, and write $L(s)=\mathbb{E}[e^{-sV}]$ and $p_0=\mathbb{P}(V=0)$.

For $s>0$, apply stationary balance to $f(v)=e^{-sv}$. When $v>0$, the deterministic decrease in workload changes $f$ at rate $s e^{-sv}$; at $v=0$, that rate is zero. An arrival changes $f(v)$ by $e^{-s(v+B)}-e^{-sv}$, whose conditional mean is $e^{-sv}(\beta(s)-1)$. Thus stationary expected change per unit time is zero and gives

0=s\bigl(L(s)-p_0\bigr)+\lambda\bigl(\beta(s)-1\bigr)L(s).

To justify this balance, over a time interval the change in $f(V_t)$ is the integral of its deterministic rate of change plus the sum of its changes at arrivals. The function $f$ and its derivative are bounded for $s>0$. Taking expectations in stationarity makes the expected total change zero, and the expected sum of arrival changes is the arrival rate times the expected change at one arrival. This is the Poisson arrival compensation identity; equivalently, the stationary Poisson arrivals see the time-average workload distribution (PASTA).

Rearranging gives $L(s)=s p_0/[s-\lambda(1-\beta(s))]$. Since $V$ is finite almost surely in stationarity, bounded convergence gives $L(s)\to1$ as $s\downarrow0$. Also, $(1-\beta(s))/s=\mathbb{E}[(1-e^{-sB})/s]\to b_1$, by monotone convergence. Divide numerator and denominator in the expression for $L(s)$ by $s$ and take the limit: $1=p_0/(1-\lambda b_1)$. Hence $p_0=1-\rho$.

Theorem (Pollaczek–Khinchine waiting-time transform): For a stable M/G/1 queue with $\lambda>0$, $0<b_1<\infty$, and $\rho=\lambda b_1<1$, the stationary FCFS waiting-time transform is $$ \widetilde W(s)=\frac{(1-\rho)s}{s-\lambda+\lambda\beta(s)},\qquad s>0, $$ with $\widetilde W(0)=1$. The denominator is positive for $s>0$: $1-\beta(s)\le s b_1$, so $s-\lambda(1-\beta(s))\ge s(1-\rho)>0$. PASTA identifies $W$ with the stationary workload seen immediately before an arrival.

The formula is for waiting time, not total time in the system. FCFS means a customer's own service does not begin until the workload ahead has cleared, so that workload is exactly the customer's wait. The customer's own service would need to be included separately to obtain total time in the system.

Zero-Wait Probability and Moments

The transform also gives a probability directly. As $s\to\infty$, $e^{-sW}$ converges to $\mathbf{1}_{\{W=0\}}$ and is bounded by one, so bounded convergence yields $\lim_{s\to\infty}\widetilde W(s)=\mathbb{P}(W=0)$. Since $\beta(s)\to\mathbb{P}(B=0)$, the transform formula gives

\mathbb{P}(W=0)=1-\rho.

This includes service distributions with mass at zero: the limit still holds because $\beta(s)$ remains bounded as $s\to\infty$, while the denominator divided by $s$ tends to one.

For moments, it is important not to assume a Taylor expansion of $\widetilde W$ involving moments that have not yet been proved finite. Instead, use limits of nonnegative functions. For the mean, $(1-e^{-sW})/s$ increases to $W$ as $s\downarrow0$, so monotone convergence gives $\mathbb{E}[W]=\lim_{s\downarrow0}(1-\widetilde W(s))/s$, allowing the limit to be infinite. If $b_2<\infty$, expanding the service transform through its quadratic term in the waiting-time formula gives a finite limit and therefore establishes the mean:

\mathbb{E}[W]=\frac{\lambda b_2}{2(1-\rho)}.

More explicitly, finite $b_2$ gives $\beta(s)=1-b_1s+\tfrac12 b_2s^2+o(s^2)$, so the denominator of $\widetilde W(s)$ is $(1-\rho)s+\tfrac12\lambda b_2s^2+o(s^2)$. Substitution shows that $(1-\widetilde W(s))/s\to\lambda b_2/[2(1-\rho)]$, proving the formula without presuming a finite waiting-time mean.

Once the mean is established, if $b_3<\infty$, use the second-moment limit. For each $x\ge0$, $$ \frac{2(e^{-sx}-1+sx)}{s^2} =2x^2\int_0^1(1-u)e^{-s xu}\,du. $$ As $s\downarrow0$, the right side increases to $x^2$. Applying monotone convergence with $x=W$ gives $\mathbb{E}[W^2]=\lim_{s\downarrow0}2(\widetilde W(s)-1+s\mathbb{E}[W])/s^2$, again allowing an infinite limit initially. Expanding $\beta(s)$ through the cubic term, now justified by $b_3<\infty$, yields

\mathbb{E}[W^2] =\frac{\lambda b_3}{3(1-\rho)} +\frac{\lambda^2 b_2^2}{2(1-\rho)^2}.

Indeed, the denominator is $(1-\rho)s+\tfrac12\lambda b_2s^2-\tfrac16\lambda b_3s^3+o(s^3)$. Dividing by $(1-\rho)s$ and expanding the reciprocal gives $\widetilde W(s)=1-as+(a^2+c)s^2+o(s^2)$, where $a=\lambda b_2/[2(1-\rho)]$ and $c=\lambda b_3/[6(1-\rho)]$. The second-moment limit is $2(a^2+c)$, which is the displayed expression. Here the expansion is used to evaluate a limit; monotone convergence is what validates that the limit equals the moment.

Worked Applications

Worked Example: Exponential Service and a Waiting-Time Tail

Let service times be exponential with rate $1$, and let arrivals occur at rate $\lambda=\tfrac12$. Find the waiting-time transform, the probability of a positive wait, the probability that the wait exceeds $2$, and the first two moments.

The service transform is $\beta(s)=1/(1+s)$, and $b_1=1$, $b_2=2$, $b_3=6$. Thus $\rho=\lambda b_1=\tfrac12$, so the stability condition holds. Substitution in the transform gives

\widetilde W(s)=\frac{\tfrac12s}{s-\tfrac12+\tfrac{1}{2(1+s)}} =\frac{\tfrac12(s+1)}{s+\tfrac12} =\frac12+\frac{\tfrac14}{s+\tfrac12}.

This is a mixture: probability $\tfrac12$ is concentrated at zero, and with the remaining probability $\tfrac12$ the wait is exponential with rate $\tfrac12$. Therefore $\mathbb{P}(W>0)=\tfrac12$ and $\mathbb{P}(W>2)=\tfrac12 e^{-1}$. The moments from the formulas are $\mathbb{E}[W]=(\tfrac12\cdot2)/(2\cdot\tfrac12)=1$ and $\mathbb{E}[W^2]=(\tfrac12\cdot6)/(3\cdot\tfrac12)+(\tfrac14\cdot4)/(2\cdot\tfrac14)=2+2=4$.

Check: The mixture transform is $\tfrac12+\tfrac12\cdot\frac{1/2}{s+1/2}=\tfrac12+\tfrac{1/4}{s+1/2}$, exactly the transform above. Its mean is $\tfrac12\cdot0+\tfrac12\cdot2=1$, and its second moment is $\tfrac12\cdot0+\tfrac12\cdot(2/(1/2)^2)=4$.

Worked Example: Deterministic Service

Suppose every service takes exactly one time unit and $\lambda=\tfrac12$. Find the waiting-time transform, mean, and second moment, and verify the moments from the transform near zero.

Here $\beta(s)=e^{-s}$, $b_1=b_2=b_3=1$, and $\rho=\tfrac12$. The transform is $\widetilde W(s)=\tfrac12s/[s-\tfrac12+\tfrac12e^{-s}]$. The moment formulas give $\mathbb{E}[W]=(\tfrac12)/(2\cdot\tfrac12)=\tfrac12$ and $\mathbb{E}[W^2]=(\tfrac12)/(3\cdot\tfrac12)+(\tfrac14)/(2\cdot\tfrac14)=\tfrac13+\tfrac12=\tfrac56$.

For an independent transform check, $e^{-s}=1-s+\tfrac12s^2-\tfrac16s^3+o(s^3)$, so the denominator is $\tfrac12s+\tfrac14s^2-\tfrac1{12}s^3+o(s^3)$. Dividing numerator and denominator by $\tfrac12s$ gives $\widetilde W(s)=1-\tfrac12s+\tfrac5{12}s^2+o(s^2)$. The linear and quadratic coefficients correspond to mean $\tfrac12$ and second moment $2\cdot\tfrac5{12}=\tfrac56$, agreeing with the formulas.

Check: The transform tends to $1$ as $s\downarrow0$, as a probability transform must. Also $1-\rho=\tfrac12$, so the zero-wait probability is $\tfrac12$.

Worked Example: Service That Is Zero or Two

Let $B=0$ or $B=2$, each with probability $\tfrac12$, and let $\lambda=\tfrac12$. Find the transform and the first two waiting-time moments.

The moments of service are $b_1=\tfrac12(0)+\tfrac12(2)=1$, $b_2=\tfrac12(0^2)+\tfrac12(2^2)=2$, and $b_3=\tfrac12(0^3)+\tfrac12(2^3)=4$. Thus $\rho=\tfrac12$, and $\beta(s)=\tfrac12+\tfrac12e^{-2s}$. Substitution gives

\widetilde W(s)=\frac{\tfrac12s}{s-\tfrac14+\tfrac14e^{-2s}}.

The mean is $\mathbb{E}[W]=(\tfrac12\cdot2)/(2\cdot\tfrac12)=1$. The second moment is $\mathbb{E}[W^2]=(\tfrac12\cdot4)/(3\cdot\tfrac12)+(\tfrac14\cdot4)/(2\cdot\tfrac14)=\tfrac43+2=\tfrac{10}{3}$. For example, at $s=1$, the transform equals $\tfrac12/(\tfrac34+\tfrac14e^{-2})=2/(3+e^{-2})$.

Check: Expanding $e^{-2s}=1-2s+2s^2+o(s^2)$, the denominator is $\tfrac12s+\tfrac12s^2+o(s^2)$. To verify the second moment, retain the cubic term $e^{-2s}=1-2s+2s^2-\tfrac43s^3+o(s^3)$; then the denominator is $\tfrac12s+\tfrac12s^2-\tfrac13s^3+o(s^3)$. The transform becomes $1-s+\tfrac53s^2+o(s^2)$, agreeing with mean $1$ and second moment $\tfrac{10}{3}$.

A Common Moment-Expansion Pitfall

A tempting but invalid argument is to write $\widetilde W(s)=1-s\mathbb{E}[W]+o(s)$ and compare coefficients to obtain the mean. That expansion presumes the very finiteness of $\mathbb{E}[W]$ that the calculation may be intended to prove. The corresponding quadratic expansion presumes a finite second moment. The correct argument uses the nonnegative transform limits above: monotone convergence first identifies the mean limit, and, once the mean is finite, identifies the second-moment limit. The service-transform expansion evaluates those limits; it does not by itself establish their interpretation as moments.

The transform formula is useful because it retains the full service distribution through $\beta(s)$, while its limits expose waiting-time quantities of interest. Its probability and moment conclusions require their stated conditions: the stability assumption $\rho<1$, a finite $b_2$ for the mean, and a finite $b_3$ for the second moment. In applied work, keeping these conditions explicit prevents a transform calculation from being mistaken for a moment-existence proof.

Check Your Understanding

For each question, state the assumptions you use and check any computed quantities against the transform or its defining limit.

For exponential service with rate $\mu$ and arrival rate $\lambda<\mu$, what is $\rho$, and what does the limit of the waiting-time transform as $s\to\infty$ represent?
For deterministic service $B=2$ and arrival rate $\lambda=\tfrac14$, compute $\rho$, $b_2$, and the mean waiting time.
Why does comparing a formal linear expansion of $\widetilde W(s)$ with $1-s\mathbb{E}[W]$ not establish that the mean is finite?
Which service-time moment condition is used to obtain the second waiting-time moment, and what monotone-convergence limit identifies that moment?
If $B=0$ with probability $\tfrac14$ and $B=1$ with probability $\tfrac34$, at what value does the waiting-time transform tend as $s\to\infty$ when $\lambda=\tfrac12$?