3
$\begingroup$

Consider a single server queue with exponential arrival rate $2$ when the queue is empty and $1$ otherwise, and exponential departure rate $3$.

To find the invariant distribution, we solve $2\pi_0=3\pi_1$,$\pi_n=3\pi_{n+1} (n\geq 1)$ to get $\pi_0=\frac{1}{2}$, $\pi_n=\frac{1}{3^n} (n\geq 1)$. The average queue length is $L=\sum_{n=0}^\infty n\pi_n=\frac{3}{4}$.

The average time between arrivals is $\pi_0 /2+(1-\pi_0)/1=3/4$, so the average arrival rate is $\lambda:=\lim_{t\rightarrow \infty}\frac{\text{No. of Arrivals up to time } t}{t}=4/3$. By Little's Law, the average waiting time is $W=L/\lambda=9/16$.

On the other hand, a customer who arrives when there are $n$ other customers already in the queue (with probability $\pi_n$) has an expected waiting time of $(n+1)/3$. Thus, we have $W=\sum_{n=0}^\infty (n+1)\pi_n /3=(L+1)/3=7/12$, disagreeing with the above.

Where is the mistake?

$\endgroup$
1
$\begingroup$

Good question. There are two mistakes here. The first is an incorrect derivation of the rate $\lambda$. The second is because $\overline{W} \neq \sum_{n=0}^{\infty}(n+1)\pi_n/3$. See below for details.

First, I agree with your computation that: \begin{align} &\pi_0=1/2 \\ &\pi_n=(1/3)^n \quad \forall n \in \{1, 2, 3, ...\}\\ &\overline{L} = \sum_{n=1}^{\infty}n\pi_n = 3/4 \end{align}

1) The total arrival rate $\lambda$ is actually: $$ \lambda = 2\pi_0 + 1(1-\pi_0) = 1 + \pi_0 = 3/2 $$ Hence, by Little's formula: $\overline{W} = \frac{\overline{L}}{\lambda} = 1/2$.

2) Your alternative derivation for $\overline{W}$ implicitly assumes that the fraction of jobs that "see" $n$ jobs in the queueing system when they arrive is equal to $\pi_n$. If arrivals were Poisson, we could claim this by PASTA (Poisson Arrivals See Time Averages). However, arrivals are not Poisson.

Here is a correct alternative derivation: Let's make the arrivals Poisson of rate $\lambda_{new}=2$ by adding "virtual arrivals" of rate 1 when the system is busy. To make the new system equivalent to the old, suppose it works this way: If an arrival occurs when the system is empty, then it is a "true" arrival and it begins its service in the queueing system. If it occurs when the system is busy, with probability 1/2 it is a "true" arrival and it joins the queue. With prob 1/2 it is a "virtual" arrival and immediately exits with total delay 0. Now, PASTA holds for this system, and $\pi_n$ is the same as before for this system. So:

$$ \overline{W}_{new} = \pi_0 (1/3) + \sum_{n=1}^{\infty} \pi_n\frac{n+1}{6} = \frac{3}{8} $$ where we have used the fact that the expected delay, given we arrive when there are $n\geq 1$ jobs, is $\frac{1}{2}0 + \frac{1}{2}\frac{n+1}{3}$.

However, $\overline{W}_{new}$ can be decomposed into a weighted sum of the delay of true arrivals and virtual arrivals. The total rate due to true arrivals is $2-(1-\pi_0)= 3/2$ and the total rate due to virtual arrivals is $1-\pi_0=1/2$. Thus: $$ \overline{W}_{new} = \frac{3/2}{2}\overline{W}_{true} + \frac{1/2}{2}0 $$ Since we already know $\overline{W}_{new}=3/8$, this gives $\overline{W}_{true} = 1/2$ which is consistent with part 1 above.

3) Why is your way of computing average time between arrivals incorrect?

You give an expression $\pi_0/2 + (1-\pi_0)/1$. This of course assumes a PASTA-like property that is not necessarily true. But even with PASTA, how do you get this expression? If you consider a job arriving to an empty system, the next inter-arrival time is not exponentially distributed with rate $1$, nor is it exponentially distributed with rate $2$.

$\endgroup$
  • $\begingroup$ Thanks for the detailed answer. I believe the service rates for 2) should be $3$ instead? Also, could you please explain why $\lambda$ should be linear in the arrival rates of the different states? $\endgroup$ – Alpher Aug 19 '16 at 1:05
  • $\begingroup$ @Alpher : Thanks, that was a typo that I fixed now. $\endgroup$ – Michael Aug 19 '16 at 2:32

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.