Three Observation Epochs, Three Queue-Length Definitions
In an M/G/1 queue, “the queue length” depends on when it is observed. An arrival sees the system just before it joins; a departure leaves a system state just after service completion; an observer at an arbitrary time samples the process in continuous time. These descriptions refer to different random variables. Under the usual stationary assumptions, the pre-arrival and arbitrary-time distributions agree by PASTA. The post-departure embedded state also has that same marginal distribution in a stable single-server queue, but for a different reason: stationary level crossing. Neither equality says that the observations are interchangeable as processes or that departures satisfy PASTA.
Consider a single-server queue with an unlimited waiting room, external Poisson arrivals of rate \(\lambda>0\), and independent, identically distributed service times \(S_1,S_2,\ldots\), independent of the arrival process. Assume \(0<\mathbb{E}[S_1]<\infty\), and write \(\rho=\lambda\mathbb{E}[S_1]\). We assume \(\rho<1\) and that the queue is in its stationary regime. Let \(N(t)\) count all customers in the system at time \(t\), including any customer in service. Write \(A_k\) for arrival epochs and \(D_k\) for departure epochs.
At an arrival epoch, “the queue is empty” ordinarily means \(N(A_k-)=0\): there was nobody there before the arriving customer joined. It cannot mean \(N(A_k)=0\), because the arriving customer is included in that count. At a departure epoch, \(Y_k=0\) means that the departing customer was the last one in the system. Keeping these time conventions explicit prevents many errors.
PASTA: What Poisson Arrivals See
The condition that arrivals are external Poisson arrivals matters: the arrival process must not choose its times using the current queue length. One precise justification uses the Poisson compensation identity. Let \((\mathcal{F}_t)_{t\geq0}\) contain the queue history up to time \(t\), and let \(H(t)\) be a bounded predictable process, meaning its value at time \(t\) is determined by information just before \(t\). If \(N_A(t)\) counts the Poisson arrivals, then \(\mathbb{E}\sum_{0<A_k\leq T}H(A_k)=\lambda\mathbb{E}\int_0^T H(t)\,dt\). This identity follows first for processes constant on time intervals with values known at the left endpoint, by independence of future Poisson increments; approximation by such processes gives the bounded predictable case. It is the standard compensator identity for a Poisson process.
Proof. Fix \(n\geq0\) and take \(H(t)=\mathbf{1}_{\{N(t-)=n\}}\), which is predictable because it uses the state immediately before \(t\). The identity gives \(\mathbb{E}\sum_{0<A_k\leq T}\mathbf{1}_{\{N(A_k-)=n\}}=\lambda\int_0^T\mathbb{P}(N(t-)=n)\,dt\). Stationarity makes the integrand equal to \(\pi_n\) for almost every \(t\), so the expected number of arrivals that find \(n\) customers is \(\lambda T\pi_n\). The expected total number of arrivals is \(\lambda T\). Dividing the first expectation by the second gives the stationary arrival-epoch fraction \(\pi_n\), as claimed. Summing over \(n\) also gives total probability \(1\), since \(\sum_{n\geq0}\pi_n=1\). \(\square\)
PASTA identifies a marginal distribution, not the queue length after the arrival. Since the arrival adds one customer, the post-arrival count has the shifted distribution \(\mathbb{P}(N(A_k)=m)=\pi_{m-1}\) for \(m\geq1\), and probability \(0\) at \(m=0\). Also, PASTA does not apply to departures: departure times are generated by service completions, whose timing is related to the queue’s history.
Why Post-Departure Marginals Agree in This Queue
Proof. Fix \(n\geq0\). In a single-server queue with unit arrivals, an upward crossing from \(n\) customers to \(n+1\) occurs exactly when an arrival finds \(N(t-)=n\). Its expected rate is \(\lambda\pi_n\), by the Poisson compensation identity used above. A downward crossing from \(n+1\) to \(n\) occurs exactly at a departure that leaves \(n\) customers, that is, a departure with post-departure state \(Y_k=n\). Let \(c_n\) be the stationary rate of these departures. Over an interval \([0,T]\), the number of upward crossings minus the number of downward crossings is \(\mathbf{1}_{\{N(T)>n\}}-\mathbf{1}_{\{N(0)>n\}}\). Its expectation is zero by stationarity. Therefore the expected upward and downward crossing counts agree, and \(c_n=\lambda\pi_n\). The total departure rate is \(\lambda\) in a stable stationary queue with no losses: over a long interval, the difference between arrivals and departures is the change in the number in the system, whose stationary mean rate is zero. Thus the fraction of departures leaving \(n\) customers is \(c_n/\lambda=\pi_n\). This is the asserted post-departure marginal. \(\square\)
The two equalities have different explanations. Poisson arrivals see time averages because their future increments are independent of the queue history. Departures have the same one-time marginal as the time occupancy because upward and downward crossings of every level balance in stationarity. The equalities do not imply independence between successive embedded states, nor do they imply that the departure process is Poisson.
Worked Example: M/M/1 Arrivals and Post-Departure States
Take an M/M/1 queue with arrival rate \(\lambda=1\) and service rate \(\mu=2\). Its traffic intensity is \(\rho=\lambda/\mu=1/2<1\). The time-stationary distribution is \(\pi_n=(1-\rho)\rho^n=2^{-(n+1)}\): the birth-death balance equations give \(\pi_{n+1}=\rho\pi_n\), and \(\sum_{n\geq0}\pi_n=(1/2)\sum_{n\geq0}(1/2)^n=1\). Hence an arrival finds the system empty with probability \(\pi_0=1/2\).
We can also check the post-departure embedded marginal directly. Given that a service begins, the number \(A\) of arrivals during that exponential service has probability generating function \(a(z)=\mathbb{E}[z^A]=2/(3-z)\). Indeed, \(A\) has probabilities \(\mathbb{P}(A=j)=(2/3)(1/3)^j\), whose sum is \((2/3)/(1-1/3)=1\). If the post-departure state is \(y\geq1\), the next departure leaves \(y-1+A\) customers; if \(y=0\), the system first waits for an arrival and the next departure leaves \(A\) customers.
Let \(g(z)=\mathbb{E}[z^{Y_k}]\) in the stationary departure-epoch distribution, and let \(p_0=\mathbb{P}(Y_k=0)\). Conditioning on whether \(Y_k=0\) gives \(g(z)=a(z)\{p_0+(g(z)-p_0)/z\}\). Solving, \(g(z)=p_0a(z)(z-1)/(z-a(z))\). Since \(a(1)=1\) and \(a'(1)=1/2\), taking \(z\) to \(1\) gives \(g(1)=p_0/(1-a'(1))=2p_0\). A probability generating function satisfies \(g(1)=1\), so \(p_0=1/2\). Substitution then gives \(g(z)=1/(2-z)=(1/2)/(1-z/2)\), whose coefficient of \(z^n\) is \(2^{-(n+1)}\). Thus the post-departure marginal agrees with \(\pi_n\), while the argument establishing it is not PASTA.
Check: \(g(1)=1/(2-1)=1\), and \(g(0)=1/2=\pi_0\). The arrival-empty probability and post-departure-empty probability are both \(1/2\), but they refer to different epochs.
Worked Example: Deterministic Service and the Embedded Boundary
Let service time be exactly \(1\), and let the Poisson arrival rate be \(\lambda=1/2\). Then \(\rho=(1/2)\cdot1=1/2<1\). The number \(A\) of arrivals during a service has probabilities \(a_j=e^{-1/2}(1/2)^j/j!\), \(j\geq0\). Their sum is \(e^{-1/2}\sum_{j\geq0}(1/2)^j/j!=e^{-1/2}e^{1/2}=1\), so these are valid transition probabilities for the arrivals-during-service count.
For the post-departure chain, from state \(0\) the next departure leaves \(A\) customers: one arrival starts service after the idle period, and \(A\) counts arrivals during that service, not the customer who started it. From state \(y\geq1\), the next departure leaves \(y-1+A\). In either case the probabilities over all possible next states sum to \(\sum_{j\geq0}a_j=1\); the boundary state \(0\) must not be treated as if a customer were already waiting at the departure epoch.
By stationary level crossing, \(p_0=\mathbb{P}(Y_k=0)=\pi_0=1-\rho=1/2\). The stationary equation for the embedded chain’s probability of moving into state \(0\) is \(p_0=(p_0+p_1)a_0\): only current states \(0\) and \(1\) can reach \(0\), and both require \(A=0\). Since \(a_0=e^{-1/2}\), this gives \(1/2=(1/2+p_1)e^{-1/2}\), so \(1/2+p_1=e^{1/2}/2\) and \(p_1=(e^{1/2}-1)/2\).
Check: \((p_0+p_1)a_0=(e^{1/2}/2)e^{-1/2}=1/2=p_0\), so the state-zero stationary equation is satisfied. This calculation also shows why the transition rule at an empty post-departure state needs its own boundary case.
Worked Example: Correcting an Arrival-Empty Calculation
Use the M/M/1 queue with \(\lambda=1\), \(\mu=2\), and \(\pi_n=2^{-(n+1)}\). An incorrect calculation might say, “An arrival sees the stationary probability of zero, so the number in the system immediately after it arrives is zero with probability \(1/2\).” The first clause applies to the pre-arrival count; the conclusion does not.
PASTA gives \(\mathbb{P}(N(A_k-)=0)=\pi_0=1/2\). But the arriving customer is included immediately afterward, so \(N(A_k)=N(A_k-)+1\). Therefore \(\mathbb{P}(N(A_k)=0)=0\), while \(\mathbb{P}(N(A_k)=1)=\mathbb{P}(N(A_k-)=0)=1/2\). More generally, \(\mathbb{P}(N(A_k)=m)=2^{-m}\) for \(m\geq1\), and these probabilities sum to \(\sum_{m\geq1}2^{-m}=1\).
The probability that the arrival must wait is \(\mathbb{P}(N(A_k-)>0)=1-\pi_0=1/2\), under the usual continuous-time model in which an arrival does not coincide with a service completion with positive probability. The probability it finds nobody ahead is instead \(1/2\). Those statements use the pre-arrival count; neither should be confused with the post-arrival event \(N(A_k)=0\), which is impossible.
What the Equalities Do—and Do Not—Mean
The empty-system probability is especially easy to mislabel. In a stable M/G/1 queue, \(\pi_0=1-\rho\) is the fraction of time the server is idle. By PASTA, it is also the probability an external Poisson arrival finds the system empty immediately before joining. By level crossing, it is also the fraction of departures that leave the system empty. These are equal probabilities for distinct observations. A departure that leaves an empty system is not a departure that “finds” an empty system: the departing customer was present just before that departure.
Likewise, a shared marginal distribution does not identify a shared sampling mechanism. The embedded sequence \((Y_k)\) records one state per departure and has dependence between successive values. The continuous-time process \(N(t)\) records occupancy at every time. PASTA concerns pre-arrival observations of the latter; it does not assert that departure epochs are Poisson, that successive departure states are independent, or that time averages can be replaced by arbitrary event-epoch averages.
Common mistake. Applying PASTA to departures and writing \(\mathbb{P}(Y_k=n)=\pi_n\) “because departures see time averages” gives the right marginal here for the wrong reason. The correction is to use PASTA only for external Poisson arrivals, and to use level crossing for post-departure states. This distinction matters when the event stream is not Poisson or when the queue’s transition rules do not give the same level-crossing balance.
Check Your Understanding
For each question, specify the observation epoch and whether the count is taken immediately before or after the event.
- In a stationary M/G/1 queue, what result identifies the distribution of \(N(A_k-)\) with \(\pi_n\), and what independence assumption about arrivals is essential?
- Why does \(\mathbb{P}(N(A_k)=0)=0\), even when \(\pi_0\) is positive?
- Which argument identifies \(\mathbb{P}(Y_k=n)\) with \(\pi_n\) in the stable single-server queue, and how does it differ from PASTA?
- For deterministic service time \(1\) and arrival rate \(1/2\), verify that \(\sum_{j\geq0}e^{-1/2}(1/2)^j/j!=1\), and state the embedded transition rule from post-departure state \(0\).
- Does equality of the post-departure and time-stationary marginals imply that departures form a Poisson process or that successive \(Y_k\) are independent? Explain.