# What does a customer see when it begins to be served in $M/M/1$ queue?

In queueing theory, the PASTA (Poisson Arrivals See Time Averages) principle [wiki] justifies $a_n = P_n$ where $$a_n = \text{proportion of customers that find } n \text{ customers in the system when they arrive}$$ and, $$P_n = \lim_{t \to \infty} P \{ X(t) = n \}$$ ($X(t) \text{ here denotes the number of customers in system at time } t$).

However, I am now more interested in the moment when a customer begins to be served, rather than when it arrives.

Specifically, I focus on the case of $M/M/1$ queue (i.e., a single-server exponential queueing system with FCFS service discipline) and consider

$$s_n = \text{proportion of customers that find } n \text{ in the } M/M/1 \text{ queue when it begins to be served.}$$

My question is:

Question: What does a customer see when it begins to be served in $M/M/1$ queue with the FCFS service discipline?

In other words, what is the relationship between $s_n$ and $P_n$ (or, the relationship between $s_n$ and $a_n$)?

• Are you assuming a FCFS service discipline? In this case the length of the queue is the number of customers that have arrived behind the tagged customer. You can therefore use the result for M/M/1 queue response time and the fact that customers arrive according to a Poisson process to compute the probabilities you wish to find. – Gareth May 9 '14 at 9:02
• @Gareth Yes, it assumes the FCFS service discipline. I have added it to the post. Thanks for pointing it out. – hengxin May 9 '14 at 9:23
• @Gareth I am still not able to solve it. Could you please give me a further hint or a start-up formula? – hengxin May 9 '14 at 10:53
• Got something from the answer below? – Did Feb 3 '15 at 12:32
• @Did I have almost forgotten this problem. Sorry for that. I will check it when I return to it later. Thanks for your efforts. – hengxin Feb 3 '15 at 13:03

Let $X$ denote the number of customers in the queue when a new customer arrives, the new customer excepted and the customer being served included, if any. Let $T$ denote the time it takes to serve these $X$ customers. Let $N$ denote the number of customers arriving during a time interval of length $T$. One asks for the distribution of $N$.
For a stationary M/M/1 queue, $X$ is geometrically distributed with parameter $\rho=\lambda/\mu$, that is, $P(X=x)=\rho^x(1-\rho)$ for every integer $x\geqslant0$. Conditionally on $X=0$, $T=0$. Conditionally on $X=x$ with $x\geqslant1$, the distribution of $T$ is gamma with parameters $(x,\mu)$. Conditionally on $T=0$, $N=0$. Conditionally on $X=x$ and $T=t$ with $t\gt0$, the distribution of $N$ is Poisson with parameter $\lambda t$.
This decomposition in terms of conditional distributions yields the distribution of $N$ through careful computations. Namely, for every positive integer $n$, $$P(N=n)=\sum_{x=1}^\infty\rho^x(1-\rho)\int_0^\infty\frac{\mu^x}{\Gamma(x)}t^{x-1}\mathrm e^{-\mu t}\mathrm e^{-\lambda t}\frac{(\lambda t)^n}{n!}\mathrm dt,$$ that is, $$P(N=n)=\frac{1-\rho}{n!}\sum_{x=1}^\infty\frac{\lambda^{x+n}}{\Gamma(x)}\int_0^\infty t^{x+n-1}\mathrm e^{-(\lambda+\mu)t}\mathrm dt,$$ or, equivalently, $$P(N=n)=\frac{1-\rho}{n!}\sum_{x=1}^\infty\frac{\lambda^{x+n}}{\Gamma(x)}\frac{\Gamma(x+n)}{(\lambda+\mu)^{x+n}}=\frac{1-\rho}{n!}\sum_{x=1}^\infty\frac{\Gamma(x+n)}{\Gamma(x)}\frac1{\sigma^{x+n}},\qquad\sigma=1+\frac1\rho.$$ Note that, for every $\sigma\gt1$, $$\sum_{x=1}^\infty\frac{\Gamma(x+n)}{\Gamma(x)}\frac1{\sigma^{x+n}}=(-1)^n\frac{\mathrm d^n}{\mathrm d\sigma^n}\sum_{x=1}^\infty\frac1{\sigma^{x}}=(-1)^n\frac{\mathrm d^n}{\mathrm d\sigma^n}\left(\frac1{\sigma-1}\right)=\frac{n!}{(\sigma-1)^{n+1}},$$ hence, for every $n\geqslant1$, $$P(N=n)=(1-\rho)\rho^{n+1},$$ and, considering the complement to $1$ of the sum, $$P(N=0)=(1-\rho)(1+\rho).$$ One can note that $N$ is distributed as $\max\{G-1,0\}$ where $G$ is geometrically distributed with parameter $\rho$ in the sense that $P(G=n)=(1-\rho)\rho^n$ for every $n\geqslant0$.
• Can you explain why $P(N=0)=(1-\rho)(1+\rho)$? I would think that since the the probability of nobody arriving consists of the probability of nobody being served OR one or more person being served, $P(N=0)$ should be just $\mu$ – CodyBugstein Feb 3 '15 at 10:21