3
$\begingroup$

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$)?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gareth May 9 '14 at 9:02
  • $\begingroup$ @Gareth Yes, it assumes the FCFS service discipline. I have added it to the post. Thanks for pointing it out. $\endgroup$ – hengxin May 9 '14 at 9:23
  • $\begingroup$ @Gareth I am still not able to solve it. Could you please give me a further hint or a start-up formula? $\endgroup$ – hengxin May 9 '14 at 10:53
  • $\begingroup$ Got something from the answer below? $\endgroup$ – Did Feb 3 '15 at 12:32
  • $\begingroup$ @Did I have almost forgotten this problem. Sorry for that. I will check it when I return to it later. Thanks for your efforts. $\endgroup$ – hengxin Feb 3 '15 at 13:03
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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$ $\endgroup$ – CodyBugstein Feb 3 '15 at 10:21
  • $\begingroup$ @Imray "the probability of nobody arriving consists of the probability of nobody being served OR one or more person being served" No idea why you think that, which seems obviously wrong. Note that "the probability of nobody being served OR one or more person being served" is 1. $\endgroup$ – Did Feb 3 '15 at 11:44
  • $\begingroup$ the way I see it, three things can happen in the system. Someone could arrive, someone could be served, or nothing at all. If nobody arrives, then either someone was served or nothing happened at all. $\endgroup$ – CodyBugstein Feb 3 '15 at 11:47
  • $\begingroup$ @Imray ?? Is all this even related to the setting of the present question? It does not seem so. If you have a specific question, I suggest that you post it as a new question, instead of diverting answers to questions by others to try to get your misconceptions dispelled. $\endgroup$ – Did Feb 3 '15 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.