# Birth and Death Process Question (Queuing)

A small shop has two people who can each serve one customer at a time. There is also space for two customers to wait. Anyone who arrives and sees that the shop is full will go to another store. Customers arrive according to a Poisson process of rate $\lambda$ per hour. The amount of time required to serve a customer is exponentially distributed with parameter $\mu$ per hour. Let $X(t)$ be the number of customers in the store at time $t$.

Here are the questions:

1) Evaluate the long-run average values for a) the number of arriving customers per hour who wait before they get served and b) amount of time spent waiting per hour by customers in shop. Express your answer in terms of $\lambda,\mu$, and limiting probabilities $(\pi_0, \pi_1, ... )$.

2) What is the limit as $t \to \infty$ of $P(\;\textrm{nobody enters or leaves the shop during}\;[t,t+3])$? Again, express answer in terms of $\lambda,\mu$, and limiting probabilities.

Here is what I have done so far: for 1a) I know that it is asking for the long-run number of people who wait... the only time people wait is when the store is in state 3 in the long run or state 4... so would this long-run value be $\pi_3 + \pi_4$? It just seems too easy for that to be the answer...

for 2) I tried conditioning on time $t$ but I was unable to proceed after the first step...

-

1b: I'm going to interpret this as asking for the long-run average amount of time a customer spends waiting in the shop. (I find "average amount of time spent... per hour" a bit confusing.) If the shop is in state 0 or 1 when a customer arrives, there is no waiting. If the shop is in state 2 when a customer arrives, the customer has to wait until the next of the two people currently being served is finished. This is the minimum of two independent exponential($\mu$) random variables, which is known to have an exponential$(2\mu)$ distribution. Thus the mean wait time if a customer enters when the shop is in state 2 is $\frac{1}{2\mu}$. If the shop is in state 3 when a customer arrives, then the customer has to wait until the next two people being served are finished. This would be the sum of two independent exponential$(2\mu)$ random variables and is known to have an Erlang$(2,2\mu)$ (or gamma$(2,2\mu)$) distribution. Thus the mean wait time if a customer enters when the shop is in state 3 is $\frac{2}{2\mu} = \frac{1}{\mu}$. So the long-run average amount of time a customer spends waiting is $\frac{\pi_2}{2\mu} + \frac{\pi_3}{\mu} = \frac{1}{\mu}(\frac{\pi_2}{2} + \pi_3)$.

2: This is $\sum_{k=0}^4 P(\text{no arrivals and no departures in 3 hours|Shop is in state }$k$) \pi_k$. To find the probabilities it would be helpful to draw a rate transition diagram. Since that's going to be hard to typeset, I'll put the information in a table instead.

State    Transition rate to state i-1   Transition rate to state i+1
0                NA                              λ
1                μ                               λ
2                2μ                              λ
3                2μ                              λ
4                2μ                              NA


Because arrivals and departures are exponentially distributed, the probability of no arrivals and no departures in three hours in (for example) state 1 is $e^{-3\lambda} e^{-3\mu}$. Putting all of this together, the long-run probability that nobody enters or leaves the shop in three hours is $e^{-3\lambda} \pi_0 + e^{-3\lambda} e^{-3\mu} \pi_1 + e^{-3\lambda} e^{-6\mu}\pi_2 + e^{-3\lambda} e^{-6\mu}\pi_3 + e^{-6\mu} \pi_4$.

-
I realize this is well after you've taken your test, but hopefully this is still helpful anyway. :) – Mike Spivey Apr 20 '11 at 17:32

Re: "1) Evaluate the long-run average values for a) the number of arriving customers per hour who wait before they get served"

For this to happen, someone has to arrive when there's 2 or 3 people already in the store. The arrival (birth) rate is $\lambda$, and the probability that there's 2 or 3 people in the store is $\pi_2+\pi_3$. So the rate is $\lambda(\pi_2+\pi_3)$.

-
After such an arrival, the system will increment its state, that is, go to $2\to 3$ or $3 \to 4$. You can therefore write an equation for the transition rate from 2 or 3 to 3 or 4. In addition to this, you will need transition rates for the various other things that can happen. When you're done, you should be able to solve for $\pi_j$ in terms of $\lambda$ and $\mu$. – Carl Brannen Apr 6 '11 at 20:46