3
$\begingroup$

Suppose there are 2 independent queues A and B having m and n customers respectively. The service time of each of the queues are Exponentially distributed with service rate as $\mu_{A}$ and $\mu_{B}$. There are external Poisson ($\lambda$) arrivals to only queue A, i.e., queue A behaves like an M/M/1 queue while queue B has no external arrivals. What is the probability that queue A becomes empty before queue B? What is the probability that queue B empties before queue A?

My response: The mean time to empty a queue with $m$ customers and external arrivals of customers is $m\left(\mu_{A}-\lambda\right)^{-1}$. Thus, to determine the required probability, I adjust the value of $\mu_{A}$ to $\mu_{A} - \lambda$, which is the net rate at which the queue length of type $i$ customers decreases at station 1. Now, the M/M/1 queue becomes static queue with no arrivals but net service rate as $\mu_{A} - \lambda$. Now, I compare the probability that sum of m exponential random variable is less than the sum of n random variable. Is this approach correct? If so, why? If not, why (and how should I do it otherwise)?

$\endgroup$
2
  • $\begingroup$ What have you done so far? $\endgroup$
    – saulspatz
    Jun 12, 2018 at 20:56
  • $\begingroup$ @saulspatz, I've edited the question to show my approach. $\endgroup$
    – RSA
    Jun 12, 2018 at 21:04

1 Answer 1

1
$\begingroup$

@RSA Adjusting the service rate $\mu_A$ is not the right way to go. Reduction of the service rate is not the same as turning off the arrival process.

One of the ways to solve your problem is to use the total probability formula.

Let us start with the queue $\bf B$. Since it has $n$ customers and no new arrivals then the probability that it becomes empty in the interval $[x,x+dx)$ is equal to $f_B(x) dx$, where $$ f_B(x)= {\mu_B^n x^{n-1} \over (n-1)!}e^{-\mu_B x}, x \ge 0. $$ This is because the time until queue $\bf B$ is empty equals the sum of $n$ exponentials with rate $\mu_B$.

Let us denote by $f_A(x) dx$ the probability that queue $\bf A$ becomes empty in the interval $[x,x+dx)$. Then the probability that queue $\bf A$ becomes empty before queue $\bf B$, i denote it for brevity by $Pr({\bf A}<{\bf B})$, is equal to $$ Pr({\bf A}<{\bf B})=\int_0^\infty f_B(u) du \int_0^u f_A(v) dv. $$

What is left to do is to determine $f_A(x)$. It is a little bit more difficult. I will use the trick from queueing theory. Since queue $\bf A$ is $M/M/1$ and it has initially $m$ customers thae the time until the queue is empty is equal to sum of $m$ busy periods. See the expression for the busy period, for example, here https://en.wikipedia.org/wiki/M/M/1_queue. Thus $f_A(x)$ is $m$th convolution of $m$ busy periods. This is not an easy thing to handle since the expression for the busy period involves the Bessel function. But one can use the Laplace Transform (LT) technique. Introduce the notation $$ {\tilde f}_A(s)=\int_0^\infty e^{-sx}f_A(x)dx. $$ From the properties of LT it follows that ${\tilde f}_A(s)=(\mbox{LT of one busy period})^m$ i.e. $$ {\tilde f}_A(s)=\left ( {\lambda + \mu_A + s - \sqrt{(\lambda + \mu_A + s)^2-4 \lambda \mu} \over 2 \lambda} \right )^m. $$ It is also very useful to notice that the $i$th derivative of ${\tilde f}_A(s)$ with respect to $s$ is equal to $$ ({\tilde f}_A(s))^{(i)}=\int_0^\infty (-1)^i x^i e^{-sx}f_A(x)dx. $$ Now it is straghtforward to calculate $Pr({\bf A}<{\bf B})$. Denote by $F_A(x)=\int_0^x f_A(u)du$ and $F_B(x)=\int_0^x f_B(u)du$. Note that $F_A(0)=F_B(0)=0$ and $F_A(\infty)=F_B(\infty)=1$. Then $$ Pr({\bf A}<{\bf B})=\int_0^\infty f_B(u) F_A(u) du =1-\int_0^\infty F_B(u) f_A(u) du= $$ $$ =\sum_{j=0}^{n-1} \int_0^\infty {\mu_B^j u^{j} \over j!}e^{-\mu_B u} f_A(u) du = \sum_{j=0}^{n-1} {\mu_B^j \over j!} \int_0^\infty u^{j} e^{-\mu_B u} f_A(u) du= $$ $$ = \sum_{j=0}^{n-1} {(-\mu_B)^j \over j!} ({\tilde f}_A(\mu_B))^{(j)}. $$

This is the complete answer and all you are left to do is to compute derivatives. This can be done analytically, but the expressions are too cumbersome. Numerical procedure is very simple instead.

Of course, $Pr({\bf A}>{\bf B})=1-Pr({\bf A}<{\bf B})$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .