# Probability that one station becomes empty before another.

Question:

There are 2 stations A and B in series having i and j customers respectively. Customers after being served at station A are routed to station B. 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 station A becomes empty before station B?

• Are you assuming no more arrivals to $\bf{A}, \bf{B}$? – PiE May 13 '17 at 1:51
• @PMF - No more customers arrive at station A. When the customers have been served at station A, they are routed to station B where they are served again. So, arrivals take place at station B. – RSA May 13 '17 at 22:14
• This is a good queueing question! Thanks. – PiE May 13 '17 at 22:23

We can separate the event that queue B empties first into $i$ disjoint cases: in the $k^{\text{th}}$ case, for $0 \le k < i$, queue B becomes empty for the first time after $k$ customers have been served at station A (so, a total of $j+k$ customers are served at station B).
Every time a customer is served from either station, the number of customers in queue B changes by either $+1$ or $-1$. So we can represent an outcome in the $k^{\text{th}}$ case as a lattice path from $(0,j)$ to $(2k+j,0)$, whose steps are all either $(+1,+1)$ or $(+1,-1)$, and which never touches $y=0$ before the end. Each outcome has a probability of $\left(\frac{\mu_A}{\mu_A + \mu_B}\right)^k \left(\frac{\mu_B}{\mu_A + \mu_B}\right)^{j+k}$ of occurring, so it remains to count the number of such lattice paths.
A lattice path of the kind we want is, equivalently, one from $(0,j)$ to $(2k+j-1,1)$ that never touches $y=0$. The total number of paths like this, without the $y=0$ restriction, is $\binom{2k+j-1}{k}$: over $2k+j-1$ steps, we take $k$ $(+1,+1)$ steps and $j+k-1$ $(+1,-1)$ steps. If a path does touch $y=0$, take the segment of the path after the first such event, and reflect it through the $x$-axis. This is a bijection between paths from $(0,j)$ to $(2k+j-1,1)$ that touch $y=0$, and paths from $(0,j)$ to $(2k+j-1,-1)$, all of which cross $y=0$. There are $\binom{2k+j-1}{k-1}$ paths of the latter kind, so excluding them, we get $$\binom{2k+j-1}{k} - \binom{2k+j-1}{k-1}$$ lattice paths of the kind we want.
So the total probability in the $k^{\text{th}}$ case is $$\left(\frac{\mu_A}{\mu_A + \mu_B}\right)^k \left(\frac{\mu_B}{\mu_A + \mu_B}\right)^{j+k} \left(\binom{2k+j-1}{k} - \binom{2k+j-1}{k-1}\right)$$ and we get (the complement of) the final answer by summing over all $k$: $$\sum_{k=0}^{i-1} \left(\frac{\mu_A}{\mu_A + \mu_B}\right)^k \left(\frac{\mu_B}{\mu_A + \mu_B}\right)^{j+k} \left(\binom{2k+j-1}{k} - \binom{2k+j-1}{k-1}\right).$$ It doesn't appear that this expression simplifies well except as some sort of hypergeometric thing, though I admit that all the work I did in that direction was plug it into Mathematica.