Deriving the Pollaczek - Khintchine formula

Question

I used this result in a paper a while back and now I want to be clear about where it comes from (I know it's correct). I wonder if someone could explain?

I have a moment generating function for an M/G/1 queue (ie Markovian, General, 1 server) of:

$\frac{1-\rho}{1-\rho h^*(s)}$

Where $\rho$ is the traffic intensity ($\rho=\lambda\mu$ where $\lambda$ is the poisson parameter - ie rate of arrivals and $\mu$ is the average service time)

While $h^*(s)=\frac{1-g^*(s)}{s\mu}$ - and $g^*(s)$ is a Laplace transform (into the domain of s) of a distribution function $g(x)$ for service times.

Now - so far, so standard - differentiating this and taking the negative of its value at $s=0$ should give us the expectation of waiting time in the queue.

The standard result for this differentiation (and negation) is $\frac{\rho\mu(1+c^2)}{2(1-\rho)}$, where $c$ is "the co-efficient of variation", namely the ratio of the standard deviation to the mean for service times.

Now this differentiation is laborious and I don't think I am getting it right - and I suspect it involves knowledge of what property is revealed by $\frac{dg^*(s)}{ds}$ - which I am not clear about.

I am happy to read a source if that's easier than an explanation but I would appreciate some pointers about how we get from $\frac{dg^*(s)}{ds}$ to $c$.

Answer 1

Recall that $g^*(s)=E[e^{-sx}]$ and that the Taylor series for $g^*(s)$ around $s=0$ is given by $g^*(s)=g^*(0)+\frac{\mathrm{d}g^*}{\mathrm{d}s}|_{s=0}+\frac{1}{2}\frac{\mathrm{d}^2g^*}{\mathrm{d}s^2}|_{s=0}+...$

It is a straightforward exercise to calculate the first few terms of the Taylor series of $g^*(s)$; $g^*(s)=1-\mu(s)+\frac{\mu^2(1+c^2)}{2}s^2 + O(s^3)$.

From this we get $h(s)=1-\frac{\mu s}{2}(1+c^2) + O(s^2)$ and $\frac{\mathrm{d}h}{\mathrm{d}s}=\frac{-\mu}2(1+c^2)+O(s)$.

We know the Laplace-Stieltjes transform (or "moment generating function") $M(s)=\frac{1-\rho}{1-\rho h^*(s)}$ and, substituting in these series for $h^*$ and $\frac{\mathrm{d}h^*}{\mathrm{d}s}$, we have that $\frac{\mathrm{d}M}{\mathrm{d}s}=\frac{\rho(\rho-1)\frac{\mathrm{d}h^*}{\mathrm{d}s}}{(1-\rho h)^2}$ can be approximated as $\frac{\mathrm{d}M}{\mathrm{d}s}=\frac{-\rho(1-\rho)\frac{\mu}{2}(1+c^2)+O(s)}{(1-\rho)^2+O(s)}$. When $s=0$ we can conclude that $\frac{\mathrm{d}M}{\mathrm{d}s}=\frac{-\rho\mu(1+c^2))}{2(1-\rho)}$.

Answer 2

Please pay attention to the fact that $T_Q^*(s)=\frac{1-\rho}{1-\rho h^*(s)}$ is not the moment generating function. It is the Laplace (or Laplace-Stieltjes) transform.

I will use the notation that you suggested. $\lambda$ - arrival rate. $\mu$ - mean service time. But $\mu$ for mean service time is not a common notation for those who work in the field of queueing theory. $\mu$ usually stands for service rate.

Note that $c^2$ is the squared coefficient of variation, i.e. if $S$ denotes the service time random variable, then $$ c^2 = {E(S-ES)^2 \over (ES)^2}={E(S^2)\over (ES)^2} -1 ={E(S^2) \over \mu^2} -1. $$ Then the quantity you are asking about, $E(T_Q)=\frac{\rho\mu(1+c^2)}{2(1-\rho)}$, which is the expected time the customer spends in the queue, is then equal to $$ E(T_Q)=\frac{\rho\mu(1+c^2)}{2(1-\rho)}= \frac{\rho\mu}{2(1-\rho)}{E(S^2)\over \mu^2} ={\lambda E(S^2) \over 2(1-\rho)} ={\lambda (g^*(s))''_{s=0} \over 2(1-\rho)}. $$ The last equality is due to the fact that $g^*(s)=\int_0^\infty e^{-sx}g(x)dx$ (you assume that $g(x)$ exists) and thus $(g^*(s))''_{s=0}=\int_0^\infty x^2 g(x)dx=E(S^2)$.

Now, since $T_Q^*(s)$ is the Laplace transform, then $(T_Q^*(s))'_{s=0}=-E(T_Q)$. Consider the euqation for $T_Q^*(s)$: $$ T_Q^*(s)(1-\rho h^*(s))=1-\rho. $$ Differentiate both sides w.r.t. $s$ and put $s=0$ and note that $T_Q^*(0)=h^*(0)=1$: $$ \tag{1} -E(T_Q)(1-\rho)-\rho (h^*(s))'_{s=0}=0. $$ Now cosider the expression for $h^*(s)$: $$ h^*(s) s \mu =1-g^*(s). $$ Differentiate both sides w.r.t. $s$: $$ (h^*(s))'_{s} s \mu + h^*(s) \mu =-(g^*(s))'_s. $$ If you put now $s=0$ then $(h^*(s))'_{s=0}$ vanishes. Differentiate once more: $$ (h^*(s))''_{s} s \mu + 2 (h^*(s))'_{s} \mu =-(g^*(s))''_s. $$ Now put $s=0$: $$ \tag{2} (h^*(s))'_{s=0} =-{(g^*(s))''_{s=0} \over 2 \mu}. $$

Combine (1) and (2) and you will get the expression for $E(T_Q)$.