Stability and Recurrence of the M/G/1 Embedded Chain

The Departure-Epoch Chain and Its Drift

Stability of an M/G/1 queue can be studied by observing it only at service completions. At these epochs the queue-length process is a discrete-time Markov chain: during each service, new arrivals increase the queue, while the completed customer decreases it by one if anyone was waiting. Its drift away from large queue lengths is controlled by the traffic intensity. The boundary at queue length zero behaves differently, so it must be handled separately.

Assume arrivals form a Poisson process of rate \(\lambda>0\), and successive service times are independent, identically distributed random variables \(B_n\), independent of the arrivals, with \(0<\beta=\mathbb{E}[B_n]<\infty\) and \(B_n<\infty\) almost surely. Let \((\Omega,\mathcal{F},\mathbb{P})\) be the underlying probability space. Write \(X_n\) for the number of customers in the system just after the \(n\)th departure, with state space \(S=\{0,1,2,\ldots\}\) and discrete time \(n\ge 0\). If \(X_n=0\), the next service starts when a customer arrives; otherwise it starts immediately. Let \(A_{n+1}\) be the number of arrivals during the next service. Conditional on that service having length \(b\), this count is Poisson with mean \(\lambda b\). Thus the \(A_n\) are identically distributed and independent, and

The quantity \(\rho=\lambda\beta\) is the traffic intensity. If \(X_n=i\ge1\), one customer departs and the arrivals during service are added, so the conditional mean increment is \(\rho-1\). If \(X_n=0\), there is no waiting customer to subtract, and the mean increment is \(\rho\).

Here the chain is irreducible. To check this, first note that \(A_n\) has positive probability of equaling every nonnegative integer. Indeed, \(\mathbb{P}(B_n>0)>0\) because \(\beta>0\), and for each integer \(k\ge0\), the conditional Poisson probability \(e^{-\lambda B_n}(\lambda B_n)^k/k!\) is strictly positive whenever \(B_n>0\). Its expectation is therefore positive. In particular, \(A_n=0\) has positive probability. From any positive state, repeated zero-arrival services can reach 0; from 0, an arrival count of \(j\) can reach any specified state \(j\).

For completeness, the transition probabilities are \(p_{ij}=\mathbb{P}(A_1=j-(i-1))\) when \(i\ge1\) and \(j\ge i-1\), and \(p_{0j}=\mathbb{P}(A_1=j)\); other entries are zero. Every row sums to one: for \(i\ge1\), summing over \(j\ge i-1\) sums the probabilities of \(A_1=0,1,\ldots\), and for \(i=0\) it sums those same probabilities. No finite truncation of this infinite state space is being used.

The Three Traffic-Intensity Regimes

Proof. First suppose \(\rho<1\), and set \(\delta=1-\rho>0\). Starting from \(X_0=x\ge1\), let \(T_0=\inf\{n\ge0:X_n=0\}\). Let \(\mathcal{F}_n\) contain the information from the chain and arrivals observed through step \(n\). Before \(T_0\), the chain is positive, so its conditional expected increment is \(-\delta\). For each integer \(m\ge0\), summing the stopped increments gives

This equality follows by writing each increment as \(\mathbf{1}_{\{T_0>n\}}(X_{n+1}-X_n)\), conditioning on \(\mathcal{F}_n\), and using that \(\{T_0>n\}\) is determined by \(\mathcal{F}_n\). All terms are integrable for finite \(m\), since \(\mathbb{E}A_n=\rho<\infty\). The left side is nonnegative, so \(\mathbb{E}_x[m\wedge T_0]\le x/\delta\). As \(m\) increases, \(m\wedge T_0\) increases to \(T_0\); monotone convergence gives \(\mathbb{E}_x[T_0]\le x/\delta\).

Starting at 0, the first step gives \(X_1=A_1\). If \(A_1=0\), the first return time \(T_0^+=\inf\{n\ge1:X_n=0\}\) is 1; otherwise, the preceding bound applies from \(A_1\). Consequently

Thus state 0 has finite mean return time. Irreducibility then makes the chain positive recurrent.

Now suppose \(\rho=1\). For \(i\ge1\), away from zero the recursion has increments \(A_n-1\), which are independent, identically distributed, integrable, have mean zero, and are nondegenerate. The standard oscillation theorem for a one-dimensional random walk with nondegenerate integrable mean-zero increments states that its partial sums have liminf \(-\infty\) and limsup \(+\infty\) almost surely; its proof is beyond this tutorial. Since \(A_n-1\ge-1\), downward steps have size at most one. Therefore, from any positive initial state, the walk reaches zero almost surely: it cannot pass from a positive value to a negative value without visiting zero. From state 0, either \(A_1=0\) and there is an immediate return, or the chain starts the same downward-crossing argument from \(A_1>0\). Hence the chain is recurrent.

It cannot be positive recurrent. Suppose instead that \(\mathbb{E}_0[T_0^+]<\infty\), and write \(T=T_0^+\). The recursion around one return cycle gives

For each \(k\ge2\), the event \(\{T\ge k\}\) is determined before \(A_k\) is observed, so it is independent of \(A_k\). Since \(\mathbb{E}[A_k-1]=0\), each term has mean zero when included. The sum can be integrated term by term: its expected absolute sum is bounded by \(\mathbb{E}|A_2-1|\,\mathbb{E}[T-1]<\infty\), using the same independence. Taking expectations in the displayed identity therefore gives \(0=\mathbb{E}[A_1]=1\), a contradiction. Thus the chain is recurrent but has infinite mean return time, so it is null recurrent.

Finally, suppose \(\rho>1\). The strong law of large numbers, a standard result, gives \(n^{-1}\sum_{k=1}^n(A_k-1)\to\rho-1>0\) almost surely. In particular, the infimum of these partial sums is finite almost surely. Hence there is some positive integer \(x\) for which

Starting from \(x\), the chain can hit 0 only if these increments sum to \(-x\) at some time before the hit. The displayed probability is therefore an upper bound on its probability of ever hitting 0, and that upper bound is strictly less than one. If state 0 were recurrent, irreducibility would imply that it is hit almost surely from every state. Thus the chain is not recurrent; by the standard recurrence-transience classification for irreducible countable-state chains, it is transient. The standard theorem that an irreducible countable-state chain has a stationary probability distribution exactly when it is positive recurrent then rules out a stationary probability distribution here; that theorem is proved later in the course. \(\square\)

Worked Regimes

A Boundary-State Pitfall

A common error is to use the positive-state drift \(\rho-1\) at state 0 as well. For example, in the first worked example \(\rho=\tfrac12\). At a positive state, the mean increment is \(\tfrac12-1=-\tfrac12\). But from state 0, the next state is \(A_1\), so the actual mean increment is \(\mathbb{E}[A_1]=\tfrac12\), not \(-\tfrac12\). Substituting the positive-state formula at zero would incorrectly predict a downward step from an empty queue. The correction is to use the recursion \(X_{n+1}=(X_n-1)^++A_{n+1}\), then compute the drift separately for \(X_n=0\) and \(X_n\ge1\).

The classification concerns the embedded chain observed at departures. Positive recurrence means that its return time to a departure-epoch state has finite mean; it does not by itself calculate the stationary queue-length distribution or waiting-time measures. Those require additional analysis. For stability classification, the essential distinctions are that \(\rho<1\) gives finite mean return time, \(\rho=1\) gives recurrence with infinite mean return time, and \(\rho>1\) gives transience.