Deriving the Pollaczek-Khinchine Mean-Waiting-Time Formula

Waiting Time as Work Already in the System

In an M/G/1 queue, arrivals form a Poisson process, there is one server, and service times have a general distribution. Under first-come, first-served (FCFS) service, an arriving customer must wait for the work already ahead of them: the unfinished part of any service in progress, followed by the full service requirements of customers already waiting. This workload viewpoint turns the mean-waiting-time calculation into a balance between residual service and queued work.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let arrivals be a Poisson process of rate \(\lambda>0\), and let their independent, identically distributed service requirements be nonnegative random variables with common distribution \(F\), mean \(m_1=\mathbb{E}[S]\), and second moment \(m_2=\mathbb{E}[S^2]\). Assume \(0<m_1<\infty\) and \(m_2<\infty\). The traffic intensity is \(\rho=\lambda m_1\). The workload process \((V(t))_{t\ge0}\) takes values in \([0,\infty)\); it decreases at rate one when positive and jumps upward by an arriving customer’s service requirement. The queue is assumed to be in its stationary regime, with \(\rho<1\).

The stability condition \(\rho<1\) is essential: the server’s long-run service capacity must exceed the incoming mean work per unit time. The standard M/G/1 stability and Foster–Lyapunov results give a stationary workload regime and finite mean waiting time when \(\rho<1\) and \(m_2<\infty\). Those general existence and integrability results are not proved here. We derive the mean formula within that stationary regime. The central distinction is that residual service is present only when the server is busy, while a Poisson arrival samples the workload at an ordinary time.

Two Ingredients: Poisson Sampling and Residual Service

First, Poisson arrivals see the time-stationary workload distribution. In the statement below, the process observed just before time \(t\) depends only on arrivals and service history before \(t\), not on whether an arrival occurs at \(t\). Such a process is called predictable.

Proof. For a process that is constant on each interval of a deterministic partition and whose value on that interval is determined by information available at its left endpoint, independence of future Poisson increments gives the identity on each interval: the expected number of arrivals is \(\lambda\) times the interval length, independently of the value being sampled. Summing these identities proves the assertion for nonnegative simple predictable processes. Approximation by increasing simple predictable processes and monotone convergence extend it to every nonnegative predictable \(g(Y(t-))\). Stationarity makes \(\mathbb{E}[g(Y(t))]\) constant in \(t\), so integration over the interval gives \(\lambda T\,\mathbb{E}[g(Y(0))]\). \(\square\)

Next calculate the residual workload in service. Let \(R(t)\) be the remaining service requirement at time \(t\) if the server is busy, and zero if it is idle. Service starts occur at rate \(\lambda\) in stationarity: in a stable, loss-free single-server queue, each arrival is eventually served, so long-run service starts and arrivals have the same rate. A service requirement \(S=s\) contributes residual workload \(s-a\) at service age \(a\), for \(0\le a<s\). Consequently, the total residual-work contribution over that service is \(\int_0^s(s-a)\,da=s^2/2\).

Proof. The stationary service-start process has intensity \(\lambda\), and each service-start mark is an independent copy of \(S\). The first-moment counting identity for a stationary marked point process says that expected occupation at an arbitrary time is its event rate times the mean occupation contributed by one event. In this case, integrating over possible service ages gives \(\mathbb{E}[R(0)]=\lambda\mathbb{E}[\int_0^S(S-a)\,da]=\lambda\mathbb{E}[S^2/2]=\lambda m_2/2\). The server is busy for a fraction \(\rho=\lambda m_1\) of stationary time, since services start at rate \(\lambda\) and have mean duration \(m_1\). Dividing the unconditional residual mean by this busy probability gives \((\lambda m_2/2)/(\lambda m_1)=m_2/(2m_1)\). \(\square\)

The conditional and unconditional quantities answer different questions. The conditional residual is the mean remaining service given that a service is in progress. The unconditional residual workload includes the probability \(\rho\) that service is in progress, and is the quantity needed in the workload decomposition.

The Pollaczek–Khinchine Mean-Waiting-Time Formula

Proof. Let \(N_q(0)\) be the number of customers waiting at time \(0\), not counting any customer in service. Write \(V(0)\) for total workload and \(R(0)\) for residual workload in service. The workload is the residual service plus the full service requirements of the waiting customers. A waiting customer’s own service requirement is independent of the event that they are waiting: under FCFS, that event is determined before their service begins. Therefore, conditioning on which customers are waiting and summing their mean service requirements gives \(\mathbb{E}[V(0)]=\mathbb{E}[R(0)]+m_1\mathbb{E}[N_q(0)]\).

Poisson sampling applied to \(V(t-)\) shows that an arriving customer’s mean wait is \(\mathbb{E}[V(0)]\). Little’s law for the waiting line gives \(\mathbb{E}[N_q(0)]=\lambda\mathbb{E}[W_q]\). Substituting these two identities and the residual-work result yields \(\mathbb{E}[W_q]=\lambda m_2/2+\lambda m_1\mathbb{E}[W_q]\). Since \(\lambda m_1=\rho<1\), subtracting \(\rho\mathbb{E}[W_q]\) from both sides and dividing by \(1-\rho\) gives \(\mathbb{E}[W_q]=\lambda m_2/[2(1-\rho)]\), as required. \(\square\)

The derivation uses three separate facts: Poisson arrivals sample the time-stationary workload, residual service has mean \(\lambda m_2/2\) at an arbitrary time, and the expected work held by waiting customers is \(m_1\) times their expected number. The factor \(1/(1-\rho)\) appears when queued customers’ own service requirements are included: their mean total work is \(\rho\mathbb{E}[W_q]\), which adds to the residual service contribution.

Conditions, Interpretation, and a Common Error

The second moment matters because a service of length \(s\) contributes \(s^2/2\) units of residual-work area over its duration. Long services are therefore represented more heavily in the residual workload than short services. The formula concerns queueing wait only; the customer’s own service time is not included. If mean time in the system is wanted, add \(m_1\) to \(\mathbb{E}[W_q]\).

Common mistake: forgetting the busy probability. In the exponential example, the mean residual service conditional on being busy is \(m_2/(2m_1)=2/(2\cdot1)=1\). Using that conditional mean as though it were the residual workload at every time would give the incorrect equation \(\mathbb{E}[W_q]=1+\tfrac12\mathbb{E}[W_q]\), and hence the incorrect answer \(2\). The server is busy only a fraction \(\rho=\tfrac12\) of the time, so the unconditional residual contribution is \(\rho\cdot1=\tfrac12\), equivalently \(\lambda m_2/2=(\tfrac12\cdot2)/2=\tfrac12\). The correct equation is \(\mathbb{E}[W_q]=\tfrac12+\tfrac12\mathbb{E}[W_q]\), giving \(\mathbb{E}[W_q]=1\).

The formula requires \(\rho<1\) and a finite second service-time moment for the finite-mean result stated here. If \(\rho\ge1\), the stable stationary queueing regime used in the derivation is unavailable. If the second moment is infinite, the residual-work calculation is not finite, and the displayed finite-mean formula does not apply. These checks should come before substituting numbers.