4.5 Poisson Arrivals See Time Averages
Recall from the example of Section 4.2 that sampling at arrival times can give very different results from sampling over time. Interestingly, as we show here, when jobs arrive as a Poisson process, both sampling methods yield the same value. This result is known as Poisson arrivals see time-averages (PASTA).
Say the system is in state \(n\) at time \(t\) when \(L(t)=n\). Then define
\begin{equation*} A(n,t) := \sum_{k=1}^{A(t)}\1{\L(A_k-) = n} \end{equation*}as the number of arrivals up to time \(t\) that saw the system in state \(n\) upon arrival.1 Ex 4.5.6. Next, let
\begin{equation*} Y(n,t) := \int_0^t \1{\L(s) = n} \d s \end{equation*}be the total time the system spends in state \(n\) during \([0,t]\).
Assume the following limits exist:
\begin{subequations} \begin{align*} \lambda &:= \lim_{t\to\infty} \frac{A(t)}{t}, & \lambda(n) &:= \lim_{t\to\infty} \frac{A(n,t)}{Y(n,t)}, \\ p(n) &:=\lim_{t\to\infty} \frac{Y(n,t)}{t}, & \pi(n) &:= \lim_{t\to\infty}\frac{A(n,t)}{A(t)}. \tag{4.5.1} \end{align*} \end{subequations}Here, \(\lambda(n)\) denotes the arrival rate when the system is in state \(n\), \(p(n)\) the long-run fraction of time the system spends in state \(n\), and \(\pi(n)\) the long-run fraction of arrivals that find \(n\) customers present.
If all limits in Eq. (4.5.1) exist,
\begin{equation*} \lambda \pi(n) = \lambda(n) p(n). \end{equation*}Proof
On the one hand,
\begin{equation*} \lim_{t\to\infty} \frac{A(n,t)}t = \lim_{t\to\infty} \frac{A(n,t)}{Y(n,t)}\frac{Y(n,t)}t = \lambda(n) p(n). \end{equation*}On the other,
\begin{equation*} \lim_{t\to\infty} \frac{A(n,t)}t = \lim_{t\to\infty} \frac{A(n,t)}{A(t)}\frac{A(t)}t = \pi(n) \lambda. \end{equation*}This result has a simple consequence. Write \(\mathcal{S}\) for all states the system can attain.2 When there is no upper bound on \(L\), then \(\mathcal{S} = \N\), but when \(L(t)\) is bounded by some number \(K\), then \(\mathcal{S} = \{0, 1, \ldots, K\}\). Clearly, any arrival must see the system in some state, hence \(\sum_{n\in \mathcal{S}} \pi(n) = 1\). Thus, summing over \(n\) in \(\lambda \pi(n) = \lambda(n) p(n)\), the overall arrival rate \(\lambda\) satisfies
\begin{equation*} \lambda = \sum_{n\in \mathcal{S}} \lambda(n)p(n). \tag{4.5.2} \end{equation*}With the above theorem, we can obtain the second result of utmost importance.
If the arrival rate does not depend on the state of the system, i.e., \(\lambda(n)=\lambda\), the sample probabilities \(\{\pi(n)\}\) equal the time-average probabilities \(\{p(n)\}\), i.e.,
\begin{equation*} \lambda(n) = \lambda \iff \pi(n) = p(n). \tag{4.5.3} \end{equation*}Proof
From Th. 4.5.1, \(\pi(n) = \lambda(n) p(n)/\lambda\). By assumption, \(\lambda=\lambda(n)\), so the \(\lambda\)'s cancel.
As the example in the introduction of this section shows, this property is not satisfied in general. However,3 A rigorous proof of this is difficult, see e.g., M. El-Taha and S. Stidham Jr., Sample-Path Analysis of Queueing Systems, 1998.
If the arrival process is Poisson, then \(\lambda(n)=\lambda\), in which case \(\pi(n)=p(n)\).
By discretizing time we can give an intuitive explanation of when PASTA holds or fails. If in some period \(k\) a job arrives (\(a_{k}=1\)) and the system contains \(m\) jobs at the end of period \(k-1\), i.e., \(L_{k-1}=m\), then we say that the arrival in period \(k\) sees \(m\) jobs in the system upon arrival. Thus, for \(k\) large, \(\pi(m) \approx \P{L_{k-1}=m | a_{k}=1}\). With Bayes' law:
\begin{equation*} \pi(m) \approx \P{L_{k-1}=m | a_{k}=1} = \frac{\P{a_{k}=1, L_{k-1}=m}}{\P{a_{k}=1}}. \end{equation*}Observe that \(L_{k-1}\) is a function of \(\{a_i\}_{i=1}^{k-1}\). If \(a_{k}\) and \(\{a_i\}_{i=1}^{k-1}\) are independent, then \(a_{k}\) and \(L_{k-1}\) are independent too, and then \(\P{a_{k}=1, L_{k-1}=m} = \P{a_{k}=1} \P{L_{k-1}=m}\). By canceling \(\P{a_{k}=1}\) in the fraction, we see that
\begin{equation*} \pi(m) \approx \P{L_{k-1}=m} \approx p(m), \end{equation*}where the last approximation follows from the fact that \(\P{L_{k-1}=m}\) is the fraction of periods that \(L=m\).4 For mathematically interested students: The assumed strong convergence \(N^{-1}\sum_{k=1}^N \1{L_{k}=m} \to p(m)\) as \(N\to\infty\) implies the weak convergence \(\P{L_{k}=m} \to p(m)\) as \(k \to \infty\).
However, PASTA does not hold when \(a_{k}\) depends on \(L_{k-1}\). For example, if \(a_{k}=0\) when \(L_{k-1}>0\) and \(c_{k}\sim \Bern{d}\) for some small probability \(d\), then \(\pi(1) = 0\) while in general \(\P{L_{k-1}=0} > 0\).
With PASTA, Little's law and memorylessness we can derive some initial results for the \(M/M/1\) queue.5 For the \(M/G/1\) queue, things are a bit subtler; see Ex 4.5.8 and Section 5.6. By PASTA, an arrival sees on average \(\E \L\) jobs in the system, and the expected time to serve these jobs is \(\E \L \E S\). This is subtler than it seems: the expected time to serve the jobs in queue is \(\E \QQ \E S\), and by the memoryless property of \(S\), the expected remaining time of the job in service (if any) is also \(\E S\).6 This is not true for the \(M/G/1\) queue. Next, as the arriving job has to be served itself before leaving, its expected sojourn time \(\E \J = \E \L \E S + \E S\). With Little's law, \(\E \L = \lambda \E \J\), and therefore,
\begin{equation*} \E\J = \E \L \E S + \E S= \lambda \E \J \E S + \E S = \rho \E \J + \E S. \end{equation*}Consequently,
\begin{subequations} \begin{align*} \E\J = \frac{\E S}{1-\rho}, \tag{4.5.4} \end{align*} from which, \begin{align*} \E \L &= \lambda \E\J = \frac{\lambda \E S}{1-\rho} = \frac\rho{1-\rho}, \\ \E{\W} &= \E \L \E S = \frac{\rho}{1-\rho} \E S \label{eq:wqes}\\ \E{\QQ} &= \lambda \E{\W} = \frac{\rho^2}{1-\rho}, \\ \E{\Ls} &= \E \L - \E{\QQ} = \frac{\rho}{1-\rho} - \frac{\rho^2}{1-\rho} = \rho, \tag{4.5.5} \end{align*} \end{subequations}To let you think a bit deeper about the PASTA property, and obtaining statistics by sampling in general, consider the next cute riddle. The problem is known as the `inspection paradox'.7 Look this paradox up on the web. You should be aware of such biases in data science.
In a small midwestern town8 This cute story comes from the book `Puzzle Math' by G. Gamow and M. Stern, https://www.arvindguptatoys.com/arvindgupta/puzzlemath.pdf. The interesting solution can also be found there. there lived a retired railroad engineer named William Johnson. The main line on which he had worked for so many years passed through the town. Mr. Johnson suffered from insomnia and would often wake up at any odd hour of the night and be unable to fall asleep again. He found it helpful, in such cases, to take a walk along the deserted streets of the town, and his way always led him to the railroad crossing. He would stand there thoughtfully watching the track until a train thundered by through the dead of the night. The sight always cheered the old railroad man, and he would walk back home with a good chance of falling asleep.
After a while he made a curious observation; it seemed to him that most of the trains he saw at the crossing were traveling eastward, and only a few were going west. Knowing very well that this line was carrying equal numbers of eastbound and westbound trains, and that they alternated regularly, he decided at first that he must have been mistaken in this reckoning. To make sure, he got his little notebook, and began putting down "E" or "W," depending on which way the first train to pass was traveling. At the end of a week, there were five "E's" and only two "W's" and the observations of the next week gave essentially the same proportion. Could it be that he always woke up at the same hour of night, mostly before the passage of eastbound trains?
Being puzzled by this situation, he decided to undertake a rigorous statistical study of the problem, extending it also to the daytime. He asked a friend to make a long list of arbitrary times such as 9:35 a.m., 12:00 noon, 3:07 p.m., and so on, and he went to the railroad crossing punctually at these times to see which train would come first. However, the result was the same as before. Out of one hundred trains he met, about seventy-five were going east and only twenty-five west. In despair, he called the depot in the nearest big city to find whether some of the westbound trains had been rerouted through another line, but this was not the case. He was, in fact, assured that the trains were running exactly on schedule, and that equal numbers of trains daily were going each way. This mystery brought him to such despair that he became completely unable to sleep and was a very sick man.
Can you reveal the mystery, thereby solving the sleeping problems of Mr. Johnson without prescribing pills?
Claim: The PASTA property implies that \(\sum_{n=0}^\infty n p(n) = \sum_{n=0}^\infty n \pi(n)\) for any \(G/M/1\) queue.
Solution
Solution, for real
False. In the \(G/M/1\) queue, jobs do not arrive as a Poisson process.
Consider a stable \(M/G/1\) queue. Claim: By the PASTA property, a fraction \(\rho\) of the arrivals sees the server occupied, while a fraction \(1-\rho\) sees a free server.
Solution
Solution, for real
True.
Claim: For the \(M/G/1\) queue it follows from the PASTA property that
\begin{equation*} \E \J = \sum_{n=0}^\infty \E{\W \given L=n} \pi(n) + \E S. \end{equation*}Solution
Solution, for real
True.
Let \(L_{S}(s)\) be the number of jobs in service at time \(s\) in an \(M/G/1\) queue. Define
\begin{equation*} \alpha = \lim_{n\to\infty} \frac 1 n \sum_{k=1}^n L_{S}(A_k). \end{equation*}Claim: PASTA implies that \(1-\rho = \alpha\).
Solution
Solution, for real
False. First we should use \(L_{S}(A_{k}-)\) instead of \(L_{S}(A_{k})\). Second, by PASTA \(\alpha\) must be the load, which is \(\rho\) for the \(M/G/1\) queue; \(1-\rho\) is the fraction of time the server is idle.
Claim: PASTA implies that for any \(G/G/1\) queue, \(\pi(n) = p(n)\).
Solution
Solution, for real
False. PASTA requires that arrivals form a Poisson process. For a general \(G/G/1\) queue, the arrival process need not be Poisson, so sample and time averages can differ.
If \(\lambda>\delta\), can it happen that \( \lim_{t\to\infty} A(n,t)/t > 0\) for some (finite) \(n\)?
Solution
Solution, for real
If \(\lambda > \delta\), then \(L(t)\to\infty\). But then there must be a last time \(s\), say, that \(L(s) = n+1\), and \(L(t) > n+1\) for all \(t>s\). Hence, after time \(s\) there will never be a job that will see the system with \(n\) jobs. Thus \(A(n,t) = A(n,s)\) for all \(t>s\) (recall that \(A(n,t)\) can only change at time \(t\), for example when a job arriving at \(t\) sees \(n\) in the system. But since \(L(t) > n+1\) for \(t>s\), this will never happen after \(s\).) As \(A(n,t)\) remains finite, \(\lim_{t\to\infty}A(n,t)/t=0\).
When \(\lambda\neq \delta\), is \(\pi(n)\geq \delta(n)\)?
Hint
Solve Ex 4.5.6 first. Use that \(\lambda \geq \delta\) always holds. Thus, when \(\lambda \neq \delta\), necessarily \(\lambda > \delta\). What are the consequences of this inequality; How does the queue length behave as a function of time?
Solution
Solution, for real
The assumptions lead us to conclude that \(\lambda > \delta\). As a consequence, the queue length must increase in the long run (jobs come in faster than they leave). Hence, \(A(n,t)/t \to 0\) for all \(n\), and \(D(n,t)/t\to 0\). Consequently, \(\pi(n) = \delta(n) = 0\), which is the only sensible reconciliation with Eq. (4.6.7).
While Eq. is true for the \(M/M/1\), it is not true for the \(M/G/1\) queue. Why?
Solution
Solution, for real
By the memoryless property of the exponentially distributed service times of the \(M/M/1\) queue, the remaining service time of a job in service, if any, is \(\Exp{\mu}\). Therefore, at an arrival moment, all jobs in the system (whether in service or not) have the same expected duration. Hence, the expected time to spend in queue equals the expected number of jobs in the system times the expected service time of each job, i.e., \(\E{\W} = \E \L \E S\). Note that we use PASTA to see that the expected number of jobs in the system at an arrival is \(\E{\L}\). For the \(M/G/1\) queue, the remaining service time of a job in service (if any) does not have the same distribution as the jobs in the queue. Hence, for the \(M/G/1\) queue, the expected time in queue is not \(\E \L \E S\).