Poisson Arrivals See Time Averages (PASTA)

We are often interested in the state an arriving customer observes in a queue. If arrivals are Poisson, then the average arrival sees the system in its equilibrium state.

This may seem counterintuitive. When a customer arrives, we might expect the system to be slightly emptier in anticipation of the arrival. However, this is not the case for Poisson processes: they are uniformly distributed over time, and arrivals after time t are independent of what happened before t.

Theorem (PASTA). If X = (X(t) : t \ge 0) is a positive recurrent continuous-time Markov chain with stationary distribution \pi, and A = (A(t) : t \ge 0) is a Poisson process (which may or may not induce transitions in X), then

\displaystyle \lim_{t \to \infty} \frac{1}{A(t)} \int_0^t \mathbb{I}[X(s)=x]\, dA(s) = \pi(x)

Proof.

Let \tau_j denote the transition times of X. Define transitions by pairs of states Z_j = (X(\tau_j), X(\tau_{j+1})). Then both (X(\tau_j)) and (Z_j) are Markov chains.

We have

\displaystyle \mathbb{P}(X(\tau_j) = x) = \frac{\pi(x)\, q(x)}{\sum_{x'} \pi(x') q(x')}

Here \pi(x) is the proportion of time spent in state x, while \pi(x) q(x) weights this by the rate of leaving x. The normalizing constant

\displaystyle R = \sum_{x' \in \mathcal{X}} \pi(x') q(x')

is the long-run rate of transitions of the process.

We can now compute the stationary distribution of the transition process:

\displaystyle \mathbb{P}(Z = (x,y)) = \frac{q(x,y)}{q(x)} \cdot \frac{\pi(x) q(x)}{R} = \frac{\pi(x)\, q(x,y)}{R}

Thus, by ergodicity, the long-run proportion of transitions from x to y is

\displaystyle \frac{\# \text{ transitions } (x,y)}{\# \text{ transitions}} \to \frac{\pi(x)\, q(x,y)}{R}

Let \mathcal{A} be a set of “arrival transitions”. Then

\displaystyle \frac{\# \text{ transitions } (x,y)}{\# \text{ transitions in } \mathcal{A}} \to \frac{\pi(x)\, q(x,y)}{\sum_{x',y' \in \mathcal{A}} \pi(x') q(x',y')}

Suppose transitions in \mathcal{A} occur as a Poisson process. In particular, assume that for each state x' there is a unique transition (x',y') \in \mathcal{A} with rate q(x',y') = \lambda. Then

\displaystyle \frac{\# \text{ transitions } (x,y)}{\# \text{ transitions in } \mathcal{A}} \to \frac{\pi(x)\, \lambda}{\sum_{x'} \pi(x') \lambda} = \pi(x)

Thus, the average arrival sees state x with probability \pi(x).

\square

Leave a comment