\(Q(t)\) the number of items in the system at time \(t\)
\(\rho = \lambda/\mu\) is the traffic intensity
\(Q\) is a continuous-time Markov chain, with generator \(G\) given by \[G(n, n-1) = \mu \text{ for all $n \geq 1$} \] and \[G(n, n+1) = \lambda \text{ for all $n \geq 0$ }\]
If \(\rho <1\), then as \(t \to \infty\) \[ \mathbb{P}(Q(t) = n) \to (1- \rho)\rho^n = \pi_n,\] were \(\pi\) is the stationary distribution.
\[ \begin{eqnarray*} 0 &=&(\pi G)_n \\ &=& \pi_{n-1}G(n-1,n) + \pi_{n+1}G(n+1,n )+ \pi_nG(n,n) \end{eqnarray*} \]
and
\[ 0=(\pi G)_0 = \pi_1 G(1, 0) + \pi_0 G(0,0)\]
\[ \pi_{n+1} = \pi_n(\rho +1) - \pi_{n-1} \rho\] and
\[ \pi_1= \rho \pi_0\]
\[ \pi_n = \rho^n \pi_0.\]
Theorem: The departures \(D(t)\) of a stationary \(M(\lambda)/M(\mu)/1\) queue are a Poisson process of rate \(\lambda\). Furthermore, \(Q(t)\) is independent of the \((D(s), s \leq t)\).
We sketch a proof using reversibility. See Reich’s proof of Burke’s theorem
It is easy to check that \(Q\) is reversible; see Exercise 4.
Given \(T>0\), the process \(R(t)= Q(T-t)\) has the same law as \((Q(s), s\leq T)\).
The process \(R\) adds an arrival at time \(t\), when \(Q\) has a departure at time \(T-t\).
The arrivals of \(R\) and \(Q\) are both Poisson
The time-reversal of a Poisson is again a Poisson.
Thus the departure process is also Poisson.
\(Q(0)\) is independent from the arrivals in \([0, T]\)
Reversing time, \(Q(T)\) is independent from the departures in \([0, T]\).
It is a general question, given a item has to pass through two queues in series, one after another, which order should the queues to placed in?
This is in general a hard question
However, using Burke’s theorem, we can show the order does not matter in the case of two M/M/1 queues in equilibrium.
Theorem Suppose items enter a \(M(\lambda)/M(\mu_1)/1\) queue, then upon exiting report to another queues with exponential service rate \(\mu_2\). If \(\lambda < \min(\mu_1, \mu_2)\), then the continuous-time Markov chain \((Q_1, Q_2)\) has stationary distribution given by
\[(m,n) \mapsto \rho_1^m(1-\rho_1) * \rho_2^n(1-\rho_2)\] where \(\rho_1 = \lambda/\mu_1\) and \(\rho_2 = \lambda/\mu_2\).
We already know that if the first queue is stationary, then by Burke’s theorem, the departures are again a Poisson process with rate \(\lambda\)
Thus what feeds into the second queue is still a Poisson.
We already know that the individual expressions correspond to the the stationary distributions of the individual queues
Independence follows from the independence assertion is Burke’s theorem.
We found the stationary distribution for a M/M/1 queue.
We used reversibility to prove Burke’s theorem.
We applied Burke’s theorem to two M/M/1 queues in series.
See also Question 5