Arrival distribution of M/M/1 queue

Question

Show that the arrivals $A_n$ of an M/M/1 queue $X$ with initial distribution $\eta_i := \rho^{i-1}(1-\rho)$ ($i \ge 1$), where $\rho$ is the traffic intensity, satisfy $X_{A_n} \sim \ \eta$.

I understand that the stationary distribution of the queue is $$\pi_i =\rho^i(1-\rho)$$ for $i \ge 0$, and at an arrival the queue cannot be empty, so the queue size should intuitively have the same geometric property but excluding the state 0. How do I show this?

Answer 1

A more elementary approach than the other answer is as follows:

Recall that $\rho=\lambda/\mu$, where $\lambda$ is the arrival rate and $\mu$ the service rate.

For $j \ge 2$, $$\mathbb{P}(X_{A_1}=j) = \sum_{i=j-1}^\infty\mathbb{P}(\text{there are exactly} \ n\ \text{departures before the first arrival}) \\ = \sum_{i=j-1}^\infty\rho^{i-1}(1-\rho)\left(\frac{\mu}{\lambda+\mu}\right)^{i-j+1}\left(\frac{\lambda}{\lambda+\mu}\right)\\ =\sum_{k=j-2}^\infty\rho^k\left(\frac{\mu}{\lambda+\mu}\right)^k(1-\rho)\left(\frac{\lambda}{\lambda+\mu}\right)\left(\frac{\mu}{\lambda+\mu}\right)^{-j+2}\\=\sum_{k=j-2}^\infty\left(\frac{\lambda}{\lambda+\mu}\right)^k(1-\rho)\left(\frac{\lambda}{\lambda+\mu}\right)\left(\frac{\lambda+\mu}{\mu}\right)^{j-2}\\=\frac{\left(\frac{\lambda}{\lambda+\mu}\right)^{j-2}}{\frac{\mu}{\lambda+\mu}}(1-\rho)\left(\frac{\lambda}{\lambda+\mu}\right)\left(\frac{\lambda+\mu}{\mu}\right)^{j-2}\\=\left(\frac{\lambda}{\mu}\right)^{j-2}(1-\rho)\left(\frac{\lambda}{\mu}\right)\\=\rho^{j-1}(1-\rho)$$ as required. For $j=0$, note that the queue is non-empty when a customer has just arrived so $\mathbb{P}(X_{A_1}=0)=0$. For $j=1$, the distribution must sum to 1, yielding $\mathbb{P}(X_{A_1}=1)=1-\rho$.

Hence $X_{A_1} \sim \eta$. By the strong Markov property (for the M/M/1 queue), $(X_{A_n})_{n\ge0}$ is a discrete-time Markov chain which starts in $\eta$ and has its first arrival given by $\eta$, so the Markov property (for the chain), $\forall n\ge0: X_{A_n} \sim \eta$.

$\square$

Answer 2

Poisson arrivals see time averages (PASTA). This is one of the basic building blocks of queueing theory. In the case of an M/M/1 queue, the state seen by the arrivals, $X_{A_n}$, is distributed according to a geometric distribution, $\eta$.

The proof of this result can be found, for instance, in Mor Harchol Balter book.

Harchol-Balter, M. (2013). Performance modeling and design of computer systems: queueing theory in action. Cambridge University Press.

Let $A(t,t+\delta)$ be the event that an arrival occurs during the interval $[t,t+\delta]$. Let $a_n$ be the probability that such arrival sees $n$ users in the system (without counting the arriving user). Let $N(t)$ be the number of users in the system at time $t$.

In page 244 of the book, we have

\begin{align} a_n &= \lim_{t \rightarrow \infty} \lim_{\delta \rightarrow 0} P(N(t)=n | A(t,t+\delta) ) \\ &=\lim_{t \rightarrow \infty} \lim_{\delta \rightarrow 0} \frac{ P( A(t,t+\delta) | N(t)=n)P(N(t)=n)}{P(A(t,t+\delta) )} \\ &= \lim_{t \rightarrow \infty} P(N(t)=n) = \pi_n \end{align}

Note that $a_n$ in the derivation above is the probability that an arrival sees $n$ customer already in the system. Immediately after the arrival, the system will contain $n+1$ customers, including the new customer. Hence, the probability that the system will contain $i=n+1$ customers after the arrival is $$\eta_i=\rho^{i-1} (1-\rho),$$ for $i=1, 2, \ldots$

Note also that \begin{align} a_n &= \lim_{t \rightarrow \infty} \lim_{\delta \rightarrow 0} P(N(t)=n | A(t,t+\delta) ) \\ &=\lim_{t \rightarrow \infty} \lim_{\delta \rightarrow 0} P(N(t+\delta)=n+1 | A(t,t+\delta) ) \\ &=\eta_{n+1} \end{align}