Expansions for Steady-State Characteristics in (max,+)–Linear Systems

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

January 30, 1996

Abstract

This paper gives finite and infinite expansion formulas for the expected value of functions of the steady state variables in open, stochastic (max, +)–linear systems with Poisson input.

Expansions for Laplace transforms, moments and tail functions of these steady state variables are considered as specific instances of our main formulas.

Such (max, +)–linear systems are known to allow to represent a class of discrete event networks called stochastic event graphs. A few examples of such event graphs pertaining to queueing theory are given in the paper in order to illustrate the proposed expansion method.

Short title: Expansions for (max,+)–Linear Systems Keywords: Queueing networks, stochastic Petri nets, Poisson input, vectorial recurrence equation, stationary state variables, marked point processes, factorial moment measures, admissibility, perturbation analysis. AMS classification: 60K25, 60G55, 90B22

1 Introduction

In the present paper, we focus on a certain class of functions f of the unique finite random vector solution W of a vectorial (max, +)–linear functional equation of the form

W ∘ θ = A ⊗ C ⊗ W ⊕ B ∘ θ,  (1)

which arises in the theory of open multidimensional discrete event systems. In this equation,

• θ is a shift operator defined on some probability space (Ω, F, IP);

• A, B and C are random matrices which characterize the topological and the stochastic structure of the system: A and B are associated with the system itself, and C with its input point process; • The reference algebra is the so-called (max, +) algebra: when operating on scalars, ⊕

1INRIA Sophia Antipolis, 2004, Route des Lucioles, B.P.93, F-06902 Sophia Antipolis Cedex, France 2Universität Ulm, Abteilung Stochastik, Helmholtzstr. 18, D-89069 Ulm, Germany

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}.

The aim of the present paper is to show that for all f : IR → IR in this class of functions, under certain assumptions, whenever the input process is Poisson, the expectation IE [f(W^{i})], where W^{i} is the i-th component of the stationary state vector W, is finite and can be expanded into a finite or infinite power series with respect to the arrival intensity λ, where an algorithm is given to determine all coefficients of the expansion. This result will then be specialized to derive series expansions for

1. Laplace transforms IE [e^{−sW^{i}}] , s ≥ 0;

2. Higher-order moments IE [(W^{i})^{ν}] , ν ∈ IN = {1, 2, …};

3. Tail functions IP (W^{i} > x), x ≥ 0.

In all cases we derive explicit expressions for the coefficients of the expansion.

The present paper is a companion paper to [3], where the practical motivations for studying equations of type (1) are analyzed in great detail, and where similar expansions were first derived for the first moments of the W_{i} variables.

For sake of brevity, we have chosen not to recall these practical motivations in the present paper. So, for a more complete understanding of the general setting and of our examples, or for more examples, the reader should refer to [3].

2 General Setting

Let α ∈ IN be an arbitrary natural number characterizing the dimension of the system. As it was shown in [3], the assumptions of the forthcoming three subsections are satisfied by α-dimensional vectorial recurrence equations of the form

X_{n+1} = A_{n} ⊗ X_{n} ⊕ B_{n+1} ⊗ T_{n+1}  (2)

which characterize the evolution of the state variables of any open, input–connected stochastic event graph with independent and i.i.d. firing times. Various incarnations of such equations will be considered in the examples.

2.1 Support and Monotonicity Assumptions

We assume that each entry of the α×α-dimensional random matrix A_{n} is either a.s. non-negative or a.s. equal to ϵ = −∞, i.e.

(A_{n})_{i,j} ≥ 0 or (A_{n})_{i,j} = ϵ,  a.s.  (3)

and that all entries on the diagonal of A_{n} are non-negative, i.e. (A_{n})_{i,i} ≥ 0. We also assume that there exists an integer 0 < α′ ≤ α such that the first α′ coordinates of the α-dimensional random vectors B_{n} are non-negative, i.e. B_{n}^{i} ≥ 0 for all 1 ≤ i ≤ α′. Let D_{0}, D_{1}, … be the following α-dimensional vectors: D_{0} = B_{0}, and

D_{k} = (⨂_{n=1}^{k} A_{−n}) ⊗ B_{−k},  for k ≥ 1.  (4)

The α′ first coordinates of D_{k} are assumed to be non-decreasing in k:

0 ≤ D_{0}^{i} ≤ D_{1}^{i} ≤ …,  for all i = 1, …, α′.  (5)

2.2 Stochastic Assumptions

Throughout the paper, we assume that {T_{n}} is a stationary, homogeneous Poisson process with intensity λ, and {Z_{n}} = {A_{n}, B_{n}} is a stationary sequence of random matrices which is independent of {T_{n}}. We further assume that the underlying probability space (Ω, F, IP) is equipped with a measurable shift θ : Ω → Ω which leaves the probability measure IP invariant, is IP-ergodic, and is such that {Z_{n}} is consistent with θ, i.e. A_{n} = A ∘ θ^{n} and B_{n} = B ∘ θ^{n} for all integers n. Since the sequences {T_{n}} and {Z_{n}} are independent, we can also assume that T_{n+1} − T_{n} = T_{1} ∘ θ^{n} for n ≥ 1 and T_{n+1} − T_{n} = (−T_{0}) ∘ θ^{n}, for n < 0, where T_{1} and T_{0} are the first positive and negative points of {T_{n}}, respectively. Put IN_{0} = IN ∪ {0}. For n ∈ IN_{0} and q ∈ IN, let

H_{n,q} = ⨁_{i=1}^{α′} {(A_{−(nq+1)} ⊗ A_{−(nq+2)} ⊗ … ⊗ A_{−(n+1)q} ⊗ (B_{−(n+1)q} ⊕ O))^{i}} ,  (6)

and

F_{n} = ⨁_{i=1}^{α} {(A_{−1} ⊗ A_{−2} ⊗ … ⊗ A_{−n} ⊗ (B_{−n} ⊕ O))^{i}} ,  (7)

where O is the α-dimensional column vector with all its components equal to zero. We assume that with probability one

lim_{q→∞} H_{0,q} = ∞.  (8)

Besides this we will assume that for some r′ ∈ IN large enough,

λ < r′[IE[H_{0,r′}]]^{−1},  (9)

and that {H_{n,r′}}_{n≥0} is a sequence of 1-dependent random variables. An immediate consequence is the following result:

Lemma 1 There exists an r ∈ IN, r ≥ r′ such that

λ < (r − 1)[IE[H_{0,r}]]^{−1}  (10)

and {H_{n,r}}_{n≥0} is a sequence of 1-dependent random variables.

In what follows, we will most often drop the index r and will only write H_{n} instead of H_{n,r}, but will always implicitly assume that r is chosen according to Lemma 1.

2.3 Steady-State Solution

Let τ_{n} = T_{n+1} − T_{n}, n ≥ 0. By subtracting T_{n+1} on both sides of (2), it is easily checked that the state vector W_{n}, the components of which are given by W_{n}^{i} = X_{n}^{i} − T_{n}, satisfies the equation

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

where, for all x ∈ IR, C(x) is the α × α matix with all diagonal entries equal to −x and all nondiagonal entries equal to ϵ. As it was shown in [2], under the above assumptions, {W_{n}} couples with a unique stationary sequence {W ∘ θ^{n}}, where W is the unique finite random variable solution of the functional equation

W ∘ θ = A ⊗ C ⊗ W ⊕ B ∘ θ,  (12)

which is given by the series

W = B ⊕ ⨁_{n≥1} A ∘ θ^{−1} ⊗ C ∘ θ^{−1} ⊗ … ⊗ A ∘ θ^{−n} ⊗ C ∘ θ^{−n} ⊗ B ∘ θ^{−n},  (13)

where C = C(−τ_{0}). Since C(x) commutes with any matrix, W admits the following equivalent representation:

W = B_{0} ⊕ ⨁_{n≥1} C(−T_{−n}) ⊗ D_{n}.  (14)

2.4 Additional Notation

We now recall a class of polynomials which were obtained in the expansion for the expectation vector of W in [3]. These polynomials are given by the following formula

p_{k}(x_{0}, x_{1}, …, x_{k−1}) = ∑_{(i_{0},i_{1},...,i_{k−1})∈S_{k}}(−1)^{γ_{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}!} ,  (15)

where

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

and

γ_{k}(i_{0}, i_{1}, …, i_{k−1}) = 1 + ∑_{s=0}^{k−1} 1(i_{s} > 0),  (17)

for all k ≥ 1, with 1(i_{s} > 0) = 1 whenever i_{s} > 0 and 1(i_{s} > 0) = 0 otherwise.

These polynomials satisfy the following properties, which can be found in [3]:

• Translation Invariance:

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

for all non-decreasing sequences of real numbers 0 ≤ x_{0} ≤ x_{1} ≤ … ≤ x_{k−1}, for all u ≥ 0 and k = 2, 3, . . ..

• Integral Representation:

p_{k}(x_{0}, …, x_{k−1}) = ∑_{n=0}^{k−2} ∫_{x_{n}}^{x_{n+1}} \{p_{k−1}(\underbrace{v, …, v}_{n}, x_{n+1}, …, x_{k−1})
− p_{k−1}(\underbrace{v, …, v}_{n+1}, x_{n+1}, …, x_{k−2})\} dv, (19)

for all non-decreasing sequences of real numbers 0 ≤ x_{0} ≤ x_{1} ≤ … ≤ x_{k−1}, k ≥ 2, with p_{1}(x_{0}) = x_{0}.

3 Main Results

Throughout the paper, it will always be supposed that all the assumptions made on {A_{n}, B_{n}} in Section 2 hold. In this section we first give an explicit finite series expansion for the expectation of a class of functions of the stationary state variables W^{i}. This result will then be applied to get expansions for Laplace transforms, higher-order moments and tail functions of the variables W^{i}.

3.1 General Theorem

Put IR^{+} = [0, ∞) and let f : IR^{+} → IR^{+} be some Riemann-integrable function (e.g. f(x) monotone or continuous). Associated with f, we define the following class of functions: q_{1}(x_{0}) = f(x_{0}), and

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

= ∑_{n=0}^{k} \binom{k}{n}(−1)^{k−n}F^{[k]}(x_{n}) − ∑_{n=0}^{k−1} ∑_{j=n}^{k−1} \binom{j}{n}(−1)^{j−n}F^{[j]}(x_{n})
{p_{k−j}(x_{n+1}, …, x_{k−j+n}) − p_{k−j}(x_{n}, …, x_{k−j+n−1})}, (20)

for 1 ≤ k ≤ m, with F^{[0]}(x) = f(x) and F^{[n]}(x), n ≥ 1, is recursively defined by the a suitably chosen version of the indefinite Riemann-integral ∫ F^{[n−1]}(x) dx, x ∈ IR^{+}. The functions p_{k} in (20) are the polynomials defined in (15).

Theorem 1 Let f : IR^{+} → IR^{+} be a Riemann-integrable, non-negative function which satisfies f(x) ≤ c x^{ν} for all x ≥ 0, where ν ∈ IN_{0} is a non-negative integer and c ∈ IR^{+} is a finite constant.

1. If the (ν +m+2)-th moment of H_{n} is finite, i.e. IE[(H_{n})^{ν+m+2}] < ∞, then, for 1 ≤ i ≤ α′,

IE[f(W^{i})] = ∑_{k=0}^{m} λ^{k} IE[ q_{k+1}(D_{0}^{i}, D_{1}^{i}, …, D_{k}^{i}) ] + O(λ^{m+1}).  (21)

2. If there exists a θ^{∗} > 0 such that for all θ ∈ [0, θ^{∗}),

IE[e^{θF_{n}}] ≤ L_{θ} (ϕ(θ))^{n} , (22)

for some finite functions ϕ(θ) > 1 and L_{θ}, then, for 1 ≤ i ≤ α′, the expectation IE[f(W^{i})] is infinitely differentiable in λ for all λ in a right neighborhood of 0,

lim_{λ↓0} \frac{d^{n}}{dλ^{n}} IE[f(W^{i})](λ) = IE[ q_{n+1}(D_{0}^{i}, D_{1}^{i}, …, D_{n}^{i}) ]  (23)

and

IE[f(W^{i})] = ∑_{k=0}^{∞} λ^{k} IE[ q_{k+1}(D_{0}^{i}, D_{1}^{i}, …, D_{k}^{i}) ] .  (24)

Remark In principle, it is possible to consider any version of the indefinite integral ∫ F^{[n−1]}(x) dx for F^{[n]}(x) in Theorem 1. However, depending on the particular function f(x), a suitably chosen version of the indefinite integral may help to reduce computational efforts significantly.

For instance, taking f(x) = x, gives a function which satisfies the boundedness requirement on f(x) with c = 1 and ν = 1. For this function, it is advantageous to take F^{[n]}(x) = ∫_{0}^{x} F^{[n−1]}(u) du, i.e. F^{[n]}(x) = \frac{x^{n+1}}{(n+1)!}, for n ∈ IN_{0}. Thus,

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

Elementary but tedious calculations show that the polynomials obtained in (25) are equal to those given by (15), see Section 6.2 of [3], i.e. Theorem 1 is actually a generalization of the result obtained in [3] and (25) gives another recurrence equation for the polynomials p_{k}.

The proof of Theorem 1 will be the object of Sections 4–6. In the following subsections, Theorem 1 will be applied to obtain expansion results for various functions of the stationary state vector W.

3.2 Laplace Transform

In order to derive an explicit finite series expansion of the Laplace transform of the components W^{i} of the stationary state vector W, we choose f(x) = e^{−sx}, for all x ∈ IR^{+} and s ≥ 0. Since f(x) is bounded by 1 for all x ∈ IR^{+}, the following corollary is an immediate consequence of Theorem 1. In this case, choosing F^{[n]}(x) = ∫_{x}^{∞} F^{[n−1]}(u) du saves a lot of computational steps later on.

Corollary 1 In addition to the assumptions made on {A_{n}, B_{n}} above, assume the (m + 2)-th moment of H_{n} to be finite for some m ∈ IN, i.e. IE[(H_{n})^{m+2}] < ∞. Then, for all s > 0, and for 1 ≤ i ≤ α′,

IE[e^{−sW^{i}}] = ∑_{k=0}^{m} λ^{k} IE[ q_{k+1}(s; D_{0}^{i}, D_{1}^{i}, …, D_{k}^{i}) ] + O(λ^{m+1}),  (26)

where q_{1}(s; x_{0}) = e^{−sx_{0}}, and

q_{k+1}(s; x_{0}, x_{1}, …, x_{k})

= \frac{1}{s^{k}} ∑_{n=0}^{k} \binom{k}{n}(−1)^{n}e^{−sx_{n}} − ∑_{j=0}^{k−1} \frac{1}{s^{j}} ∑_{n=0}^{j} \binom{j}{n}(−1)^{n}e^{−sx_{n}}
{p_{k−j}(x_{n+1}, …, x_{k−j+n}) − p_{k−j}(x_{n}, …, x_{k−j+n−1})}  (27)
= \frac{q_{k}(s; x_{0}, x_{1}, …, x_{k−1}) − q_{k}(s; x_{1}, x_{2}, …, x_{k})}{s}
− e^{−sx_{0}}[p_{k}(x_{1}, x_{2}, …, x_{k}) − p_{k}(x_{0}, x_{1}, …, x_{k−1})], (28)

for k = 1, …, m, and the functions p_{k} are the polynomials defined in (15).

Equation (28) gives a recurrence equation for the exponential-polynomial functions q_{k+1}, where the polynomials p_{j} of order 1 ≤ j ≤ k have to be known in order to calculate q_{k+1}. To see that (28) is actually the same as (27), we split up the summations in (27) as follows:

q_{k+1}(s; x_{0}, x_{1}, …, x_{k})

= \frac{1}{s} \frac{1}{s^{k−1}} \{e^{−sx_{0}} + ∑_{n=1}^{k−1}\{\binom{k − 1}{n} + \binom{k − 1}{n − 1}\}(−1)^{n}e^{−sx_{n}} + (−1)^{k}e^{−sx_{k}}\}

− \frac{1}{s} ∑_{j=1}^{k−1} \frac{1}{s^{j−1}} \{ ∑_{n=0}^{j−1} \binom{j − 1}{n}(−1)^{n}e^{−sx_{n}}\{p_{k−j}(x_{n+1}, …, x_{k−j+n})

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

− ∑_{n=0}^{j−1} \binom{j − 1}{n}(−1)^{n}e^{−sx_{n+1}}\{p_{k−j}(x_{n+2}, …, x_{k−j+n+1})

− p_{k−j}(x_{n+1}, …, x_{k−j+n})}}
− e^{−sx_{0}}{p_{k}(x_{1}, …, x_{k}) − p_{k−j}(x_{0}, …, x_{k−1})},

which gives (28) after substituting j → j + 1 and grouping corresponding parts together.

3.2.1 Example: Pollaczek-Khinchine Formula for the M/GI/1 Queue

Corollary 1 can be specialized to the Pollaczek-Khinchine formula for the M/GI/1 queue, which is the simplest instance of a one–dimensional open event graph. As it is known from [3], in this case we have α = α′ = 1, D_{0} = 0 and D_{n} = ∑_{i=1}^{n} σ_{−i}, for n ≥ 1, where {σ_{i}} is the sequence of service times. From [3] we also know that the polynomials p_{k}(x_{0}, …, x_{k−1}) are translationinvariant for k ≥ 2, which implies that p_{k}(x_{1}, x_{2}, …, x_{k}) = p_{k}(0, x_{2} − x_{1}, , …, x_{k} − x_{1}), for all k ≥ 2.

By further noticing that the sequence {σ_{i}} forms a sequence of i.i.d. random variables, and therefore D_{n} − D_{1} = ∑_{i=2}^{n} σ_{−i} =^{d} D_{n−1}, for all n ≥ 1, we conclude that

IE[p_{k}(D_{1}, …, D_{k})] = IE[p_{k}(D_{0}, …, D_{k−1})],  (29)

for all k ≥ 2.

Now let S^{∗}(s) := IE[e^{−sσ_{0}}]. The first coefficient of the expansion provided in Corollary 1 is given by IE[q_{1}(s; D_{0})] = 1. Using (28) of Corollary 1, we get

IE[q_{2}(s; D_{0}, D_{1})] = IE [\frac{q_{1}(s; D_{0}) − q_{1}(s; D_{1})}{s} − e^{−sD_{0}}\{p_{1}(D_{1}) − p_{1}(D_{0})\}]
= IE [\frac{1 − e^{−sσ_{−1}}}{s} − σ_{−1}] = \frac{1 − S^{∗}(s)}{s} − \frac{1}{μ},  (30)

where μ^{−1} = IE[σ_{0}]. Making use of (29), we obtain from (28) that for k ≥ 2

IE[q_{k+1}(s; D_{0}, D_{1}, …, D_{k})] = \frac{IE[q_{k}(s; D_{0}, …, D_{k−1}) − q_{k}(s; D_{1}, …, D_{k})]}{s}
= IE[q_{k}(s; D_{0}, …, D_{k−1})] \frac{1 − S^{∗}(s)}{s},  (31)

because from (27) and the translation-invariance property (18) of the polynomials p_{k}, it is easily seen that q_{k}(s; x_{0} − u, …, x_{k−1} − u) = e^{su} q_{k}(s; x_{0}, …, x_{k−1}) for k ≥ 1, and therefore

IE[q_{k}(s; D_{1}, …, D_{k})] = IE [q_{k}(s; σ_{−1}, …, ∑_{i=1}^{k} σ_{−i})]

= IE[e^{−sσ_{−1}}] IE [q_{k}(s; 0, σ_{−2}, …, ∑_{i=2}^{k} σ_{−i})]
= IE[e^{−sσ_{0}}] IE[q_{k}(s; D_{0}, D_{1}, …, D_{k−1})].

Iterating (31) (k − 1)-times and using (30) finally yields

IE[q_{k+1}(s; D_{0}, D_{1}, …, D_{k})] = (\frac{1 − S^{∗}(s)}{s} − \frac{1}{μ}) (\frac{1 − S^{∗}(s)}{s})^{k−1} ,  (32)

for all k ≥ 1.

Since for the M/GI/1 queue we have an infinite-order expansion of IE [e^{−sW} ] in λ, we obtain from Corollary 1 that

IE[e^{−sW} ] = 1 + ∑_{k=1}^{∞} λ^{k}IE[q_{k+1}(s; D_{0}, D_{1}, …, D_{k})]

= 1 + λ (\frac{1 − S^{∗}(s)}{s} − \frac{1}{μ}) ∑_{k=0}^{∞} λ^{k} (\frac{1 − S^{∗}(s)}{s})^{k}
= 1 + (\frac{λ(1 − S^{∗}(s))}{s} − ρ) (\frac{s}{s − λ(1 − S^{∗}(s))})
= \frac{(1 − ρ)s}{s − λ(1 − S^{∗}(s))},

i.e.

IE[e^{−sW} ] = \frac{(1 − ρ)s}{s − λ(1 − S^{∗}(s))},

a formula in which we recognize the Pollaczek-Khinchine formula for the Laplace transform of stationary waiting times in the M/GI/1 queue.

3.2.2 Example: Queues in Tandem

Consider a network of α single-server FIFO queues with infinite capacity in tandem, with all queues initially empty, α = α′ ≥ 2. Let σ_{n}^{i} denote the service time of customer n in station i. The i-th component W^{i} of the random vector W describes the stationary waiting time of a randomly chosen customer until the beginning of his service on station i. It was shown in [3] that in this case, the vectors D_{n} have the following form:

D_{n}^{i} = max_{1≤l_{n}≤...≤l_{1}≤i} { ∑_{k=l_{1}}^{i−1} σ_{0}^{k} + ∑_{k=l_{2}}^{l_{1}} σ_{−1}^{k} + … + ∑_{k=l_{n}}^{l_{n−1}} σ_{−n+1}^{k} + ∑_{k=1}^{l_{n}} σ_{−n}^{k}} .  (33)

Expansions — Deterministic Service Times Case Let σ^{i} denote the service time in queue i ∈ {1, …, α}. Without loss of generality we can and will assume that σ^{1} ≤ σ^{2} ≤ … ≤ σ^{α}. In the other case, say σ^{i} > σ^{i+1} for some i < α, we can consider the i-th queue and the (i + 1)-th queue as one single-server queue with service time σ^{i} + σ^{i+1} because in front of the (i + 1)-th server the waiting room is always empty. In this case

D_{n} = ( nσ^{1} ; σ^{1} + nσ^{2} ; σ^{1} + σ^{2} + nσ^{3} ; σ^{1} + σ^{2} + σ^{3} + nσ^{4} ; ⋮ ; ∑_{k=1}^{α−1} σ^{k} + nσ^{α} ) . (34)

Due to the translation-invariance (18) of the polynomials p_{k}, for all j = 0, …, k − 2, and for all n = 0, …, j,

p_{k−j}(D_{n+1}^{i}, …, D_{k−j+n}^{i}) = p_{k−j}(D_{n}^{i}, …, D_{k−j+n−1}^{i}).

So, from Corollary 1, for all m ≥ 1, IE[e^{−sW^{i}}] admits an expansion of order m in λ, with the k-th coefficient c_{k} = q_{k+1}(D_{0}^{i}, D_{1}^{i}, …, D_{k}^{i}), k = 0, 1, …, m, given by the formula

c_{k} = \frac{1}{s^{k}} e^{−s ∑_{l=1}^{i−1} σ^{l}} ∑_{n=0}^{k} \binom{k}{n}(−1)^{n}e^{−snσ^{i}} − \frac{1}{s^{k−1}} σ^{i}e^{−s ∑_{l=1}^{i−1} σ^{l}} ∑_{n=0}^{k−1} \binom{k − 1}{n}(−1)^{n}e^{−snσ^{i}}. (35)

Expansions — Random Identical Service Times Case Assume now that σ_{−n}^{i} = σ(n) for all i, a model which was for instance considered in [3]. Assume that

IE [(σ(n))^{m+2}] < ∞. (36)

The integrability condition of Corollary 1 is then satisfied. From (33) it follows that in this case the random variables D_{n}^{i} are given by the following expressions:

D_{0}^{i} = (i − 1)σ(0)
D_{n}^{i} = σ(1) + ⋯ + σ(n) + (i − 1) max{σ(0), …, σ(n)}, n ≥ 1.

So, for instance, under moment condition (36) for m = 2, the coefficients c_{k} of the second order expansion

IE [e^{−sW^{i}}] = c_{0} + λc_{1} + λ^{2}c_{2} + O(λ^{3})

are given by the following formulas:

c_{0} = IE [e^{−s(i−1)σ(0)}] ,

c_{1} = \frac{IE [e^{−s(i−1)σ(0)}] − IE [e^{−s\{σ(1)+(i−1)(σ(0)⊕σ(1))\}}]}{s}
− IE [e^{−s(i−1)σ(0)} {σ(1) + (i − 1)(σ(1) − σ(0))^{+}}] ,

c_{2} = \frac{IE [e^{−s(i−1)σ(0)}] − 2IE [e^{−s\{σ(1)+(i−1)(σ(0)⊕σ(1))\}}] + IE [e^{−s\{σ(1)+σ(2)+(i−1)(σ(0)⊕σ(1)⊕σ(2))\}}]}{s^{2}}
− \frac{IE [e^{−s(i−1)σ(0)} \{σ(1) + (i − 1)(σ(1) − σ(0))^{+}\}]}{s}
+ \frac{IE [e^{−s\{σ(1)+(i−1)(σ(0)⊕σ(1))\}} \{σ(2) + (i − 1)(σ(2) − (σ(0) ⊕ σ(1)))^{+}\}]}{s}
− \frac{IE [e^{−s(i−1)σ(0)} \{(σ(2) + (i − 1)(σ(2) − (σ(0) ⊕ σ(1)))^{+})^{2} − (σ(1) + (i − 1)(σ(1) − σ(0))^{+})^{2}\}]}{2}.

3.3 Higher-Order Moments

We can derive a similar expansion for higher-order moments of W^{i}, 1 ≤ i ≤ α′. Choosing f(x) = x^{ν} and setting c = 1 allows us to apply Theorem 1 to get the following result:

Corollary 2 In addition to the foregoing assumptions on {A_{n}, B_{n}} above, assume that the (ν + m + 2)-th moment of H_{n} is finite for some m, ν ∈ IN, i.e. IE[(H_{n})^{ν+m+2}] < ∞. Then

IE[(W^{i})^{ν}] = ∑_{k=0}^{m} λ^{k} IE[ p_{k+1}^{(ν)}(D_{0}^{i}, D_{1}^{i}, …, D_{k}^{i}) ] + O(λ^{m+1}),  (37)

for 1 ≤ i ≤ α′, where p_{1}^{(ν)}(x_{0}) = x_{0}^{ν}, and

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

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

for 1 ≤ k ≤ m, and the functions p_{k} are the polynomials given by (15).

Remark Having in mind that

IE[(W^{i})^{ν}] = lim_{s↓0} \{(−1)^{ν} \frac{d^{ν}}{ds^{ν}} IE[e^{−s W^{i}}]\} ,

whenever the ν-th moment of W^{i} is finite, one is tempted to think that the polynomials p_{k}^{(ν)}(x_{0}, …, x_{k−1}) can be obtained from the exponential-polynomial functions q_{k}(s; x_{0}, …, x_{k−1}) by differentiating and taking the limit s ↓ 0, i.e.

p_{k}^{(ν)}(x_{0}, x_{1} …, x_{k−1}) = lim_{s↓0} \{(−1)^{ν} \frac{d^{ν}}{ds^{ν}} q_{k}(s; x_{0}, x_{1} …, x_{k−1})\} ,  (39)

for all k ≥ 1. Elementary calculations show that equality (39) holds indeed.

Example: Blocking Queues The following finite capacity queueing system with blocking was considered in [3]: the system consists of four single-server FIFO stations in tandem. The first station, which is fed by the arrival point process, has an infinite capacity buffer, whereas all other stations have no buffering capacity. The blocking mechanism is that of “blocking after service”, i.e. in each station, a customer can always start his service but once his service is completed, the customer can only proceed to the downstream station whenever this one is empty (this is also called manufacturing blocking). Taking as state variables the variables W_{n}^{i}, where W_{n}^{i} gives the time which elapses between the n-th external arrival and the time when customer n leaves station i, it was shown in [3] that the corresponding D_{n} vectors are given by the following formulas: whenever the system starts empty and whenever the service times are deterministic and equal to σ^{i} in station i with σ^{1} ≤ σ^{2} ≤ σ^{3} ≤ σ^{4}:

D_{0} = ( \begin{matrix}σ^{1} \\ σ^{1} + σ^{2} \\ σ^{1} + σ^{2} + σ^{3} \\ σ^{1} + σ^{2} + σ^{3} + σ^{4} \end{matrix} ) , D_{1} = ( \begin{matrix}σ^{1} + σ^{2} \\ σ^{1} + σ^{2} + σ^{3} \\ σ^{1} + σ^{2} + σ^{3} + σ^{4} \\ σ^{1} + σ^{2} + σ^{3} + 2σ^{4} \end{matrix} ) , (40)

D_{2} = ( \begin{matrix}σ^{1} + σ^{2} + σ^{3} \\ σ^{1} + σ^{2} + σ^{3} + σ^{4} \\ σ^{1} + σ^{2} + σ^{3} + 2σ^{4} \\ σ^{1} + σ^{2} + σ^{3} + 3σ^{4} \end{matrix} ) , D_{n} = ( \begin{matrix}σ^{1} + σ^{2} + σ^{3} + (n − 2)σ^{4} \\ σ^{1} + σ^{2} + σ^{3} + (n − 1)σ^{4} \\ σ^{1} + σ^{2} + σ^{3} + (n)σ^{4} \\ σ^{1} + σ^{2} + σ^{3} + (n + 1)σ^{4} \end{matrix} ) , ∀ n ≥ 3. (41)

So, as a direct application of Corollary 2, the coefficients c_{k} of the expansion of the second moment of the stationary “waiting time” in station 1

IE [(W^{1})^{2}] = c_{0} + c_{1}λ + c_{2}λ^{2} + O(λ^{3})

are given by the following formulas:

c_{0} = (σ^{1})^{2}
c_{1} = (σ^{1})(σ^{2})^{2} + \frac{1}{3}(σ^{2})^{3}
c_{2} = \frac{(σ^{3})^{4} − (σ^{1})^{4}}{12} − \frac{(σ^{1})(σ^{2})^{3} − (σ^{1})(σ^{3})^{3} − (σ^{2})(σ^{3})^{3}}{3} + \frac{1}{2}(σ^{2})^{2}(σ^{3})^{2} + (σ^{1})(σ^{2})(σ^{3})^{2}.

3.4 The Tail Function of W^{i}

Another interesting function of W^{i} is its distribution function, or equivalently its tail function IP (W^{i} > ξ), ξ ≥ 0. Before we can apply Theorem 1 to derive a finite series expansion of IP (W^{i} > ξ), we first notice that IP (W^{i} > ξ) = IE [1(W^{i} > ξ)] and thus choose f(x) = 1(x > ξ) for all x ≥ 0. Clearly, 0 ≤ f(x) ≤ 1, for all x ∈ IR^{+}. Applying Theorem 1, we use the version F^{[n]}(x) = \frac{1}{n!}(x − ξ)^{n} 1(x > ξ), for all n ∈ IN_{0}, of the indefinite integral ∫ F^{[n−1]}(x) dx. So we obtain

Corollary 3 In addition to the foregoing assumptions on {A_{n}, B_{n}}, assume the (m + 2)-th moment of H_{n} to be finite for some m ∈ IN, i.e. IE [(H_{n})^{m+2}] < ∞. Then, for all ξ ≥ 0 and for 1 ≤ i ≤ α′,

IP (W^{i} > ξ) = ∑_{k=0}^{m} λ^{k} IE [ q̃_{k+1}(D_{0}^{i}, D_{1}^{i}, …, D_{k}^{i})] + O(λ^{m+1}),  (42)

where q̃_{1}(x_{0}) = 1(x_{0} > ξ),

q̃_{k+1}(x_{0}, x_{1}, …, x_{k})

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

for 1 ≤ k ≤ m, and the functions p_{k} are the polynomials defined in (15).

Example: Queues in Tandem — Continued We continue the example of tandem queues with random and identical service times in all stations. Under the assumption that the service times have moments of order m + 2, the frist three coefficients c_{k}, k = 0, 1, 2, of the expansion

IP (W^{i} > ξ) = ∑_{k=0}^{m} c_{k}λ^{k} + O(λ^{m+1})

are given by the formulas:

c_{0} = IP((i − 1)σ(0) > ξ),
c_{1} = IE [1((i − 1)σ(0) ≤ ξ) · (σ(1) + (i − 1)(σ(0) ⊕ σ(1)) − ξ)^{+}] ,
c_{2} = IE [1((i − 1)σ(0) ≤ ξ) · \{\frac{1}{2}((σ(1) + σ(2) + (i − 1)(σ(0) ⊕ σ(1) ⊕ σ(2)) − ξ)^{+})^{2}
− (σ(1) + (i − 1)(σ(0) ⊕ σ(1)) − ξ)^{+}(σ(1) + σ(2) + (i − 1)(σ(0) ⊕ σ(1) ⊕ σ(2)) − ξ)^{+}}] .

4 Factorial Moment Expansion

4.1 Preliminary Results

In this subsection we will recall the general method for proving part 1 of our main theorem and also give some simple inequalities which turn out to be useful later on.

4.1.1 General Expansion Theorem

In order to prove the series expansion stated in Theorem 1 we will use a general idea which consists in expanding the expectation of vector-valued functionals of marked point processes. This method, which was introduced in [5], was shown to be quite useful for approximating the characteristics of several stochastic models (see e.g. [3], [4], [6], [7], [8] or [9]).

Expansion Kernels For any given natural number α, let ψ be an IR^{α}-valued functional of a marked point process, i.e. a measurable mapping ψ : M × K^{∞} → IR^{α}, where M is the space of all realizations of the point process {T_{n}} and K^{∞} is the space of all sequences Z = {Z_{n}} of potential marks. We assume that the mark space K is a complete separable metric space. Note that the sequence {T_{n}} of points may be infinite, finite or empty, whereas the sequence Z = {Z_{n}} of potential marks is always two-sided infinite. Let Z_{n} denote the mark of point T_{n}. We represent a realization {t_{n}} of the point process {T_{n}} by the counting measure μ = ∑_{n} δ_{t_{n}}. By o we denote the null measure, representing an input with no arrivals (i.e. o(IR) = 0).

For every x ∈ IR, let the restriction μ|^{x} of μ ∈ M be defined by

μ|^{x}(D) = μ(D ∩ (x, ∞)).

Furthermore, for any x ∈ IR and z ∈ K^{∞}, let

ψ_{x}(μ, z) = ψ(μ|^{x} + δ_{x}, z) − ψ(μ|^{x}, z).  (44)

Let k ≥ 1 be an arbitrary, but fixed integer. For any x_{1}, …, x_{k} ∈ IR, let ψ_{x_{1},...,x_{k}} be defined by iteration of the mapping ψ → ψ_{x}, i.e.

ψ_{x_{1},...,x_{k}}(μ, z) = ( … (ψ_{x_{1}})_{x_{2}} …)_{x_{k}}(μ, z).

Note that the functional ψ_{x_{1},...,x_{k}} can be written in the form

ψ_{x_{1},...,x_{k}}(μ, z) = \{ \begin{matrix}∑_{j=0}^{k}(−1)^{k−j} ∑_{π∈K_{k,j}} ψ(μ|^{x_{k}} + ∑_{i∈π} δ_{x_{i}}, z) & for x_{1} < … < x_{k}, \\ 0 & otherwise, \end{matrix}  (45)

where K_{k,j} denotes the collection of all subsets of {1, …, k} containing j elements. Following [5], we call the functional ψ continuous at infinity if

lim_{x→∞} ψ(μ|^{x} + ν, z) = ψ(ν, z),  lim_{x→−∞} ψ(μ|^{x}, z) = ψ(μ, z)  (46)

for all μ, ν ∈ M, z ∈ K^{∞} with ν(IR) < ∞.

Representation Formula For the stationary Poisson process {T_{n}} with intensity λ, and for the stationary sequence Z = {Z_{n}} of K-valued random variables which is independent of {T_{n}}, let P_{λ} denote the distribution of {T_{n}}, and Q the distribution of Z.

A slight variant of the following result is given in [9], where the general expansion derived in [5] is specified to the Poisson case. With ψ^{i} we denote the i-th component of the IR^{α}-valued functional ψ.

Theorem 2 Let m ≥ 1 be a fixed integer. If the functional ψ is continuous at infinity, if

∫_{IR^{k}} ∫_{K^{∞}} ∫_{M} | ψ_{x_{1},...,x_{k}}^{i}(μ, z) | P_{λ}(dμ) Q(dz) d(x_{1}, …, x_{k}) < ∞,  (47)

for all k = 1, …, m, and if

lim sup_{λ→0} ∫_{IR^{m+1}} ∫_{K^{∞}} ∫_{M} | ψ_{x_{1},...,x_{m+1}}^{i}(μ, z) | P_{λ}(dμ) Q(dz) d(x_{1}, …, x_{m+1}) < ∞,  (48)

then

IE[ ψ^{i}({(T_{n}, Z_{n})}) ]

= IE[ ψ^{i}(o, {Z_{n}}) ] + ∑_{k=1}^{m} λ^{k} ∫_{IR^{k}} IE[ ψ_{x_{1},...,x_{k}}^{i}(o, {Z_{n}}) ] d(x_{1}, …, x_{k}) + O(λ^{m+1}). (49)

4.1.2 Simple Inequalities

A useful bound is given by

Lemma 2 For k, r ∈ IN and 1 ≤ i ≤ α

D_{kr}^{i} ≤ H_{0} + H_{1} + … + H_{k−1}.  (50)

Proof It suffices to note that

D_{kr}^{i} = ( (⨂_{n=1}^{kr} A_{−n}) ⊗ B_{−kr} )^{i} = ( (⨂_{p=0}^{k−1} ⨂_{q=0}^{r−1} A_{−(pr+q+1)}) ⊗ B_{−kr} )^{i}

≤ ⨂_{p=0}^{k−1} (⨂_{q=0}^{r−1} A_{−(pr+q+1)} ⊗ (B_{−(p+1)r} ⊗ O))^{i} ≤ ⨂_{p=0}^{k−1} H_{p}.

We will also use the next simple result later on.

Lemma 3 For x_{1}, …, x_{k} ∈ IR_{0}^{+}, i_{1}, …, i_{k}, k ∈ IN and n ∈ IN_{0} the following (conventional algebra) inequalities hold:

(a)  x_{1}^{i_{1}} · · · · · x_{k}^{i_{k}} ≤ x_{1}^{i_{1}+···+i_{k}} + ⋯ + x_{k}^{i_{1}+···+i_{k}},  (51)
(b)  (x_{1} + ⋯ + x_{k})^{n} ≤ k^{n} (x_{1}^{n} + ⋯ + x_{k}^{n}).  (52)

Proof In order to prove (a) note that

∏_{j=1}^{k} x_{j}^{i_{j}} ≤ ∏_{j=1}^{k} ( max_{1≤j≤k}{x_{j}})^{i_{j}} = ( max_{1≤j≤k}{x_{j}})^{∑_{j=1}^{k} i_{j}} ≤ ∑_{j=1}^{k} x_{j}^{∑_{j=1}^{k} i_{j}}.

On the other hand, using (a) gives (b) for n ≥ 1 by the following reasoning:

( ∑_{j=1}^{k} x_{j})^{n} = ∑_{{(i_{1},...,i_{k}): \atop i_{1}+...+i_{k}=n}}^{k} \binom{k}{i_{1} … i_{k}} ∏_{j=1}^{k} x_{j}^{i_{j}} ≤ ∑_{{(i_{1},...,i_{k}): \atop i_{1}+...+i_{k}=n}}^{k} \binom{k}{i_{1} … i_{k}} ∑_{j=1}^{k} x_{j}^{n} = k^{n} ∑_{j=1}^{k} x_{j}^{n}.

For n = 0, (b) is immediate.

4.2 Proof of the Finite Expansion Formula

In this subsection we will use Theorem 2 in order to show that the finite expansion of IE [f(W^{i})] given in (21) holds. To prove that the conditions of Theorem 2 are fulfilled under the assumptions made above, we can proceed in a way which is similar to that used in [3] for expanding the first moment IE [W^{i}]. Consider the following functional ψ given by

ψ(μ, z) = (ψ^{i}(μ, z))_{i=1,...,α}

= (f(d_{0}^{i} ⊕ ⨁_{n=1}^{μ((−∞,0))}(d_{n}^{i} ⊗ t_{−n})))_{i=1,...,α} ,  (53)

where μ = ∑_{n} δ_{t_{n}} denotes the realization of the arrival process {T_{n}}. Furthermore, let z = {a_{n}, b_{n}}, where a_{n} and b_{n} denote the realizations of the random matrices A_{n} and B_{n}, respectively. In the same vein, let d_{0}^{i} = b_{0}^{i} and d_{k}^{i} = ((⨂_{n=1}^{k} a_{−n}) ⊗ b_{−k})^{i}, for k ≥ 1, denote the realizations of the i-th component of the random vectors D_{k} defined in (4). In what follows, we are going to look only at those components ψ^{i} of the functional ψ, where 1 ≤ i ≤ α′, in accordance with the statement of Theorem 1.

The fact that ψ is a.s. continuous at infinity whenever ρ < 1 follows directly from the backward monotone construction used in Chapter 7 of [2], where ρ = λ a and a is the maximal (max,+)– Lyapunov exponent of the sequence {A_{n}}.

4.2.1 Integrability

We first show that the expectation IE [f(W^{i})] is finite for each i ∈ {1, …, α′} whenever the conditions of Theorem 1 are satisfied. Let r ∈ IN be chosen according to Lemma 1. Since f(·) is assumed to be bounded by f(x) ≤ c x^{ν}, for all x ∈ IR^{+}, we get

ψ^{i}(μ, z) = f(d_{0}^{i} ⊕ ⨁_{n=1}^{μ((−∞,0))}(d_{n}^{i} + t_{−n})) ≤ c (d_{0}^{i} ⊕ ⨁_{n=1}^{μ((−∞,0))}(d_{n}^{i} + t_{−n}))^{ν}

≤ c (b_{0}^{i} + sup_{p≥0} max_{1≤q≤r} {d_{pr+q} + t_{−(pr+q)}}^{+})^{ν} ≤ c (b_{0}^{i} + sup_{p≥0} {d_{(p+1)r} + t_{−(pr+1)}}^{+})^{ν}
≤ c (b_{0}^{i} + sup_{p≥0} {h_{0} + … + h_{p} + t_{−pr}}^{+})^{ν}
= c (b_{0}^{i} + sup_{p≥0} {h_{0} + ∑_{{1≤2k≤p}} (h_{2k} + (t_{−2kr} − t_{−(2k−1)r}))

+ ∑_{{1≤2k−1≤p}} (h_{2k−1} + (t_{−(2k−1)r} − t_{−(2k−2)r}))}^{+})^{ν}

≤ c ( max_{j}{b_{0}^{j}} + h_{0} + φ^{(0)}(μ, z) + φ^{(1)}(μ, z))^{ν},  (54)

where φ^{(j)}(μ, z), j = 0, 1, denotes the realization of the random variable

φ^{(j)}({T_{n}}, {Z_{n}}) = sup_{p≥1} {∑_{k=1}^{p} (H_{2k−j} + (T_{−(2k−j)r} − T_{−(2k−j−1)r}))}^{+} , j = 0, 1,  (55)

for a given (μ, z) and {x}^{+} = max{0, x} for all x ∈ IR. Applying Lemma 3 on (54) yields

| ψ^{i}(μ, z) | ≤ c 4^{ν} {( max_{j}{b_{0}^{j}})^{ν} + (h_{0})^{ν} + (φ^{(0)}(μ, z))^{ν} + (φ^{(1)}(μ, z))^{ν}} .

Because of the general stochastic assumptions made in Section 2, we see that φ^{(j)}({T_{n}}, {Z_{n}}), j = 0, 1, is actually the maximum of a random walk with negative drift, since under (10), for j = 0, 1, we have

IE [ H_{2k−j} + (T_{−(2k−j)r} − T_{−(2k−j−1)r}) ] = IE[H_{0}] − \frac{r}{λ} < IE[H_{0}] − \frac{r − 1}{λ} < 0.

The finiteness of IE [(W^{i})^{ν}] now follows from the well known fact that the ν-th moment of the maximum of a random walk with negative drift is finite whenever the (ν + 1)-th moment of its increments is finite (see e.g. Theorem VIII.2.1 in [1]). But this is true since

IE[(H_{2k−j} + (T_{−(2k−j)r} − T_{−(2k−j−1)r}))^{ν+1}] ≤ 2^{ν+1} \{IE[(H_{0})^{ν+1}] + (ν + 1)! (\frac{r}{λ})^{ν+1}\}
< ∞,

for j = 0, 1, whenever IE[(H_{0})^{ν+1}] < ∞.

4.2.2 Proof of Condition (47): k = 1

We first prove that condition (47) holds for k = 1. Let x ∈ [t_{−l}, t_{−(l−1)}), for some l ∈ {1, 2, …}. The first expansion kernel of the functional ψ can then be written as

ψ_{x}^{i}(μ, z) = ψ^{i}(μ|^{x} + δ_{x}, z) − ψ^{i}(μ|^{x}, z)
= f(d_{0}^{i} ⊕ ⨁_{n=1}^{l−1}(d_{n}^{i} + t_{−n}) ⊕ (d_{l}^{i} + x)) − f(d_{0}^{i} ⊕ ⨁_{n=1}^{l−1}(d_{n}^{i} + t_{−n})).

It is easily seen that ψ_{x}^{i}(μ, z) is equal to zero whenever the last term (d_{l}^{i} + x) of the sum in the argument of f(·) corresponding to ψ^{i}(μ|^{x} + δ_{x}, z) is smaller than or equal to all other terms in this sum; so

| ψ_{x}^{i}(μ, z) | = | f(d_{l}^{i} + x) − f(d_{0}^{i} ⊕ ⨁_{n=1}^{l−1}(d_{n}^{i} + t_{−n})) | 1(d_{l}^{i} + x > d_{0}^{i} ⊕ ⨁_{n=1}^{l−1}(d_{n}^{i} + t_{−n}))
≤ c (d_{l}^{i} + x)^{ν} 1(d_{l}^{i} + x > 0),  (56)

since d_{l}^{i} + x > d_{0}^{i} ≥ 0.

We assumed that l was chosen such that x ∈ [t_{−l}, t_{−(l−1)}). Let us first consider the case when l ≤ (r − 1)^{2}. Then

(d_{l}^{i} + x)^{ν} 1(d_{l}^{i} + x > 0) ≤ (d_{(r−1)^{2}}^{i})^{ν} 1(d_{(r−1)^{2}}^{i} + x > 0) ≤ (d_{r^{2}}^{i})^{ν} 1( − x < d_{r^{2}}^{i}),

where these inequalities hold for a.e. (μ, z) due to (5). Hence

∫_{IR} ∫_{K} ∫_{M} | ψ_{x}^{i}(μ, z) | 1(x : x ≥ t_{−(r−1)^{2}})P_{λ}(dμ) Q(dz) dx
≤ c ∫_{K} ∫_{M} ∫_{−∞}^{0} (d_{r^{2}}^{i}(μ, z))^{ν} 1((μ, z) : −x < d_{r^{2}}^{i}(μ, z)) dx P_{λ}(dμ) Q(dz)
= c IE[(D_{r^{2}}^{i})^{ν+1}] ≤ c IE[(H_{0} + H_{1} + … + H_{r−1})^{ν+1}]
≤ c r^{ν+2} IE[(H_{0})^{ν+1}] < ∞,

where the second and third inequalities follow from Lemma 2 and 3, respectively.

For l > (r − 1)^{2}, we choose p ∈ IN to be such that p(r − 1) < l ≤ (p + 1)(r − 1). Therefore both l and p are actually functions of μ, z and x. In particular, for a given realization (μ, z) of the arrival process, the values of l = l(x) and p = p(x) will possibly change when x is changed.

We first derive an upper bound on (d_{l}^{i} + x) using the fact that for a.e. realization (μ, z), the sequence {d_{n}^{i}}_{n≥0} is non-decreasing, thanks to (5). Note that in this case, l ≤ pr. This is true, because we have l > (r−1)(r−1) and also l ≤ (p+1)(r−1) which implies r−1 ≤ p and therefore pr + (r − 1) − p ≤ pr, or, equivalently, (p + 1)(r − 1) ≤ pr. Making use of these considerations and applying Lemma 2 once more, we obtain

d_{l}^{i} + x ≤ d_{pr}^{i} + t_{−(l−1)} ≤ d_{pr}^{i} + t_{−p(r−1)} ≤ h_{0} + h_{1} + … + h_{p−1} + t_{−p(r−1)}
≤ ∑_{k=0}^{p−1} (h_{k} + (t_{−(k+1)(r−1)} − t_{−k(r−1)}))
= ∑_{{k: 0≤2k≤p−1}} (h_{2k} + (t_{−(2k+1)(r−1)} − t_{−2k(r−1)}))

+ ∑_{{k: 0≤2k−1≤p−1}} (h_{2k−1} + (t_{−2k(r−1)} − t_{−(2k−1)(r−1)}))

= ξ_{p}^{(0)} + ξ_{p}^{(1)},

where ξ_{p}^{(j)} = ξ_{p}^{(j)}(μ, z), j = 0, 1, denote the realizations of the random variables

ξ_{p}^{(j)}({T_{n}}, {Z_{n}}) = ∑_{{k: 0≤2k−j≤p−1}} (H_{2k−j} + (T_{−(2k+1−j)(r−1)} − T_{−(2k−j)(r−1)})),  (57)

for j = 0, 1 and n ∈ IN, where {T_{n}} is the stationary Poisson process with intensity λ, and {H_{n}} is defined in (6). So in this second case,

(d_{l}^{i} + x)^{ν} 1(d_{l}^{i} + x > 0) ≤ (ξ_{p}^{(0)} + ξ_{p}^{(1)})^{ν} 1(ξ_{p}^{(0)} + ξ_{p}^{(1)} > 0).  (58)

We now derive upper bounds on each term of the last product.

Lemma 4 Let η^{(j)} = η^{(j)}(μ, z), j = 0, 1 denote the realizations of the random variables

η^{(j)}({T_{n}}, {Z_{n}}) = sup_{p≥1} { − T_{−(p+1)(r−1)} : ξ_{p}^{(j)}({T_{n}}, {Z_{n}}) > 0},  j = 0, 1.  (59)

and let

ϕ^{(j)} = sup_{p≥1} {ξ_{p}^{(j)}}, j = 0, 1. (60)

Then

(d_{l}^{i} + x)^{ν} 1(d_{l}^{i} + x > 0) ≤ (ξ_{p}^{(0)} + ξ_{p}^{(1)})^{ν} 1(ξ_{p}^{(0)} + ξ_{p}^{(1)} > 0)
≤ (ϕ^{(0)} + ϕ^{(1)} )^{ν} 1( − x < η^{(0)} + η^{(1)}).

Proof The fact that ξ_{p}^{(0)} + ξ_{p}^{(1)} ≤ ϕ^{(0)} + ϕ^{(1)} is immediate, and we now concentrate on the second term. Because {H_{n}} is a sequence of 1-dependent random variables, the random variables H_{0}, H_{2}, … are i.i.d. and independent of the i.i.d. random variables −(T_{−(r−1)}−T_{0}), −(T_{−3(r−1)}− T_{−2(r−1)}), …, which are Erlang distributed with expectation (r − 1) · λ^{−1}. Under (10), we see that

IE [ H_{2k} + (T_{−(2k+1)(r−1)} − T_{−2k(r−1)}) ] = IE[H_{0}] − \frac{r − 1}{λ} < 0,  (61)

so that ξ_{p}^{(0)}({T_{n}}, {Z_{n}}) is a random walk with negative drift. Therefore ξ_{p}^{(0)} → −∞ a.s. for p → ∞. Since the sequences H_{1}, H_{3}, … and −(T_{−2(r−1)} − T_{−(r−1)}), −(T_{−4(r−1)} − T_{−3(r−1)}), … have the same properties as the sequences considered above, also ξ_{p}^{(1)}({T_{n}}, {Z_{n}}) exhibits the same limiting behavior. Because the arrival process is Poisson, we know that for almost every realisation (μ, z), p = p(x) → ∞ whenever x → −∞ and as a consequence both ξ_{p}^{(0)} → −∞ and ξ_{p}^{(1)} → −∞ a.s. for x → −∞. Therefore, the inequality ξ_{p(x)}^{(0)} + ξ_{p(x)}^{(1)} > 0 cannot hold for x arbitrarily small. More precisely, since the relation between x and p(x) is that x ∈ [t_{−(p(x)+1)(r−1)}, t_{−p(x)(r−1)}), {ξ_{p(x)}^{(0)} + ξ_{p(x)}^{(1)} > 0} implies that

x > inf_{ζ≤0} {t_{−(p(ζ)+1)(r−1)} : ξ_{p(ζ)}^{(0)} + ξ_{p(ζ)}^{(1)} > 0},  (62)

or, equivalently,

−x < sup_{ζ≤0} { − t_{−(p(ζ)+1)(r−1)} : ξ_{p(ζ)}^{(0)} + ξ_{p(ζ)}^{(1)} > 0}.  (63)

An obvious bound for the righthand side of (63) is given by

sup_{ζ≤0} { − t_{−(p(ζ)+1)(r−1)} : ξ_{p(ζ)}^{(0)} + ξ_{p(ζ)}^{(1)} > 0}

≤ sup_{ζ≤0} { − t_{−(p(ζ)+1)(r−1)} : ξ_{p(ζ)}^{(0)} > 0 or ξ_{p(ζ)}^{(1)} > 0}
≤ sup_{ζ≤0} { − t_{−(p(ζ)+1)(r−1)} : ξ_{p(ζ)}^{(0)} > 0} + sup_{ζ≤0} { − t_{−(p(ζ)+1)(r−1)} : ξ_{p(ζ)}^{(1)} > 0}
= sup_{p≥1} { − t_{−(p+1)(r−1)} : ξ_{p}^{(0)} > 0} + sup_{p≥1} { − t_{−(p+1)(r−1)} : ξ_{p}^{(1)} > 0}.
= η^{(0)} + η^{(1)}.  (64)

Using (63) and (64) we see that

{(μ, z) : ξ_{p}^{(0)} + ξ_{p}^{(1)} > 0} ⊆ {(μ, z) : −x < η^{(0)} + η^{(1)}},  (65)

which concludes the proof.

Therefore, up to this point we have shown that

∫_{IR} ∫_{K} ∫_{M} | ψ_{x}^{i}(μ, z) | 1(x : x < t_{−(r−1)^{2}})P_{λ}(dμ) Q(dz) dx
≤ c ∫_{K} ∫_{M} ∫_{−∞}^{0} (ϕ^{(0)} + ϕ^{(1)} )^{ν} 1( − x < η^{(0)} + η^{(1)}) dx P_{λ}(dμ) Q(dz)

= c IE[(ϕ^{(0)} + ϕ^{(1)} )^{ν} (η^{(0)} + η^{(1)})] ≤ c 2^{ν} IE[((ϕ^{(0)})^{ν} + (ϕ^{(1)})^{ν}) (η^{(0)} + η^{(1)})]

≤ c 2^{ν+1} { IE[(φ^{(0)})^{ν+1}] + IE[(φ^{(1)})^{ν+1}] + IE[(η^{(0)})^{ν+1}] + IE[(η^{(1)})^{ν+1}] },  (66)

where the arguments have been dropped if no misunderstanding is possible. We used Lemma 3 to obtain the last two inequalities and the fact that P (ϕ^{(j)} ≤ y) = P (φ^{(j)} ≤ y), for all y ∈ IR, and j = 0, 1, to get the final line.

Our last step consists in proving the integrability of (η^{(j)}({T_{n}}, {Z_{n}}))^{ν+1}, j = 0, 1. Before doing so, let us first introduce some additional notation. For i, j = 0, 1 let

ζ^{(i,j)}({T_{n}}, {Z_{n}}) = sup_{p≥1} { − ∑_{{k: 0≤2k−i≤p}}(T_{−(2k−i+1)(r−1)} − T_{−(2k−i)(r−1)}) : ξ_{p}^{(j)} > 0}, (67)

where we write ξ_{p}^{(j)} instead of ξ_{p}^{(j)}({T_{n}}, {Z_{n}}) for sake of simplicity; as usual, let ζ^{(i,j)} = ζ^{(i,j)}(μ, z), for i, j = 0, 1, denote the realizations of the corresponding random variables. For ζ^{(i,j)}({T_{n}}, {Z_{n}}) the following result holds:

Lemma 5 The q-th moment of ζ^{(i,j)}({T_{n}}, {Z_{n}}), i, j = 0, 1 is finite provided that the (q+1)-th moment of H_{n} is finite, i.e. IE[(H_{n})^{q+1}] < ∞.

A proof for this statement in case i = j is given in Lemma 6 in [3]. For i ≠ j see Lemma 7 in the same paper.

Lemma 6 The q-th moment of η^{(j)}({T_{n}}, {Z_{n}}), j = 0, 1 is finite whenever the (q + 1)-th moment of H_{n} is finite, i.e. IE[(H_{n})^{q+1}] < ∞.

Proof For j = 0, 1

η^{(j)} = sup_{p≥1} { − t_{−(p+1)(r−1)} : ξ_{p}^{(j)} > 0}
= sup_{p≥1} { − ∑_{{k: 0≤2k≤p}}(t_{−(2k+1)(r−1)} − t_{−2k(r−1)})

− ∑_{{k: 0≤2k−1≤p}}(t_{−2k(r−1)} − t_{−(2k−1)(r−1)}) : ξ_{p}^{(j)} > 0}

≤ ζ^{(0,j)} + ζ^{(1,j)}.  (68)

So we conclude that

IE[(η^{(j)}({T_{n}}, {Z_{n}}))^{q}] ≤ IE[(ζ^{(0,j)}({T_{n}}, {Z_{n}}) + ζ^{(1,j)}({T_{n}}, {Z_{n}}))^{q}]
≤ 2^{q} {IE[(ζ^{(0,j)}({T_{n}}, {Z_{n}}))^{q}] + IE[(ζ^{(1,j)}({T_{n}}, {Z_{n}}))^{q}]},  (69)

where we used (52) to get the last inequality. The desired statement follows immediately from Lemma 5.

Applying Lemma 6 to (66) yields

∫_{IR} ∫_{K} ∫_{M} | ψ_{x}^{i}(μ, z) | P_{λ}(dμ) Q(dz) dx < ∞,

provided that IE[(H_{n})^{ν+2}] < ∞, which completes the proof of the validity of (47) for k = 1.

4.2.3 Proof of Condition (47): k ≥ 1

Now we want to look at condition (47) for k ≥ 1. Therefore, let x_{1} < x_{2} < … < x_{k} for k ∈ {1, …, m} and x_{k} ∈ [t_{−l}, t_{−(l−1)}) for some l ∈ {1, 2, …}. By applying (45) we obtain

ψ_{x_{1},...,x_{k}}^{i}(μ, z) = ∑_{j=0}^{k}(−1)^{k−j} ∑_{π∈K_{k,j}} ψ(μ|^{x_{k}} + ∑_{i∈π} δ_{x_{i}}, z) 1(x_{1} < … < x_{k})
= ∑_{j=0}^{k}(−1)^{k−j} ∑_{π∈K_{k,j}} f(d_{0}^{i} ⊕ ⨁_{n=1}^{l−1}(d_{n}^{i} + t_{−n}) ⊕ ⨁_{n=1}^{j}(d_{l−1+n}^{i} + x_{π_{(j+1−n)}})),  (70)

where π_{(n)} denotes the n-th smallest element of the j-tupel π. The summation can now be organized in the following way (with the three dots being placeholders for the function f(·) in (70) ):

ψ_{x_{1},...,x_{k}}^{i}(μ, z) = ∑_{j=0}^{k−1}(−1)^{k−j} { ∑_{π∈K_{k,j},π∌1} … − ∑_{π∈K_{k,j+1},π∋1} … }

= ∑_{j=0}^{k−1}(−1)^{k−j} ∑_{π∈K_{k,j},π∌1} { f(d_{0}^{i} ⊕ ⨁_{n=1}^{l−1}(d_{n}^{i} + t_{−n}) ⊕ ⨁_{n=1}^{j}(d_{l−1+n}^{i} + x_{π_{(j+1−n)}}))

− f(d_{0}^{i} ⊕ ⨁_{n=1}^{l−1}(d_{n}^{i} + t_{−n}) ⊕ ⨁_{n=1}^{j}(d_{l−1+n}^{i} + x_{π_{(j+1−n)}}) ⊕ (d_{l+j} + x_{1}))}. (71)

If we assume that d_{l−1+k}^{i} + x_{1} ≤ 0, then we also have d_{l+j}^{i} + x_{1} ≤ 0, for all 1 ≤ j ≤ k − 1, since the d_{n}^{i}’s are non-decreasing in n. Using this information together with d_{0}^{i} ≥ 0, the above representation of the functional ψ_{x_{1},...,x_{k}}^{i} immediately yields

ψ_{x_{1},...,x_{k}}^{i}(μ, z) = 0  whenever  d_{l−1+k}^{i} + x_{1} ≤ 0,

and therefore (with the three dots representing the corresponding functions in (71) )

| ψ_{x_{1},...,x_{k}}^{i}(μ, z) | ≤ ∑_{j=0}^{k−1} ∑_{π∈K_{k,j},π∌k} | … − … |

≤ ∑_{j=0}^{k−1} \binom{k − 1}{j} c (d_{l−1+k}^{i} + x_{1})^{ν} 1(d_{l−1+k}^{i} + x_{1} > 0)
= 2^{k−1} c (d_{l−1+k}^{i} + x_{1})^{ν} 1(d_{l−1+k}^{i} + x_{1} > 0),  (72)

We first consider the case l ≤ (r − 1)^{2} + (r − 1)(k − 1). Then

(d_{l−1+k}^{i} + x_{1})^{ν} 1(d_{l−1+k}^{i} + x_{1} > 0) ≤ (d_{(r−1)^{2}+r(k−1)}^{i})^{ν} 1(d_{(r−1)^{2}+r(k−1)}^{i} + x_{1} > 0)
≤ (d_{kr^{2}}^{i})^{ν} 1( − x_{1} < d_{kr^{2}}^{i}),

and, as a consequence, for n = (r − 1)^{2} + (r − 1)(k − 1),

∫_{IR^{k}} ∫_{K} ∫_{M} | ψ_{x_{1},...,x_{k}}^{i}(μ, z) | 1(x_{k} : x_{k} ≥ t_{−n})P_{λ}(dμ) Q(dz) d(x_{1} … x_{k})
≤ ∫_{K} ∫_{M} ∫_{−∞}^{0} ∫_{x_{1}}^{0} … ∫_{x_{k−1}}^{0} 2^{k−1} c (d_{kr^{2}}^{i})^{ν} 1( − x_{1} < d_{kr^{2}}^{i}) dx_{k} … dx_{2} dx_{1} P_{λ}(dμ) Q(dz)
= c 2^{k−1} ∫_{K} ∫_{M} (d_{kr^{2}}^{i})^{ν} ∫_{−d_{kr^{2}}^{i}}^{0} ∫_{x_{1}}^{0} … ∫_{x_{k−2}}^{0}(−x_{k−1}) dx_{k−1} … dx_{2} dx_{1} P_{λ}(dμ) Q(dz)
⋮
= c 2^{k−1} ∫_{K} ∫_{M} (d_{kr^{2}}^{i})^{ν}(−1)^{k} \frac{(−d_{kr^{2}}^{i})^{k}}{k!} P_{λ}(dμ) Q(dz) = c 2^{k−1} \frac{1}{k!} IE [(D_{kr^{2}}^{i})^{ν+k}]
≤ c 2^{k−1} \frac{1}{k!} IE[(H_{0} + H_{1} + … + H_{kr−1})^{ν+k}] ≤ c 2^{k−1} \frac{(kr)^{ν+k+1}}{k!} IE[(H_{0})^{ν+k}]
< ∞,

provided that IE[(H_{0})^{ν+k}] < ∞, where we used Lemma 2 and Lemma 3 b) for the last inequalities.

Next we will look at the case l > (r − 1)^{2} + (r − 1)(k − 1). As we did for k = 1, we choose p ∈ IN to be such that p(r − 1) < l ≤ (p + 1)(r − 1). From l > (r − 1)^{2} + (r − 1)(k − 1) and l ≤ (p + 1)(r − 1) we conclude that (r − 1) + (k − 1) ≤ p and thus pr + (r − 1) − p ≤ pr − (k − 1) or, equivalently, (p + 1)(r − 1) ≤ pr + 1 − k. So we note that under the given assumptions l − 1 + k ≤ pr. By applying this information we obtain the following inequalities for a.e. (μ, z):

d_{l−1+k}^{i} + x_{1} ≤ d_{pr}^{i} + x_{k} − (x_{k} − x_{1}) ≤ d_{pr}^{i} + t_{−(l−1)} − (x_{k} − x_{1})
≤ d_{pr}^{i} + t_{−p(r−1)} − (x_{k} − x_{1}) ≤ ξ_{p}^{(0)} + ξ_{p}^{(1)} − (x_{k} − x_{1})
≤ ϕ^{(0)} + ϕ^{(1)},

where we use the same notation as in the k = 1 part above. Only this time we find x_{k} ∈ [t_{−(p+1)(r−1)}, t_{−p(r−1)}) and by the same arguments as for k = 1 we conclude that

{(μ, z) : ξ_{p}^{(0)} + ξ_{p}^{(1)} > x_{k} − x_{1}}
⊆ {(μ, z) : −x_{k} < sup_{p≥1} { − t_{−(p+1)(r−1)} : ξ_{p}^{(0)} + ξ_{p}^{(1)} > x_{k} − x_{1}}}
= {(μ, z) : −x_{1} < sup_{p≥1} { − t_{−(p+1)(r−1)} + (x_{k} − x_{1}) : ξ_{p}^{(0)} + ξ_{p}^{(1)} > x_{k} − x_{1}}}
⊆ {(μ, z) : −x_{1} < sup_{p≥1} { − t_{−(p+1)(r−1)} : ξ_{p}^{(0)} + ξ_{p}^{(1)} > 0}}
⊆ {(μ, z) : −x_{1} < η^{(0)} + η^{(1)}}.

So we have learned that, for n = (r − 1)^{2} + (r − 1)(k − 1),

∫_{IR^{k}} ∫_{K} ∫_{M} | ψ_{x_{1},...,x_{k}}^{i}(μ, z) | 1(x_{k} : x_{k} < t_{−n})P_{λ}(dμ) Q(dz) d(x_{1} … x_{k})
≤ c 2^{k−1} ∫_{K} ∫_{M} ∫_{−∞}^{0} ∫_{x_{1}}^{0} … ∫_{x_{k−1}}^{0} (ϕ^{(0)} + ϕ^{(1)} )^{ν} 1( − x_{1} < η^{(0)} + η^{(1)})
dx_{k} … dx_{2} dx_{1} P_{λ}(dμ) Q(dz)
= c 2^{k−1} ∫_{K} ∫_{M} (ϕ^{(0)} + ϕ^{(1)} )^{ν} ∫_{−(η^{(0)}+η^{(1)})}^{0} ∫_{x_{1}}^{0} … ∫_{x_{k−2}}^{0}(−x_{k−1}) dx_{k−1} … dx_{2} dx_{1}
P_{λ}(dμ) Q(dz)
⋮
= c 2^{k−1} ∫_{K} ∫_{M} (ϕ^{(0)} + ϕ^{(1)} )^{ν} (−1)^{k} \frac{( − η^{(0)} − η^{(1)})^{k}}{k!} P_{λ}(dμ) Q(dz)
= c 2^{k−1} \frac{1}{k!} IE [(ϕ^{(0)} + ϕ^{(1)} )^{ν} (η^{(0)} + η^{(1)})^{k}]
≤ c 2^{ν+2k} \frac{1}{k!} \{ IE[(φ^{(0)})^{ν+k}] + IE[(φ^{(1)})^{ν+k}] + IE[(η^{(0)})^{ν+k}] + IE[(η^{(1)})^{ν+k}] \} .

From Lemma 6 we know that the k-th moment of η^{(j)}({T_{n}}, {Z_{n}}), j=0,1, is finite, provided that IE[(H_{n})^{k+1}] < ∞, and therefore

∫_{IR^{k}} ∫_{K} ∫_{M} | ψ_{x_{1},...,x_{k}}^{i}(μ, z) | P_{λ}(dμ) Q(dz) d(x_{1} … x_{k}) < ∞,

for all k ∈ {1, … m} as long as IE[(H_{n})^{ν+m+1}] < ∞. This completes the proof of the validity of (47) in the given setting.

4.2.4 Proof of Condition (48)

In order to show the validity of (48) we use the same arguments as for k ∈ {1, … m} to start with. This leads us to

lim sup_{λ→0} ∫_{IR^{m+1}} ∫_{K^{∞}} ∫_{M} | ψ_{x_{1},...,x_{m+1}}^{i}(μ, z) | P_{λ}(dμ) Q(dz) dx_{1} … dx_{m+1}

≤ \frac{c 2^{ν+2m+2}}{(m + 1)!} lim sup_{λ→0} \{IE[(φ^{(0)}(\{T_{n}\}, \{Z_{n}\}))^{ν+m+1}] + IE[(φ^{(1)}(\{T_{n}\}, \{Z_{n}\}))^{ν+m+1}]
+ IE[(η^{(0)}({T_{n}}, {Z_{n}}))^{ν+m+1}] + IE[(η^{(1)}({T_{n}}, {Z_{n}}))^{ν+m+1}] }. (73)

Looking at the definitions of φ^{(j)}({T_{n}}, {Z_{n}}) and ξ^{(j)}({T_{n}}, {Z_{n}}) for j = 0, 1 we observe that these random variables are stochastically decreasing as λ → 0 and, as a consequence, so are the η^{(j)}({T_{n}}, {Z_{n}}), j = 0, 1. One can even construct a probability space such that these monotonicity properties hold pathwise. This follows from the well-known fact that a stationary Poisson process with a smaller intensity can be obtained by thinning from a stationary Poisson process with a larger intensity. Thus, (73) can be bounded by fixing λ at any permissible value λ′, i.e. 0 < λ′ < a, where a denotes the maximal (max,+)–Lyapunov exponent of {A_{n}}. The finiteness of (73), provided that IE[(H_{n})^{ν+m+2}] < ∞, then follows from Lemma 6. Therefore,

(48) also holds under the assumptions made.

5 Differentiability, Admissibility

In general, the conditions of Theorem 2 are not sufficient to ensure any differentiability property. However, it was shown in [3] that under Cramer type assumptions on the random variables D_{n}^{i}, the mean values of the random variables W^{i} are such that (23) holds and are infinitely differentiable in λ in a right neighborhood of 0.

We show below that this infinite differentiability result can also be extended to the more general functions of W considered here. In this sense, at least in this particular Cramer case, the expansion given in Theorem 1 is a Taylor type expansion.^{3}

The proof of this property is based on the notion of admissibility defined in [10], which is sufficient to grant (23) and (24).

In order to prove the admissibility of ψ, where ψ is the function defined in (53), we have to show that there exist constants K, N < ∞ and 1 < a < ∞, θ > 0, such that for all s < t < 0,

∫ ∫ |ψ(μ|^{t}, z) − ψ(μ|^{s}, z)| P_{λ}(dμ | C(l, j))Q(dz) ≤ K(j + l)^{N}a^{j+l}e^{−θt},  (74)

3We actually conjecture that this is always the case.

where C(l, j) = {μ′ : μ′([s, t)) = l, μ′([t, 0)) = j}. Let B^{i}(l, j) be the event

B^{i}(l, j) = { ⋂_{n=j+1}^{j+l} {d_{n}^{i} − t_{−n} < 0}} .  (75)

On B^{i}(l, j) ∩ (C(l, j) × K^{∞}), we have ψ(μ|^{t}, z) = ψ(μ|^{s}, z), so that

∫ ∫ |ψ(μ|^{t}, z) − ψ(μ|^{s}, z)| P_{λ}(dμ | C(l, j))Q(dz)
= ∫ ∫ |ψ(μ|^{t}, z) − ψ(μ|^{s}, z)| 1\overline{B^{i}(l,j)} P_{λ}(dμ | C(l, j))Q(dz) ≤ h^{\frac{1}{2}} g^{\frac{1}{2}} ,

where

h = ∫ ∫ (ψ(μ|^{t}, z) − ψ(μ|^{s}, z))^{2} P_{λ}(dμ | C(l, j))Q(dz)  (76)

and

g = IP (\overline{B^{i}(l, j)} | C(l, j) × K^{∞} ) .  (77)

Using now the special form of ψ and the independence assumptions, we obtain that

h ≤ 2 c IE [(D_{l+j}^{i})^{2ν} | C(l, j) × K^{∞} ] = 2 c IE [(D_{l+j}^{i})^{2ν}] .  (78)

Let χ_{n} = max_{i,j} {(A_{−n})_{i,j} + (B_{−n})_{j} ⊕ 0}. We have, for all n ≥ 1,

(D_{n}^{i})^{2ν} ≤ (∑_{p=1}^{n} χ_{p})^{2ν} ≤ n^{2ν} ∑_{p=1}^{n}(χ_{p})^{2ν}

and so h ≤ n^{2ν+1}κ, with κ = 2 c IE(χ_{1})^{2ν} = 2 c IE[(F_{1})^{2ν}] < ∞, where F_{n} is defined in (7).

As for h, we have

g = IP ( ⋃_{n=j+1}^{j+l} {D_{n}^{i} − T_{−n} > 0} | C(l, j) × K^{∞} )
≤ IP (D_{j+l}^{i} > t | C(l, j) × K^{∞} ) = IP (D_{j+l}^{i} > t)
= IP (e^{uD_{j+l}^{i}} > e^{ut}) ≤ IE [e^{uD_{j+l}^{i}}] e^{−ut}
≤ L_{u}ϕ(u)^{j+l}e^{−ut},

where u is any real number in the interval (0, θ^{∗}), and where we used Chebyshev’s inequality and Assumption (22) in order to derive the last two inequalities. Finally admissibility is proved with θ = \frac{u}{2}, a = (ϕ(u))^{\frac{1}{2}} , N = ν + 1 and K = \sqrt{κL_{u}}.

6 Calculation of the Coefficients

Now that we have seen that Theorem 2 can be applied to derive the expansion of IE[f(W^{i})], we will calculate the coefficients of λ^{k}. We will first give a recursive representation of these coefficients and will later on use this result to reveal their explicit form.

6.1 Recursion Formula

From Theorem 2 or from admissibility, we know that the coefficients of λ^{k} in the expansions are given by

IE[ ψ^{i}(o, {Z_{n}}) ] ,  ∫_{IR^{k}} IE[ ψ_{x_{1},...,x_{k}}^{i}(o, {Z_{n}}) ] d(x_{1}, …, x_{k}),  (79)

for k = 0, k ≥ 1, respectively, where ψ is the functional defined in (53). Introducing the notation q_{1}(d_{0}^{i}) = ψ^{i}(o, z) and

q_{k+1}(d_{0}^{i}, d_{1}^{i}, …, d_{k}^{i}) = ∫_{IR^{k}} ψ_{x_{1},...,x_{k}}^{i}(o, z) d(x_{1}, …, x_{k}),  (80)

for k ≥ 1, we obtain the following result.

Theorem 3 Under the monotonicity assumption (5) it holds for each i ∈ {1, …, α′} that q_{1}(d_{0}^{i}) = f(d_{0}^{i}) and

q_{k+1}(d_{0}^{i}, d_{1}^{i}, …, d_{k}^{i}) = ∑_{p=0}^{k−1} ∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} \{q_{k}(\underbrace{d_{0}^{i}, …, d_{0}^{i}}_{p}, d_{p+1}^{i} − u, …, d_{k}^{i} − u)
− q_{k}(\underbrace{d_{0}^{i}, …, d_{0}^{i}}_{p+1}, d_{p+1}^{i} − u, …, d_{k−1}^{i} − u)\} du,  (81)

for all k ≥ 1.

Proof From (53) it is immediate to see that

q_{1}(d_{0}^{i}) = ψ^{i}(o, {Z_{n}}) = f(d_{0}^{i}).

Using (45), (53) and (80) for k ≥ 1 we obtain

q_{k+1}(d_{0}^{i}, d_{1}^{i}, …, d_{k}^{i})

= ∫_{−∞}^{0} ∫_{x_{1}}^{0} … ∫_{x_{k−1}}^{0} ∑_{j=0}^{k}(−1)^{k−j} ∑_{π∈K_{k,j}} f(d_{0}^{i} ⊕ ⨁_{n=1}^{j}(d_{n}^{i} + x_{π_{(j+1−n)}})) dx_{k} … dx_{2} dx_{1},

= ∫_{0}^{∞} ∫_{s_{1}}^{∞} … ∫_{s_{k−1}}^{∞} ∑_{j=0}^{k}(−1)^{k−j} ∑_{π∈K_{k,j}} f(d_{0}^{i} ⊕ ⨁_{n=1}^{j}(d_{n}^{i} − s_{π_{(n)}})) ds_{k} … ds_{2} ds_{1},  (82)

where π_{(n)} denotes the n-th order statistic of π, i.e., the n-th smallest element of the j-tupel π ∈ K_{k,j}. The second equality is due to the substitution x_{j} → −x_{j}, j ∈ {1, …, k}, an interchange of the order of integration and finally by another substitution x_{j} → s_{k+1−j}, for all 1 ≤ j ≤ k.

As a next step, we decompose the outer integral in the following way:

∫_{0}^{∞} … = ∑_{p=0}^{k−1} ∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} … + ∫_{d_{k}^{i}−d_{0}^{i}}^{∞} … = ∑_{p=0}^{k−1} ∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} …  (83)

because from s_{1} ≤ … ≤ s_{k}, d_{0}^{i} ≤ … ≤ d_{k}^{i} and s_{1} ≥ d_{k}^{i} − d_{0}^{i} it follows that s_{m} ≥ s_{1} ≥ d_{k}^{i} − d_{0}^{i} ≥ d_{n}^{i} − d_{0}^{i} and therefore d_{n}^{i} − s_{m} ≤ d_{0}^{i} for all 1 ≤ m, n ≤ k. But this means that the integrand of the integral ranging from d_{k}^{i} − d_{0}^{i} to ∞ is equal to

∑_{j=0}^{k}(−1)^{k−j} ∑_{π∈K_{k,j}} f(d_{0}^{i}) = f(d_{0}^{i}) ∑_{j=0}^{k} \binom{k}{j}(−1)^{k−j} = 0.

For each of the remaining summands in (83), we decompose the summation according to

∑_{j=0}^{k}(−1)^{k−j} ∑_{π∈K_{k,j}} … = ∑_{j=1}^{k}(−1)^{k−j} ∑_{π∈K_{k,j},π∋1} … + ∑_{j=0}^{k−1}(−1)^{k−j} ∑_{π∈K_{k,j},π∌1} …,  (84)

where the dots are placeholders for the function f(·) given in (82).

We first consider that part of the integration involving only the first of these two sums, i.e., for 0 ≤ p ≤ k − 1,

∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} ∫_{s_{1}}^{∞} … ∫_{s_{k−1}}^{∞} ∑_{j=1}^{k}(−1)^{k−j} ∑_{π∈K_{k,j},π∋1} f(d_{0}^{i} ⊕ ⨁_{n=1}^{j}(d_{n}^{i} − s_{π_{(n)}})) ds_{k} … ds_{2} ds_{1}

= ∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} ∫_{s_{1}}^{∞} … ∫_{s_{k−1}}^{∞} ∑_{j=1}^{k}(−1)^{k−j} ∑_{π∈K_{k,j},π∋1} f(d_{0}^{i} ⊕ ⨁_{n=min{j,p}+1}^{j}(d_{n}^{i} − s_{π_{(n)}}))
ds_{k} … ds_{2} ds_{1}, (85)

because from s_{1} ≥ d_{p}^{i} − d_{0}^{i}, it follows that d_{n}^{i} − s_{π_{(n)}} ≤ d_{n}^{i} − s_{1} ≤ d_{p}^{i} − s_{1} ≤ d_{0}^{i}, for all 1 ≤ n ≤ p, and therefore, in particular, for all 1 ≤ n ≤ min{j, p}.

We will first consider the case p = 0. Because π ∋ 1, we see that s_{π_{(1)}} = s_{1}, and since in this case d_{1}^{i} − s_{1} ≥ d_{0}^{i} we get that (85) is equal to

∫_{0}^{d_{1}^{i}−d_{0}^{i}} ∫_{s_{1}}^{∞} … ∫_{s_{k−1}}^{∞} ∑_{j=1}^{k}(−1)^{k−j} ∑_{π∈K_{k,j},π∋1} f((d_{1}^{i} − s_{1}) ⊕ ⨁_{n=2}^{j}(d_{n}^{i} − s_{π_{(n)}})) ds_{k} … ds_{2} ds_{1}

= ∫_{0}^{d_{1}^{i}−d_{0}^{i}} ∫_{0}^{∞} ∫_{s_{2}}^{∞} … ∫_{s_{k−1}}^{∞} ∑_{j=0}^{k−1}(−1)^{k−1−j} ∑_{π∈K_{k,j+1},π∋1}f((d_{1}^{i} − u) ⊕ ⨁_{n=1}^{j}(d_{n+1}^{i} − u − s_{π_{(n+1)}}))
ds_{k} … ds_{3} ds_{2} du
= ∫_{0}^{d_{1}^{i}−d_{0}^{i}} ∫_{0}^{∞} ∫_{s_{1}}^{∞} … ∫_{s_{k−2}}^{∞} ∑_{j=0}^{k−1}(−1)^{k−1−j} ∑_{π∈K_{k−1,j}} f((d_{1}^{i} − u) ⊕ ⨁_{n=1}^{j}((d_{n+1}^{i} − u) − s_{π_{(n)}}))
ds_{k−1} … ds_{2} ds_{1} du
= ∫_{0}^{d_{1}^{i}−d_{0}^{i}} q_{k}(d_{1}^{i} − u, d_{2}^{i} − u, …, d_{k}^{i} − u) du,  (86)

where the first of the above equalities follows from the substitutions s_{1} → u, s_{n} → s_{n} − u for all 2 ≤ n ≤ k, j → j + 1 and n → n + 1. The last but one equality is a consequence of the substitution s_{n} → s_{n−1} for all n = 2, …, k. Now we come back to the remaining cases 1 ≤ p ≤ k − 1. Applying the transformations we just used for p = 0 yields

∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} ∫_{s_{1}}^{∞} … ∫_{s_{k−1}}^{∞} ∑_{j=1}^{k}(−1)^{k−j} ∑_{π∈K_{k,j},π∋1} f(d_{0}^{i} ⊕ ⨁_{n=min{j,p}+1}^{j}(d_{n}^{i} − s_{π_{(n)}})) ds_{k} … ds_{2} ds_{1}

= ∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} ∫_{0}^{∞} ∫_{s_{1}}^{∞} … ∫_{s_{k−2}}^{∞} ∑_{j=0}^{k−1}(−1)^{k−1−j} ∑_{π∈K_{k−1,j}}

f(d_{0}^{i} ⊕ ⨁_{n=1}^{min{j,p−1}}(d_{0}^{i} − s_{π_{(n)}}) ⊕ ⨁_{n=min{j,p−1}+1}^{j}(d_{n+1}^{i} − u − s_{π_{(n)}}))

ds_{k−1} … ds_{2} ds_{1} du

= ∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} q_{k}(\underbrace{d_{0}^{i}, …, d_{0}^{i}}_{p}, d_{p+1}^{i} − u, …, d_{k}^{i} − u) du,  (87)

for p = 1, …, k − 1. Aggregating (86) and (87), we obtain for (85)

∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} ∫_{s_{1}}^{∞} … ∫_{s_{k−1}}^{∞} ∑_{j=1}^{k}(−1)^{k−j} ∑_{π∈K_{k,j},π∋1} f(d_{0}^{i} ⊕ ⨁_{n=1}^{j}(d_{n}^{i} − s_{π_{(n)}})) ds_{k} … ds_{2} ds_{1}

= ∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} q_{k}(\underbrace{d_{0}^{i}, …, d_{0}^{i}}_{p}, d_{p+1}^{i} − u, …, d_{k}^{i} − u) du,  (88)

for all p = 0, …, k − 1. Using analogous reasoning for the remaining second part of the integration, we get

∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} ∫_{s_{1}}^{∞} … ∫_{s_{k−1}}^{∞} ∑_{j=0}^{k−1}(−1)^{k−j} ∑_{π∈K_{k,j},π∌1} f(d_{0}^{i} ⊕ ⨁_{n=1}^{j}(d_{n}^{i} − s_{π_{(n)}})) ds_{k} … ds_{2} ds_{1}

= − ∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} q_{k}(\underbrace{d_{0}^{i}, …, d_{0}^{i}}_{p+1}, d_{p+1}^{i} − u, …, d_{k−1}^{i} − u) du,  (89)

for all 0 ≤ p ≤ k − 1, and thus

q_{k+1}(d_{0}^{i}, d_{1}^{i}, …, d_{k}^{i}) = ∑_{p=0}^{k−1} ∫_{d_{p}^{i}−d_{0}^{i}}^{d_{p+1}^{i}−d_{0}^{i}} \{q_{k}(\underbrace{d_{0}^{i}, …, d_{0}^{i}}_{p}, d_{p+1}^{i} − u, …, d_{k}^{i} − u)

− q_{k}(\underbrace{d_{0}^{i}, …, d_{0}^{i}}_{p+1}, d_{p+1}^{i} − u, …, d_{k−1}^{i} − u)\} du,

which is the statement of Theorem 3.

6.2 Explicit Solution

In this section we want to derive the explicit representation (20) of the functions q_{k}(x_{0}, …, x_{k−1}), k ≥ 1, that show up in the calculation of the coefficients IE [q_{k+1}(D_{0}^{i}, …, D_{k}^{i})] of λ^{k} in the series expansion of IE [f(W^{i})] considered in Theorem 1.

Theorem 4 For k ≥ 1 and 0 ≤ x_{0} ≤ x_{1} ≤ … ≤ x_{k} a solution to the integral recursion equation (81) stated in Theorem 3 is given by the functions q_{k} outlined in Theorem 1, particularly in (20).

Proof We show (20) by induction with respect to k ≥ 1. Using (81) for k = 1 yields

q_{2}(x_{0}, x_{1}) = ∫_{0}^{x_{1}−x_{0}} {q_{1}(x_{1} − u) − q_{1}(x_{0})} du = ∫_{0}^{x_{1}−x_{0}} {f(x_{1} − u) − f(x_{0})} du
= [ − F (x_{1} − u) − f(x_{0})u ]_{0}^{x_{1}−x_{0}}
= (F (x_{1}) − F (x_{0})) − f(x_{0})[p_{1}(x_{1}) − p_{1}(x_{0})],

where we wrote F (x) for F^{[1]}(x) and thus, (20) holds for k = 1.

In the following k will always be assumed to be greater than one, i.e. k ≥ 2. Equation (81) can be rewritten in the form:

q_{k+1}(x_{0}, x_{1}, …, x_{k}) = ∑_{p=0}^{k−1} ∫_{x_{p}−x_{0}}^{x_{p+1}−x_{0}} q_{k}(\underbrace{x_{0}, …, x_{0}}_{p}, x_{p+1} − u, …, x_{k} − u) du  (90)

− ∑_{p=0}^{k−1} ∫_{x_{p}−x_{0}}^{x_{p+1}−x_{0}} q_{k}(\underbrace{x_{0}, …, x_{0}}_{p+1}, x_{p+1} − u, …, x_{k−1} − u) du.  (91)

In what follows, (90) and (91) will be evaluated separately.

Now let (20) be true for some natural k ≥ 2, i.e.

q_{k}(x_{1}, x_{2}, …, x_{k})

= ∑_{n=0}^{k−1} \binom{k − 1}{n}(−1)^{k−1−n}F^{[k−1]}(x_{n+1}) − ∑_{n=0}^{k−2} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}F^{[j]}(x_{n+1})
{p_{k−1−j}(x_{n+2}, …, x_{k−j+n}) − p_{k−1−j}(x_{n+1}, …, x_{k−j+n−1})}, (92)

for some k ≥ 2. Since the polynomials p_{n}(x_{0}, …, x_{n−1}) are translation-invariant with respect to a constant translation of all arguments, for n ≥ 2, and since p_{1}(x) = x implies p_{1}(x_{1} − u) − p_{1}(x_{0} − u) = p_{1}(x_{1}) − p_{1}(x_{0}), it follows that for p = 0

∫_{0}^{x_{1}−x_{0}} q_{k}(x_{1} − u, …, x_{k} − u) du

= ∑_{n=0}^{k−1} \binom{k − 1}{n}(−1)^{k−1−n} ∫_{0}^{x_{1}−x_{0}} F^{[k−1]}(x_{n+1} − u) du

− ∑_{n=0}^{k−2} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}\{p_{k−1−j}(x_{n+2}, …, x_{k−j+n})

− p_{k−1−j}(x_{n+1}, …, x_{k−j+n−1})} ∫_{0}^{x_{1}−x_{0}} F^{[j]}(x_{n+1} − u) du
= ∑_{n=0}^{k−1} \binom{k − 1}{n}(−1)^{k−1−n}(F^{[k]}(x_{n+1}) − F^{[k]}(x_{n+1} + x_{0} − x_{1}))  (93)

− ∑_{n=0}^{k−2} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}\{p_{k−1−j}(x_{n+2}, …, x_{k−j+n}) − p_{k−1−j}(x_{n+1}, …, x_{k−j+n−1})\}

(F^{[j+1]}(x_{n+1}) − F^{[j+1]}(x_{n+1} + x_{0} − x_{1})). (94)

For 1 ≤ p ≤ k − 1 the integrand is given by:

q_{k}(\underbrace{x_{0}, …, x_{0}}_{p}, x_{p+1} − u, …, x_{k} − u)

= ∑_{n=0}^{p−1} \binom{k − 1}{n}(−1)^{k−1−n}F^{[k−1]}(x_{0}) + ∑_{n=p}^{k−1} \binom{k − 1}{n}(−1)^{k−1−n}F^{[k−1]}(x_{n+1} − u)

− ∑_{n=0}^{p−1} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}F^{[j]}(x_{0})\{p_{k−1−j}(\underbrace{x_{0}, …, x_{0}}_{p−n−1}, x_{p+1} − u, …, x_{k−j+n} − u)

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

− ∑_{n=p}^{k−2} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}F^{[j]}(x_{n+1} − u)\{p_{k−1−j}(x_{n+2} − u, …, x_{k−j+n} − u)

− p_{k−1−j}(x_{n+1} − u, …, x_{k−j+n−1} − u)},

and therefore, if we use the translation-invariance property (18) of the polynomials p_{n} to shift all arguments by u and then substitute x_{0} + u → v, we see that

∫_{x_{p}−x_{0}}^{x_{p+1}−x_{0}} q_{k}(\underbrace{x_{0}, …, x_{0}}_{p}, x_{p+1} − u, …, x_{k} − u) du

= ∑_{n=0}^{p−1} \binom{k − 1}{n}(−1)^{k−1−n}F^{[k−1]}(x_{0})\{p_{1}(x_{p+1}) − p_{1}(x_{p})\}  (95)
+ ∑_{n=p}^{k−1} \binom{k − 1}{n}(−1)^{k−1−n}\{F^{[k]}(x_{n+1} + x_{0} − x_{p}) − F^{[k]}(x_{n+1} + x_{0} − x_{p+1})\}  (96)

− ∑_{n=0}^{p−1} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}F^{[j]}(x_{0}) ∫_{x_{p}}^{x_{p+1}} \{p_{k−1−j}(\underbrace{v, …, v}_{p−n−1}, x_{p+1}, …, x_{k−j+n})

− p_{k−1−j}(\underbrace{v, …, v}_{p−n}, x_{p+1}, …, x_{k−j+n−1})\} dv  (97)

− ∑_{n=p}^{k−2} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}\{F^{[j+1]}(x_{n+1} + x_{0} − x_{p}) − F^{[j+1]}(x_{n+1} + x_{0} − x_{p+1})\}

{p_{k−1−j}(x_{n+2}, …, x_{k−j+n}) − p_{k−1−j}(x_{n+1}, …, x_{k−j+n−1})}  (98)
= I_{p} + II_{p} + III_{p} + IV_{p},

for 1 ≤ p ≤ k − 1, where I_{p}, II_{p}, III_{p} and IV_{p} are shorthand notations for the expressions given by (95), (96), (97) and (98), respectively. So we see that (90) can be represented as the sum of the terms given by (93) and (94) as well as the expressions just introduced for 1 ≤ p ≤ k − 1 above. We will now continue by summing up these terms in the following way:

∑_{p=1}^{k−1} I_{p} = F^{[k−1]}(x_{0}) ∑_{n=0}^{k−2} \binom{k − 1}{n}(−1)^{k−1−n} ∑_{p=n}^{k−2} \{p_{1}(x_{p+2}) − p_{1}(x_{p+1})\}

= −F^{[k−1]}(x_{0}) ∑_{n=0}^{k−1} \binom{k − 1}{n}(−1)^{k−1−n}p_{1}(x_{n+1}),  (99)

where we substituted p → p + 1 and then interchanged the order of summation to get the first equality. The last line was obtained after calculating the telescope-sum, splitting up the result into two summations and using the fact that

∑_{n=0}^{k−2} \binom{k − 1}{n}(−1)^{k−1−n} = −1.

If we compare (93) to (96) we notice that (93) can just as well be interpreted as a II_{0}. Thus, a substitution n → n − 1 and similar calculations as before yield

∑_{p=0}^{k−1} II_{p} = ∑_{n=1}^{k} \binom{k − 1}{n − 1}(−1)^{k−n} ∑_{p=0}^{n−1} \{F^{[k]}(x_{n} + x_{0} − x_{p}) − F^{[k]}(x_{n} + x_{0} − x_{p+1})\}

= ∑_{n=1}^{k} \binom{k − 1}{n − 1}(−1)^{k−n}F^{[k]}(x_{n}),  (100)

as well as

∑_{p=1}^{k−1} III_{p} = − ∑_{n=0}^{k−2} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}F^{[j]}(x_{0}) ∑_{p=n}^{k−2} ∫_{x_{p+1}}^{x_{p+2}} \{p_{k−1−j}(\underbrace{v, …, v}_{p−n}, x_{p+2}, …, x_{k−j+n})

− p_{k−1−j}(\underbrace{v, …, v}_{p−n+1}, x_{p+2}, …, x_{k−j+n−1})\} dv

= − ∑_{n=0}^{k−2} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}F^{[j]}(x_{0})p_{k−j}(x_{n+1}, …, x_{k−j+n}).  (101)

The second equality holds because the polynomials p_{k−1−j} cancel out whenever p−n ≥ k −1−j or, equivalently, if p ≥ k − 1 − j + n, and therefore

∑_{p=n}^{k−2} ∫_{x_{p+1}}^{x_{p+2}} \{p_{k−1−j}(\underbrace{v, …, v}_{p−n}, x_{p+2}, …, x_{k−j+n}) − p_{k−1−j}(\underbrace{v, …, v}_{p−n+1}, x_{p+2}, …, x_{k−j+n−1})\} dv

= ∑_{p=n}^{k−2−j+n} ∫_{x_{p+1}}^{x_{p+2}} \{p_{k−1−j}(\underbrace{v, …, v}_{p−n}, x_{p+2}, …, x_{k−j+n})

− p_{k−1−j}(\underbrace{v, …, v}_{p−n+1}, x_{p+2}, …, x_{k−j+n−1})\} dv

= ∑_{p=0}^{k−2−j} ∫_{x_{p+n+1}}^{x_{p+n+2}} \{p_{k−1−j}(\underbrace{v, …, v}_{p}, x_{p+n+2}, …, x_{k−j+n})

− p_{k−1−j}(\underbrace{v, …, v}_{p+1}, x_{p+n+2}, …, x_{k−j+n−1})\} dv

= p_{k−j}(x_{n+1}, …, x_{k−j+n}),

where the last equality follows from (19).

It can be seen that the IV_{p}’s show up only for 1 ≤ p ≤ k − 2. Similarly as we did for the II_{p}’s above, we realize that (94) can be interpreted as a IV_{0}. So we include this term in the summation of the IV_{p}’s and obtain

∑_{p=0}^{k−1} IV_{p} = − ∑_{n=0}^{k−2} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n} ∑_{p=0}^{n} \{F^{[j+1]}(x_{n+1} + x_{0} − x_{p}) − F^{[j+1]}(x_{n+1} + x_{0} − x_{p+1})\}
{p_{k−1−j}(x_{n+2}, …, x_{k−j+n}) − p_{k−1−j}(x_{n+1}, …, x_{k−j+n−1})}
= − ∑_{n=1}^{k−1} ∑_{j=n}^{k−1} \binom{j − 1}{n − 1}(−1)^{j−n}\{F^{[j]}(x_{n}) − F^{[j]}(x_{0})\}
{p_{k−j}(x_{n+1}, …, x_{k−j+n}) − p_{k−j}(x_{n}, …, x_{k−j+n−1})}. (102)

We can approach term (91) in an almost identical way. For p = k − 1 we obtain

q_{k}(\underbrace{x_{0}, …, x_{0}}_{k}) = F^{[k−1]}(x_{0}) ∑_{n=0}^{k−1} \binom{k − 1}{n}(−1)^{k−1−n} − ∑_{n=0}^{k−2} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}F^{[j]}(x_{0})
{p_{k−1−j}(x_{0}, …, x_{0}) − p_{k−1−j}(x_{0}, …, x_{0})}
= 0,

and for p = 0, …, k − 2

∫_{x_{p}−x_{0}}^{x_{p+1}−x_{0}} q_{k}(\underbrace{x_{0}, …, x_{0}}_{p+1}, x_{p+1} − u, …, x_{k−1} − u) du

= ∑_{n=0}^{p} \binom{k − 1}{n}(−1)^{k−1−n}F^{[k−1]}(x_{0})\{p_{1}(x_{p+1}) − p_{1}(x_{p})\}  (103)

+ ∑_{n=p+1}^{k−1} \binom{k − 1}{n}(−1)^{k−1−n}\{F^{[k]}(x_{n} + x_{0} − x_{p}) − F^{[k]}(x_{n} + x_{0} − x_{p+1})\}  (104)

− ∑_{n=0}^{p} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}F^{[j]}(x_{0}) ∫_{x_{p}}^{x_{p+1}} \{p_{k−1−j}(\underbrace{v, …, v}_{p−n}, x_{p+1}, …, x_{k−j+n−1})

− p_{k−1−j}(\underbrace{v, …, v}_{p−n+1}, x_{p+1}, …, x_{k−j+n−2})\} du (105)

− ∑_{n=p+1}^{k−2} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}\{F^{[j+1]}(x_{n} + x_{0} − x_{p}) − F^{[j+1]}(x_{n} + x_{0} − x_{p+1})\}

{p_{k−1−j}(x_{n+1}, …, x_{k−j+n−1}) − p_{k−1−j}(x_{n}, …, x_{k−j+n−2})} (106)
= i_{p} + ii_{p} + iii_{p} + iv_{p},

with i_{p}, ii_{p}, iii_{p} and iv_{p} representing expression (103), (104), (105) and (106), respectively. Using similar calculations as before we get the following expressions for the summations of the different terms:

∑_{p=0}^{k−2} i_{p} = −F^{[k−1]}(x_{0}) ∑_{n=0}^{k−1} \binom{k − 1}{n}(−1)^{k−1−n}p_{1}(x_{n}),  (107)

∑_{p=0}^{k−2} ii_{p} = − ∑_{n=0}^{k−1} \binom{k − 1}{n}(−1)^{k−n}F^{[k]}(x_{n}),  (108)

∑_{p=0}^{k−2} iii_{p} = − ∑_{n=0}^{k−2} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}F^{[j]}(x_{0}) p_{k−j}(x_{n}, …, x_{k−j+n−1}),  (109)

∑_{p=0}^{k−2} iv_{p} = ∑_{n=1}^{k−2} ∑_{j=n+1}^{k−1} \binom{j − 1}{n}(−1)^{j−n}\{F^{[j]}(x_{n}) − F^{[j]}(x_{0})\}
{p_{k−j}(x_{n+1}, …, x_{k−j+n}) − p_{k−j}(x_{n}, …, x_{k−j+n−1})}. (110)

So we know that q_{k+1}(x_{0}, x_{1}, …, x_{k}) for k ≥ 1 is given by the sum of (99), (100), (101) and (102), subtracted by the sum of (107), (108), (109) and (110). To continue we evaluate the following differences:

∑_{p=1}^{k−1} I_{p} − ∑_{p=0}^{k−2} i_{p} = − ∑_{n=0}^{k−1} \binom{k − 1}{n}(−1)^{k−1−n}F^{[k−1]}(x_{0})\{p_{1}(x_{n+1}) − p_{1}(x_{n})\},  (111)

whereas

∑_{p=0}^{k−1} II_{p} − ∑_{p=0}^{k−2} ii_{p} = F^{[k]}(x_{k}) + ∑_{n=1}^{k−1} \{\binom{k − 1}{n − 1} + \binom{k − 1}{n}\} (−1)^{k−n}F^{[k]}(x_{n})
+ (−1)^{k}F^{[k]}(x_{0})
= ∑_{n=0}^{k} \binom{k}{n}(−1)^{k−n}F^{[k]}(x_{n}),  (112)

since \binom{k−1}{n−1} + \binom{k−1}{n} = \binom{k}{n}. Furthermore,

∑_{p=1}^{k−1} III_{p} − ∑_{p=0}^{k−2} iii_{p} = − ∑_{n=0}^{k−2} ∑_{j=n}^{k−2} \binom{j}{n}(−1)^{j−n}F^{[j]}(x_{0}) \{ p_{k−j}(x_{n+1}, …, x_{k−j+n})

− p_{k−j}(x_{n}, …, x_{k−j+n−1}) } (113)

and

∑_{p=0}^{k−2} IV_{p} − ∑_{p=0}^{k−2} iv_{p} = − ∑_{n=0}^{k−1} ∑_{j=n}^{k−1} \binom{j}{n}(−1)^{j−n}\{F^{[j]}(x_{n}) − F^{[j]}(x_{0})\}
{p_{k−j}(x_{n+1}, …, x_{k−j+n}) − p_{k−j}(x_{n}, …, x_{k−j+n−1})},  (114)

where we extended the summation to start from n = 0 instead of n = 1. This does not change the overall value of (114) as all these additional terms cancel out.

Looking at the sum of (111) and (113), we realize that the result is just equal to the negative of the part of (114) involving F^{[j]}(x_{0}), i.e. these parts cancel out when summed up. Thus, we are left with (112) and the remaining part of (114), and we eventually obtain that

q_{k+1}(x_{0}, x_{1}, …, x_{k}) = ∑_{n=0}^{k} \binom{k}{n}(−1)^{k−n}F^{[k]}(x_{n}) − ∑_{n=0}^{k−1} ∑_{j=n}^{k−1} \binom{j}{n}(−1)^{j−n}F^{[j]}(x_{n})
{p_{k−j}(x_{n+1}, …, x_{k−j+n}) − p_{k−j}(x_{n}, …, x_{k−j+n−1})},

which is the statement of Theorem 4.

References

[1] Asmussen, S. (1987) Applied Probability and Queues. J. Wiley & Sons, Chichester.

[2] Baccelli, F., Cohen, G., Olsder, G.J. and J.P. Quadrat (1992) Synchronization and Linearity. J. Wiley & Sons, Chichester.

[3] Baccelli, F. and V. Schmidt (1996) Taylor Series Expansions for Poisson Driven (max,+)– Linear Systems. Ann. Appl. Probab. (to appear)

[4] Baccelli, F. and V. Schmidt (1995) Expansions for conditional expectation of steady state variables in (max,+)–linear systems. Preprint. INRIA Sophia / Universität Ulm.

[5] Błaszczyszyn, B. (1995) Factorial moment expansion for stochastic systems. Stoch. Proc. Appl. 56, 321–335.

[6] Błaszczyszyn, B., Frey, A. and V. Schmidt (1995) Light-traffic approximations for Markovmodulated multi-server queues. Stochastic Models 11, 423–445.

[7] Błaszczyszyn, B. and T. Rolski (1995) Expansions for Markov-modulated systems and approximations of ruin probability. J. Appl. Probab. 32 (to appear)

[8] Frey, A. and V. Schmidt (1996) Taylor-series expansion for multivariate characteristics of risk processes. Insurance: Mathematics and Economics (to appear)

[9] Kroese, D.P. and V. Schmidt (1996) Light-traffic analysis for queues with spatially distributed arrivals. Math. Oper. Res. (to appear)

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