# Probability that queue A becomes empty before queue B?

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.

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.

• This should help, thanks a lot! :)
– RSA
Mar 29, 2017 at 19:08
• Hi, I have quick question on this. Why do we assume that the required probability is X $\geq$ i instead of just X=i?
– RSA
May 17, 2017 at 19:49
• 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. May 17, 2017 at 20:10
• Thank you. That cleared all my doubts. :)
– RSA
May 17, 2017 at 20:14
• 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)?
– RSA
Jun 12, 2018 at 21:37