[CST-2] Burke's Theorem

[Tim Harris]

Hi --

quite a few people have asked about section (b) from the 1998 Paper 9
CS Modelling question.  This asks for "an outline proof showing that 
the distribution of the departure process is the same as that of the
arrivals process" in an M/M/m queue.

The result there is part of Burke's Theorem.  It wasn't covered this
year but for anyone that's interested here is one way that it could
be tackled.

Let the arrival and service rates be \lambda and \mu respectively.
For such an M/M/m system the utilization of each server, \rho, will
be \lambda / (m \mu).

Consider the mean number of departures, d_k, that occur over a small
interval of time, h, when there are k customers in the system.  
If k=0 then evidently d_0=0.  For 1<k<=m then d_k=hk\mu.  Beyond that
all of the servers are busy and so the mean number of departures
saturates at d_k=hm\mu.

Let p_k be the probability that there are k customers in the system.
Averaging over the different probabilities:

     d = h \mu ( p_1 + 2p_2 + 3p_3 + ... + mp_m + mp_{m+1} + ... )

Recognising the bit in brackets as m\rho:

     d = h \mu m \rho = \lambda h

Hence the departures form a poisson process with mean rate \lambda.

I think that'd be fine as an "outline proof"!

Tim