Non-Ambiguous Description of PASTA Property

1.2k Views Asked by At

I find the word "see" as in PASTA (Poisson Arrivals See Time Averages) to be a bit ambiguous and thus wanted some clarification in what it means (see http://pages.cs.wisc.edu/~dsmyers/cs547/lecture_11_pasta.pdf).

Basically the above says the probability of an arrival coming in some period of length $b$, say $[c,d]: c,d \in [0,t], t \in \mathbb{R^{+}}$ and $c<d$ such that $d-c=b$ given that an arrival occurs in the time up until now, being time $t$, is merely $\frac{b}{t}$.

That is, P(arrival in period $b$| there is an arrival before time $t$)=$b/t$. This implies that the probability of a system being in some state A of the state space of this system before the time of an arrival is stationary.

Now, I am wondering if the above is merely saying that the system conforms to a stationary distribution or if there is more specificity with regard to "before the time of arrival" (e.g., the system turns stationary given that an arrival is to occur, which seems to make more sense but is never explicitly stated - could this be the explicit definition of "seeing"?).

1

There are 1 best solutions below

1
On BEST ANSWER

Let $\{t_1, t_2, t_3, ...\}$ be arrival times of a Poisson process of rate $\lambda>0$. Let $X(t)$ be a real-valued random process that possibly depends (causally) on the Poisson process. Assume that $\overline{X}$ is a real number such that: $$ \lim_{T\rightarrow\infty} \frac{1}{T}\int_0^T X(t)dt = \overline{X} \quad (\mbox{ with prob 1}) $$ The PASTA result says that under "mild" conditions we have: \begin{align} &(a) \quad \lim_{k\rightarrow\infty} \frac{1}{k}\sum_{i=1}^k X(t_i^-) = \overline{X} \quad (\mbox{ with prob 1}) \\ &(b) \quad \lim_{k\rightarrow\infty} \frac{1}{k}\sum_{i=1}^k E[X(t_i^-)] = \overline{X} \end{align} where $X(t_i^-)$ is the value of the random process sampled "just before" the $i$th Poisson arrival (so it is the value "seen" by this $i$th arrival). Since $\overline{X}$ is the "time average" of $X(t)$, we have that the average of the sequence of samples that are "seen" by arrivals is the same as the full time average (integrated over all time). This can be interpreted to mean that Poisson Arrivals See Time Averages (PASTA).


Example: Consider an M/G/1 queue $Q(t)$ and define $$ X(t) = 1_{\{Q(t)>0\}}= \left\{ \begin{array}{ll} 1 &\mbox{ if the queue is nonempty at time $t$} \\ 0 & \mbox{ if the queue is empty at time $t$} \end{array} \right.$$ Then: $$ \lim_{k\rightarrow\infty} \frac{1}{k}\sum_{i=1}^k X(t_i^-) = \lim_{T\rightarrow\infty} \frac{1}{T}\int_{0}^T 1_{\{Q(t)>0\}}dt = \rho$$ so the fraction of Poisson arrivals that see a non-empty system is the same as the fraction of time the system is non-empty.

This is not necessarily true if the arrivals are not Poisson. For example if arrivals are periodic with period $2$ and service times are $1$, then $\rho=1/2$ but all arrivals see an empty system, so $$ \lim_{k\rightarrow\infty} \frac{1}{k}\sum_{i=1}^k X(t_i^-)=0 \neq 1/2 = \lim_{T\rightarrow\infty} \frac{1}{T}\int_0^TX(t)dt$$

Other examples:

  • Fix $m \in \{0, 1, 2, ...\}$. Defining $X(t) = 1_{\{Q(t)=m\}}$ shows that the fraction of Poisson arrivals that see $m$ jobs in the system (not including the arrival itself) is the same as the fraction of time there are $m$ jobs in the system. For ergodic Markov chains with steady state distributions (stationary distributions), this is the same as the steady state probability there are $m$ jobs in the system.

  • Defining $X(t) = Q(t)$ shows that the average number of jobs in the system as seen by a Poisson arrival is the same as the time average number of jobs in the system.