6
$\begingroup$

Burke's theorem says that the output process of an $\rm M/M/1$, an $\rm M/M/C$, and a $\rm M/M/\infty$ queue with arrival rate $\lambda$ and service rate $\mu$ follows a Poisson with parameter $\lambda$.

I was able to derive the proof for the $\rm M/M/1$ easily using Laplace transforms:

For the busy period, the time spent in between departures is given by an exponential distribution with parameter $\mu$. For the non-busy period the inter-departure is given by a sum of an inter-arrival and one service time.

\begin{align}LD(s)&=\frac{\lambda}{\mu}\cdot\frac{\mu}{\mu+s}+(1−\frac{\lambda}{\mu})\cdot\frac{\lambda}{\lambda+s}\cdot\frac{ \mu}{\mu+s}=\frac{\lambda}{\lambda+s}\\D(t)&=\lambda e^{-\lambda t}\end{align}

However, I am struggling immensely to derive the proof for the $\rm M/M/\infty$ case. Can someone point out where I am going wrong?

So far I have for the busy period: $\sum\limits_{i=1}^\infty e^{-\lambda/μ}\cdot \frac{i\mu}{ i\mu+s}$. I am not even sure if this is correct. Do we need to account for the possibility of new arrivals before the departure too? How one would go with that?

Also, how would I set it up for the non-busy period? And how do I deal with this $\frac{i\mu}{ i\mu+s}$ term in the busy one?

Thanks!

$\endgroup$
  • 4
    $\begingroup$ Hello Pedro, and welcome to OR.SE. I have modified as much of the maths into MathJax as it makes sense, but there are certain parts such as $i\mu$ and $\lambda\lambda\cdot\mu\mu+s$ where notation such as exponentiation etc. can get ambiguous. Please take a look at this MathJax guide and you can modify the expressions accordingly. $\endgroup$ – TheSimpliFire Sep 21 '19 at 16:51
4
$\begingroup$

The following proof approach for Bruke's Theorem was given in this Lecture by Richard Clegg:

Definition: A chain is called time-reversible if $p_{ij} = p^*_{ij}$ for all $i$ and $j$. This occurs if and only if:

$p_{ij}\pi_i = p_{ji}\pi_j \ \ \forall i, j$.

So the Birth-Death processes are time-reversible. Therefore all the queues which can be modelled as such are, themselves time-reversible. This includes the $M/M/1$, the $M/M/m$ and the $M/M/\infty$ queues. Therefore, queue which can be represented as a Birth-Death process can be considered, once it has reached the steady-state. An important point here is that the departure process of the forward system is the arrival process of the forward system.

Broke's Theorem: For a $M/M/1$, $M/M/m$ or $M/M/\infty$ queue in the steady-state then:

  1. The departure process is Poisson with a rate of $λ$.
  2. At the time $t$ the number of customers is independent of the sequence of departure times prior to $t$.

Proof. Part (1) follows immediately from the fact that the arrival process is Poisson with rate $λ$ the time reverse of this is also a Poisson with rate $λ$. Part (2) follows from the fact that the departures prior to $t$ in the reversed system is the same process as the arrival process after $t$ in the reversed process. It can be seen that the number in the system queue is independent of the arrivals after that point in a Poisson system.

$\endgroup$

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.