Baltzer Journals April 28, 1997

Transient and Stationary Waiting Times in (max,+)–Linear Systems with Poisson Input

François Baccelli^{1}, Sven Hasenfuss^{2} and Volker Schmidt^{2}

1 INRIA Sophia Antipolis, 2004, Route des Lucioles, B.P.93, F-06902 Sophia Antipolis Cedex, France

                E-mail: baccelli@sophia.inria.fr

2 Universität Ulm, Abteilung Stochastik, Helmholtzstr. 18, D-89069 Ulm, Germany

             E-mail: hasenfus@mathematik.uni-ulm.de
                 schmidt@mathematik.uni-ulm.de

We consider a certain class of vectorial evolution equations, which are linear in the (max,+) semi-field. They can be used to model several types of discrete event systems, in particular queueing networks where we assume that the arrival process of customers (tokens, jobs, etc.) is Poisson. Under natural Cramér type conditions on certain variables, we show that the expected waiting time which the n-th customer has to spend in a given subarea of such a system can be expanded analytically in an infinite power series with respect to the arrival intensity λ. Furthermore, we state an algorithm for computing all coefficients of this series expansion and derive an explicit finite representation formula for the remainder term. We also give an explicit finite expansion for expected stationary waiting times in (max,+)-linear systems with deterministic queueing services.

Subject classification: AMS(MOS) 60K25, 60G55, 90B22

Keywords: Queueing networks, stochastic Petri nets, Poisson input, vectorial recurrence equation, waiting times, analyticity, Taylor series expansion.

1 Introduction

Several types of discrete event systems, in particular queueing networks, can be described in terms of linear vectorial evolution equations in the (max,+) semi-field, see [1]. In this paper we consider the class of such vectorial evolution equations governing open systems, where we assume that the arrival process of customers (tokens, jobs, etc.) is Poisson. For such systems, it is difficult to obtain exact analytical results for characteristics such as expectations of transient or steadystate waiting times.

We show that under natural Cramér type conditions on certain variables, the expected waiting time which the n-th customer has to spend in a given subarea of such a system can be expanded analytically in an infinite power series with respect to the arrival intensity λ.

Furthermore, we give an algorithm for computing all coefficients of this series expansion and derive an explicit finite representation formula for the remainder term. Finite expansions, which lead to approximation formulas for the expectation and for further characteristics (like higher-order moments, Laplace transform, tail function) of stationary waiting times in (max, +)–linear systems have already been derived in [2] and [3]. Note, however, that in [2] and [3], the remainder term has not been analyzed.

The approach presented in this paper allows one to obtain exact analytical results for expected transient waiting times, as well as for expected stationary waiting times for all arrival intensities that admit a stationary regime. In particular, we give an explicit finite expansion for expected stationary waiting times of a randomly chosen customer in a certain class of (max,+)-linear systems with deterministic service. This class contains many important queueing systems, such as tandem queues with various types of blocking (e.g. communication– or manufacturing–blocking), as well as basic manufacturing systems, such as Kanban networks or Job-Shop systems.

Similar questions were discussed by various other authors in the past years. Reiman and Simon ([9], [10]) considered Poisson-driven queueing networks and first showed the existence of expansions of performance measures and calculated derivatives with respect to the arrival rate, similar to those in [2] and [3], but mostly for isolated queues. Gong and Hu [4] derived the MacLaurin series for the moments of the system time and the delay in the GI/G/1 queue. Based on the recursive procedure developed in [4], Hu [5] answers the question of analyticity of single-server queues in light traffic. The method of [4] has also been applied to obtain series expansions for inventory systems, see [7], and for the departure process of the GI/G/1 queue, see [6].

Using a different approach, (max,+)-linear systems with Poisson input and known services have recently been studied by Jean-Marie [8], where all service times are assumed deterministic. Starting from the task graph representation of such systems, in [8] a recursive algorithm is derived for computing distributions and Laplace transforms of response times in the transient as well as in the stationary regime.

The basic tool for our approach is the class of polynomials introduced for the steady-state case in [3]. In this sense, the present paper is a direct continuation of [3] and [2]. The derivation of the basic theorems leads us to several new properties of this class of polynomials, including new recurrence formulas, which are of independent interest.

The evolution of open (max, +)–linear stochastic systems is described by the α-dimensional vectorial (max,+)–linear evolution equation

V_{n+1} = A_{n} ⊗ C(τ_{n}) ⊗ V_{n} ⊕ B_{n+1},  (1)

with some initial condition V_{0}, where α ≥ 1, τ_{n} = T_{n+1} − T_{n}, n ≥ 0. In this equation, the reference algebra is the so-called (max, +) algebra: when operating on scalars, ⊕ stands for max and ⊗ for +, whereas the ⊗-product of two matrices, say A of size p × q and B of size q × r is the p × r matrix A ⊗ B with entries

(A ⊗ B)_{i,j} = ⨁_{k=1}^{q} A_{i,k} ⊗ B_{k,j}

and the ⊕-sum of two matrices, say A and B both of size p × q is the p × q matrix A ⊕ B with entries

(A ⊕ B)_{i,j} = A_{i,j} ⊕ B_{i,j}.

(See [1] for more details on this formalism). The involved variables are the following

• {T_{n}} is a non-decreasing sequence of real-valued random variables (the epochs of the Poisson arrival point process);

• {A_{n}} is a stationary and ergodic sequence of α×α matrices with real-valued random entries;

• {B_{n}} is a stationary and ergodic sequence of α×1 matrices with real-valued random entries;

• {V_{n}} is the sequence of α-dimensional state vectors;

• C(x) is the α × α matrix with diagonal entries equal to −x and all nondiagonal entries equal to ε = −∞.

Throughout the paper, it is assumed that the sequences {A_{n}} and {B_{n}} are independent of the Poisson process {T_{n}}.

Several examples of such evolution equations have been discussed in [3], within the framework of queueing theory and stochastic Petri nets. The interpretation of the components V_{n}^{i} of the state variables V_{n} in stochastic event graphs is the waiting time of the n-th token entering the system until this token is consumed by the firing of transition i, where i = 1, …, α. The reader should refer to [3] for detailed examples on the matter.

We have

V_{n} = B_{n} ⊕ ⨁_{k=0}^{n−1} C(T_{n} − T_{k}) ⊗ D_{n,k},  (2)

for n ≥ 1, where

D_{n,k} = A_{n} ⊗ A_{n−1} … ⊗ A_{k} ⊗ B_{k}.  (3)

Equation (2) is sometimes called the forward construction of waiting times. However, for our purposes, it is more convenient to consider the following backward construction of the waiting times. In connection with this, we consider the twosided infinite extensions of {A_{n}} and {B_{n}} and the Poisson process on the whole real line. Then, this backward construction is given by

W_{n} = B_{0} ⊕ ⨁_{k=1}^{n} C(−T_{−k}) ⊗ D_{k},  (4)

where we define

D_{k} = A_{0} ⊗ A_{−1} … ⊗ A_{−k} ⊗ B_{−k},  (5)

for n ≥ 1; D_{0} = B_{0}. Since under our assumptions W_{n} =^{d} V_{n}, we will use the simpler backward representation (4) of W_{n} from now on. In the following we still need a certain monotonicity property of the D_{k}. Namely, we assume that {A_{n}} and {B_{n}} are such that

0 ≤ D_{0}^{i} ≤ D_{1}^{i} ≤ …  (6)

holds for all i = 1, …, α, where D_{k}^{i} denotes the i-th component of the vector D_{k}. Sufficient conditions for this are given in [3].

2 Main Results

2.1 Analyticity and Computation of Coefficients

The following lemma follows from Section 2.84 in [11], and will be instrumental in the proof of the forthcoming theorem:

Lemma 1 Let f(λ, x_{1}, …, x_{n}) be a continuous function of λ, x_{1}, …, x_{n}, which is analytic in λ in a domain D, for all x_{1} ∈ C_{1}, …, x_{n} ∈ C_{n}, where C_{1}, …, C_{n} are infinite contours. If there exists a function g(x_{1}, …, x_{n}) such that

|f(λ, x_{1}, …, x_{n})| ≤ g(x_{1}, …, x_{n}), ∀ λ ∈ D,

and

∫_{C_{1}} … ∫_{C_{n}} g(x_{1}, …, x_{n}) dx_{1} … dx_{n} < ∞,

then the function

∫_{C_{1}} … ∫_{C_{n}} f(λ, x_{1}, …, x_{n}) dx_{1} … dx_{n}

is analytic in λ ∈ D. In addition, for all λ ∈ D, and k ≥ 0,

\frac{∂^{k}}{∂λ^{k}} ∫_{C_{1}} … ∫_{C_{n}} f(λ, x_{1}, …, x_{n}) dx_{1} … dx_{n}

= ∫_{C_{1}} … ∫_{C_{n}} \frac{∂^{k}}{∂λ^{k}} f(λ, x_{1}, …, x_{n})dx_{1} … dx_{n}.

We first consider the expected transient waiting time IEW_{n}^{i} for each i ∈ {1, …, α} and n ≥ 0, under some Cramér-type condition on D_{n}^{i}. We show that IEW_{n}^{i} is an analytical function of the arrival intensity λ. For another viewpoint on the problem of analyticity of functionals of Poisson processes, see also [12].

Theorem 1 Assume that D_{n}^{i} is such that

IE [e^{aD_{n}^{i}}] < ∞,  (7)

for some positive a. Then IEW_{n}^{i} is an analytical function of the arrival intensity λ in (0, ∞), and this function can be continued analytically to the complex domain R(λ) > −a, and in particular, it is analytic at point λ = 0.

Proof Let x_{1}, …, x_{n} all be positive. The density of the random vector (−T_{−1}, …, −T_{−n}) at (x_{1}, …, x_{n}) is equal to

1(x_{1} < x_{2} < … < x_{n}) e^{−λx_{n}}λ^{n} dx_{1} … dx_{n},

where 1(E) denotes the indicator function of the set E. So, (4) yields

IE[W_{n}^{i}] = ∫_{0}^{∞} … ∫_{0}^{∞} IE [max{D_{0}^{i}, D_{1}^{i} − x_{1}, …, D_{n}^{i} − x_{n}}]
1(x_{1} < x_{2} < … < x_{n}) e^{−λx_{n}}λ^{n} dx_{1} … dx_{n}

and consequently

IE[W_{n}^{i} − W_{n−1}^{i}]

= ∫_{0}^{∞}… ∫_{0}^{∞} IE [max{0, D_{n}^{i} − x_{n} − max{D_{0}^{i}, D_{1}^{i} − x_{1}, …, D_{n−1}^{i} − x_{n−1}}}]
1(x_{1} < x_{2} < … < x_{n})e^{−λx_{n}}λ^{n} dx_{1} … dx_{n}.

The function

f(λ, x_{1}, …, x_{n})
= IE [max{0, D_{n}^{i} − x_{n} − max{D_{0}^{i}, D_{1}^{i} − x_{1}, …, D_{n−1}^{i} − x_{n−1}}}]
1(x_{1} < x_{2} < … < x_{n}) e^{−λx_{n}}

is continuous and such that

|f(λ, x_{1}, …, x_{n})| ≤ g(x_{1}, …, x_{n})

with

g(x_{1}, …, x_{n})
= IE [max{0, D_{n}^{i} − x_{n} − max{D_{0}^{i}, D_{1}^{i} − x_{1}, …, D_{n−1}^{i} − x_{n−1}}}]
1(x_{1} < x_{2} < … < x_{n}) e^{ax_{n}}.

Thus

∫_{0}^{∞} … ∫_{0}^{∞} g(x_{1}, …, x_{n}) dx_{1} … dx_{n}

= IE[ ∫_{0}^{D_{n}^{i}}… ∫_{0}^{D_{n}^{i}} max {0, D_{n}^{i} − x_{n} − max{D_{0}^{i}, D_{1}^{i} − x_{1}, …, D_{n−1}^{i} − x_{n−1}}}

1(x_{1} < x_{2} < … < x_{n}) e^{ax_{n}} dx_{1} … dx_{n}]

≤ IE [∫_{0}^{D_{n}^{i}}… ∫_{0}^{D_{n}^{i}} D_{n}^{i} e^{ax_{n}} dx_{1} … dx_{n}]

≤ IE [(D_{n}^{i})^{n} \frac{e^{aD_{n}^{i}} − 1}{a}] < ∞,

where we made use of (7) to prove that the last expression is finite. In view of Lemma 1, IE[W_{n}^{i} − W_{n−1}^{i}] is analytic for λ ∈ D, where D is the half plane R(λ) > −a. Using (6), we get by the same argument that IE[W_{m}^{i} − W_{m−1}^{i}] is analytic in the same region for all 0 < m ≤ n. Since IEW_{0}^{i} is constant in λ and therefore analytic, an immediate finite induction shows that IEW_{n}^{i} is also analytic for λ ∈ D.

Moreover, we can apply the same construction which was already used in [3] to obtain the following expression for the coefficients of the infinite power-series expansion of IEW_{n+1}^{i} with respect to the arrival intensity λ.

Theorem 2 For each λ ≥ 0,

IE[W_{n+1}^{i}] = ∑_{k=0}^{n} λ^{k} IE [p_{k+1}(D_{0}^{i}, …, D_{k}^{i})]

+ ∑_{k=n+1}^{∞} λ^{k} IE[p_{k+1}(D_{0}^{i}, …, D_{n−1}^{i}, \underbrace{D_{n}^{i}, …, D_{n}^{i}}_{k+1−n})],  (8)

where

p_{k}(x_{0}, x_{1}, …, x_{k−1}) = ∑_{(i_{0},i_{1},...,i_{k−1}) ∈ S_{k}}(−1)^{q_{k}(i_{0},i_{1},...,i_{k−1})} \frac{x_{0}^{i_{0}}}{i_{0}!} \frac{x_{1}^{i_{1}}}{i_{1}!} … \frac{x_{k−1}^{i_{k−1}}}{i_{k−1}!} , (9)

with

S_{k} = { (i_{0}, i_{1}, …, i_{k−1}) ∈ {0, 1, …}^{k} : i_{0} + i_{1} + … + i_{k−1} = k
and if i_{s} = l > 1, then i_{s−1} = i_{s−2} = … = i_{s−l+1} = 0 }, (10)

(the s − j are modulo k) and

q_{k}(i_{0}, i_{1}, …, i_{k−1}) = 1 + ∑_{s=0}^{k−1} 1(i_{s} > 0).  (11)

Proof Note that the (transient) waiting time W_{n+1} defined above can be brought to the form of the stationary waiting time W defined in equation (9) of [3] if we set D_{k} = D_{n}, for k ≥ n, since T_{−k} is non-increasing in k. Thus, proceeding in the same way as in Section 7 of [3] we obtain that the functional W_{n+1} is admissible in the Reiman–Simon sense (see [10]), under the Cramér condition (7). Using the results of Section 6 in [3], we therefore have the following result: For each m ≥ 0,

IE[W_{n+1}^{i}] = ∑_{k=0}^{min{m,n}} λ^{k} IE [p_{k+1}(D_{0}^{i}, …, D_{k}^{i})]

+ ∑_{k=min\{m,n\}+1}^{m}λ^{k} IE[p_{k+1}(D_{0}^{i}, …, D_{n−1}^{i}, \underbrace{D_{n}^{i}, …, D_{n}^{i}}_{k+1−n})] + O(λ^{m+1}).

Since the above expansion is a Taylor expansion, in view of Theorem 1, we obtain equation (8) by letting m go to ∞.

Remark Formula (8) can also be obtained by the representation of IE[W_{n}^{i}−W_{n−1}^{i}] in Theorem 1. Let us exemplify this on the expansion of IE[W_{1}^{i} − W_{0}^{i}]. Using the last assertion of Lemma 1, we obtain

\frac{d^{k}}{dλ^{k}} |_{λ=0}IE[W_{1}^{i} − W_{0}^{i}] = ∫_{0}^{∞} IE[ max\{D_{0}^{i}, D_{1}^{i} − x_{1}\} − D_{0}^{i}] \frac{∂^{k}}{∂λ^{k}} |_{λ=0} e^{−λx_{1}}λ dx_{1}
= ∫_{0}^{∞} IE[ max{D_{0}^{i}, D_{1}^{i} − x_{1}} − D_{0}^{i}] k(−x_{1})^{k−1} dx_{1}.

Finally, using the results of Section 6 in [3], it is easy to check that indeed

IE[p_{k+1}(D_{0}^{i}, \underbrace{D_{1}^{i}, …, D_{1}^{i}}_{k})] = ∫_{0}^{∞} IE [max\{D_{0}^{i}, D_{1}^{i} − x_{1}\} − D_{0}^{i}] \frac{(−x_{1})^{k−1}}{(k − 1)!} dx_{1}.

For the rest of the paper we will omit the superscript i in order not to overload notation but always mean an arbitrarily chosen but fixed component of the vector (W_{n}^{i})_{i=1,...,α} or (D_{n}^{i})_{i=1,...,α}, respectively.

2.2 Explicit Representation of the Remainder Term

We want to investigate the series expansion (8) of IE[W_{n+1}] more closely. Note, representation (8) implies that

IE[W_{n+1}] = ∑_{k=0}^{n} λ^{k} IE[ p_{k+1}(D_{0}, …, D_{k})]

+ \frac{1}{λ} ∑_{k=n+1}^{∞} IE[ p_{k+1}(λ (D_{0} − D_{n}), …, λ (D_{n−1} − D_{n}), \underbrace{0, …, 0}_{k+1−n})], (12)

where we used a translation–invariance and a homogenity property of the polynomials p_{k}. Namely,

p_{k+1}(x_{0}, x_{1}, …, x_{k}) = p_{k+1}(x_{0} + t, x_{1} + t, …, x_{k} + t)  (13)

and

p_{k}(t x_{0}, t x_{1}, …, t x_{k}) = t^{k} p_{k}(x_{0}, x_{1}, …, x_{k})  (14)

hold for all k ≥ 1 and t ∈ IR. A proof of (13) and (14) is given in Section 4. Consider the remainder term \frac{1}{λ} R_{n+1} involved in the righthand side of (12), where we define

R_{n+1} = ∑_{k=n+1}^{∞} p_{k+1}(λ (D_{0} − D_{n}), …, λ (D_{n−1} − D_{n}), \underbrace{0, …, 0}_{k+1−n}). (15)

Then we can state a series expansion of IEW_{n+1} with the explicit representation of its remainder term defined in (15).

Theorem 3 For each arrival intensity λ > 0 and for all n ≥ 0,

IE[W_{n+1}] = ∑_{k=0}^{n} λ^{k} IE[p_{k+1}(D_{0}, …, D_{k})] + \frac{1}{λ} IE[R_{n+1}],  (16)

where

R_{n+1} = ∑_{m=0}^{n−1} T_{n+1}(e^{λ(D_{m}−D_{n})}) − ∑_{m=0}^{n−2} ∑_{j=1}^{n−1−m} λ^{j} T_{n+1−j}(e^{λ(D_{m}−D_{n})})

× {p_{j}(D_{m+1} − D_{n}, …, D_{m+j} − D_{n})
− p_{j}(0, D_{m+1} − D_{n}, …, D_{m+j−1} − D_{n})} (17)

and T_{j}(e^{x}) = ∑_{k=j+1}^{∞} \frac{x^{k}}{k!} = e^{x} − ∑_{k=0}^{j} \frac{x^{k}}{k!} .

We can also rewrite the remainder R_{n+1} and collect all coefficients of those expressions involving the same powers of λ to obtain another interesting representation of the expectation of the transient waiting time W_{n+1}.

Theorem 4 For each arrival intensity λ > 0 and for all n ≥ 0,

IE[W_{n+1}] = \frac{1}{λ} ∑_{m=0}^{n−1} IE [e^{−λ(D_{n}−D_{m})} − 1] + IE[D_{n}]

+ ∑_{j=0}^{n−2} λ^{j} ∑_{m=0}^{n−j−2} IE [e^{−λ(D_{n}−D_{m})} {p_{j+1}(D_{n}, D_{m+1}, …, D_{m+j})

− p_{j+1}(D_{m+1}, …, D_{m+1+j})}] . (18)

Before stating the combinatorial properties of the polynomials which will allow one to prove Theorems 3 and 4 in Section 5, we first want to give explicit formulæ for the expectation of some of the transient waiting times considered in this paper.

Examples We want to look at the expectation of the waiting times of the first four customers:

IE[W_{1}] = IE[D_{0}],
IE[W_{2}] = \frac{1}{λ}IE[e^{−λ(D_{1}−D_{0})} − 1] + IE[D_{1}],

IE[W_{3}] = \frac{1}{λ}\{IE[e^{−λ(D_{2}−D_{0})} − 1] + IE[e^{−λ(D_{2}−D_{1})} − 1]\} + IE[D_{2}]
+ IE [(D_{2} − D_{1}) e^{−λ(D_{2}−D_{0})}] ,
IE[W_{4}] = \frac{1}{λ}\{IE[e^{−λ(D_{3}−D_{0})} − 1] + IE[e^{−λ(D_{3}−D_{1})} − 1]

+ IE[e^{−λ(D_{3}−D_{2})} − 1]} + IE[D_{3}]

+ IE [(D_{3} − D_{1}) e^{−λ(D_{3}−D_{0})}] + IE [(D_{3} − D_{2}) e^{−λ(D_{3}−D_{1})}]

+ λ \frac{1}{2}IE [(D_{3}^{2} − D_{2}^{2} + 2D_{1}(D_{2} − D_{3})) e^{−λ(D_{3}−D_{0})}] .

2.3 Expansion of Stationary Characteristics

Let a denote the maximal (max,+)-Lyapunov exponent of the sequence of matrices {A_{k}}, i.e.

a = lim_{r→∞} \frac{1}{r} max_{i,j} \{(⨂_{k=0}^{r} A_{−k})_{i,j}\} .  (19)

It was shown in Chapter 7 of [1] that, for all λ < a^{−1}, the waiting times W_{n} have an almost surely finite limit W as n → ∞ which is given by

W = B_{0} ⊕ ⨁_{k=1}^{∞} C(−T_{−k}) ⊗ D_{k}.  (20)

Now we additionally assume that the net-topology is such that the sequence of the D_{k}’s is given by

D_{k} = \{ \begin{matrix}η_{k},  for & k = 0, …, ξ − 1, \\ η_{ξ} + (k − ξ)a, for & k ≥ ξ, \end{matrix}  (21)

where 0 ≤ η_{0}^{i} ≤ η_{1}^{i} ≤ … ≤ η_{ξ}^{i} and ξ ∈ IN_{0}. This case covers many important queueing system with deterministic service, such as tandem queues with various types of blocking (e.g. communication– or manufacturing–blocking), as well as basic manufacturing systems, such as Kanban networks or Job-Shop systems. However, we want to mention that this assumption does not comprise all scenarios of possible stationary behavior in (max,+)-linear system with deterministic service. More precisely, this only covers the case with deterministic matrices A_{k} = A, B_{k} = B, for all k, such that the cyclicity of A is equal to 1 (see [1]).

Using the explicit representation formula given in Theorem 4 for the remainder term in the expansion of IE[W_{n}], we obtain the following finite expansion of the expected stationary waiting times IE[W^{{ξ+1}}], where the superscript indicates the special structure of the underlying sequence {D_{k}} as defined in (21).

Theorem 5 Let the sequence D_{0}, D_{1}, … be defined according to (21) for some ξ ∈ IN_{0} and η_{0}, …, η_{ξ} ∈ IR. Then the expectation of the stationary waiting time W^{{ξ+1}} has the following explicit representation for all arrival intensities λ ∈ [0, \frac{1}{a}):

IE [W^{\{ξ+1\}}] = \frac{aρ}{2(1 − ρ)} + η_{ξ} − \frac{ξ}{λ} + \frac{(1 − ρ)}{λ} \{

∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})} + ∑_{m=0}^{ξ−2} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})} ∑_{l=1}^{ξ−1−m}e^{−ρl}

× {p_{l}(λ(η_{ξ} + (l + m − ξ)a), λη_{m+1}, …, λη_{m+l−1})
− p_{l}(λη_{m+1}, …, λη_{m+l})} } .

Before we start proving this theorem, we want to look at the explicit formula for IE[W^{{ξ+1}}] for some particular values of ξ. For small values of ξ the expectation of the stationary waiting time is given by the following formulas:

IE [W^{\{1\}}] = \frac{aρ}{2(1 − ρ)} + η_{0}

IE [W^{\{2\}}] = \frac{aρ}{2(1 − ρ)} + η_{1} − \frac{1}{λ} \{1 − (1 − ρ)e^{−λ(η_{1}−a−η_{0})}\}

IE [W^{\{3\}}] = \frac{aρ}{2(1 − ρ)} + η_{2} − \frac{2}{λ} + \frac{(1 − ρ)}{λ} \{ e^{−λ(η_{2}−2a−η_{0})}

+ e^{−λ(η_{2}−a−η_{1})} + λ(η_{2} − a − η_{1})e^{−λ(η_{2}−a−η_{0})} }

IE [W^{\{4\}}] = \frac{aρ}{2(1 − ρ)} + η_{3} − \frac{3}{λ} + \frac{(1 − ρ)}{λ} \{ e^{−λ(η_{3}−3a−η_{0})}
+ e^{−λ(η_{3}−2a−η_{1})} + e^{−λ(η_{3}−a−η_{2})}
+ λ(η_{3} − 2a − η_{1}) e^{−λ(η_{3}−2a−η_{0})}
+ λ(η_{3} − a − η_{2}) e^{−λ(η_{3}−a−η_{1})}
+ {p_{2}(λ(η_{3} − a), λη_{1}) − p_{2}(λη_{1}, λη_{2})} e^{−λ(η_{3}−a−η_{0})} } .

Examples of (max,+)-linear systems with ξ small are given by tandem queues and the Kanban system considered in Section 4.2 of [3]. Before we continue we want to give a further discussion of these examples that show the applicability of the theorems stated in Section 2.

3 Examples

3.1 A Three-Station Tandem Queueing Network

In this section we apply our results to investigate some transient characteristics of a three-single-server FIFO tandem queue with infinite capacity and all queues initially empty. A Petri-net representation of this system is given in Section 4.2.2 of [3]. The sequences of matrices A_{n} and vectors B_{n} that describe the evolution of this particular stochastic system are

A_{n} = ( \begin{matrix}σ_{n}^{1} & ε & ε \\ σ_{n}^{1} + σ_{n+1}^{1} & σ_{n}^{2} & ε \\ σ_{n}^{1} + σ_{n+1}^{1} + σ_{n+1}^{2} & σ_{n}^{2} + σ_{n+1}^{2} & σ_{n}^{3} \end{matrix} ) , B_{n} = ( \begin{matrix}0 \\ σ_{n}^{1} \\ σ_{n}^{1} + σ_{n}^{2} \end{matrix} ) ,

respectively, where σ_{n}^{i} denotes the n-th service time at server i. For more details on how to derive these matrices from a given Petri net representation of a stochastic network, see [3]. In this example, we assume that an arriving customer experiences identical service times at all servers, i.e. σ_{−n}^{i} = σ(n) for all i = 1, 2, 3. We investigate the mean delay between an arrival and the time that this customer starts his service at Station 3. The first random variables D_{n}^{3} necessary to answer this question can easily be calculated by simple (max,+) matrix multiplication:

D_{0}^{3} = 2 σ(0)
D_{1}^{3} = σ(1) + 2 max{σ(0), σ(1)}
D_{2}^{3} = σ(1) + σ(2) + 2 max{σ(0), σ(1), σ(2)}.

If we are interested in the mean delay of the second customer, Theorems 3 and 4 imply that we have to calculate

IE[W_{2}] = \frac{1}{λ}IE [e^{−λ(D_{1}^{3}−D_{0}^{3})} − 1] + IE [D_{1}^{3}] ,

or, when using the structure of {D_{n}^{3}} given above,

IE[W_{2}]
= ∫_{0}^{∞} ∫_{0}^{x_{0}} \{\frac{1}{λ} e^{−λ x_{1}} + (x_{1} + 2 x_{0})\} dF_{σ(1)}(x_{1}) dF_{σ(0)}(x_{0})

+ ∫_{0}^{∞} ∫_{x_{0}}^{∞} \{\frac{1}{λ} e^{−λ(3 x_{1}−2 x_{0})} + 3 x_{1}\} dF_{σ(1)}(x_{1}) dF_{σ(0)}(x_{0}) − \frac{1}{λ}.

Now let us assume that σ(n) is given by a sequence of i.i.d. random variables and that the distribution function F_{σ(n)} is given by F_{σ(n)}(x) = 1 − e^{− \frac{1}{β} x}, for all x ∈ [0, ∞) and n ≥ 0, where β > 0. Then we can calculate IE[W_{2}] as a function of λ ≥ 0 and obtain

IE[W_{2}] = \frac{12 β^{3} λ^{2} + 25 β^{2} λ + 4 β}{3 β^{2} λ^{2} + 7 β λ + 2} .  (22)

The same calculation can be done for the mean delay of the third customer. According to Theorem 4 we know that

IE[W_{3}] = \frac{1}{λ} \{ IE [e^{−λ(D_{2}^{3}−D_{0}^{3})} − 1] + IE [e^{−λ(D_{2}^{3}−D_{1}^{3})} − 1] \}
+ IE [D_{2}^{3}] + IE [(D_{2}^{3} − D_{1}^{3}) e^{−λ(D_{2}^{3}−D_{0}^{3})}] ,

and therefore, in the given context,

IE[W_{3}] + \frac{2}{λ}

= ∫_{0}^{∞} ∫_{0}^{x_{0}} ∫_{0}^{x_{0}} \{\frac{1}{λ} e^{−λ(x_{1}+x_{2})} + \frac{1}{λ} e^{−λ x_{2}} + (2 x_{0} + x_{1} + x_{2})

+x_{2} e^{−λ(x_{1}+x_{2})}} dF_{σ(2)}(x_{2}) dF_{σ(1)}(x_{1}) dF_{σ(0)}(x_{0})

+ ∫_{0}^{∞} ∫_{x_{0}}^{∞} ∫_{0}^{x_{1}} \{\frac{1}{λ} e^{−λ(3 x_{1}+x_{2}−2 x_{0})} + \frac{1}{λ} e^{−λ x_{2}} + (3 x_{1} + x_{2})

+ x_{2} e^{−λ(3 x_{1}+x_{2}−2 x_{0})}} dF_{σ(2)}(x_{2}) dF_{σ(1)}(x_{1}) dF_{σ(0)}(x_{0})

+ ∫_{0}^{∞} ∫_{0}^{x_{0}} ∫_{x_{0}}^{∞} \{\frac{1}{λ} e^{−λ(x_{1}+3 x_{2}−2 x_{0})} + \frac{1}{λ} e^{−λ(3 x_{2}−2 x_{0})} + (x_{1} + 3 x_{2})

+ (3 x_{2} − 2 x_{0}) e^{−λ(x_{1}+3 x_{2}−2 x_{0})}} dF_{σ(2)}(x_{2}) dF_{σ(1)}(x_{1}) dF_{σ(0)}(x_{0})

+ ∫_{0}^{∞} ∫_{x_{0}}^{∞} ∫_{x_{1}}^{∞} \{\frac{1}{λ} e^{−λ(x_{1}+3 x_{2}−2 x_{0})} + \frac{1}{λ} e^{−λ(3 x_{2}−2 x_{1})} + (x_{1} + 3 x_{2})

+ (3 x_{2} − 2 x_{1}) e^{−λ(x_{1}+3 x_{2}−2 x_{0})}} dF_{σ(2)}(x_{2}) dF_{σ(1)}(x_{1}) dF_{σ(0)}(x_{0}).

Figure 1: Mean waiting times of the second and third customer.

If we make the same assumption on the service time distribution as above, we can evaluate these integrals. We can use a computer algebra system like MAPLE V or Mathematica to do the symbolic integration and obtain

IE[W_{3}] = (4896 β^{10}λ^{9} + 55392 β^{9}λ^{8} + 259504 β^{8}λ^{7} + 655376 β^{7}λ^{6}
+ 972012 β^{6}λ^{5} + 864155 β^{5}λ^{4} + 451939 β^{4}λ^{3}

+ 132462 β^{3}λ^{2} + 19980 β^{2}λ + 1296 β) /

( (144 β^{4}λ^{4} + 552 β^{3}λ^{3} + 708 β^{2}λ^{2} + 342 β λ + 54)
(1 + 5 β λ + 6 β^{2}λ^{2})(4 + 4 β λ + β^{2}λ^{2})(β λ + 3) ) .

Both IE[W_{2}] and IE[W_{3}] are plotted in Figure 1 for β = 3.

3.2 A Two-Stage Kanban System

Since in the previous example the service times were chosen to be random, we want to give another example where the service times are deterministic. We analyze a two-stage Kanban system. A Petri-net representation of this system is given in Figure 2. This example has already been studied in Section 4.2.4 of [3], where polynomial approximations for mean stationary waiting times were calculated. Note, however, that the remainder term has not been considered in [3].

Alternative 1 We want to apply Theorem 5 to the stationary mean waiting time

[figure: σ_{n}^{(1)}; σ_{n}^{(2)}; ; W^{(4)}; u; t_{1}; t_{2}; t_{3}; t_{4}; t_{5}; t_{6}; t_{7}; Station 1; Station 2]

Figure 2: Petri-net representation of a two-stage Kanban system

IE[W^{4}] starting from the arrival of a customer to the system (or, equivalently, the firing of transition u), until this customer leaves Station 1 (firing of transition t_{4}). To give a numerical example we assume that the service time σ_{n}^{(1)} of the machine at Station 1 is constant and equal to 3 units of time. Also, the service time σ_{n}^{(2)} of machine 2 at the second station is assumed to be constant and equal to 5 units of time. Thus, we can use the formulas obtained in Section 4.2.4 of [3] to compute D_{0}^{4} = 3, D_{1}^{4} = 6, D_{2}^{4} = 9 and D_{n}^{4} = 13 + 5 (n − 3), for n ≥ 3, and get, for λ ∈ [0, 0.2),

IE [W^{4}] = \frac{25 λ}{2 − 10 λ} + 13 − \frac{3}{λ}

+ \frac{(1 − 5 λ) (e^{5 λ} + e^{3 λ} + e^{λ} − 3 λ − λ e^{−2 λ} − \frac{5}{2} λ^{2} e^{−5 λ})}{λ}. (23)

On the other hand, if we want to investigate W^{7}, i.e. the delay between the arrival of a customer into the system and his departure from the system, or, equivalently, from Station 2, we find D_{n}^{7} = 8 + 5 n, for all n ≥ 0. Thus, in a sense, this system characteristic is much simpler, and we obtain

IE [W^{7}] = \frac{25 λ}{2 − 10 λ} + 8 = \frac{16 − 55 λ}{2 − 10 λ},  (24)

for λ ∈ [0, 0.2).

Alternative 2 Consider the same system as above, but with service times given by σ_{n}^{(1)} = σ_{n}^{(2)} = 4. So we still have the same total service time per customer, with the only difference that the work is now balanced symmetrically on both servers. This gives D_{n}^{4} = 4 + 4 n and D_{n}^{7} = 8 + 4 n, for n ≥ 0, respectively. Thus, Theorem 5 yields

IE [W^{4}] = \frac{4 − 8 λ}{1 − 4 λ}  and  IE [W^{7}] = \frac{8 − 24 λ}{1 − 4 λ},  (25)

for 0 ≤ λ < 0.25. Next, we want to use the mean stationary waiting times

Figure 3: Mean stationary waiting times until leaving Station 2

computed in (23), (24) and (25) to compare the performance of these two system configurations. Direct computation or looking at Figure 3 yields

IE^{(3−5)} [W^{7}] = \frac{16 − 55 λ}{2 − 10 λ} > \frac{8 − 24 λ}{1 − 4 λ} = IE^{(4−4)} [W^{7}] ,

for all 0 < λ < 0.2. The additional superscripts were introduced to help keeping waiting times from different examples apart. If we look at the mean stationary waiting time until leaving Station 1, and plot the different examples in Figure 4, the situation is as follows:

IE^{(3−5)} [W^{4}] \begin{matrix}≤ \\ > \end{matrix} IE^{(4−4)} [W^{4}] for \begin{aligned}0 & ≤ & λ & ≤ & 0.1438 \\ 0.1438 & < & λ & < & 0.2. \end{aligned}

Alternative 3 Interchanging the service times in the first system alternative yields D_{n}^{4} = 5 + 5 n and D_{n}^{7} = 8 + 5 n, for n ≥ 0, and thus

IE^{(5−3)} [W^{4}] = \frac{10 − 25 λ}{2 − 10 λ} > \frac{8 − 24 λ}{1 − 4 λ} = IE^{(4−4)} [W^{4}] ,

Figure 4: Mean stationary waiting times until leaving Station 1

for all 0 < λ < 0.2. Since we have IE^{(5−3)}[W^{7}] = IE^{(3−5)}[W^{7}], it is immediate

that IE^{(5−3)}[W^{7}] > IE^{(4−4)}[W^{7}] holds for all 0 < λ < 0.2.

Conclusion We conclude that, compared to a balanced design, shifting service time from Station 1 to Station 2 leads to an increased overall waiting time in the system and yields a better performance at Station 1 only if the arrival intensity is kept under a certain bound. On the other hand, shifting service time from Station 2 to Station 1 even worsens the situation without providing any compensatory benifit whatsoever. Thus, if we take mean stationary waiting times as the critical performance measure for this Kanban system and if short expected delays at Station 1 are not a restriction imposed by the system, a balanced design, where service times are chosen equal, or as close as possible, should be prefered.

4 Combinatorial Properties of the Polynomials

The polynomials p_{k} appearing in the coefficients of the power series expansions stated in Section 2 are of independent combinatorial interest.

In addition to (13), they have a number of further remarkable properties, which will be instrumental to prove the theorems stated in Section 2 (see Section 5 and 6), and which are collected in the present section. Most of these properties are new, although we also give purely combinatorial proofs of some properties that were already mentioned in [3].

4.1 Recursion Formula

In addition to the explicit representation of the polynomials p_{k} stated in Theorem 2, another simple recursive construction of these polynomials can be given:

Theorem 6 For all k ≥ 1 and x_{0}, …, x_{k−1} ∈ IR, the polynomials p_{k}(x_{0}, x_{1}, …, x_{k−1}) defined in (9) can be expressed recursively by p_{1}(x_{0}) = x_{0} and

p_{k+1}(x_{0}, x_{1}, …, x_{k}) = \frac{1}{k + 1} ∑_{m=0}^{k}\{x_{m} − x_{(m−1 mod k+1)}\}

× p_{k}(x_{(m mod k+1)}, …, x_{(m+k−1 mod k+1)}). (26)

Proof We first introduce another notation. Let I be an additional condition on the indices i_{j} considered in the set S_{k} in the definition of the polynomials p_{k}. Then we denote by S_{k+1}^{I} the subset of S_{k+1}, the elements of which also satisfy condition I, i.e. S_{k+1}^{I} = {(i_{0}, i_{1}, …, i_{k}) ∈ S_{k+1} : I}. Next we rewrite statement (26) to

p_{k+1}(x_{0}, x_{1}, …, x_{k})

= \frac{1}{k + 1} ∑_{m=0}^{k} x_{m}\{p_{k}(x_{(m mod k+1)}, …, x_{(m+k−1 mod k+1)})
− p_{k}(x_{(m+1 mod k+1)}, …, x_{(m+k mod k+1)})}, (27)

a representation, which we will use from now on. Looking at the righthand side of equation (27) we first examine the case that m = 0, i.e. expression x_{0} {p_{k}(x_{0}, x_{1}, …, x_{k−1})−p_{k}(x_{1}, x_{2}, …, x_{k})}. Using (9) together with the notation introduced in (10), (11) and above, we get

x_{0} p_{k}(x_{0}, x_{1}, …, x_{k−1}) = x_{0} ∑_{(i_{0},i_{1},...,i_{k−1})∈S_{k}}(−1)^{q_{k}(i_{0},i_{1},...,i_{k−1})} ∏_{j=0}^{k−1} \frac{x_{j}^{i_{j}}}{i_{j}!}

= ∑_{(i_{0},i_{1},...,i_{k−1})∈S_{k}}(−1)^{q_{k}(i_{0},i_{1},...,i_{k−1})} \frac{x_{0}^{i_{0}+1}}{i_{0}!} ∏_{j=1}^{k−1} \frac{x_{j}^{i_{j}}}{i_{j}!}

= ∑_{(i_{0},i_{1},...,i_{k−1})∈S_{k}^{i_{0}=0}} … + ∑_{(i_{0},i_{1},...,i_{k−1})∈S_{k}^{i_{0}>0}} …

F. Baccelli, S. Hasenfuss and V. Schmidt / (max,+)–Linear Systems 19

=  − \begin{matrix}& ∑ \\ [ & (τ_{0},τ_{1},...,τ_{k}) where τ_{0}=1,τ_{k}=0 τ_{j}=i_{j},j=1,...,k−1 and (i_{0},i_{1},...,i_{k−1})∈S_{k}^{i_{0}=0} & ] \end{matrix}(−1)^{q_{k+1}(τ_{0},τ_{1},...,τ_{k})} ∏_{j=0}^{k} \frac{x_{j}^{τ_{j}}}{τ_{j}!}

+ \begin{matrix}& ∑ \\ [ & (τ_{0},τ_{1},...,τ_{k}) where τ_{0}=i_{0}+1>1,τ_{k}=0 τ_{j}=i_{j},j=1,...,k−1 and (i_{0},i_{1},...,i_{k−1})∈S_{k}^{i_{0}>0} & ] \end{matrix}(−1)^{q_{k+1}(τ_{0},τ_{1},...,τ_{k})}τ_{0} ∏_{j=0}^{k} \frac{x_{j}^{τ_{j}}}{τ_{j}!} .

On the other hand we see that

− x_{0}p_{k}(x_{1}, x_{2}, …, x_{k}) = − x_{0} ∑_{(i_{1},i_{2},...,i_{k})∈S_{k}}(−1)^{q_{k}(i_{1},i_{2},...,i_{k})} ∏_{j=1}^{k} \frac{x_{j}^{i_{j}}}{i_{j}!}

= ∑_{(i_{1},i_{2},...,i_{k})∈S_{k}}(−1)^{q_{k}(i_{1},i_{2},...,i_{k})+1}x_{0} ∏_{j=1}^{k} \frac{x_{j}^{i_{j}}}{i_{j}!}
= ∑_{(i_{1},i_{2},...,i_{k})∈S_{k}^{i_{k}=0}} … + ∑_{(i_{1},i_{2},...,i_{k})∈S_{k}^{i_{k}>0}} …
= \begin{matrix}& ∑ \\ [ & (τ_{0},τ_{1},...,τ_{k}) where τ_{0}=1,τ_{k}=0 τ_{j}=i_{j},j=1,...,k−1 and (i_{1},i_{2},...,i_{k})∈S_{k}^{i_{k}=0} & ] \end{matrix}(−1)^{q_{k+1}(τ_{0},τ_{1},...,τ_{k})} ∏_{j=0}^{k} \frac{x_{j}^{τ_{j}}}{τ_{j}!}

+ \begin{matrix}& ∑ \\ [ & (τ_{0},τ_{1},...,τ_{k}) where τ_{0}=1,τ_{k}>0 τ_{j}=i_{j},j=1,...,k−1 and (i_{1},i_{2},...,i_{k})∈S_{k}^{i_{k}>0} & ] \end{matrix}(−1)^{q_{k+1}(τ_{0},τ_{1},...,τ_{k})} ∏_{j=0}^{k} \frac{x_{j}^{τ_{j}}}{τ_{j}!} .

Putting both results together then yields x_{0} {p_{k}(x_{0}, x_{1}, …, x_{k−1}) − p_{k}(x_{1}, x_{2}, …, x_{k})}

= ∑_{(τ_{0},τ_{1},...,τ_{k})∈S_{k+1}^{τ_{0}>1}} (−1)^{q_{k+1}(τ_{0},τ_{1},...,τ_{k})}τ_{0} ∏_{j=0}^{k} \frac{x_{j}^{τ_{j}}}{τ_{j}!}

+ ∑_{(τ_{0},τ_{1},...,τ_{k})∈S_{k+1}^{τ_{0}=1}} (−1)^{q_{k+1}(τ_{0},τ_{1},...,τ_{k})} ∏_{j=0}^{k} \frac{x_{j}^{τ_{j}}}{τ_{j}!}

= ∑_{(τ_{0},τ_{1},...,τ_{k})∈S_{k+1}^{τ_{0}>0}}(−1)^{q_{k+1}(τ_{0},τ_{1},...,τ_{k})}τ_{0} ∏_{j=0}^{k} \frac{x_{j}^{τ_{j}}}{τ_{j}!} .

Analogous reasoning for 1 ≤ m ≤ k gives

x_{m}{p_{k}(x_{(m mod k+1)}, …, x_{(m+k−1 mod k+1)})

− p_{k}(x_{(m+1 mod k+1)}, …, x_{(m+k mod k+1)})}
= ∑_{(τ_{0},τ_{1},...,τ_{k})∈S_{k+1}^{τm>0}}(−1)^{q_{k+1}(τ_{0},τ_{1},...,τ_{k})}τ_{m} ∏_{j=0}^{k} \frac{x_{j}^{τ_{j}}}{τ_{j}!} ,

and therefore, since τ_{0} + τ_{1} + … + τ_{k} = k + 1 for (τ_{0}, τ_{1}, …, τ_{k}) ∈ S_{k+1},

\frac{1}{k + 1} ∑_{m=0}^{k} x_{m}\{p_{k}(x_{(m mod k+1)}, …, x_{(m+k−1 mod k+1)})

− p_{k}(x_{(m+1 mod k+1)}, …, x_{(m+k mod k+1)})}

= \frac{1}{k + 1} ∑_{m=0}^{k} ∑_{(τ_{0},τ_{1},...,τ_{k})∈S_{k+1}^{τm>0}}(−1)^{q_{k+1}(τ_{0},τ_{1},...,τ_{k})}τ_{m} ∏_{j=0}^{k} \frac{x_{j}^{τ_{j}}}{τ_{j}!}
= \frac{1}{k + 1} ∑_{(τ_{0},τ_{1},...,τ_{k})∈S_{k+1}}(−1)^{q_{k+1}(τ_{0},τ_{1},...,τ_{k})}(τ_{0} + τ_{1} + … + τ_{k}) ∏_{j=0}^{k} \frac{x_{j}^{τ_{j}}}{τ_{j}!}
= ∑_{(τ_{0},τ_{1},...,τ_{k})∈S_{k+1}}(−1)^{q_{k+1}(τ_{0},τ_{1},...,τ_{k})} ∏_{j=0}^{k} \frac{x_{j}^{τ_{j}}}{τ_{j}!} = p_{k+1}(x_{0}, x_{1}, …, x_{k}).

The following properties of the polynomials p_{k} can now be stated as simple consequences of the preceeding theorem.

Corollary 1 The polynomials p_{k}, k ≥ 1, are invariant with respect to circular permutation, i.e.

p_{k}(x_{0}, x_{1}, …, x_{k−1}) = p_{k}(x_{1}, …, x_{k−1}, x_{0}),  (28)

for all x_{0}, x_{1}, …, x_{k−1} ∈ IR.

Proof Making direct use of (27) yields

p_{k+1}(x_{1}, …, x_{k}, x_{0})
= \frac{1}{k + 1} \{ x_{1}(p_{k}(x_{1}, …, x_{k}) − p_{k}(x_{2}, …, x_{k}, x_{0}))
+ x_{2}(p_{k}(x_{2}, …, x_{k}, x_{0}) − p_{k}(x_{3}, …, x_{k}, x_{0}, x_{1}))
+ …
+ x_{0}(p_{k}(x_{0}, x_{1}, …, x_{k−1}) − p_{k}(x_{1}, …, x_{k})) }
= \frac{1}{k + 1} ∑_{m=0}^{k} x_{m}\{p_{k}(x_{(m mod k+1)}, …, x_{(m+k−1 mod k+1)})
− p_{k}(x_{(m+1 mod k+1)}, …, x_{(m+k mod k+1)})}
= p_{k+1}(x_{0}, x_{1}, …, x_{k}),

where the order of summation has been rearranged to get the second equality.

Corollary 2 For all k ≥ 1 and x_{0}, x_{1}, …, x_{k} ∈ IR, the polynomials p_{k+1}(x_{0}, x_{1}, …, x_{k}) are translation–invariant, i.e. the equality

p_{k+1}(x_{0}, x_{1}, …, x_{k}) = p_{k+1}(x_{0} + t, x_{1} + t, …, x_{k} + t)  (29)

holds for all t ∈ IR.

Proof by induction with respect to k. Let k = 1. Then

p_{2}(x_{0} + t, x_{1} + t) = \frac{1}{2}(x_{0} + t)^{2} + \frac{1}{2}(x_{1} + t)^{2} − (x_{0} + t)(x_{1} + t)
= \frac{1}{2}x_{0}^{2} + \frac{1}{2}x_{1}^{2} − x_{0}x_{1} = p_{2}(x_{0}, x_{1}).

Now we assume the validity of statement (29) for some natural k ≥ 1. Using representation (26) of Theorem 6 we get that

p_{k+1}(x_{0} + t, x_{1} + t, …, x_{k} + t)

= \frac{1}{k + 1} ∑_{m=0}^{k}(x_{m} + t − x_{(m−1 mod k+1)} − t)
× p_{k}(x_{(m mod k+1)} + t, …, x_{(m+k−1 mod k+1)} + t)
= \frac{1}{k + 1} ∑_{m=0}^{k}(x_{m} − x_{(m−1 mod k+1)}) p_{k}(x_{(m mod k+1)}, …, x_{(m+k−1 mod k+1)})
= p_{k+1}(x_{0}, x_{1}, …, x_{k}),

where the last but one equality follows from the induction hypothesis.

The next property can immediately be seen from the definition of the polynomials but will be stated here for completeness reasons: For all k ≥ 1 and x_{0}, x_{1}, …, x_{k−1} ∈ IR,

p_{k}(t x_{0}, t x_{1}, …, t x_{k−1}) = t^{k} p_{k}(x_{0}, x_{1}, …, x_{k−1}),  (30)

for all t ∈ IR.

4.2 Differences

As one can already suspect from looking at representation (27), polynomial differences play a very important role when investigating the polynomials p_{k}. Especially, when their explicit formula becomes too complex to overlook.

In order to get an idea what impact on the overall value of the polynomial the variation of a single argument has, the following result will be helpful.

Theorem 7 For all k ≥ 1 and x_{0}, x_{1}, …, x_{k−1} ∈ IR the following equality holds:

p_{k}(x_{0}, x_{1}, …, x_{k−1}) − p_{k}(0, x_{1}, …, x_{k−1})
= \frac{x_{0}^{k}}{k!} − ∑_{j=1}^{k−1} \frac{x_{0}^{k−j}}{(k − j)!} \{ p_{j}(x_{1}, x_{2}, …, x_{j}) − p_{j}(0, x_{1}, …, x_{j−1}) \} . (31)

Proof The summation in equation (9) of the definition of the polynomials p_{k} can be split into the following summands:

p_{k}(x_{0}, x_{1}, …, x_{k−1})

= ∑_{(i_{0},i_{1},...,i_{k−1})∈S_{k}^{i_{0}=0}} … + ∑_{(i_{0},i_{1},...,i_{k−1})∈S_{k}^{i_{0}=1}} … + … + ∑_{(i_{0},i_{1},...,i_{k−1})∈S_{k}^{i_{0}=k}} …

Looking at the first sum yields the following reasoning. In order to get those terms belonging to the first sum, we have to take all the monomials of p_{k}(x_{0}, …, x_{k−1}) and discard exactly those, which have i_{0} > 0. But since the terms are products of powers of the x_{i}’s, this can precisely be achieved by setting x_{0} = 0. Then all the monomials with i_{0} > 0 vanish and only those with i_{0} = 0 remain. Therefore

∑_{(i_{0},i_{1},...,i_{k−1})∈S_{k}^{i_{0}=0}}(−1)^{q_{k}(i_{0},i_{1},...,i_{k−1})} ∏_{n=0}^{k−1} \frac{x_{n}^{i_{n}}}{i_{n}!} = p_{k}(0, x_{1}, …, x_{k−1}).

It is very easy to see that

∑_{(i_{0},i_{1},...,i_{k−1})∈S_{k}^{i_{0}=k}}(−1)^{q_{k}(i_{0},i_{1},...,i_{k−1})} ∏_{n=0}^{k−1} \frac{x_{n}^{i_{n}}}{i_{n}!} = \frac{x_{0}^{k}}{k!} ,

because S_{k}^{i_{0}=k} = {(k, 0, 0, …, 0)}. Now let us look at the case i_{0} = j, where j ∈ {1, …, k − 1}. We see that

∑_{(i_{0},i_{1},...,i_{k−1})∈S_{k}^{i_{0}=j}}(−1)^{q_{k}(i_{0},i_{1},...,i_{k−1})} ∏_{n=0}^{k−1} \frac{x_{n}^{i_{n}}}{i_{n}!}

= ∑_{(j,i_{1},...,i_{k−j},^{0,...,0}_{j−1})∈S_{k}^{i_{k−j} >0}}(−1)^{q_{k}(j,i_{1},...,i_{k−j},^{0,...,0}_{j−1})} \frac{x_{0}^{j}}{j!} ∏_{n=1}^{k−j} \frac{x_{n}^{i_{n}}}{i_{n}!} ∏_{n=k−j+1}^{k−1} \frac{x_{n}^{0}}{0!}

= \frac{x_{0}^{j}}{j!} ∑_{(i_{1},...,i_{k−j})∈S_{k−j}^{i_{k−j} >0}}(−1)^{q_{k−j}(i_{1},...,i_{k−j})+1} ∏_{n=1}^{k−j} \frac{x_{n}^{i_{n}}}{i_{n}!}

= −\frac{x_{0}^{j}}{j!} \{  ∑_{(i_{1},...,i_{k−j})∈S_{k−j}}(−1)^{q_{k−j}(i_{1},...,i_{k−j})} ∏_{n=1}^{k−j} \frac{x_{n}^{i_{n}}}{i_{n}!}

− ∑_{(i_{1},...,i_{k−j})∈S_{k−j}^{i_{k−j} =0}}(−1)^{q_{k−j}(i_{1},...,i_{k−j})} ∏_{n=1}^{k−j} \frac{x_{n}^{i_{n}}}{i_{n}!} \}

= −\frac{x_{0}^{j}}{j!} \{ p_{k−j}(x_{1}, …, x_{k−j}) − p_{k−j}(x_{1}, …, x_{k−j−1}, 0) \} .

Using the invariance–property stated in Corollary 1 and putting all the different cases together proves the theorem.

If the arguments of such polynomial differences considered in Theorem 7 have a certain structure, the resulting expansion may simplify significantly. Two important cases which we will need in the proofs later on are considered in the next corollaries.

Corollary 3 For all k, m ∈ IN_{0} and x_{0}, x_{1}, …, x_{k} ∈ IR the following equality holds:

p_{k+m+1}(\underbrace{0, …, 0}_{m}, x_{0}, x_{1}, …, x_{k}) − p_{k+m+1}(\underbrace{0, …, 0}_{m+1}, x_{1}, …, x_{k})

= \frac{x_{0}^{k+m+1}}{(k + m + 1)!} − ∑_{j=1}^{k} \frac{x_{0}^{k+m+1−j}}{(k + m + 1 − j)!} \{ p_{j}(x_{1}, x_{2}, …, x_{j})
− p_{j}(0, x_{1}, …, x_{j−1}) } . (32)

Proof We first realize that due to the translation-invariance property of the poloynomials p_{k} we can rewrite the lefthand side of (32) according to

p_{k+m+1}(\underbrace{0, …, 0}_{m}, x_{0}, x_{1}, …, x_{k}) − p_{k+m+1}(\underbrace{0, …, 0}_{m+1}, x_{1}, …, x_{k})

= p_{k+m+1}(x̃_{0}, x̃_{1}, …, x̃_{k+m}) − p_{k+m+1}(0, x̃_{1}, …, x̃_{k+m}),

where x̃_{j} = x_{j} for j = 0, …, k and x̃_{j} = 0 for j = k + 1, …, k + m. But this allows us to apply Theorem 7 to obtain

p_{k+m+1}(x̃_{0}, x̃_{1}, …, x̃_{k+m}) − p_{k+m+1}(0, x̃_{1}, …, x̃_{k+m})
= \frac{x̃_{0}^{k+m+1}}{(k + m + 1)!} − ∑_{j=1}^{k+m} \frac{x̃_{0}^{j}}{j!} \{ p_{k+m+1−j}(x̃_{1}, x̃_{2}, …, x̃_{k+m+1−j})
− p_{k+m+1−j}(0, x̃_{1}, …, x̃_{k+m−j}) }
= \frac{x_{0}^{k+m+1}}{(k + m + 1)!} − ∑_{j=m+1}^{k+m} \frac{x_{0}^{j}}{j!} \{ p_{k+m+1−j}(x_{1}, x_{2}, …, x_{k+m+1−j})
− p_{k+m+1−j}(0, x_{1}, …, x_{k+m−j}) },

where we used the fact that for j ≤ m we have k + m + 1 − j ≥ k + 1 and thus

p_{k+m+1−j}(x̃_{1}, x̃_{2}, …, x̃_{k+m+1−j}) = p_{k+m+1−j}(x_{1}, x_{2}, …, x_{k}, \underbrace{0, …, 0}_{m+1−j})

= p_{k+m+1−j}(0, x_{1}, x_{2}, …, x_{k}, \underbrace{0, …, 0}_{m−j})
= p_{k+m+1−j}(0, x̃_{1}, x̃_{2}, …, x̃_{k+m−j}).

If we substitute j by m + j + 1 we get the statement of this corollary.

Corollary 4 For all k, m ∈ IN_{0} and x_{0}, x_{1}, …, x_{m} ∈ IR the following equality holds:

p_{k+1}(x_{0}, …, x_{m−1}, x_{m}, 1, …, k − m) − p_{k+1}(x_{0}, …, x_{m−1}, 0, 1, …, k − m)

= \{ p_{k+1}(x_{0}, …, x_{m−1}, x_{m}, \underbrace{0, …, 0}_{k−m}) − p_{k+1}(x_{0}, …, x_{m−1}, \underbrace{0, …, 0}_{k+1−m}) \}

− \{ p_{k}(x_{0}, …, x_{m−1}, x_{m}, \underbrace{0, …, 0}_{k−m−1}) − p_{k}(x_{0}, …, x_{m−1}, \underbrace{0, …, 0}_{k−m}) \} . (33)

Proof The proof of this corollary is given by induction with respect to k. We first apply Corollary 1 to reorder the arguments of the polynomials on the left-hand side of (33) so as to apply Theorem 7.

p_{k+1}(x_{0}, …, x_{m−1}, x_{m}, 1, …, k − m) − p_{k+1}(x_{0}, …, x_{m−1}, 0, 1, …, k − m)

= p_{k+1}(x_{m}, 1, …, k − m, x_{0}, …, x_{m−1}) − p_{k+1}(0, 1, …, k − m, x_{0}, …, x_{m−1})
= \frac{x_{m}^{k+1}}{(k + 1)!} − \frac{x_{m}^{k}}{k!} − ∑_{j=1}^{m} \frac{x_{m}^{j}}{j!} \{ p_{k+1−j}(1, …, k − m, x_{0}, …, x_{m−j})

− p_{k+1−j}(0, 1, …, k − m, x_{0}, …, x_{m−j−1}) },

where we used the fact that p_{1}(1) − p_{1}(0) = 1. Due to translation–invariance property (29) we used that p_{j}(1, …, j) − p_{j}(0, 1, …, j − 1) = 0 to omit all terms with j = m + 1, …, k − 1. After another reordering of the arguments of the polynomials, we use the induction hypothesis on the differences in the last line above and obtain

p_{k+1}(x_{0}, …, x_{m−1}, x_{m}, 1, …, k − m) − p_{k+1}(x_{0}, …, x_{m−1}, 0, 1, …, k − m)

= \frac{x_{m}^{k+1}}{(k + 1)!} − ∑_{j=1}^{m} \frac{x_{m}^{j}}{j!} \{ p_{k+1−j}(x_{0}, …, x_{m−j}, \underbrace{0, …, 0}_{k−m})

− p_{k+1−j}(x_{0}, …, x_{m−j−1}, \underbrace{0, …, 0}_{k+1−m}) \}

− \{\frac{x_{m}^{k}}{k!} − ∑_{j=1}^{m} \frac{x_{m}^{j}}{j!} \{ p_{k−j}(x_{0}, …, x_{m−j}, \underbrace{0, …, 0}_{k−m−1})

− p_{k−j}(x_{0}, …, x_{m−j−1}, \underbrace{0, …, 0}_{k−m}) \} \}

= p_{k+1}(x_{0}, …, x_{m−1}, x_{m}, \underbrace{0, …, 0}_{k−m}) − p_{k+1}(x_{0}, …, x_{m−1}, \underbrace{0, …, 0}_{k+1−m})

− \{ p_{k}(x_{0}, …, x_{m−1}, x_{m}, \underbrace{0, …, 0}_{k−m−1}) − p_{k}(x_{0}, …, x_{m−1}, \underbrace{0, …, 0}_{k−m}) \},

where we can give the same arguments as before to rebuild the differences according to Theorem 7.

Sometimes it is helpful to use a representation slightly different from the expansion stated in Theorem 7. Since the next result can be proved following the same lines as given for Theorem 7 with only minor modifications, an explicit proof is omitted here.

Theorem 8 For all k ≥ 0 and x_{0}, x_{1}, …, x_{k} ∈ IR the following equality holds:

p_{k+1}(x_{0}, …, x_{k−1}, x_{k}) − p_{k}(x_{0}, …, x_{k−1}, 0)

= \frac{x_{k}^{k+1}}{(k + 1)!} − ∑_{j=1}^{k} \frac{(x_{k−j})^{k+1−j}}{(k + 1 − j)!} \{p_{j}(x_{k+1−j}, …, x_{k})
− p_{j}(x_{k+1−j}, …, x_{k−1}, 0)}. (34)

Having this result we can state yet another recurrence representation of the polynomials p_{k}.

Theorem 9 For all x_{0}, x_{1}, …, x_{m} ∈ IR, 0 ≤ m ≤ k −1 and k ∈ IN the following equality holds:

p_{k+1}(x_{0}, …, x_{m−1}, x_{m}, 1, …, k − m) − p_{k+1}(x_{0}, …, x_{m−1}, 0, 1, …, k − m)

= h_{k+1}(x_{m}) − ∑_{j=0}^{m−1} h_{k−j}(x_{m−1−j}) {p_{j+1}(x_{m−j}, …, x_{m})
− p_{j+1}(0, x_{m−j}, …, x_{m−1})} ,

where the family of functions h_{j} : IR → IR, j ∈ {…, −1, 0, 1, 2, …}, is given by

h_{j}(x) = \{ \begin{matrix}\frac{x^{j}}{j!} − \frac{x^{j−1}}{(j − 1)!}, & j ≥ 1, \\ 1, & j = 0, \\ 0, & otherwise. \end{matrix}  (35)

Proof From Corollary 4 we know that

p_{k+1}(x_{0}, …, x_{m−1}, x_{m}, 1, …, k − m) − p_{k+1}(x_{0}, …, x_{m−1}, 0, 1, …, k − m)

= \{ p_{k+1}(x_{0}, …, x_{m−1}, x_{m}, \underbrace{0, …, 0}_{k−m}) − p_{k+1}(x_{0}, …, x_{m−1}, \underbrace{0, …, 0}_{k+1−m}) \} (36)

− \{ p_{k}(x_{0}, …, x_{m−1}, x_{m}, \underbrace{0, …, 0}_{k−m−1}) − p_{k}(x_{0}, …, x_{m−1}, \underbrace{0, …, 0}_{k−m}) \} . (37)

Let us first focus on difference (36) above. We use translation–invariance property (28) to reorder the arguments of the polynomials to be able to apply Theorem 8 to this difference and obtain

p_{k+1}(x_{0}, …, x_{m−1}, x_{m}, \underbrace{0, …, 0}_{k−m}) − p_{k+1}(x_{0}, …, x_{m−1}, \underbrace{0, …, 0}_{k+1−m})

= p_{k+1}(\underbrace{0, …, 0}_{k−m}, x_{0}, …, x_{m−1}, x_{m}) − p_{k+1}(\underbrace{0, …, 0}_{k−m}, x_{0}, …, x_{m−1}, 0)

= \frac{x_{m}^{k+1}}{(k + 1)!} − ∑_{j=1}^{m} \frac{x_{m−j}^{k+1−j}}{(k + 1 − j)!} \{ p_{j}(x_{m+1−j}, …, x_{m})
− p_{j}(x_{m+1−j}, …, x_{m−1}, 0) },

where we used that the summands are equal to zero for j = m + 1, …, k due to the zero factor that shows up in these cases. For difference (37) we get the same expression except for having k instead of k + 1. Putting these results together finally leads to

p_{k+1}(x_{0}, …, x_{m−1}, x_{m}, 1, …, k − m) − p_{k+1}(x_{0}, …, x_{m−1}, 0, 1, …, k − m)

= \frac{x_{m}^{k+1}}{(k + 1)!} − \frac{x_{m}^{k}}{k!} − ∑_{j=1}^{m} \{\frac{(x_{m−j})^{k+1−j}}{(k + 1 − j)!} − \frac{(x_{m−j})^{k−j}}{(k − j)!} \}
× { p_{j}(x_{m+1−j}, …, x_{m}) − p_{j}(x_{m+1−j}, …, x_{m−1}, 0) },

which is the statement of the theorem if we shift the summation index j by one and use the definition of the functions h_{j}(x).

Little extra effort is necessary to prove the next result which turns out to be the key representation formula for the proof of Theorem 5.

Theorem 10 Let k ∈ IN and m ∈ IN_{0}. For all x_{0}, x_{1}, …, x_{m} ∈ IR, the following equality holds:

p_{k}(x_{0}, x_{1}, …, x_{m}, m + 1, …, k − 1) − p_{k}(x_{1}, …, x_{m}, m + 1, …, k)
= h_{k}(x_{0}) − ∑_{j=1}^{m} {p_{j}(x_{1}, …, x_{j}) − p_{j}(j, x_{1}, …, x_{j−1})} h_{k−j}(x_{0} − j), (38)

where the functions h_{j}(·) are defined according to (35).

Proof We first want to consider the non-degenerate case, that is m < k. The main idea is to split up each of the polynomials into a telescopic sum.

p_{k}(x_{0}, x_{1}, …, x_{m}, m + 1, …, k − 1) − p_{k}(x_{1}, …, x_{m}, m + 1, …, k)

= ∑_{j=0}^{m} {p_{k}(x_{0}, …, x_{j}, j + 1, …, k − 1) − p_{k}(x_{0}, …, x_{j−1}, j, …, k − 1)}

− ∑_{j=1}^{m} {p_{k}(x_{1}, …, x_{j}, j + 1, …, k) − p_{k}(x_{1}, …, x_{j−1}, j, …, k)}

= ∑_{j=0}^{m} {p_{k}(x_{0} − j, …, x_{j} − j, 1, …, k − j − 1)
− p_{k}(x_{0} − j, …, x_{j−1} − j, 0, …, k − j − 1)}

− ∑_{j=1}^{m} {p_{k}(x_{1} − j, …, x_{j} − j, 1, …, k − j)

− p_{k}(x_{1} − j, …, x_{j−1} − j, 0, …, k − j)},

where we used the translation–invariance property of the polynomials p_{k} to bring the single differences of these polynomials into a form where Theorem 9 can be applied. Thus,

p_{k}(x_{0}, x_{1}, …, x_{m}, m + 1, …, k − 1) − p_{k}(x_{1}, …, x_{m}, m + 1, …, k)

= ∑_{j=0}^{m} { h_{k}(x_{j} − j) − ∑_{l=1}^{j} h_{k−l}(x_{j−l} − j) {p_{l}(x_{j+1−l} − j, …, x_{j} − j)

−p_{l}(0, x_{j+1−l} − j, …, x_{j−1} − j)} }

− ∑_{j=1}^{m} { h_{k}(x_{j} − j) − ∑_{l=1}^{j−1} h_{k−l}(x_{j−l} − j){p_{l}(x_{j+1−l} − j, …, x_{j} − j)

− p_{l}(0, x_{j+1−l} − j, …, x_{j−1} − j)} }

= h_{k}(x_{0}) − ∑_{j=1}^{m} h_{k−j}(x_{0} − j) {p_{j}(x_{1} − j, …, x_{j} − j)

− p_{j}(0, x_{1} − j, …, x_{j−1} − j)}.

Shifting all the arguments of the polynomials p_{j} by j finally yields (38). In case m ≥ k, we actually mean the difference p_{k}(x_{0}, x_{1}, …, x_{k−1})−p_{k}(x_{1}, …, x_{k}). Thus, the arguments given above remain valid with the summations ranging to k instead of m. But because of the way we defined h_{j}(x) for j < 0 we can also let the summation range to m instead of k without changing the result.

5 Proof of Theorem 3 and 4

We are now in a position to give the proofs of Theorem 3 and 4. Since the sequence {D_{n}} is independent of the Poisson process {T_{n}}, we will assume for the moment that the sequence {D_{n}} is deterministic. We then get the stochastic formulas of these two theorems by integrating our results w.r.t. the law of the sequence {D_{n}}.

5.1 Proof of Theorem 3

To simplify notation we define x_{j} = D_{j} − D_{n}, for j = 0, …, n − 1. Before we look at R_{n+1} as defined in (15), we notice that we can represent the polynomials p_{k} as follows:

p_{k+1}(z_{0}, …, z_{n−1}, \underbrace{0, …, 0}_{k+1−n}) = p_{k+1}(\underbrace{0, …, 0}_{k+1−n}, z_{0}, …, z_{n−1})

= ∑_{m=0}^{n−1} \{p_{k+1}( \underbrace{0, …, 0}_{k−n+m+1}, z_{m}, …, z_{n−1}) − p_{k+1}( \underbrace{0, …, 0}_{k−n+m+2}, z_{m+1}, …, z_{n−1})\}.(39)

Thus, with the usual convention that ∑_{a}^{b} = 0 whenever b < a, and using Corollary 3 for the second step, we obtain

∑_{k=n+1}^{∞} p_{k+1}(λ x_{0}, …, λ x_{n−1}, \underbrace{0, …, 0}_{k+1−n})

= ∑_{k=n+1}^{∞} ∑_{m=0}^{n−1} \{p_{k+1}( \underbrace{0, …, 0}_{k−n+m+1}, \underbrace{λ x_{m}, …, λ x_{n−1}}_{n−m})

− p_{k+1}( \underbrace{0, …, 0}_{k−n+m+2}, \underbrace{λ x_{m+1}, …, λ x_{n−1}}_{n−m−1})\}

= ∑_{k=n+1}^{∞} ∑_{m=0}^{n−1} \{\frac{(λ x_{m})^{k+1}}{(k + 1)!} − ∑_{j=1}^{n−m−1} \frac{(λ x_{m})^{k+1−j}}{(k + 1 − j)!}

× {p_{j}(λ x_{m+1}, …, λ x_{m+j}) − p_{j}(0, λ x_{m+1}, …, λ x_{m+j−1})}}

= ∑_{m=0}^{n−1} \{ ∑_{k=n+2}^{∞} \frac{(λ x_{m})^{k}}{k!} − ∑_{j=1}^{n−1−m} ( ∑_{k=n+2−j}^{∞} \frac{(λ x_{m})^{k}}{k!} )

× {p_{j}(λ x_{m+1}, …, λ x_{m+j}) − p_{j}(0, λ x_{m+1}, …, λ x_{m+j−1})}}

= ∑_{m=0}^{n−1} T_{n+1}(e^{λx_{m}}) − ∑_{m=0}^{n−2} ∑_{j=1}^{n−1−m} λ^{j} T_{n+1−j}(e^{λx_{m}})
× {p_{j}(x_{m+1}, …, x_{m+j}) − p_{j}(0, x_{m+1}, …, x_{m+j−1})}.

This completes the proof of Theorem 3.

5.2 Proof of Theorem 4

To get representation (18) as stated in Theorem 4 we have to choose another way to look at the remainder R_{n+1}.

R_{n+1} = ∑_{m=0}^{n−1} (e^{λx_{m}} − ∑_{i=0}^{n+1} λ^{i} \frac{x_{m}^{i}}{i!} ) − ∑_{m=0}^{n−2} ∑_{j=1}^{n−1−m} λ^{j} (e^{λx_{m}} − ∑_{i=0}^{n+1−j} λ^{i} \frac{x_{m}^{i}}{i!} )

× {p_{j}(x_{m+1}, …, x_{m+j}) − p_{j}(0, x_{m+1}, …, x_{m+j−1})}

= ∑_{m=0}^{n−1} \{e^{λx_{m}} − 1\} − ∑_{i=1}^{n+1} λ^{i} ∑_{m=0}^{n−1} \frac{x_{m}^{i}}{i!} − ∑_{m=0}^{n−2} ∑_{j=1}^{n−1−m} λ^{j} e^{λx_{m}}

× {p_{j}(x_{m+1}, …, x_{m+j}) − p_{j}(0, x_{m+1}, …, x_{m+j−1})}

+ ∑_{m=0}^{n−2} ∑_{j=1}^{n−1−m} λ^{j} ∑_{i=0}^{n+1−j} λ^{i} \frac{x_{m}^{i}}{i!} \{p_{j}(x_{m+1}, …, x_{m+j})

− p_{j}(0, x_{m+1}, …, x_{m+j−1})}  (40)
= I − II − III + IV,

where we naturally defined I, II, III and IV to be equal to the more complex summations showing up in (40). We first want to focus on expression III. An interchange of summation gives

III = ∑_{j=1}^{n−1} λ^{j} ∑_{m=0}^{n−1−j} e^{λx_{m}}{p_{j}(x_{m+1}, …, x_{m+j}) − p_{j}(0, x_{m+1}, …, x_{m+j−1})}. (41)

A few more steps have to be taken to rewrite IV to an appropriate form. As we just did we first interchanged those summations involving m and j. Then we also interchange those involving m and i which results in

IV = ∑_{j=1}^{n−1} ∑_{i=0}^{n+1−j} λ^{i+j} ∑_{m=0}^{n−1−j} \frac{x_{m}^{i}}{i!} \{p_{j}(x_{m+1}, …, x_{m+j})
− p_{j}(0, x_{m+1}, …, x_{m+j−1})}
= ∑_{i=1}^{n−1} λ^{i} ∑_{j=1}^{i} ∑_{m=0}^{n−1−j} \frac{x_{m}^{i−j}}{(i − j)!} \{p_{j}(x_{m+1}, …, x_{m+j})
− p_{j}(0, x_{m+1}, …, x_{m+j−1})} (42)

+ ∑_{i=n}^{n+1} λ^{i} ∑_{j=1}^{n−1} ∑_{m=0}^{n−1−j} \frac{x_{m}^{i−j}}{(i − j)!} \{p_{j}(x_{m+1}, …, x_{m+j})

− p_{j}(0, x_{m+1}, …, x_{m+j−1})}, (43)

where we substituted i → i − j, then split up the summation into two expressions and finally interchanged those summations involving j and i in both expressions to come up with the second equality. Next, we split up (42) into two parts to be able to interchange the summation over j and m, which we also did for expression (43).

IV = ∑_{i=1}^{n−1} λ^{i} ∑_{m=0}^{n−1−i} ∑_{j=1}^{i} \frac{x_{m}^{i−j}}{(i − j)!} \{p_{j}(x_{m+1}, …, x_{m+j})
− p_{j}(0, x_{m+1}, …, x_{m+j−1})} (44)

+ ∑_{i=1}^{n−1} λ^{i} ∑_{m=n−i}^{n−2} ∑_{j=1}^{n−1−m} \frac{x_{m}^{i−j}}{(i − j)!} \{p_{j}(x_{m+1}, …, x_{m+j})

− p_{j}(0, x_{m+1}, …, x_{m+j−1})} (45)

+ λ^{n} ∑_{m=0}^{n−2} ∑_{j=1}^{n−1−m} \frac{x_{m}^{n−j}}{(n − j)!} \{p_{j}(x_{m+1}, …, x_{m+j})

− p_{j}(0, x_{m+1}, …, x_{m+j−1})} (46)

+ λ^{n+1} ∑_{m=0}^{n−2} ∑_{j=1}^{n−1−m} \frac{x_{m}^{n+1−j}}{(n + 1 − j)!} \{p_{j}(x_{m+1}, …, x_{m+j})

− p_{j}(0, x_{m+1}, …, x_{m+j−1})}. (47)

Note, that we can formally allow m to range to n − 1 instead of n − 2 in (45),

(46) and (47) without changing the value of IV. Furthermore, (45) and (46) can be combined to one summation over i ranging from 1 to n. Using this representation of IV we split up II accordingly to calculate

II − IV = ∑_{i=1}^{n} λ^{i} \{ ∑_{m=0}^{n−1−i} \{ \frac{x_{m}^{i}}{i!} − ∑_{j=1}^{i} \frac{x_{m}^{i−j}}{(i − j)!} \{p_{j}(x_{m+1}, …, x_{m+j})
− p_{j}(0, x_{m+1}, …, x_{m+j−1})} }

+ ∑_{m=n−i}^{n−1} \{ \frac{x_{m}^{i}}{i!} − ∑_{j=1}^{n−1−m} \frac{x_{m}^{i−j}}{(i − j)!} \{p_{j}(x_{m+1}, …, x_{m+j})

− p_{j}(0, x_{m+1}, …, x_{m+j−1})} } }

+ λ^{n+1} ∑_{m=0}^{n−1} \{ \frac{x_{m}^{n+1}}{(n + 1)!} − ∑_{j=1}^{n−1−m} \frac{x_{m}^{n+1−j}}{(n + 1 − j)!}

× {p_{j}(x_{m+1}, …, x_{m+j}) − p_{j}(0, x_{m+1}, …, x_{m+j−1})} }

= ∑_{i=1}^{n} λ^{i} { ∑_{m=0}^{n−1−i} {p_{i}(x_{m}, …, x_{m+i−1}) − p_{i}(x_{m+1}, …, x_{m+i})}

+ ∑_{m=n−i}^{n−1} \{p_{i}(\underbrace{0, …, 0}_{m+i−n}, x_{m}, …, x_{n−1})

− p_{i}( \underbrace{0, …, 0}_{m+i−n+1}, x_{m+1}, …, x_{n−1})\} \}

+ λ^{n+1} ∑_{m=0}^{n−1} \{p_{n+1}(\underbrace{0, …, 0}_{m+1}, x_{m}, …, x_{n−1})

− p_{n+1}(\underbrace{0, …, 0}_{m+2}, x_{m+1}, …, x_{n−1})\}

= ∑_{i=1}^{n} λ^{i} p_{i}(x_{0}, …, x_{i−1}) + λ^{n+1} p_{n+1}(0, x_{0}, …, x_{n−1}),

where the first part of the second equality follows from Theorem 7 by noting that

\frac{x_{m}^{i}}{i!} − ∑_{j=1}^{i} \frac{x_{m}^{i−j}}{(i − j)!} \{p_{j}(x_{m+1}, …, x_{m+j}) − p_{j}(0, x_{m+1}, …, x_{m+j−1})\}

= \frac{x_{m}^{i}}{i!} − ∑_{j=1}^{i−1} \frac{x_{m}^{i−j}}{(i − j)!} \{p_{j}(x_{m+1}, …, x_{m+j}) − p_{j}(0, x_{m+1}, …, x_{m+j−1})\}
− {p_{i}(x_{m+1}, …, x_{m+i}) − p_{i}(0, x_{m+1}, …, x_{m+i−1})}
= {p_{i}(x_{m}, …, x_{m+i−1}) − p_{i}(0, x_{m+1}, …, x_{m+i−1})}
− {p_{i}(x_{m+1}, …, x_{m+i}) − p_{i}(0, x_{m+1}, …, x_{m+i−1})}

for all m = 0, …, n − 1 − i, and i = 1, …, n, whereas the second and third part of this equality are direct consequences of Corollary 3. Resubstituting D_{j} − D_{n} for x_{j}, j = 0, …, n − 1, as well as using invariance property (28) and (29) finally yields

II − IV = −λ D_{n} + ∑_{i=1}^{n+1} λ^{i} p_{i}(D_{0}, …, D_{i−1}),

and therefore

R_{n+1} = ∑_{m=0}^{n−1} {e^{λ(D_{m}−D_{n})} − 1} + λ D_{n} − ∑_{i=0}^{n} λ^{i+1} p_{i+1}(D_{0}, …, D_{i})

− ∑_{j=1}^{n−1} λ^{j} ∑_{m=0}^{n−1−j} e^{λ(D_{m}−D_{n})} {p_{j}(D_{m+1}, …, D_{m+j})

− p_{j}(D_{m+1}, …, D_{m+j−1}, D_{n})}, (48)

which proves Theorem 4.

6 Proof of Theorem 5

Our starting-point is the following modification of statement (18) of Theorem 4 for the expectation of the transient waiting time of the n + 1-th customer:

IE[W_{n+1}] = \frac{1}{λ} \{ ∑_{m=1}^{n} e^{−λ(D_{n}−D_{n−m})} − n + λD_{n} + ∑_{m=2}^{n} e^{−λ(D_{n}−D_{n−m})}

× ∑_{j=1}^{m−1} λ^{j} {p_{j}(D_{n}, D_{n−m+1}, …, D_{n−m+j−1})

− p_{j}(D_{n−m+1}, …, D_{n−m+j})} }. (49)

Remember that in this section we assume that D_{0}, D_{1}, … is a deterministic sequence having a special structure, see (21), that originates from a (max,+)-linear systems with deterministic services. The most simple system in this class of networks is the M/D/1 queue. We will therefore investigate this system first with respect to the formulas derived so far, and later extend this result to more general deterministic (max,+)-linear systems.

6.1 The M/D/1 Queue

The M/G/1 queue can be modelled as an open (max,+)-linear system with Poisson input. The variables D_{n} are then given by D_{0} = 0 and D_{n} = ∑_{j=1}^{n} σ_{−j}, where σ_{j} is the service time of the j-th arriving customer, see, for example, section 4.2.1 of [3]. In the M/D/1 case this simply reduces to D_{n} = n a, for n ∈ IN_{0}, since for this system the Lyapunov exponent a is equal to the constant service time σ. So we know that D_{n} − D_{m} = (n − m) a, and thus, from formula (49), with the notation ρ = λa, the expected waiting time W_{n+1}^{{0}} until service of the n + 1-th customer in the M/D/1 queue is given by

IE [W_{n+1}^{\{0\}}] = \frac{1}{λ} \{ ∑_{m=1}^{n} e^{−ρm} − n + ρn + ∑_{m=2}^{n} e^{−ρm} ∑_{j=1}^{m−1} λ^{j}
× {p_{j}(na, (n − m + 1)a, …, (n − m + j − 1)a)
− p_{j}((n − m + 1)a, …, (n − m + j)a)} }

= \frac{1}{λ} \{ ∑_{m=1}^{n} e^{−ρm} − n + ρn + ∑_{m=2}^{n} e^{−ρm} ∑_{j=1}^{m−1} ρ^{j}
× {p_{j}(m, 1, …, j − 1) − p_{j}(1, …, j)} }, (50)

where we used the translation–invariance property (29) of the polynomials p_{k} and the fact that a common factor of all arguments can be pulled out, see (30), to obtain the second equality. Theorem 7 gives an explicit formula for the polynomial difference p_{j}(m, 1, …, j − 1) − p_{j}(1, …, j), for all j ≥ 1. Thus,

IE [W_{n+1}^{\{0\}}] = \frac{1}{λ} \{ ∑_{m=1}^{n} e^{−ρm} − n + ρn + ∑_{m=2}^{n} e^{−ρm} ∑_{j=1}^{m−1} ρ^{j} \{\frac{m^{j}}{j!} − \frac{m^{j−1}}{(j − 1)!}\} \}

= \frac{1}{λ} \{ −n(1 − ρ) + ∑_{m=1}^{n} e^{−ρm} \{ ∑_{j=0}^{m−1} \frac{(ρm)^{j}}{j!} − ρ ∑_{j=0}^{m−2} \frac{(ρm)^{j}}{j!} \}\} .

Let us now investigate the summand given in the summation above a bit more closely.

e^{−ρm} \{ ∑_{j=0}^{m−1} \frac{(ρm)^{j}}{j!} − ρ ∑_{j=0}^{m−2} \frac{(ρm)^{j}}{j!} \}

= (1 − ρ) − \{ 1 − e^{−ρm} ∑_{j=0}^{m−1} \frac{(ρm)^{j}}{j!} \} + ρ \{ 1 − e^{−ρm} ∑_{j=0}^{m−2} \frac{(ρm)^{j}}{j!} \}

= (1 − ρ) − e^{−ρm} ∑_{j=m}^{∞} \frac{(ρm)^{j}}{j!} + e^{−ρm} ∑_{j=m}^{∞} \frac{j}{m} \frac{(ρm)^{j}}{j!}

= (1 − ρ) + e^{−ρm} ∑_{j=m+1}^{∞} \frac{j − m}{m} \frac{(ρm)^{j}}{j!} .

Since we will need this result later on, we summarize these computations in a separate line.

e^{−ρm} \{ ∑_{j=0}^{m−1} \frac{(ρm)^{j}}{j!} − ρ ∑_{j=0}^{m−2} \frac{(ρm)^{j}}{j!} \} = (1 − ρ) + e^{−ρm} ∑_{j=m+1}^{∞} \frac{j − m}{m} \frac{(ρm)^{j}}{j!} . (51)

So we conclude that the (transient) waiting time of the n+1-th customer entering an M/D/1 queue is given by the expression

IE [W_{n+1}^{\{0\}}] = \frac{1}{λ} ∑_{m=1}^{n} e^{−ρm} ∑_{j=m+1}^{∞} \frac{j − m}{m} \frac{(ρm)^{j}}{j!} .

Taking the limit n → ∞ we obtain, for ρ < 1,

lim_{n→∞} IE [W_{n+1}^{\{0\}}] = \frac{1}{λ} ∑_{m=1}^{∞} e^{−ρm} ∑_{j=m+1}^{∞} \frac{j − m}{m} \frac{(ρm)^{j}}{j!} = \frac{a ρ}{2(1 − ρ)}
= IE [W^{{0}}] ,  (52)

the very last equality being due to the well–known Pollaczek-Khinchin formula from queueing theory, where W^{{0}} denotes the stationary waiting time until service in an M/D/1 single-server queue. A proof of the identity

∑_{m=1}^{∞} e^{−ρm} ∑_{j=m+1}^{∞} \frac{j − m}{m} \frac{(ρm)^{j}}{j!} = \frac{ρ^{2}}{2(1 − ρ)}  (53)

is given in the appendix, see Lemma 4. This Lemma also implies the following conclusion:

Θ_{m} = e^{−ρm} ∑_{j=m+1}^{∞} \frac{j − m}{m} \frac{(ρm)^{j}}{j!} → 0  for m → ∞,  (54)

for all ρ ∈ [0, 1), an observation, which will be particularly useful in the next section.

6.2 More Complex (max,+)-Linear Systems

In this section we want to consider more general networks where the net-topology is such that the sequence of the D_{m}’s is given by D_{m} = η_{m}, for m = 0, …, ξ, and D_{m} = η_{ξ} + (m − ξ) a, for m ≥ ξ, ξ ∈ IN_{0}. We want to agree upon the convention that we will allways write as many arguments of a sequence of polynomial p_{k} as we think that are necessary to understand what the arguments of all the various polynomials p_{k} are. This notation in connection with a polynomial p_{j}, j ∈ IN, should be read such that the first j arguments of this list are the arguments of p_{j} whereas the remaining arguments are to be ignored. For n > ξ, plugging in formula (49) the assumed structure of the D_{m}’s yields,

IE [W_{n+1}^{{ξ+1}}]
= \frac{1}{λ} \{ ∑_{m=1}^{n−ξ} e^{−ρm} + ∑_{m=n−ξ+1}^{n} e^{−λ(η_{ξ}+(n−ξ)a−η_{n−m})} − n + λη_{ξ} + ρ(n − ξ)

+ ∑_{m=2}^{n−ξ} e^{−ρm} ∑_{j=1}^{m−1} λ^{j}{p_{j}(η_{ξ} + (n − ξ)a, η_{ξ} + (n − m + 1 − ξ)a,

…, η_{ξ} + (n − m + j − 1 − ξ)a)

− p_{j}(η_{ξ} + (n − m + 1 − ξ)a, …, η_{ξ} + (n − m + j − ξ)a)}

+ ∑_{m=n−ξ+1}^{n}e^{−λ(η_{ξ}+(n−ξ)a−η_{n−m})} ∑_{j=1}^{m−1} λ^{j}{p_{j}(η_{ξ} + (n − ξ)a, η_{n−m+1},

…, η_{ξ}, η_{ξ} + a, …, η_{ξ} + (n − m + j − 1 − ξ)a)

− p_{j}(η_{n−m+1}, …, η_{ξ}, η_{ξ} + a, …, η_{ξ} + (n − m + j − ξ)a)} }

= \frac{1}{λ} \{ ∑_{m=1}^{n−ξ} e^{−ρm} + ∑_{m=n−ξ+1}^{n}e^{−λ(η_{ξ}+(n−ξ)a−η_{n−m})} − n + λη_{ξ} + ρ(n − ξ)

+ ∑_{m=2}^{n−ξ} e^{−ρm} ∑_{j=1}^{m−1} ρ^{j}{p_{j}(m, 1, …, j − 1) − p_{j}(1, …, j)}

+ ∑_{m=n−ξ+1}^{n} e^{−λ(η_{ξ}+(n−ξ)a−η_{n−m})} ∑_{j=1}^{m−1} ρ^{j}

× \{p_{j}(m, \frac{η_{n−m+1} + (ξ − (n − m))a − η_{ξ}}{a} ,

…, \frac{η_{ξ−1} + (ξ − (n − m))a − η_{ξ}}{a} , ξ − (n − m), …, j − 1)

− p_{j}(\frac{η_{n−m+1} + (ξ − (n − m))a − η_{ξ}}{a} ,

…, \frac{η_{ξ−1} + (ξ − (n − m))a − η_{ξ}}{a} , ξ − (n − m), …, j)\} \},

where we used the translation–invariance of the polynomials p_{k} when shifting all arguments by −(η_{ξ} + (n − m − ξ)a). Finally, we also extracted a^{j} from all polynomials p_{j}. In the expression above we find IE [W_{n−ξ+1}^{{0}}] by collecting corresponding terms (compare with (50)). So we are left with

IE [W_{n+1}^{{ξ+1}}]
= IE [W_{n−ξ+1}^{\{0\}}] + \frac{1}{λ} \{ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(n−ξ)a−η_{m})} − ξ + λη_{ξ}

+ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(n−ξ)a−η_{m})} ∑_{j=1}^{n−m−1} ρ^{j}\{p_{j}(n − m, \frac{η_{m+1} + (ξ − m)a − η_{ξ}}{a} ,

…, \frac{η_{ξ−1} + (ξ − m)a − η_{ξ}}{a} , ξ − m, …, j − 1)

− p_{j}(\frac{η_{m+1} + (ξ − m)a − η_{ξ}}{a} ,

…, \frac{η_{ξ−1} + (ξ − m)a − η_{ξ}}{a} , ξ − m, …, j)\} \},

F. Baccelli, S. Hasenfuss and V. Schmidt / (max,+)–Linear Systems 38 where we rewrote the summation by substituting the summation variable m by n − m. So we can apply Theorem 10 and obtain

IE [W_{n+1}^{{ξ+1}}]
= IE [W_{n−ξ+1}^{\{0\}}] + \frac{1}{λ} \{ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(n−ξ)a−η_{m})} − ξ + λη_{ξ}

+ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(n−ξ)a−η_{m})} ∑_{j=1}^{n−m−1} ρ^{j} { h_{j}(n − m)

− ∑_{l=1}^{ξ−1−m} \{p_{l}(\frac{η_{m+1} + (ξ − m)a − η_{ξ}}{a} , …, \frac{η_{m+l} + (ξ − m)a − η_{ξ}}{a})

− p_{l}(l, \frac{η_{m+1} + (ξ − m)a − η_{ξ}}{a} , …, \frac{η_{m+l−1} + (ξ − m)a − η_{ξ}}{a})\}

× h_{j−l}(n − m − l) } }
= IE [W_{n−ξ+1}^{\{0\}}] + \frac{1}{λ} \{ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(n−ξ)a−η_{m})} − ξ + λη_{ξ}

+ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(n−ξ)a−η_{m})} { ∑_{j=1}^{n−m−1} ρ^{j}h_{j}(n − m)

+ ∑_{l=1}^{ξ−1−m} {p_{l}(λ(η_{ξ} + (m + l − ξ)a), λη_{m+1}, …, λη_{m+l−1})

− p_{l}(λη_{m+1}, …, λη_{m+l})}

× ∑_{j=1}^{n−m−1} ρ^{j−l} h_{j−l}(n − m − l) }}
= IE [W_{n−ξ+1}^{\{0\}}] + \frac{1}{λ} \{ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(n−ξ)a−η_{m})} − ξ + λη_{ξ}

+ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(n−ξ)a−η_{m})} \{ ∑_{j=1}^{n−m−1} \{ \frac{(ρ(n − m))^{j}}{j!} − ρ\frac{(ρ(n − m))^{j−1}}{(j − 1)!} \}

+ ∑_{l=1}^{ξ−1−m} {p_{l}(λ(η_{ξ} + (m + l − ξ)a), λη_{m+1}, …, λη_{m+l−1})

− p_{l}(λη_{m+1}, …, λη_{m+l})}

× \{ ∑_{j=l}^{n−m−1} \frac{(ρ(n − m − l))^{j−l}}{(j − l)!} − ρ ∑_{j=l+1}^{n−m−1} \frac{(ρ(n − m − l))^{j−l−1}}{(j − l − 1)!} \}\}\}

= IE [W_{n−ξ+1}^{\{0\}}] + η_{ξ} − \frac{ξ}{λ} + \frac{1}{λ} \{ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})}

× e^{−ρ(n−m)} \{ ∑_{j=0}^{n−m−1} \frac{(ρ(n − m))^{j}}{j!} − ρ ∑_{j=0}^{n−m−2} \frac{(ρ(n − m))^{j}}{j!} \}

+ ∑_{m=0}^{ξ−2} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})}

× ∑_{l=1}^{ξ−1−m} {p_{l}(λ(η_{ξ} + (m + l − ξ)a), λη_{m+1}, …, λη_{m+l−1})

− p_{l}(λη_{m+1}, …, λη_{m+l})} e^{−ρl}

× e^{−ρ(n−m−l)} \{ ∑_{j=0}^{n−m−l−1} \frac{(ρ(n − m − l))^{j}}{j!}

− ρ ∑_{j=0}^{n−m−l−2} \frac{(ρ(n − m − l))^{j}}{j!} \}\}

But in this formula we realize expressions which we have already investigated in the previous section, namely in (51). Thus, using the abbreviation Θ_{m} we introduced in (54), we obtain

IE [W_{n+1}^{{ξ+1}}]
= IE [W_{n−ξ+1}^{\{0\}}] + η_{ξ} − \frac{ξ}{λ}

+ \frac{1}{λ} \{ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})} \{ (1 − ρ) + Θ_{n−m} \}

+ ∑_{m=0}^{ξ−2} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})}

× ∑_{l=1}^{ξ−1−m} {p_{l}(λ(η_{ξ} + (m + l − ξ)a), λη_{m+1}, …, λη_{m+l−1})

− p_{l}(λη_{m+1}, …, λη_{m+l})} e^{−ρl} { (1 − ρ) + Θ_{n−m−l} } }

= IE [W_{n−ξ+1}^{\{0\}}] + η_{ξ} − \frac{ξ}{λ} + \frac{(1 − ρ)}{λ} \{ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})}

+ ∑_{m=0}^{ξ−2} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})}

× ∑_{l=1}^{ξ−1−m} {p_{l}(λ(η_{ξ} + (m + l − ξ)a), λη_{m+1}, …, λη_{m+l−1})

− p_{l}(λη_{m+1}, …, λη_{m+l})} e^{−ρl} }

+ \frac{1}{λ} \{ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})} Θ_{n−m} + ∑_{m=0}^{ξ−2} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})}

× ∑_{l=1}^{ξ−1−m} {p_{l}(λ(η_{ξ} + (m + l − ξ)a), λη_{m+1}, …, λη_{m+l−1})

− p_{l}(λη_{m+1}, …, λη_{m+l})} e^{−ρl} Θ_{n−m−l} } .

As a final step we can rewrite

IE [W_{n−ξ+1}^{{0}}] = IE [W^{{0}}] − (IE [W^{{0}}] − IE [W_{n−ξ+1}^{{0}}])
= \frac{aρ}{2(1 − ρ)} − \frac{1}{λ} ∑_{m=n−ξ+1}^{∞} Θ_{m},

and get for the expectation of the (transient) waiting time of the n+1-th customer in a network of the assumed structure

IE [W_{n+1}^{{ξ+1}}]  (55)
= \frac{aρ}{2(1 − ρ)} + η_{ξ} − \frac{ξ}{λ} + \frac{(1 − ρ)}{λ} \{ ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})}

+ ∑_{m=0}^{ξ−2} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})}

× ∑_{l=1}^{ξ−1−m} {p_{l}(λ(η_{ξ} + (m + l − ξ)a), λη_{m+1}, …, λη_{m+l−1})

− p_{l}(λη_{m+1}, …, λη_{m+l})} e^{−ρl} }

− \frac{1}{λ} \{ ∑_{m=n−ξ+1}^{∞} Θ_{m} − ∑_{m=0}^{ξ−1} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})} Θ_{n−m}

− ∑_{m=0}^{ξ−2} e^{−λ(η_{ξ}+(m−ξ)a−η_{m})}

× ∑_{l=1}^{ξ−1−m} {p_{l}(λ(η_{ξ} + (m + l − ξ)a), λη_{m+1}, …, λη_{m+l−1})

− p_{l}(λη_{m+1}, …, λη_{m+l})} e^{−ρl} Θ_{n−m−l} }

From (54) we know that Θ_{m} goes to zero as m → ∞ and thus we see that the expectation of W_{n+1}^{{ξ+1}} converges to a finite limit, namely to the limit stated in Theorem 5. On the other hand, by the way W_{n} has been defined in (4) we also know that this convergence is monotone in n. So we can interchange limit and integration by Lévy’s theorem on monotone convergence and conclude

lim_{n→∞} IE [W_{n+1}^{{ξ+1}}] = IE [ lim_{n→∞} W_{n+1}^{{ξ+1}}] = IE[W^{{ξ+1}}],

which proves the theorem.

Remark In the above proof we have actually done more than just proving the explicit representation of the expectation for the stationary waiting times. With (55) we have also given an explicit representation of the transient waiting times using only polynomials up to order ξ − 1. Whenever n ≫ ξ this will clearly result in a significant reduction of computational efforts necessary to obtain the exact solution of transient waiting times.

Remark In [3] another property of the polynomials p_{k} is mentioned: p_{k}(0, 1, …, k −1) = \frac{1}{2} for all k ≥ 2. If we apply this property to the M/D/1 case, where D_{n} = n a for all n ≥ 0, we learn that

∑_{k=0}^{∞} λ^{k} p_{k+1}(D_{0}, …, D_{k}) = a ∑_{k=1}^{∞} ρ^{k} p_{k+1}(0, 1, …, k)
= \frac{a ρ}{2 (1 − ρ)} = IE[W^{\{0\}}],

for each arrival intensity λ ∈ [0, a^{−1}). So this observation suggests that

IE[W^{{ξ+1}}] = ∑_{k=0}^{∞} λ^{k} p_{k+1}(D_{0}, …, D_{k})  (56)

for all finite ξ ≥ 0, i.e. that the expected stationary waiting time IE[W^{{ξ+1}}] can be expanded in an infinite power-series with respect to the arrival intensity λ, where the coefficients of this expansion are given by p_{k+1}(D_{0}, …, D_{k}). This conjecture is actually true. All the tools that are required to prove this statement are given in this paper. But since the proof is similar to the one of Theorem 5, perhaps even more technical, we will not outline it here.

Appendix

Before we give the proof of identity (53) we state some preliminary results:

Lemma 2 For all k ≥ 1 the following equality holds:

∑_{j=0}^{k} \binom{k}{j}(−1)^{k−j}j^{l} = \{ \begin{matrix}0 for & l = 0, …, k − 1, \\ k! for & l = k. \end{matrix}  (57)

Proof We prove this result by induction with respect to k. For l = 0 the left–hand side of (57) breaks down to a simple binomial series which simplifies to (1 + (−1))^{k} = 0. Let l ≥ 1. It is immediate to see that (57) holds for k = 1. Let us assume the validity of (57) for some k ≥ 1. Then

∑_{j=0}^{k+1} \binom{k + 1}{j}(−1)^{k+1−j}j^{l} = ∑_{j=1}^{k+1} \frac{(k + 1)!}{(k + 1 − j)! j!} (−1)^{k+1−j} j^{l}

= (k + 1) ∑_{j=1}^{k+1} \binom{k}{j − 1}(−1)^{k+1−j}j^{l−1}

= (k + 1) ∑_{j=0}^{k} \binom{k}{j}(−1)^{k−j}(j + 1)^{l−1}

= (k + 1) ∑_{j=0}^{k} \binom{k}{j}(−1)^{k−j} ∑_{i=0}^{l−1} \binom{l − 1}{i}j^{i}

= (k + 1) ∑_{i=0}^{l−1} \binom{l − 1}{i} ∑_{j=0}^{k} \binom{k}{j}(−1)^{k−j}j^{i}

= \{ \begin{matrix}0  for & l = 0, …, k, \\ (k + 1)! for & l = k + 1, \end{matrix}

where the last equality follows from the induction hypothesis, since we assumed that the inner summation is equal to zero, whenever i = 0, 1, …, k − 1, and equal to k! if i = k, which only happens if l = k + 1.

Lemma 3 For each k ≥ 0,

∑_{m=0}^{k} \binom{k}{m}(−1)^{k−m}(m + 1)^{k+1} = \frac{1}{2} (k + 2)! .  (58)

Proof Note that

∑_{m=0}^{k} \binom{k}{m}(−1)^{k−m}(m + 1)^{k+1} = ∑_{m=0}^{k} \binom{k}{m}(−1)^{k−m} ∑_{j=0}^{k+1} \binom{k + 1}{j}m^{j}

= ∑_{j=0}^{k+1} \binom{k + 1}{j} ∑_{m=0}^{k} \binom{k}{m}(−1)^{k−m}m^{j}.

Using Lemma 2 yields

∑_{m=0}^{k} \binom{k}{m}(−1)^{k−m}(m + 1)^{k+1} = \binom{k + 1}{k}k! + ∑_{m=0}^{k} \binom{k}{m}(−1)^{k−m}m^{k+1}

= (k + 1)! + ∑_{m=1}^{k} \binom{k}{m}(−1)^{k−m}m^{k+1}

= (k + 1)! + k ∑_{m=1}^{k} \binom{k − 1}{m − 1}(−1)^{k−1−(m−1)}m^{k}

= (k + 1)! + k ∑_{m=0}^{k−1} \binom{k − 1}{m}(−1)^{k−1−m}(m + 1)^{k}.

Assume now that (58) holds for some k − 1. Then,

∑_{m=0}^{k} \binom{k}{m}(−1)^{k−m}(m + 1)^{k+1} = (k + 1)! + \frac{k}{2} (k + 1)! = \frac{1}{2}(k + 2)!

and thus, (58) holds for all k ≥ 0 by induction with respect to k.

Lemma 4 For all 0 ≤ ρ < 1, the following identity holds:

∑_{m=1}^{∞} e^{−ρm} ∑_{j=m+1}^{∞} \frac{j − m}{m} \frac{(ρm)^{j}}{j!} = \frac{ρ^{2}}{2(1 − ρ)}.  (59)

Proof Let ρ ∈ [0, 1) and define

g(ρ) = ∑_{m=1}^{∞} e^{−ρm} ∑_{j=m+1}^{∞} \frac{j − m}{m} \frac{(ρm)^{j}}{j!} .

Since we have \frac{ρ^{2}}{2(1−ρ)} = \frac{1}{2} ∑_{k=0}^{∞} ρ^{k+2}, for ρ ∈ [0, 1), (59) is proved if we show that g(ρ) can be represented in the form g(ρ) = \frac{1}{2} (ρ^{2} + ρ^{3} + …) for each ρ ∈ [0, 1). Thus, it suffices to show that

\frac{d^{k}}{dρ^{k}} g(ρ) |_{ρ=0} = \{ \begin{matrix}0, for & k = 0, 1, \\ \frac{1}{2} k!, for & k ≥ 2. \end{matrix}  (60)

For k = 0, i.e. g(0) = 0, there is nothing to show. The first two derivatives of g(ρ) are given by

\frac{d}{dρ} g(ρ) = ∑_{m=1}^{∞} e^{−ρm} ∑_{j=m}^{∞} \frac{(ρm)^{j}}{j!}  (61)

and

\frac{d^{2}}{dρ^{2}} g(ρ) = ∑_{m=1}^{∞} me^{−ρm} \frac{(ρm)^{m−1}}{(m − 1)!} .  (62)

Thus, \frac{d}{dρ} g(ρ)|_{ρ=0} = 0 holds as well. Furthermore, (61) and (62) give

\frac{d^{k+2}}{dρ^{k+2}} g(ρ) = ∑_{m=1}^{∞} m ∑_{j=0}^{k} \binom{k}{j}\frac{d^{k−j}}{dx^{k−j}} e^{−ρm} \frac{d^{j}}{dρ^{j}} \frac{(ρm)^{m−1}}{(m − 1)!}

for k ≥ 0 and, in particular,

\frac{d^{k+2}}{dρ^{k+2}} g(ρ) |_{ρ=0} = ∑_{m=1}^{k+1} m\binom{k}{m − 1}(−m)^{k−m+1}m^{m−1}

= ∑_{m=0}^{k} \binom{k}{m}(−1)^{k−m}(m + 1)^{k+1}
= \frac{1}{2} (k + 2)!

from Lemma 3 which completes the proof of (59).

F. Baccelli, S. Hasenfuss and V. Schmidt / (max,+)–Linear Systems 45

References

[1] F. Baccelli, G. Cohen, G.J. Olsder and J.P. Quadrat, Synchronisation and Linearity, J. Wiley & Sons, Chichester, 1992.

[2] F. Baccelli, S. Hasenfuss and V. Schmidt, Expansions for steady–state characteristics in (max, +)–linear systems. INRIA Report N^{∘} 2785 / Preprint University of Ulm, 1996.

[3] F. Baccelli and V. Schmidt, Taylor series expansions for Poisson driven (max,+)–linear systems, Ann. Appl. Probab., 6 (1996) 138–185.

[4] W.B. Gong and J.Q. Hu, The MacLaurin series for the GI/G/1 queue, J. Appl. Prob., 29 (1992) 176–184.

[5] J.Q. Hu, Analyticity of single-server queues in light traffic, Queueing Systems, 19 (1995) 63–80.

[6] J.Q. Hu, The departure process of the GI/G/1 queue and its MacLaurin series, Oper. Res., 44 (1996) 810–815.

[7] J.Q. Hu, S. Nananuku and W.B. Gong, A new approach to (s,S) inventory problems, J. Appl. Prob., 30 (1994) 898–912.

[8] A. Jean-Marie, The waiting time distribution in Poisson-driven deterministic systems. IN-RIA Report N^{∘} 3083, INRIA Sophia-Antipolis, 1997.

[9] M.I. Reiman and B. Simon, An interpolation approximation for queueing systems with Poisson input, Oper. Res., 36 (1988) 454–469.

[10] M.I. Reiman and B. Simon, Open queueing systems in light traffic, Math. Oper. Res., 14 (1989) 26–59.

[11] E.C. Titchmarsh, The Theory of Functions, Oxford University Press, 1939.

[12] M.A. Zazanis, Analyticity of Poisson-driven stochastic systems, Adv. Appl. Probab., 24 (1992) 532–541.