I have the following $M/M/1$ queue where:

$\cdot$ customers arrive at a rate $\lambda$ and they require an exponential service time with rate $\mu$.

$\cdot$ customers leave the queue at a rate $\delta$, independently of their position in the queue.

I am asked to prove that for any $\delta>0$ the queue has an invariant distribution.

My approach: I am trying to find the generator(Q-matrix) in order to apply detail balance equation.

The process of leaving the queue and the service process are independent so $g_{i,i-1}=\mu+\delta$. And as customers arrive as a Poisson process with rate $\lambda$ we have that $g_{i,i+1}=\lambda$.

Applying detail balance we have that:



So we have that: $\pi_{n}=\Big(\frac{\lambda}{\mu+\delta}\Big)^n\pi_{0}$

However this is a distribution only if $\lambda<\mu+\delta$. And as this has to be true for any $\delta>0$, we must have that $\lambda<\delta$. But this information is not given to me in the problem.

  • 4
    $\begingroup$ It seems like if all customers leave the queue at a rate of $\delta$, then a state with $n$ queued customers transitions to a state with $n-1$ queued customers at a rate of $\mu + n\delta$, not $\mu+\delta$. $\endgroup$ – Misha Lavrov Mar 10 '18 at 21:53
  • $\begingroup$ This is actually known as "reneging." "Balking" refers to the phenomenon when customers decide not to enter the system if the queue is too long. $\endgroup$ – Math1000 Mar 19 '18 at 23:45

As Mishra Lavrov noted in the comments, the transition rate from state $n$ to state $n-1$ is $\mu+n\delta$. So the detailed balance equations are $$ \lambda\pi_n = (\mu+n\delta)\pi_{n+1}. $$ This yields the recursion $\pi_{n+1}=\frac\lambda{\mu+ n\delta}\pi_n$, with solution $$ \pi_{n+1}=\prod_{k=0}^{n-1}\left(\frac\lambda{\mu+ k\delta}\right)^k\pi_0. $$ Since $\sum_{n=0}^\infty \pi_n=1$, it follows that $$ \pi_0 = \left(1 + \sum_{n=1}^\infty\prod_{k=0}^{n-1}\left(\frac\lambda{\mu+ k\delta}\right)^k\right)^{-1}, $$ and hence $$ \pi_{n+1} = \prod_{k=0}^{n-1}\left(\frac\lambda{\mu+ k\delta}\right)^k\left(1 + \sum_{n=1}^\infty\prod_{k=0}^{n-1}\left(\frac\lambda{\mu+ k\delta}\right)^k\right)^{-1},\; n\geqslant0. $$


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.