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 Answer 1

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$
2
  • $\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, 2016 at 1:05
  • $\begingroup$ @Alpher : Thanks, that was a typo that I fixed now. $\endgroup$
    – Michael
    Aug 19, 2016 at 2:32

You must log in to answer this question.

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