Consider a single-server queue where arrivals are Poisson with rate $10$ per hour. An arriving customer, upon finding $n$ in the system, departs the system with probability $p_n = \frac{n}{n+1}$ (so, as the system becomes more congested, arriving customers are more likely to go elsewhere without ever entering the line.) Suppose that the time to service each customer is exponential with rate $10$ per hour.

(a) Find the birth and death rates

(b) Find the expected time for the system to reach $3$ customers starting from the empty system.

My attempt: (a) The birth rate is $10q_n = \frac{10}{n+1}$, and the death rate is $\frac{10n}{n+1}$.

(b) My thought is: I tried forming the recusion formula by letting $E_i =$ expected time to reach $i$ customers. Now, $E_{i} = \frac{10}{10*2+10}E_{i-1} + \frac{20}{20+10}E_{i+1}$ with $E(0) = 0$ and $E(1) = 6$ minutes. Thus $E(2) = 9$ and $E(3) = (9 - 2)\frac{3}{2} = \fbox{$10.5$}$ minutes. Is this correct?

My question: I am not sure at all about my solution above. Could anyone give me some thoughts in case my way to solve this one was completely wrong?


The death rate here, i.e. the rate to go from $n$ to $n-1$ when $n \geq 1$, is just $10$ uniformly. It has nothing to do with the customers that leave the system before properly entering it; they never change the state.

The birth rate here is analogous to what happens in the Metropolis dynamics: you "try" to go from $n$ to $n+1$ with rate $10$ but you only succeed with probability $\frac{1}{n+1}$, which is effectively the same as actually going from $n$ to $n+1$ with rate $\frac{10}{n+1}$ (which is what you said). This is a nontrivial but ultimately elementary fact: the sum of $Geo(p)$-many independent exponential random variables with common rate $\lambda$, where the $Geo(p)$ variable is independent of the exponential variables, is an exponential random variable with rate $p \lambda$.

  • $\begingroup$ Many thanks for your help Ian. How do you think of my solution to part (b)? Of course I need to use the new birth rate to plug in, but is the method correct? $\endgroup$ – user177196 Oct 25 '16 at 17:28
  • $\begingroup$ You should instead take $E_i $ to be the team to get to 3 customers starting from $i $ customers and then derive a recurrence from there. (Also note that the answer should clearly be at least 10+20+30 because that would be the mean time if no service were offered.) $\endgroup$ – Ian Oct 25 '16 at 18:02
  • $\begingroup$ Thank you so much. Is the recurrent $E_{i} = \frac{10}{10+\frac{10}{i+2}}E_{i+1} + \frac{\frac{10}{i}}{\frac{10}{i} + 10}E_{i-1}}$? The reason is because to get from $E_{i+1}$ to $E_i$, the person who arrives must be BEFORE one person who "dies" from the system, and in the system currently having $n$ people, the arrival time ($T_1$) and death time ($T_2$) are exponential random variable with rate $\frac{10}{n+1}$ and $10$, respectively. It's a bit difficult to compute $P(T_1<T_2)$ as the birth rate is not constant here, but changing based on the number of the people currently in the system. $\endgroup$ – user177196 Oct 25 '16 at 18:24
  • $\begingroup$ In general the probability to go from $i$ to $j$ in one step of a CTMC is $\frac{q_{ij}}{\sum_{k \neq i} q_{ik}}$. (This defines the embedded DTMC in a CTMC, also called the "jump chain".) So $E_i$ is given by the sum over $j$ of $E_j+1$ (since it takes a step to to go to $j$) times the probability to go to $j$ from $i$. $\endgroup$ – Ian Oct 25 '16 at 19:28
  • 1
    $\begingroup$ I have $E_0=\frac{1+10E_1}{10}$,$E_1=\frac{1+5E_2+10E_0}{15},E_2=\frac{1+\frac{10}{3}E_3+10E_1}{\frac{10}{3}+10},E_3=0$, which gives $2$ indeed. $\endgroup$ – Ian Oct 26 '16 at 0:45

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.