4. Better Bounds

$\displaystyle \forall n$	$\textstyle :$	$\displaystyle \quad \: \left( 1-\rho ^{n+1}\right) w_{1}\left[ n\right] \leq \left( 1-\rho ^{n+2}\right) w_{1}\left[ n+1\right] \leq w_{1}$	(6)
$\displaystyle \forall n$	$\textstyle :$	$\displaystyle \exists T_{n}\, :\, \forall t\leq T_{n}\, :\, w_{1}\left( t\right... ..._{1}\left[ n+1\right] \left( t\right) \leq w_{1}\left[ n\right] \left( t\right)$	(7)

Figure 4: Left: lower bounds. Right : upper bounds.

$\resizebox* {0.45\columnwidth}{5cm}{\includegraphics{md04_min.eps}}$

$\resizebox* {0.45\columnwidth}{5cm}{\includegraphics{md04_max.eps}}$

As an illustration of this theorem, Fig. 4 (left) shows the sequence of the lower bounds relative to $n=1\, ..\, 8$ and $n=16$ for an M/D/1 queue (i.e. for a deterministic service distribution) where $\rho =0.75\, ;\, \mu =0.1$ , while Fig. 4 (right) shows some $T_{n}$ values.

Inequality (6) may be proved in the same way as the left hand inequality in (5). It leads to a global lower bound of the conditional waiting time pdf. The only existence of a $T_{n}$ satisfying inequality (7) is trivial ( $T_{n}=0$ works !): what is to be proved is that an optimal value can be derived and that the corresponding $T_{n}$ is meaningful.

2. Asymptotic Approximation

Let us begin by computing the coordinate $T_{n,\, n+j}$ where the two curves $w_{1}\left[ n\right]$ and $w_{1}\left[ n+j\right]$ intersect. Figure 5 plots $T_{n,\, n+1}$ and $T_{n,\, n+4}$ against $n$ : the resulting graph appears as almost rectilinear. Computing the regression line (M/GI/1 file, with the given values of parameters) leads to $T_{n,\, n+1}\approx 3.468+3.401n$ and $T_{n,\, n+4}\approx 6.032+3.406n$ . Each of these regression lines is "strongly explicative", since it reduces the standard deviation of the $T_{n}$ 's by a factor 300.

**Figure 5:** Plotting $T_{n,\, n+1}$ and $T_{n,\, n+4}$ against $n$ .
$\resizebox* {1\columnwidth}{5cm}{\includegraphics{mdloc_tn.eps}}$

Observing that $x\geq T_{n,\, n+j}$ induces $w_{1}\left[ n\right] \left( x\right) \geq w_{1}\left[ n+j\right] \left( x\right) \geq w_{1}\left( x\right)$ , these regression lines can be used to choose the number of requested iterations to obtain reliable bounds on a given initial interval. With the parameters' values that were chosen in the example, it appears that exact bounds on the $\left[ 0,\, 200\right]$ interval are obtained when $n=57$ . Using this value leads to a relative error less than $\rho ^{57}\approx 10^{-6}$ . Therefore, events whose probability is more than $10^{-5}$ are almost exactly described (this probability corresponds to $x=200$ ).

3. Proof

To prove the existence and unicity of an abscissa $T_{n,\, n+1}$ such that $w_{1}\left[ n\right] \left( x\right) =w_{1}\left[ n+j\right] \left( x\right)$ , the main point is to observe that the difference between two successive $w_{1}\left[ n\right]$ functions goes from negative values to positive values only once (Fig. 6, left).

This situation can be derived from the fact that $w_{1}\left[ n+1\right] -w_{1}\left[ n\right]$ is proportional to $c\left[ n+1\right] -w_{1}\left[ n\right]$ , and therefore we are intersecting $w_{1}\left[ n\right]$ and $c\left[ n+1\right]$ . By the way (Fig. 6, right), we obtain a better conditionned numerical equation. More precisely,

$\begin{displaymath} w_{1}\left[ n+1\right] \left( t\right) -w_{1}\left[ n\right]... ... \left( t\right) -w_{1}\left[ n\right] \left( t\right) \right) \end{displaymath}$

For increasing values of $n$ , $c\left[ n\right]$ becomes indistinguishable from $nlaw\left( \overline{x}n,\, \sigma \sqrt{n}\right)$ , the normal law with mean $n\, \mathbf{E}\left( \mathbf{C} \right) =n\, \overline{x}$ and variance $n\, \mathbf{var}\left( \mathbf{C} \right) =n\, \sigma ^{2}$ , while $w_{1}\left[ n\right]$ converges towards $w_{1}$ . But, for sufficiently large $t$ , $w_{1}$ is indistinguishable from an exponential law (large deviation theorem). When $c$ is zero outside some finite domain, we have the more precise result : $w_{1}\left( t\right) \approx w_{large\, dev}\left( t\right)$ when $t\rightarrow \infty$ where $w_{large\, dev}\left( t\right) \doteq \sum _{k\geq 1}\left( \rho ^{k}\, nlaw\... ...t{n}\right) \left( t\right) \right) \left/ \, \sum _{k\geq 1}\rho ^{k}\right.$ . One obtains:

$\begin{displaymath} w_{large\, dev}\left( t\right) \approx \frac{1-\rho }{\rho }... ... =\sqrt{\overline{x}^{2}-2\ln \left( \rho \right) \sigma ^{2}} \end{displaymath}$

(8)

Figure 6: Left: $w_{1}\left [ 18\right ] -w_{1}\left [ 17\right ]$ . Right : $w_{1}\left [ 8\right ]$ , $w_{1}\left [ 9\right ]$ and $c\left [ 9\right ]$ .

$\resizebox* {0.45\columnwidth}{5cm}{\includegraphics{b18_b17.eps}}$

$\resizebox* {0.45\columnwidth}{5cm}{\includegraphics{rgf_d_89.eps}}$

Therefore, intersecting $w_{1}\left[ n\right]$ and $w_{1}\left[ n+1\right]$ is equivalent to intersect a fixed (exponential) curve decreasing to $0$ and a moving to right (bell) curve increasing from $0$ , proving the existence and unicity of $T_{n},\, n+1$ and the relation $T_{n+1,\, n+2}>T_{n,\, n+1}$ . Combining these relations, we obtain that, for a fixed $n$ , the sequence $T_{n,\, n+j}$ is increasing. Its limit is the requested $T_{n}$ .

The core of the preceding proof being decreasing versus increasing (and not exponential versus normal), the result still holds for small values of $n$ (without requiring a formal proof, since a simple examination of the curves is sufficient).

4. About Complexity

The computation from convolution of functions $r\left[ n\right] ,\, R\left[ n\right] ,\, c\left[ n\right]$ has a cost, that needs to be evaluated carefully. For M/D/1 queues, the $w_{1}\left[ n\right]$ are piecewise polynomial functions ( $n+1$ parts of degree $n-1$ ). For the first iterations, it is efficient to use fractional numbers, while for the next ones, it is necessary to use floating point numbers. Then it is necessary to use a sufficient precision in order to avoid instability problems due to inversion of Laplace transform [6].

We used up to 100 decimal digits (which let us get an accuracy of only 5 useful digits for the final result). Programming carefully and using recent computers allow to compute convolutions of piecewise functions up to 100 pieces, each of degree 100, but not more.

4. Better Bounds

1. Statement and Illustration

2. Asymptotic Approximation

3. Proof

4. About Complexity