3
$\begingroup$

Suppose there are 3 bank tellers, all currently occupied with a customer. You are waiting in line (and there are no other customers that will come in after you). All service times are iid exponential random variables with parameter $\lambda$. You must find the probability that you are the last to leave.

I have set up this problem as follows:

  • Denote $X_a, X_b, X_c$ as the service times for the currently served customers.
  • Denote $X_d$ as your service time (i.e. the time you will spend at the counter with a teller).
  • Denote $X_- = min\{X_a , X_b, X_c\}$ as the shortest service time of the currently served customers.
  • Denote $X_+ = max\{X_a, X_b, X_c\}$ as the longest service time of the currently served customers.

With this setup, we must computer $P[X_d + X_- > X_+]$. So far, I have established the following:

  • $P[X_- > x] = e^{-3\lambda x}$
  • $P[X_+ > x] = 1 - (1 - e^{-\lambda x})^3$

I'm a bit stuck on how to move on from here. Any guidance would be awesome. Thanks.

$\endgroup$

2 Answers 2

3
$\begingroup$

Part I: Intuitive answer.

This was already describe by @BruceET. I'll just say it again with some different words...

The answer is $1/3$.

The exponential distribution is "memoryless". From the time you begin being serviced, think of the two others exponential clocks as being "reset": the additional time required for service by the each of the other two is still $\mbox{Exp}(\lambda)$, and all three times are independent. Therefore you'll as equally likely to finish last as any of the two others, and since the probability that any two finish at the same time is zero, the probability you finish last is $1/3$. This generalizes to any number of tellers.

Part II. Proof.

Here's a detailed analysis, which could be made shorter (and closer in spirit to Part I), but I decided to expand on the joint distributions because it is very informative and useful for other problems.

$X_1,X_2,X_3$ are times until tellers finish with current customers.

You'll begin at time $Y_1=\min(X_1,X_2,X_3)$. Let $Y_3=\max (X_1,X_2,X_3)$, and let $Y_2$ be the remaining variable (since all three are distinct with probability $1$, $Y_2$ is defined except on an event of probability $0$).

Your service time is $T\sim \mbox{Exp}(\lambda)$, independently of all the rest. You'll be last if and only if $Y_1+T > Y_3$. Denote this event by $A$.

Consider the joint distribution of $X_1,X_2,X_3$ conditioned on $Y_1=X_1<X_2<X_3=Y_3$. The latter event has probability $1/6$, and therefore the joint density is

$$ 6 \lambda^3 e^{-\lambda x_1} e^{-\lambda x_2} e^{-\lambda x_3} {\bf 1}_{\{x_1 < x_2\}}{\bf 1}_{\{x_2<x_3}\}.$$

The can be written as

$$ 6 \lambda^3 e^{-3\lambda x_1} e^{-2\lambda (x_2-x_1) } e^{-\lambda (x_3-x_2)}{\bf 1}_{\{x_2-x_1 >0\}} {\bf 1}_{\{x_3-x_2>0\}}.$$

By considering all $6$ permutations, we conclude from the formula above that

  1. $Y_1 \sim \mbox{Exp}(3\lambda)$;

  2. $Y_2-Y_1\sim \mbox{Exp}(2\lambda)$; and

  3. $Y_3-Y_2\sim \mbox{Exp}(\lambda)$; with

  4. $Y_1,Y_2-Y_1,Y_3-Y_2$ independent.

Therefore, the event $A$, $Y_1 + T > Y_3$, can be rewritten as $Y_1 +T > Y_1 + (Y_2-Y_1) + (Y_3-Y_2)$ or $T> (Y_2 -Y_1) + (Y_3-Y_2)$.

Since $T\sim \mbox{Exp}(\lambda)$ and is independent of $Y_1,Y_2,Y_3$, we conclude that

$$P(A) = E[e^{-\lambda [(Y_2-Y_1) + (Y_3-Y_2)]}]=E[e^{-\lambda (Y_2-Y_1)}] E[e^{-\lambda(Y_3-Y_2)}].$$

Recall that the MGF of $\mbox{Exp}(\rho)$ at $t$ is equal to $ \frac{\rho}{\rho -t}$, and therefore the righthand side is

$$ \frac{2\lambda}{2\lambda +\lambda}\frac{\lambda}{\lambda + \lambda}=\frac 13 $$

$\endgroup$
0
2
$\begingroup$

By the no memory property, it makes no difference how long each of the customers ahead of you have been 'in service' with their tellers.

As soon as you start with one of the tellers, by the no-memory property, all three waiting times to finish have the same distribution. So you have one chance in three of being last to leave.

The simulation below is not a proof, but it gives an idea of how long the waiting times are. In the simulation, $\lambda=0.1$ per min. for all tellers and you have just started with teller #1.

There are 10 million iterations; x1,x2,x3 are waiting times at each teller, w is the maximum waiting time among the three, mean(x1==w) is the proportion of instances in which you finish last. (With 10 million iterations, one can expect about two place accuracy in service times.)

set.seed(2021)
x1 = rexp(10^7, .1)
x2 = rexp(10^7, .1)
x3 = rexp(10^7, .1)
w = pmax(x1,x2,x3)
mean(w)
[1] 18.33176

After you begin service (in about $\frac{1}{3\lambda}=3.33$ minutes), you can expect to finish after about $18.33$ additional minutes.

$\endgroup$
2
  • 1
    $\begingroup$ I believe you can formalize an answer using the memoryless property. This is very interesting - thanks for the insight. $\endgroup$
    – oschwartz
    May 25, 2021 at 0:54
  • $\begingroup$ Glad you like the idea of doing it in terms of the no memory property.// Total average time for 'max' after beginning service: Wait for minimum of 3, wait for min of remaining 2, wait for last: 3.33 + 5 + 10 = 18.33. (Works easily only if all three servers have same rate.) $\endgroup$
    – BruceET
    May 25, 2021 at 3:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .