Consider two users who arrive to a system with exponential arrival times with parameters $\lambda_a$ and $\lambda_b$. Once they arrive, the users stay in the system for an exponentially distributed time (parameters $\mu_a$ $\mu_b$) before leaving. The four exponential RVs are independent. What is the probability that A arrives before B AND leaves after B.

Letting $T_a$, $T_b$ denote the arrival times of each, and $S_a$, $S_b$ denote the service times. This probability is then $Pr(T_a < T_b \cap T_a + S_a > T_b + S_b)$ We can solve this by conditioning but it gets quite messy, is there a simpler way to tackle this? Perhaps something involving the memoryless property of the exponential distribution?


There are three exponential time 'contests', and each is independent of the others.

First, A must arrive before B. Second (no memory), B must arrive before A finishes being served. Third (no memory), B must finish service before A finishes service.

Thus, the desired probability is the product of three ratios: $$\frac{\lambda_a}{\lambda_a + \lambda_b} \frac{\lambda_b}{\mu_a + \lambda_b} \frac{\mu_b}{\mu_a + \mu_b}.$$

For example, if both arrival rates are 1 and both service rates are 2, then the result is $(1/2)(1/3)(1/2) = 1/12.$

The following brief simulation in R illustrates to about three-place accuracy:

 ta = rexp(10^6, 1);  tb = rexp(10^6, 1)
 sa = rexp(10^6, 2);  sb = rexp(10^6, 2)
 mean(ta < tb & ta+sa > tb+sb)
 ## 0.082959
  • $\begingroup$ Thanks I think that makes sense. Can a similar approach be used to find the expected time of the final departure? I know if I define Xa = Ta+Sa, Xb = Tb+Sb, then this will be E[Xa | Xa > Xb]P(Xa>Xb) + E[Xb | Xa < Xb]P(Xa < Xb), but this will get messy quick it seems. $\endgroup$ – user67081 May 2 '15 at 21:34
  • $\begingroup$ Unclear. Time until departure of whom and starting from when? $E(X_a) = E(T_a)+E(S_a) = 1/\lambda_a + 1/\mu_a.$ The sum of two exponentials is not gamma unless the rates are equal. PDF at arxiv.org/pdf/1307.3945 $\endgroup$ – BruceET May 2 '15 at 22:15
  • $\begingroup$ Essentially the quantity i'm looking for would be E[max(Sa+Ta, Sb+Tb)] $\endgroup$ – user67081 May 2 '15 at 23:27
  • $\begingroup$ As is the case for very many queueing problems, simulation is a lot easier than analysis. (The original problem really clever precisely because an analytic solution is not difficult.) For simulation, append 'mean(pmax(ta+sa,tb+sb))' to the first two lines in my Answer. I got 2.08. The expectation of each element of the max is 1.5, so at least that seems reasonable for the expectation of the max. $\endgroup$ – BruceET May 2 '15 at 23:41
  • $\begingroup$ I agree, simulation is far simpler, but this is a textbook problem so I'm expecting there is another trick for solving it. Unfortunately a sum of exponentials no longer has the memoryless property which would have made finding E[max(Sa+Ta,Sb+Tb)] easy $\endgroup$ – user67081 May 3 '15 at 19:46

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.