The Embedded Queue-Length Recursion in an M/G/1 Queue

Queue Lengths at Departure Epochs

In an M/G/1 queue, arrivals form a Poisson process, there is one server, and service times have a general distribution. Observing the queue continuously records both busy periods and idle periods. Instead, we can look only at the moments just after service completions. Between two such moments, the queue changes in a simple way: one customer departs, and arrivals during the service interval join the customers already waiting. The empty-queue case needs care, because the next service cannot start until a new customer arrives.

Work on a probability space $(\Omega,\mathcal{F},\mathbb{P})$. Let $N(t)$, $t\geq 0$, be a Poisson arrival process of rate $\lambda>0$. Service requirements are independent and identically distributed random variables with common distribution $F$, independent of the arrival process; write $V$ for a random variable with distribution $F$. Assume $0<V<\infty$ almost surely. The server works whenever the system is nonempty, serves customers in order of arrival, and has unlimited capacity. These assumptions define the M/G/1 setting used here.

Definition: Let $D_n$ be the time of the $n$th departure, and let $Q_n$ be the number of customers in the system immediately after that departure. Thus $Q_n$ includes any customer who begins service immediately after $D_n$, as well as everyone waiting. The embedded process $(Q_n)_{n\geq 0}$ is a discrete-time process with state space $S=\{0,1,2,\ldots\}$.

We use an observed-history filtration at departure epochs. Let $\mathcal{H}_n$ contain the arrival and service history observed through $D_n$, including completed service times and the queue length $Q_n$, but not the service requirements of customers whose service has not begun. In particular, any next service requirement is independent of $\mathcal{H}_n$. This information convention matters: if an unstarted customer's service time is already revealed, a conditional-mean formula given the enlarged information generally changes.

Counting Arrivals Between Departures

After $D_n$, let $B_{n+1}$ be the start of the service that ends at $D_{n+1}$, and let $V_{n+1}$ be that service duration. If $Q_n>0$, service starts immediately, so $B_{n+1}=D_n$. If $Q_n=0$, the server waits until the first arrival after $D_n$; that arrival begins service, so $B_{n+1}>D_n$. Define $A_{n+1}$ to be the number of arrivals strictly between $B_{n+1}$ and $D_{n+1}$. The arrival that initiates service when the system was empty is not included in $A_{n+1}$: that customer is the one who departs at $D_{n+1}$.

Proposition (Pathwise embedded recursion): With these definitions, for every $n\geq 0$, almost surely, $$ Q_{n+1}=(Q_n-1)^+ + A_{n+1}, \qquad (q-1)^+=\max\{q-1,0\}. $$

Proof. Fix $n$. If $Q_n>0$, one of the customers present just after $D_n$ begins service and departs at $D_{n+1}$. The other $Q_n-1$ customers remain in the system, and each of the $A_{n+1}$ arrivals during that service is still present just after the departure. Therefore $Q_{n+1}=Q_n-1+A_{n+1}=(Q_n-1)^++A_{n+1}$. If $Q_n=0$, there are no customers to carry over. The first arrival after $D_n$ begins service and is the customer who departs at $D_{n+1}$; the only customers left immediately afterward are the $A_{n+1}$ arrivals during that service. Thus $Q_{n+1}=A_{n+1}=(Q_n-1)^++A_{n+1}$. These cases exhaust the nonnegative integer values of $Q_n$, proving the recursion. $\square$

The arrival count has a useful conditional description. At a service start, the future increments of a Poisson process are independent of its observed history; this is the standard strong Markov property of the Poisson process. The next service requirement is independent of $\mathcal{H}_n$ by the information and independence assumptions above. Consequently, conditional on $V_{n+1}=v$ and the history at the start of service, $A_{n+1}$ has a Poisson distribution with mean $\lambda v$. In particular, for each integer $r\geq 0$,

\mathbb{P}(A_{n+1}=r\mid V_{n+1}=v,\mathcal{H}_n) =e^{-\lambda v}\frac{(\lambda v)^r}{r!}.

Here the conditional statement is understood under the stated independence assumptions; service durations are finite, so this conditional Poisson count is finite almost surely. Averaging over the service-time distribution gives the mixed-Poisson probabilities $\mathbb{P}(A_{n+1}=r\mid\mathcal{H}_n)=\mathbb{E}\!\left[e^{-\lambda V}(\lambda V)^r/r!\right]$. The same law applies whether the server starts service immediately or first waits for an arrival: after that service start, the arrivals during service are governed by fresh Poisson increments.

Theorem (Conditional recursion law and mean): For every $n$, conditional on $\mathcal{H}_n$, the law of $Q_{n+1}$ is that of $(Q_n-1)^++A$, where $A$ has the mixed-Poisson probabilities above. If $\mathbb{E}[V]<\infty$, then $$ \mathbb{E}[Q_{n+1}\mid\mathcal{H}_n] =(Q_n-1)^+ + \lambda\mathbb{E}[V]. $$ Thus the conditional law depends on the observed history only through $Q_n$.

Proof. The pathwise proposition gives $Q_{n+1}=(Q_n-1)^++A_{n+1}$. Conditional on $\mathcal{H}_n$, $Q_n$ is known, and the service duration for the next service has distribution $F$ independently of that history. Given this duration $V_{n+1}=v$, the number of arrivals during the service has the Poisson law with mean $\lambda v$, by the independent-increments property at the service start. Integrating this conditional law over $F$ yields the stated mixed-Poisson law, so the conditional distribution of $Q_{n+1}$ is determined by $Q_n$. If $\mathbb{E}[V]<\infty$, then conditional expectation first given the service duration gives $\mathbb{E}[A_{n+1}\mid V_{n+1},\mathcal{H}_n]=\lambda V_{n+1}$. Taking conditional expectation given $\mathcal{H}_n$, independence gives $\mathbb{E}[A_{n+1}\mid\mathcal{H}_n]=\lambda\mathbb{E}[V]$. Substitution in the pathwise recursion proves the mean formula. $\square$

This result establishes the Markov property of the embedded queue-length process under the stated assumptions: its next-step conditional distribution given the observed embedded history depends only on its current state. It does not assert that the process is stationary, or that it has a stationary distribution. Those are separate questions and are not needed to derive the recursion.

Worked Examples

Worked Example: Deterministic Service and a Busy Server

Suppose arrivals have rate $\lambda=2$ and every service takes $V=\tfrac12$ time units. Given $Q_n=3$, find the distribution and mean of $Q_{n+1}$.

The next service begins immediately. During its $\tfrac12$ time units, the Poisson arrival count has mean $\lambda V=2\cdot\tfrac12=1$. Hence $A_{n+1}$ is Poisson with mean $1$, and the recursion gives $Q_{n+1}=3-1+A_{n+1}=2+A_{n+1}$. For $r=0,1,2$, the corresponding probabilities are $\mathbb{P}(Q_{n+1}=2)=e^{-1}$, $\mathbb{P}(Q_{n+1}=3)=e^{-1}$, and $\mathbb{P}(Q_{n+1}=4)=e^{-1}/2$, using $e^{-1}1^r/r!$ for the Poisson probabilities.

Check: The whole distribution is $\mathbb{P}(Q_{n+1}=2+r)=e^{-1}/r!$ for $r\geq0$, whose probabilities sum to $e^{-1}\sum_{r\geq0}1/r!=1$. Its mean is $2+\mathbb{E}[A_{n+1}]=2+1=3$. The conditional-mean formula gives $(3-1)^++2\cdot\tfrac12=2+1=3$, the same result.

Worked Example: Random Service and a Busy Server

Let $\lambda=1$, and suppose service time $V$ equals $\tfrac12$ or $\tfrac32$, each with probability $\tfrac12$. If $Q_n=2$, compute the mean of $Q_{n+1}$ and its probabilities of being $1$ and $2$.

There is one customer left waiting after the next service begins, so $Q_{n+1}=1+A_{n+1}$. The mean service time is $\mathbb{E}[V]=\tfrac12\cdot\tfrac12+\tfrac12\cdot\tfrac32=\tfrac14+\tfrac34=1$. The conditional Poisson means are $1\cdot\tfrac12=\tfrac12$ and $1\cdot\tfrac32=\tfrac32$, each with probability $\tfrac12$. Therefore $$ \mathbb{P}(Q_{n+1}=1) =\mathbb{P}(A_{n+1}=0) =\tfrac12e^{-1/2}+\tfrac12e^{-3/2}, $$ and $$ \mathbb{P}(Q_{n+1}=2) =\mathbb{P}(A_{n+1}=1) =\tfrac12\left(\tfrac12e^{-1/2}\right) +\tfrac12\left(\tfrac32e^{-3/2}\right) =\tfrac14e^{-1/2}+\tfrac34e^{-3/2}. $$

Check: Given $V=\tfrac12$, the conditional mean of $Q_{n+1}$ is $1+\tfrac12=\tfrac32$; given $V=\tfrac32$, it is $1+\tfrac32=\tfrac52$. Averaging gives $\tfrac12\cdot\tfrac32+\tfrac12\cdot\tfrac52=\tfrac34+\tfrac54=2$. The unconditional formula also gives $(2-1)^++1\cdot1=2$.

Worked Example: An Empty Queue After Departure

Suppose $\lambda=2$, $V=\tfrac12$ deterministically, and $Q_n=0$. Find the distribution of $Q_{n+1}$. Explain why the wait for the next arrival is not added to the queue length.

The server waits for the first new arrival, who immediately begins service. That initiating customer then departs at $D_{n+1}$, so this customer contributes nothing to $Q_{n+1}$. During the service, the number of further arrivals is Poisson with mean $2\cdot\tfrac12=1$. Since $(0-1)^+=0$, the recursion is $Q_{n+1}=A_{n+1}$. Thus $\mathbb{P}(Q_{n+1}=r)=e^{-1}/r!$ for each integer $r\geq0$, and $\mathbb{E}[Q_{n+1}]=1$.

Check: The probability of no arrivals during service is $e^{-1}/0!=e^{-1}$, so $Q_{n+1}=0$ has probability $e^{-1}$. The mean formula gives $(0-1)^++2\cdot\tfrac12=0+1=1$, agreeing with the direct Poisson mean.

Information and Counting Pitfalls

A common counting error is to include the customer who arrives to restart an empty system as an arrival during service. That customer starts the service whose completion defines $D_{n+1}$, and has already departed by the time $Q_{n+1}$ is measured. In the empty case, only arrivals after that service start remain in $Q_{n+1}$. A second error is to assume that the conditional-mean formula holds for any filtration, including one that reveals unstarted service requirements.

For a concrete check of the information issue, take $\lambda=2$, $Q_n=1$, and let the next service time be $\tfrac14$ or $\tfrac34$, each with probability $\tfrac12$. If the filtration reveals which service time is next, the recursion gives $Q_{n+1}=A_{n+1}$, and the conditional mean is $2\cdot\tfrac14=\tfrac12$ when $V_{n+1}=\tfrac14$, or $2\cdot\tfrac34=\tfrac32$ when $V_{n+1}=\tfrac34$. The expression $(1-1)^++2\mathbb{E}[V]=0+2(\tfrac12)=1$ is the mean given the history that does not reveal the service time; it is not the conditional mean given the enlarged information. If the service time is revealed, the appropriate conditional formula is $(Q_n-1)^++\lambda V_{n+1}$. The filtration must match the conditioning statement.

The recursion is useful because it converts the continuous-time queue between departures into a discrete-time update driven by the number of service arrivals. Its derivation requires neither a stationary regime nor a stability assumption. For mean calculations, the additional condition $\mathbb{E}[V]<\infty$ ensures the displayed conditional mean is finite. Questions about recurrence or a stationary departure-queue distribution require further analysis.

Check Your Understanding

In each question, count only customers present immediately after the next departure.

If $Q_n=4$, express $Q_{n+1}$ in terms of $A_{n+1}$, and explain the deterministic part of the expression.
If $Q_n=0$, why is the customer who starts the next service not included in $A_{n+1}$?
For $\lambda=3$ and deterministic service time $V=\tfrac13$, what is the conditional mean of $Q_{n+1}$ when $Q_n=0$?
For a general service-time distribution, what is $\mathbb{P}(A_{n+1}=0\mid\mathcal{H}_n)$ under the stated information assumptions?
In the revealed-service-time example, what conditional-mean expression should replace $(Q_n-1)^++\lambda\mathbb{E}[V]$?

The Embedded Queue-Length Recursion in an M/G/1 Queue

What You'll Learn