The Waiting-Time Distribution Under FCFS

Queueing Delay Under FCFS

In an M/M/1 queue, some arrivals begin service immediately, while others wait for the customers ahead of them. The waiting time therefore has two parts to its distribution: a probability mass at zero and a continuous tail for positive waits. Under first-come, first-served (FCFS) service, both parts can be derived by conditioning on the number of customers already in the system when an arrival occurs.

Consider a queue on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(N(t)\) be the number of customers in the system at time \(t\), a continuous-time Markov chain with state space \(\{0,1,2,\ldots\}\). Arrivals form a Poisson process of rate \(\lambda\), service times are independent exponential random variables of rate \(\mu\), and the arrival process and service times are independent. There is one server, service is FCFS, and the queue is in stationarity. We assume \(0<\lambda<\mu\), and write \(\rho=\lambda/\mu\), so \(0<\rho<1\).

For a stationary arrival, let \(W_q\) denote the time from that arrival until its service begins. It does not include the arrival’s own service time. An arrival that finds the system empty has \(W_q=0\); one that finds at least one customer has a positive wait with probability one.

Thus a stationary arrival sees zero customers with probability \(1-\rho\), and sees \(n\geq1\) customers with probability \((1-\rho)\rho^n\). Conditional on seeing \(n\geq1\), FCFS means the arrival must wait for \(n\) service completions before its own service starts. The service currently in progress, if there is one, has an exponential remaining time of rate \(\mu\), by the memoryless property. The following \(n-1\) service times are also independent exponentials of rate \(\mu\). The wait is therefore a sum of \(n\) independent exponential random variables.

The Conditional Waiting-Time Calculation

Proof. For \(n=1\), the exponential tail is \(\mathbb{P}(S_1>t)=e^{-\mu t}\), which is the stated formula. For general \(n\), convolution gives the density \(f_n(u)=\mu^n u^{n-1}e^{-\mu u}/(n-1)!\) for \(u>0\). Indeed, this holds for \(n=1\); if it holds for \(n\), then for \(t>0\), convolution with one more exponential density gives \(f_{n+1}(t)=\int_0^t f_n(u)\mu e^{-\mu(t-u)}\,du =\mu^{n+1}e^{-\mu t}\int_0^t u^{n-1}/(n-1)!\,du =\mu^{n+1}t^n e^{-\mu t}/n!\). This proves the density formula by induction. Integrating this density from \(t\) to infinity and integrating by parts gives \(\mathbb{P}(S_n>t)=e^{-\mu t}(\mu t)^{n-1}/(n-1)!+\mathbb{P}(S_{n-1}>t)\) for \(n\geq2\). Starting with the \(n=1\) tail and applying this recurrence yields the stated finite sum. \(\square\)

The lemma applies to the conditional wait when the arrival sees \(n\) customers. In particular, for \(t\geq0\), the contribution to the tail from that queue length is its probability of occurring multiplied by the conditional probability that the sum of \(n\) service times exceeds \(t\). Summing those contributions produces the waiting-time distribution.

Proof. The arrival waits zero time exactly when it sees an empty system. By PASTA, that event has probability \(1-\rho\), proving the mass at zero. For \(t\geq0\), condition on the number \(n\geq1\) seen. The queue-length probabilities and the lemma give \(\mathbb{P}(W_q>t)=(1-\rho)\sum_{n=1}^{\infty}\rho^n e^{-\mu t}\sum_{k=0}^{n-1}(\mu t)^k/k!\). All terms are nonnegative, so the order of these sums may be interchanged. For each \(k\geq0\), the terms involving that \(k\) have \(n\geq k+1\), and \(\sum_{n=k+1}^{\infty}\rho^n=\rho^{k+1}/(1-\rho)\). Consequently, \(\mathbb{P}(W_q>t)=\rho e^{-\mu t}\sum_{k=0}^{\infty}(\rho\mu t)^k/k! =\rho e^{-\mu t}e^{\rho\mu t} =\rho e^{-(\mu-\lambda)t}\), because \(\rho\mu=\lambda\). This calculation includes \(t=0\): the strict tail there is \(\mathbb{P}(W_q>0)=\rho\), as required by the zero-wait mass. \(\square\)

The tail formula describes positive waits as well as the unconditional delay. Since \(\mathbb{P}(W_q>0)=\rho\), for \(t\geq0\) the conditional tail given that a wait occurs is \(\mathbb{P}(W_q>t\mid W_q>0)=e^{-(\mu-\lambda)t}\). Thus, conditional on waiting, the delay is exponential with rate \(\mu-\lambda\). Unconditionally, this exponential component has total probability \(\rho\), while the remaining probability \(1-\rho\) is concentrated at zero. Integrating the tail also gives \(\mathbb{E}[W_q]=\int_0^\infty\mathbb{P}(W_q>t)\,dt=\rho/(\mu-\lambda)\). This tail-integral identity applies because \(W_q\) is nonnegative.

Worked Calculations

Why the Atom Matters

A common mistake is to treat the waiting time as exponential for every arrival. For example, with \(\lambda=2\) and \(\mu=5\), writing \(\mathbb{P}(W_q>t)=e^{-3t}\) would give \(\mathbb{P}(W_q>0)=e^0=1\). That contradicts the fact that a stationary arrival sees an empty system with probability \(1-\rho=3/5\). The correction is the factor \(\rho=2/5\): the correct tail is \((2/5)e^{-3t}\). The exponential law describes the delay conditional on a positive wait; the factor \(\rho\) accounts for the chance that a wait occurs at all.

The service rate alone is also not the rate of the positive waiting-time tail. A customer may have several customers ahead, so its delay is a mixture of sums of service times. Summing over the stationary queue-length distribution changes the exponential rate to \(\mu-\lambda\), while leaving the probability of a positive wait as \(\rho\). The result depends on stationarity, Poisson arrivals independent of the queue state, exponential service, and FCFS service. If the queue is unstable, \(\rho<1\) fails and there is no stationary arrival distribution of the stated form. If \(\lambda=0\), there are no stationary arrivals to sample; the stationary queue is empty and a hypothetical customer arriving to that empty system waits zero.

This distribution concerns only time until service begins. The service duration of the arriving customer is not included. Keeping that distinction explicit prevents confusing queueing delay with total time in the system.