1
$\begingroup$

Question:

Suppose, there are 2 queues A and B having i and j customers respectively. The service time of each of the queues are Exponentially distributed with parameter $\mu_a$ and $\mu_b$ (i.e., mean service time of one customer in Queue A is 1/$\mu_a$ and of Queue B is 1/$\mu_b$). What is the probability that queue A becomes empty before queue B?

My approach:

Assume Exponentially distributed R.V. $X_a$ and $X_b$ ~ Service time of each customer in respective queues

Pr{Queue A becomes empty before Queue B}

=Pr{i customers in Queue A are served before j customers in Queue B}

=Pr{Sum of i $X_a$ < Sum of j $X_b$} (Since we can't directly add Exponentially distributed random variables.

=...

How do I proceed after this since the sums are Erlang distributed and I'm not able to tackle this.

$\endgroup$

1 Answer 1

1
$\begingroup$

Thinking about the Erlang sums is adding in lots of information you ultimately don't need.

Instead, think of it this way: for as long as both queues have people in them, the next customer to be served comes from Queue A with probability $p = \frac{\mu_A}{\mu_A + \mu_B}$, and from Queue B with probability $1-p$.

So we are interested in whether a sequence of $\operatorname{Bernoulli}(p)$ random variables will see $i$ successes before it sees $j$ failures. This is now a question about the negative binomial distribution: If $X \sim \operatorname{NB}(j; p)$, what is the probability that $X \ge i$?


There's actually a subtle point here that I should stress further. To interpret this process as a question about the negative binomial distribution, we're going to use a fictitious continuation:

  1. For as long as we've seen fewer than $i$ successes and fewer than $j$ failures, we keep flipping $\operatorname{Bernoulli}(p)$ coins coupled with the outcome of the queueing process.
  2. If we see $j$ failures, the queueing process stops (this means that Queue B is empty) and the coin-flipping process stops we've determined the value of $X$.
  3. If we see $i$ successes, the queueing process stops (this means that Queue A is empty) but the coin-flipping process does not stop. We keep flipping $\operatorname{Bernoulli}(p)$ coins until we see $j$ failures, but they're now no longer related to the queueing process in any way.

The reason we do step 3 in this way is to make $X$, the number of successes, have the nice negative binomial distribution.

The reason we're allowed to do step 3 in this way is that we're only interested in the probability of the event $\Pr[X \ge i]$. If the two processes deviate, then the question of whether $X \ge i$ or not has already been settled, and it doesn't matter what we do.

(However, we must ask if $X \ge i$, not if $X=i$: in the outcome where Queue A empties first, the fictitious continuation might see additional (fictitious) successes before it sees $j$ failures, so $X=i$ will underestimate the probability.)

Another way of thinking about the fictitious continuation is that we pretend that Queue A has infinitely many people in it, but we only care if the first $i$ people in Queue A get served before all $j$ people in Queue B get served. It's easy to see that's equivalent - but now we need to ask whether at least $i$ people from Queue A get served before Queue B is empty, rather than exactly $i$ people.

$\endgroup$
5
  • $\begingroup$ This should help, thanks a lot! :) $\endgroup$
    – RSA
    Mar 29, 2017 at 19:08
  • 1
    $\begingroup$ Hi, I have quick question on this. Why do we assume that the required probability is X $\geq$ i instead of just X=i? $\endgroup$
    – RSA
    May 17, 2017 at 19:49
  • 1
    $\begingroup$ That's a good question that points out an important missing part of my answer, so I've added the answer to include that missing part. $\endgroup$ May 17, 2017 at 20:10
  • $\begingroup$ Thank you. That cleared all my doubts. :) $\endgroup$
    – RSA
    May 17, 2017 at 20:14
  • $\begingroup$ 1. How should I proceed if one of the queue has external arrival? 2. How should I proceed if both the queues have external arrivals (like 2 competing M/M/1 queues)? $\endgroup$
    – RSA
    Jun 12, 2018 at 21:37

You must log in to answer this question.

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