Probability that queue A becomes empty before queue B?

Question

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.

Answer 1

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.