3. First Bounds

According to our general notations, $R\left[ n\right] \left( t\right)$ will denote $\int _{0}^{t}r\left[ n\right] \left( u\right) du$ . A first claim is:

$\begin{displaymath} \forall n\, :\, \left( 1-\rho ^{n+1}\right) R\left[ n\right]... ...+1\right] \leq R\leq R\left[ n+1\right] \leq R\left[ n\right] \end{displaymath}$

(5)

As an illustration of this theorem, the left part of Fig. 3 shows the sequence of the lower bounds relative to and for an M/D/1 queue where the right part shows the related upper bounds.

Figure 3: M/D/1 file: cdf lower (left) and upper (right) bounds

$\resizebox* {0.45\textwidth}{5cm}{\includegraphics{md06_min.eps}}$

$\resizebox* {0.45\textwidth}{5cm}{\includegraphics{md06_max.eps}}$

2. Proof

For the left part: from the very definition of $r\left[ n\right]$ , $\left( 1-\rho ^{n+1}\right) r\left[ n\right] \left( t\right)$ equals $\sum _{n\geq k}\rho ^{k}\, b\left( t\right) \otimes c\left[ k\right] \left( t\right)$ . Convolution products of $c$ and $b$ are pdf's, so every term in this sum is positive and the sequence of functions $\left( 1-\rho ^{n+1}\right) r\left[ n\right] \left( t\right)$ is increasing. This remains true when integrating, so the sequence of functions $\left( 1-\rho ^{n+1}\right) R\left[ n\right] \left( t\right)$ is also increasing .

For the right part: each $c\left[ k\right]$ is the pdf of a r.v. $\mathbf{X}_{k}$ , equal to the sum of $k$ i.i.d. variables $\mathbf{X}_{1,k}\, ...\, \mathbf{X}_{k,k}$ , each one being distributed according to $c$ . The function $w_{0}\left[ n\right]$ can be viewed as the pdf of the r.v. $\mathbf{Y}_{n}$ defined by: pick a $k\in \left[ 0,n\right]$ according to weight $\rho ^{k}$ (i.e. with a probability proportional to $\rho ^{k}$ ) and then pick a $\mathbf{X}_{k}$ . Therefore, $1-R\left[ n\right] \left( t\right)$ is the probability that $\mathbf{B}+\mathbf{Y}_{n}\geq t$ while $1-R\left[ n+1\right] \left( t\right)$ is the probability that $\mathbf{B}+\mathbf{Y}_{n+1}\geq t$ . Since the odds of the former are obviously lower than those of the latter, the sequence $R\left[ n\right]$ is decreasing.

3. Limitations of this Result

The bounds given in (5) are simple, and apply to the whole scale of response times. But their efficiency has to face two kinds of remarks. Firstly, and it can be easily seen on Fig. 3, the exact curve is not at the same distance from the two bounds, starting very near to the lower bound and ending very near to the upper bound, giving the limit value $R\left( \infty \right) =1$ .

Secondly, these bounds provide nearly no information about the tail of the distribution. Let us for example consider a deterministic law. It may easily be seen that residual service duration pdf is: $c\left( t\right) =\mu \, \chi _{\left[ 0\, ;\, 1/\mu \right] }$ where $\chi$ is the usual indicator function ( $1$ inside, $0$ outside). Therefore $c\left[ k\right]$ is zero outside $\left[ 0\, ;\, k/\mu \right]$ and $R\left[ k\right] \left( t\right) =1$ when $t\geq k/\mu$ . So let us look for more efficient bounds.

3. First Bounds

1. Statement and Illustration

2. Proof

3. Limitations of this Result