The Sojourn-Time Distribution in the System

From the Queue Seen on Arrival to Time in System

For a customer, time in system includes both any wait for service and the customer's own service. In an M/M/1 queue, these two parts are linked: the number of customers already present determines how many exponential service completions must occur before the arriving customer leaves. Averaging over the stationary number seen on arrival gives a particularly simple result—the total time in system has an exponential distribution.

Consider a probability space $(\Omega,\mathcal{F},\mathbb{P})$ supporting a single-server queue. Arrivals form a Poisson process of rate $\lambda>0$, service times are independent exponential random variables of rate $\mu>0$, and the arrival and service mechanisms are independent. The server works whenever the queue is nonempty, serves customers in first-come, first-served (FCFS) order, and does not interrupt a service already in progress. Let $X_t\in S=\{0,1,2,\ldots\}$ be the number of customers in the system at time $t\ge0$. Use the natural history $(\mathcal{F}_t)_{t\ge0}$ of arrivals and service completions when conditioning on the system's history. We assume $\lambda<\mu$, and consider the queue in its stationary regime.

Write $\rho=\lambda/\mu$, so $0<\rho<1$. The stationary distribution of the number in system is $\mathbb{P}(X_t=k)=(1-\rho)\rho^k$ for $k\ge0$. By PASTA, Poisson arrivals see this same distribution just before they arrive. If $N$ is that pre-arrival number, then $\mathbb{P}(N=k)=(1-\rho)\rho^k$. This use of PASTA requires Poisson arrivals and stationarity.

Definition: For a customer arriving in stationarity, the time in system $T$ is the elapsed time from that customer's arrival until its departure, including its wait in queue and its own service. Under FCFS, conditional on $N=k$, the customer must wait through the service of the $k$ customers already present and then receive its own service.

If $k\ge1$, one of those $k$ customers may be in service at the arrival instant. The exponential service assumption matters: conditional on the service being unfinished, its remaining duration is again exponential with rate $\mu$, independent of the past. The $k$ service completions ahead of the arriving customer, followed by the arriving customer's own service completion, therefore give $k+1$ independent exponential durations of rate $\mu$. For $k=0$, there is just the arriving customer's service duration.

The Conditional Distribution and Its Mixture

A sum of $k+1$ independent exponential random variables of rate $\mu$ has the Erlang density $\mu^{k+1}x^ke^{-\mu x}/k!$ for $x\ge0$. Its survival probability is

\mathbb{P}(T>t\mid N=k) =e^{-\mu t}\sum_{j=0}^{k}\frac{(\mu t)^j}{j!}, \qquad t\ge0.

Here and below, $T>t$ is the strict tail event. Since $T$ has a continuous distribution, there is no atom at any fixed $t\ge0$; in particular, $\mathbb{P}(T>0)=1$.

Proof. For $r=k+1$, convolution gives the density of the sum of $r$ independent rate-$\mu$ exponentials. For $r=1$ the density is $\mu e^{-\mu x}$. If the density for $r$ terms is $\mu^r x^{r-1}e^{-\mu x}/(r-1)!$, convolution with one more exponential gives, for $x\ge0$,

\int_0^x \frac{\mu^r u^{r-1}e^{-\mu u}}{(r-1)!}\, \mu e^{-\mu(x-u)}\,du =\frac{\mu^{r+1}x^re^{-\mu x}}{r!}.

Thus the stated density follows by induction. Its tail is the integral of that density from $t$ to infinity. For $k=0$, this integral is $e^{-\mu t}$, as claimed. For $k\ge1$, integration by parts gives the tail as $e^{-\mu t}(\mu t)^k/k!$ plus $k$ times the corresponding integral with power $k-1$, scaled by $1/k$. Repeating this identity down to power zero yields $e^{-\mu t}\sum_{j=0}^k(\mu t)^j/j!$. The density integrates to one by the same integration-by-parts recurrence at $t=0$, so this integral is indeed the survival probability. $\square$

Theorem (Stationary FCFS sojourn-time distribution): In a stationary M/M/1 queue with $\lambda>0$, $\mu>0$, and $\lambda<\mu$, the time in system $T$ of an arriving customer satisfies $$ \mathbb{P}(T>t)=e^{-(\mu-\lambda)t},\qquad t\ge0. $$ Equivalently, $T$ is exponential with rate $\mu-\lambda$, with density $(\mu-\lambda)e^{-(\mu-\lambda)t}$ for $t\ge0$ and mean $1/(\mu-\lambda)$.

Proof. Condition on $N$, whose stationary arrival distribution is geometric. The conditional Erlang tail just established gives, for $t\ge0$,

\begin{aligned} \mathbb{P}(T>t) &=\sum_{k=0}^{\infty}(1-\rho)\rho^k e^{-\mu t}\sum_{j=0}^{k}\frac{(\mu t)^j}{j!}\\ &=e^{-\mu t}(1-\rho)\sum_{j=0}^{\infty} \frac{(\mu t)^j}{j!}\sum_{k=j}^{\infty}\rho^k\\ &=e^{-\mu t}(1-\rho)\sum_{j=0}^{\infty} \frac{(\mu t)^j}{j!}\frac{\rho^j}{1-\rho}\\ &=e^{-\mu t}\sum_{j=0}^{\infty}\frac{(\rho\mu t)^j}{j!} =e^{-\mu t}e^{\lambda t} =e^{-(\mu-\lambda)t}. \end{aligned}

The rearrangement of the two sums is valid because all terms are nonnegative. The geometric series is finite since $0<\rho<1$; also, $\rho\mu=\lambda$. In particular, the factor $1-\rho$ from the probability of $N=0$ is canceled by the denominator $1-\rho$ in the geometric tail sum. The resulting survival function equals one at $t=0$, tends to zero as $t$ tends to infinity, and differentiating its complement gives the stated density. Integrating the tail gives $\mathbb{E}[T]=\int_0^\infty e^{-(\mu-\lambda)t}\,dt=1/(\mu-\lambda)$. $\square$

This derivation explains why the result is not simply the service-time distribution: arrivals who find customers present must wait for additional service completions. Mixing over the geometric number in system changes the exponential rate from $\mu$ to $\mu-\lambda$. The theorem concerns a customer arriving in stationarity; it is not a claim about the time in system from every possible initial queue state.

Worked Example: Checking the Geometric Mixture Exactly

Let $\lambda=2$, $\mu=5$, and $t=\tfrac15$. The stability condition holds because $2<5$, and $\rho=\lambda/\mu=2/5$. The theorem gives $\mathbb{P}(T>1/5)=e^{-3/5}$, since $(\mu-\lambda)t=3/5$. We now check the value by summing the conditional Erlang tails.

First, $\mu t=5(1/5)=1$ and $\rho\mu t=(2/5)(1)=2/5$. Substituting into the mixture and changing the order of its nonnegative sums gives

\begin{aligned} \mathbb{P}(T>1/5) &=e^{-1}\frac35\sum_{k=0}^{\infty} \left(\frac25\right)^k\sum_{j=0}^{k}\frac{1}{j!}\\ &=e^{-1}\frac35\sum_{j=0}^{\infty}\frac{1}{j!} \sum_{k=j}^{\infty}\left(\frac25\right)^k\\ &=e^{-1}\frac35\sum_{j=0}^{\infty}\frac{1}{j!} \frac{(2/5)^j}{1-2/5}\\ &=e^{-1}\sum_{j=0}^{\infty}\frac{(2/5)^j}{j!} =e^{-1}e^{2/5} =e^{-3/5}. \end{aligned}

Check: The geometric denominator is $1-2/5=3/5$, which cancels the prefactor $3/5$. The series argument is $\rho\mu t=2/5$, not $1/5$. The final exponent is $-1+2/5=-3/5$, agreeing with $-(\mu-\lambda)t=-(5-2)(1/5)=-3/5$.

Worked Example: A Tail Probability and a Quantile

Suppose $\lambda=1$ and $\mu=3$. Then $\rho=1/3<1$, so the stationary result applies, and the sojourn-time rate is $\mu-\lambda=2$. At time $t=1/2$,

\mathbb{P}(T>1/2)=e^{-2(1/2)}=e^{-1}, \qquad \mathbb{P}(T\le1/2)=1-e^{-1}.

For a time $t\ge0$ at which the tail probability is $1/4$, solve $e^{-2t}=1/4$. Taking logarithms gives $-2t=\ln(1/4)=-\ln4$, so $t=(\ln4)/2=\ln2$.

Check: Substituting $t=\ln2$ into the tail gives $e^{-2\ln2}=e^{-\ln4}=1/4$. The complementary probability is $3/4$, as required. This is a tail target, not a statement that the customer waits in queue for $\ln2$; it concerns the entire time through departure.

Worked Example: Probability of Departing in a Time Interval

Take $\lambda=1$ and $\mu=4$, so $\rho=1/4<1$ and $\mu-\lambda=3$. Find the probability that the customer's time in system is greater than $1/6$ but at most $1/2$. Because $T$ is continuous, this probability is the difference of the two strict tails:

\begin{aligned} \mathbb{P}(1/6<T\le1/2) &=\mathbb{P}(T>1/6)-\mathbb{P}(T>1/2)\\ &=e^{-3(1/6)}-e^{-3(1/2)} =e^{-1/2}-e^{-3/2}. \end{aligned}

Check: The first exponent uses $3(1/6)=1/2$, and the second uses $3(1/2)=3/2$. The answer is positive because $e^{-1/2}>e^{-3/2}$. It also equals $\mathbb{P}(T\le1/2)-\mathbb{P}(T\le1/6)=(1-e^{-3/2})-(1-e^{-1/2})$, giving the same difference.

How This Relates to Waiting Time

Let $W$ denote the time spent waiting in queue before service begins, excluding the arriving customer's own service. The earlier FCFS waiting-time result gives $\mathbb{P}(W=0)=1-\rho$ and $\mathbb{P}(W>t)=\rho e^{-(\mu-\lambda)t}$ for $t\ge0$. Thus $W$ has a probability mass at zero, whereas $T$ has no mass there: every arriving customer must receive a positive service duration almost surely. The time in system can be written $T=W+S$, where $S$ is the arriving customer's service time. In this model $S$ is independent of the work already ahead of the customer, but the waiting and service contributions should not be confused with the separate distributional statements for $W$ and $T$.

The stability assumption is essential to the stationary calculation. For example, if $\lambda=\mu$, then $\rho=1$, and the geometric probabilities $(1-\rho)\rho^k$ cannot define a probability distribution: each is zero and their sum is zero. If $\lambda>\mu$, the proposed geometric series does not converge. In either case this stationary M/M/1 result does not apply. The formula should not be used as though it established a stationary sojourn-time law in an unstable queue.

Common pitfall: mishandling the mixture. In the first worked example, one might accidentally use $1/5$ as the exponential-series argument because the observation time is $t=1/5$. That is incorrect: the argument after summing the queue-length mixture is $\rho\mu t=\lambda t$, which here equals $(2/5)(5)(1/5)=2/5$. A second possible error is to retain the geometric prefactor $3/5$ after the geometric sum: it cancels against the denominator $1-\rho=3/5$. Keeping both errors would give $e^{-1}(3/5)e^{1/5}$, which is not the tail probability. The correctly simplified expression is $e^{-1}e^{2/5}=e^{-3/5}$.

For a service target, the tail formula can be used directly: for any $t\ge0$, the fraction of stationary arrivals whose time in system exceeds $t$ is $e^{-(\mu-\lambda)t}$. If a target tail level $\alpha$ satisfies $0<\alpha<1$, solving $e^{-(\mu-\lambda)t}=\alpha$ gives $t=-\ln(\alpha)/(\mu-\lambda)$. This inversion relies on $\mu-\lambda>0$, exactly the stability condition used in the derivation.

Check Your Understanding

Use the stationary FCFS assumptions throughout. When computing a tail, use the strict event $T>t$.

For $\lambda=2$ and $\mu=6$, find $\rho$, the rate of $T$, and $\mathbb{P}(T>1/4)$.
Explain why, conditional on $N=k$, the arriving customer's time in system is a sum of $k+1$ exponential service durations, including the case $k=0$.
In the geometric-mixture derivation, identify the sum $\sum_{k=j}^{\infty}\rho^k$ and explain why its denominator cancels the factor $1-\rho$.
For $\lambda=1$ and $\mu=4$, solve for the time $t$ at which $\mathbb{P}(T>t)=1/2$, then substitute it into the tail formula.
State one difference between the waiting-time distribution $W$ and the time-in-system distribution $T$ in a stable M/M/1 queue.

The Sojourn-Time Distribution in the System

What You'll Learn