2. Inversion of the Pollaczek-Khintchine formula

It is well known that the Laplace transforms of the sojourn time $\mathbf{R}$ and the service duration $\mathbf{B}$ are related by the Pollaczek-Khintchine formula: $\widehat{r}\left( z\right) =\frac{\left( 1-\rho \right) z\, \widehat{b}\left( z\right) }{z-\rho \, \mu +\rho \, \mu \, \widehat{b}\left( z\right) }$ . But the residual service time obeys to $\widehat{c}\left( z\right) =\mu \, \frac{1-\widehat{b}\left( z\right) }{z}$ , and we have:

$\begin{displaymath} \widehat{r}\left( z\right) =\widehat{b}\left( z\right) \, \f... ...\left( 1-\rho \right) }{1-\rho \, \widehat{c}\left( z\right) } \end{displaymath}$

(1)

Since the Laplace transform of the sum of two independent r.v.'s is the product of the Laplace transforms of these r.v.'s, (1) leads to $\widehat{w_{0}}\left( z\right) =\frac{1-\rho }{1-\rho \, \widehat{c}\left( z\right) }$ , the sojourn time of a customer being the sum of his waiting time and his service duration.

The computation of $\widehat{w_{1}}$ may be derived when noticing that a conditional waiting time is the sum of a residual service duration and an ordinary waiting time, leading to $\widehat{w_{1}}=\widehat{c}\, \widehat{w_{0}}$ . It may also be noticed that an ordinary waiting time is either null (with probability $1-\rho$ ) or is a conditional waiting time (with probability $\rho$ ), leading to $\widehat{w_{0}}=\left( 1-\rho \right) +\rho \, \widehat{w_{1}}$ , i.e. to the same result.

2. An Inverse Transform Method

The power-series expansion of (1) is: $\widehat{r}\left( z\right) =\left( 1-\rho \right) \, \widehat{b}\left( z\right) \, \sum _{k\geq 0\, }\left( \rho \, \widehat{c}\left( z\right) \right) ^{k}$ and these series converge (when $z$ is in the right-hand half-plane, i.e. $\Re \left( z\right) \geq 0$ ) since $c$ verifies: $\left\vert \widehat{c}\left( z\right) \right\vert =\left\vert \int _{0}^{\inf... ...\vert \leq \left\vert \int _{0}^{\infty }c\left( t\right) \, dt\right\vert =1$ and $\rho <1$ . Therefore we have:

$\begin{displaymath} r\left( t\right) =b\left( t\right) \otimes \sum _{k\geq 0}\l... ...t( t\right) \right) \left/ \, \sum _{k\geq 0}\rho ^{k}\right. \end{displaymath}$

(2)

$\displaystyle r\left( t\right)$	$\textstyle =$	$\displaystyle \left( 1-\rho \right) b\left( t\right) +\rho \, b\left( t\right) \otimes w_{1}\left( t\right)$	(3)
$\displaystyle w_{1}\left( t\right)$	$\textstyle =$	$\displaystyle \sum _{k\geq 1}\left( \rho ^{k}\, c\left[ k\right] \left( t\right) \right) \left/ \, \sum _{k\geq 1}\rho ^{k}\right.$	(4)

Equation (3) says again that the sojourn time is equal to the service time when a customer arrives in an empty queue (which happens with probability $1-\rho$ ) and otherwise is increased by the conditional waiting time. Equation (4) says that the pdf of the conditional waiting time may be obtained by a disjunction into an infinite number of cases, each one occurring with probability $\left( 1-\rho \right) \rho ^{k-1}$ and corresponding to the sum of $k$ independent residual service times [7]. Let us note $r\left[ n\right]$ and $w_{1}\left[ n\right]$ the functions obtained by truncating the summations in both numerator and denominator of (2) and (4). These functions have again a unit mass, i.e. are again the pdf of some random variables.

3. Example of Deterministic Services

Let us consider a deterministic server with $\rho =0.75\, ,\, \, \mu =0.1$ . In other words, $c\left( t\right) =\mu =0.1$ when $t<10$ and $c\left( t\right) =0$ otherwise. After some computations [8], the convolutions $c\left[ 2\right] \, ...\, c\left[ 16\right]$ of the residual service time pdf can be obtained, leading to Fig. 1.

**Figure 1:** M/D/1 file: from $c\left [ 2\right ]$ to $c\left [ 16\right ]$ .
$\resizebox* {1\columnwidth}{5cm}{\includegraphics{dur_k2.eps}}$

These functions become more and more regular, while flattening on the horizontal axis and sliding towards right. This sliding is due to $\mathbf{E}\left( c\left[ n\right] \right) =n\, \mathbf{E}\left( \mathbf{C} \right) =n\, \overline{x}$ , while flattening is due to $\mathbf{var}\left( c\left[ n\right] \right) =n\, \mathbf{var}\left( \mathbf{C} \right) =n\, \sigma ^{2}$ : when the curve gets wider, its height has to decrease, since the area underneath the curve is constant. Getting regular is nothing but the central limit theorem, i.e. the convergence of the reduced pdf of a sum of i.i.d. variables towards the normal law.

Figure 2 shows the approximations $w_{1}\left[ 3\right] \, ...\, w_{1}\left[ 16\right]$ of the conditional waiting time distribution. It appears that those functions converge to a limit function and that convergence is faster for small values of $t$ . More precise statements about this convergence will be given in next section.

**Figure 2:** M/D/1 file: from $w_{1}\left [ 3\right ]$ to $w_{1}\left [ 13\right ]$ .
$\resizebox* {1\columnwidth}{5cm}{\includegraphics{dur_k3.eps}}$

2. Inversion of the Pollaczek-Khintchine formula

1. Introduction

2. An Inverse Transform Method

3. Example of Deterministic Services