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?

  • $\begingroup$ Are you assuming no more arrivals to $\bf{A}, \bf{B}$? $\endgroup$ – PiE May 13 '17 at 1:51
  • $\begingroup$ @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. $\endgroup$ – RSA May 13 '17 at 22:14
  • $\begingroup$ This is a good queueing question! Thanks. $\endgroup$ – 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.

This problem is very similar to the Dyck path counting problem (one characterization of the Catalan numbers), and just like that problem, we can solve it by the reflection method.

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.

  • $\begingroup$ As per my understanding, the lattice path represent the total number of events that need to happen. At Queue A, a total of k events happen and at Queue B, a total of j+k events happen. We need to find out the number of ways k failure at Queue A and j+k success at Queue B. However, in determining the total number of such events, there are few events in which j+k success took place before k failures. In such case, Queue B becomes empty before the required k units are served at Queue A. Hence, we need to exclude those events. $\endgroup$ – RSA May 23 '17 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.