PASTA and What Arriving Customers Observe

What Does an Arrival Observe?

At a randomly chosen time, an M/M/1 queue may be empty, busy with one customer, or contain several customers. An arriving customer samples the system at a particular event time, however, not at an arbitrary time. The PASTA principle—Poisson Arrivals See Time Averages—explains when these two ways of observing the system give the same distribution. The key condition is that arrivals are Poisson and their future increments are independent of the system’s history.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(N_t\) be a Poisson process of rate \(\lambda>0\), and let \((\mathcal{F}_t)_{t\ge0}\) be a filtration containing the system’s history up to time \(t\), with future increments of \(N_t\) independent of \(\mathcal{F}_t\). Let \(X_t\) be the system state, adapted to this filtration, with right-continuous paths and left limits. An arrival at time \(t\) sees the pre-arrival state \(X_{t-}\), the state immediately before \(t\). This convention excludes the customer who has just arrived.

The finite-time statement is an equality of expected counts. It does not say that a random fraction of arrivals in a finite interval equals the random fraction of time spent in a state. A long-run, pathwise equality requires additional ergodicity conditions; PASTA’s expected-count identity does not require a Markov assumption.

Why the Poisson Sampling Identity Holds

For a state \(i\), define \(H_i(t)=\mathbf{1}_{\{X_{t-}=i\}}\). This indicator is predictable: at time \(t\), its value is determined by the state just before \(t\), not by the arrival at \(t\) or by future information. We first establish the identity that makes the argument work.

Proof. First take a predictable process of the form \(H(t)=Y\mathbf{1}_{(a,b]}(t)\), where \(0\le a<b\le T\) and \(Y\) is bounded and \(\mathcal{F}_a\)-measurable. The integral against \(dN_t\) is \(Y(N_b-N_a)\). Since \(N_b-N_a\) is independent of \(\mathcal{F}_a\) and has mean \(\lambda(b-a)\),

Finite sums of these elementary predictable processes therefore satisfy the identity. To extend it, define two finite measures on the predictable sets \(B\subseteq(0,T]\times\Omega\): \(\alpha(B)=\mathbb{E}\int\mathbf{1}_B\,dN_t\) and \(\beta(B)=\lambda\mathbb{E}\int\mathbf{1}_B\,dt\). The calculation just given shows that the measures agree on generating rectangles \((a,b]\times A\), where \(A\in\mathcal{F}_a\). Uniqueness of finite measures then gives \(\alpha(B)=\beta(B)\) for every predictable \(B\). Integration of bounded predictable \(H\) gives the stated identity. \(\square\)

Apply the identity with \(H=H_i\). The integral against \(dN_t\) adds one for each arrival whose pre-arrival state is \(i\); the integral against \(dt\) records the time spent in state \(i\). Thus

Stationarity makes \(\mathbb{P}(X_{t-}=i)=\pi_i\) for almost every \(t\), so the right-hand side is \(\lambda T\pi_i\). The expected total number of arrivals in the interval is \(\lambda T\). Dividing the state-\(i\) arrival rate by the total arrival rate gives \(\pi_i\), proving PASTA. The same calculation also gives a useful nonstationary version: the expected number of arrivals seeing \(i\) over \((0,T]\) is \(\lambda\int_0^T\mathbb{P}(X_{t-}=i)\,dt\). In that case it matches the time-averaged expected occupancy, not necessarily the occupancy distribution at any one fixed time.

Applying PASTA to the M/M/1 Queue

For an M/M/1 queue, let \(X_t\in S=\{0,1,2,\ldots\}\) be the number of customers in the system at time \(t\). 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. Write \(\rho=\lambda/\mu\). When \(\rho<1\), the stationary distribution is \(\pi_n=(1-\rho)\rho^n\), for \(n\ge0\). PASTA applies to the state just before each arrival.

The geometric probabilities are normalized because \(\sum_{n\ge0}(1-\rho)\rho^n=1\) when \(0\le\rho<1\). They also satisfy the M/M/1 balance equations: \(\pi_0\lambda=\pi_1\mu\), and, for \(n\ge1\), \(\pi_{n-1}\lambda+\pi_{n+1}\mu=\pi_n(\lambda+\mu)\). For example, substituting \(\pi_n=(1-\rho)\rho^n\) into the latter gives \((1-\rho)\rho^{n-1}\lambda+(1-\rho)\rho^{n+1}\mu=(1-\rho)\rho^n(\lambda+\mu)\), using \(\lambda=\rho\mu\). The earlier stationary-distribution result for the stable M/M/1 queue gives uniqueness. PASTA therefore yields

Proof. The stationary state just before an arrival has distribution \(\pi\) by the PASTA theorem, so the probability of finding exactly \(n\) customers is \(\pi_n=(1-\rho)\rho^n\). For the tail probability, sum the geometric series: \(\sum_{n=k}^{\infty}(1-\rho)\rho^n=(1-\rho)\rho^k/(1-\rho)=\rho^k\). The formula also holds at \(k=0\), when the event is certain and \(\rho^0=1\). \(\square\)

When Arrivals Do Not See Time Averages

The independence condition matters. If arrivals are more likely in some system states than others, arrivals overrepresent those states. For example, suppose an external environment switches between states \(0\) and \(1\), with transition rate \(1\) in each direction, and has stationary probabilities \(1/2\) and \(1/2\). Suppose arrivals occur at rate \(1\) in state \(0\) and rate \(3\) in state \(1\). The time fraction in state \(1\) is \(1/2\), but the arrival fraction there is \(3/(1+3)=3/4\). This state-dependent arrival stream is not an independent Poisson input of constant rate, so PASTA does not apply.

Common mistake. Do not use the post-arrival customer count as the state an arrival finds. In the example with \(\lambda=1\) and \(\mu=2\), the stationary probability of one customer at an arbitrary time is \(\pi_1=1/4\). It would be wrong to conclude that an arrival sees one customer with probability \(1/2\) merely because the post-arrival system has one customer with probability \(1/2\). Post-arrival count one means pre-arrival count zero; pre-arrival count one has probability \(1/4\). PASTA applies to \(X_{t-}\), the state before the arrival joins.

In an M/M/1 queue, PASTA lets us use stationary time probabilities directly for arrival observations. It does not by itself give the arriving customer’s waiting-time or total time-in-system distribution; those require further analysis. Its immediate use here is precise: first identify the state just before an arrival, then use the stationary probabilities for that state.