2. ORDERINGS

We give definitions of needed integral orderings and classes of functions defining these orderings. It is standard to denote by cx and cv respectively the class of convex and concave functions

. For multivariable functions, we have the following fundamental notion.

Definition 2.1: A function

is said to be supermodular (sm) if for any x and

,

where the operators ∧ and ∨ denote respectively coordinatewise minimum and maximum.

A suitable extensions of cx and cv classes for the multivariate case are as follows.

Definition 2.2: A function

is said to be directionally convex (dcx) (directionally concave or [dcv]) if for any

such that for x₁ ≤ x₂ and y ≥ 0,

We write “i” before “sm,” “dcx,” or “dcv” for restrictions to increasing functions. Note also that the directional convexity is not the same as ordinary convexity. Important properties of dcx and dcv functions are as follows. If f is dcx (dcv) and twice differentiable, then ∂²f (x)/∂x_i ∂x_j ≥ (≤) 0 for all i and j. Note that for sm, we have only ∂²f (x)/∂x_i ∂x_j ≥ (≤) 0 for all i ≠ j. More on sm and dcx functions can be found in Müller and Stoyan [9]. Functions dcv and idcv appeared in the doctoral thesis of Meester [6]. It was pointed out there that the composition

of an icv function f with idcv function d on

is also an idcv function of y [6, Lemma2.2.6]. Note that f (x) is idcx if and only if −f (−x) is idcv. We will use the fact that idcx functions form a cone (see, e.g., [9]).

To each class of the above-considered functions we relate the stochastic ordering, which in the terminology of Müller and Stoyan [9] are integral orderings. Let

be a class of functions like cx, icx, cv, icv, sm, ism, dcx, idcx, dcv, and idcv. We say that two random vectors (in the case of cx, icx, cv, and icv random variables) X and Y are

-ordered if E[f (X)] ≤ E[f (Y)] for any function

, such that the expectations are finite. In this way, we define orderings ≤_icx, ≤_ism, ≤_idcx, ≤_icv, and ≤_idcv used in this note. For ordering of stochastic processes, we have the following definition.

Definition 2.3:

1. For two

-valued stochastic processes

, we say that

is smaller than

in the

-ordering and write

, if for any positive integer k and any

.

2. Let

be two increasing stochastic processes defining random measures dC(t) and dC′(t), respectively. It is said that

, or

, if for any k and 0 ≤ s₁ ≤ t₁ ≤ s₂ ≤ t₂ ≤…≤ s_k ≤ t_k,

3. We say that a stationary stochastic process {Y_t}_t∈T, where

is ≤_idcv-regular (≤_idcx-regular) if for each k and all idcv functions

, function φ, defined by

We first recall that from the Lorenz inequality (see, e.g., [9]), we have the following lemma.

Lemma 2.4: If Z₀ =_st Z₁ =_st···=_st Z_n, then (Z₀,…,Z_k) ≤_sm (Z₀,…,Z₀).

The notion of ≤_idcx-regularity, also called monotonicity in lag, was studied in Miyoshi and Rolski [8]. For later use, we need the following quite obvious lemma.

Lemma 2.5: If a stationary process ξ(t) is ≤_idcv-regular, then for a monotone function f, the process f (ξ(t)) is ≤_idcv-regular.

3. GENERAL FRAMEWORK

Let M(t) and {C(t)} be two increasing processes with stationary increments such that M(0) = 0 and C(0) = 0 and let

. Our aim is to study bounds and comparison theorems for

or

We have the following representations for V:

where I_i,k = ((k − 1)/2ⁱ, k/2ⁱ] for k = 1,…,i2ⁱ and

conventionally. We have

where I_i,k^T = ((k − 1)(T/2ⁱ),k(T/2ⁱ)] for k = 1,…,2ⁱ, and X, M, and C are independent.

Let

be icx, which is also assumed to be continuous on the whole

. Similarly to Lemma 1 of [12], we have from the monotone convergence theorem and the continuity of f,

where g_k(x) = max{0,x₁,…,x₁ + ··· + x_k} for

. Similarly, we can represent f (V_T) by the use of functions x → max{0,y + x₁ +···+ x_k,x₂ +···+ x_k,…,x₁}. The above functions are idcx.

As in Lemma 2 of [12], g_k(x) is idcx (and, moreover, it is a convex function too). Furthermore,

is an idcv function of y. This can be justified as follows. The composition

of an icx function f with an idcx function g_k on

is also an idcx function of

[6, Lemma2.2.6]. Therefore,

is idcv. Hence, we have the following lemma.

Lemma 3.1: Let f be icx. Then

is idcv and, hence, −ψ_k(y₁,…,y_k) is a decreasing sm function.

Further, to a given process {C(t)}, we now associate two increasing processes {C′(t)} and {C′′(t)} defined as follows:

• C′(dt) = γ dt.
• C′′(dt) = c(0) dt, provided dC(t) is absolute continuous and c(t) is a stationary nonnegative process, called an intensity process. We always assume that intensity processes have Riemann integrable sample paths.

For further reference, we state the following lemma without proof.

Lemma 3.2: If φ is sm of k variables, then the function

of l₁ ×···× l_k variables

is sm, provided all c_ij are positive numbers.

Lemma 3.3: We have for an sm function φ,

where I₁,…,I_k are finite intervals. Hence, for an idcv function φ,

Proof: For the proof we have to use the following facts: ≤_sm-order is generated by continuous nonnegative sm functions [9, Thm.3.9.13]; hence, for a continuous sm function φ, we have the convergence in distribution of

By Lemma 3.2, φ([sum ]_{j: j/n∈I1} c(j/n)/n,…,[sum ]_{j: j/n∈Ik} c(j/n)/n) can be considered an sm function of variables c(j/n). From the Lorentz inequality

Hence,

Hence, we can say that −f (V(∞;C)) and −f (V(T;C)) are idcv representable; that is, their expectations are limits of functions, as in Lemma 3.3.

In the next proposition, we consider three stochastic functionals: V(T;C) as defined in (3.1),

and

Similarly, we define V(T;C), V(T;C′), and V(T;C′′).

In point (iv) of Proposition 3.4, we assume that C(dt) = c(t) dt admits an intensity process c(t) and consider a family of random variables V(T;C_a) defined by random measures C_a(dt) = c_a(t) dt, where a > 0, admitting an intensity process c_a(t) respectively defined by c_a(t) = c(at), where {c(t)} is the intensity process of some random measure C. Similarly to [9], we can prove the following a monotonicity of V(T;C_a) with respect to a > 0. In Proposition 3.4, T is finite or infinite and it is tacitly assumed that all stochastic functionals V are proper random variables.

Proposition 3.4:

Proof:

which yields

(iv) In view of (3.6) and Lemma 3.1, it suffices to demonstrate that for an idcv function

is decreasing in a > 0. Without loss of generality, we can assume that intervals I are of forms I_k = [a_i,b_i), where a₁ = 0 and b_i = a_i+1. Then, for each n = 1,2,…, we define the function

Hence,

is increasing in a > 0 because c(t) is assumed to be idcv-regular and

is idcv. █

4. EXAMPLES

In this section, we show two applications of the theory to single-server queues with Poisson arrivals.

4.1. M/G/1 Queue with Varying Instantaneous Service Speed

Let {N(t)} be the Poisson process with rate λ > 0, {S_i} a sequence of nonnegative independent and identically distributed (i.i.d.) random variables (r.v.'s). We denote by

the cumulative service requirement arriving within interval (s,t] .

Suppose now that the service rate is given by a process c*(t), where 0 ≤ c*(t) ≤ 1 for all t. We assume that c*(t) is stationary (and ergodic) and that {N(t)}, {S_i}, and {c*(t)} are independent.

Let V(t) = V(t;C*) be a stochastic process defined by

The solution of (4.1) is

The process {V(t)} represents the workload at time t in the work-conserving single-server queues with varying instantaneous service speed. Since we wish to study the stationary workload, without loss of generality we can assume V(0−) = 0. Otherwise, we have to assume that V(−0) is independent of (M,C). Then

and, hence, the stationary workload

where c(t) = c*(−t). The above is well defined for

. Note that V(∞;C′) is the workload in the standard M/G/1 system, with arrival rate λ/γ and service time distribution B. Under the condition that C(dt) = c(t) dt admits stationary intensity and

a.s., we consider

Note that the above is the workload in the M/G/1 system, with arrival rate λ/c(0) and service time distribution B, of course provided

a.s. Unfortunately, in many cases, the latter assumption is a difficult requirement.

Proposition 4.1: If T is finite or infinite and

, then

and if T is finite or infinite and

a.s., then

Furthermore,

and under the assumption that

a.s.,

Proof: The first part follows directly from Proposition 3.4. For the second part, we use that in the standard M/G/1 queue with arrival rate λ and generic service time S, the mean workload is

. █

Consider now a preemptive resume priority M/G/1 system with two types of customers: low and high priority. Customers of the low (high) priority arrive at the system according to the Poisson process with rate λ_l (λ_h) and with i.i.d. service times with distribution B_l (B_h). Then, the workload process for low-priority customers is the workload process in the M/G/1 system with instantaneous service speed

Thus, c*(t) is an on–off process with on and off times being distributed as in the busy and idle periods, respectively, in the M/G/1 system with arrival rate λ_h and service time distribution B_h. Now, γ is the stationary probability of no high-priority customers. Let V^l be the steady-state workload for the low-priority customers.

Corollary 4.2:

Proof: Use Eq. (4.3) and Proposition 3.4. █

We can also ask for the monotonicity of V(T;C_a) with respect to a > 0. In this case, we must know the answer for the following question.

Question: Is the stationary workload process V(t) in the M/G/1 system ≤_idcx-regular or ≤_idcv-regular? From this, we would have that

has the same property.

4.2. Queues with Positive and Negative Customers

Two types of customer are arriving at the system: according to a Poisson process with rate λ⁺ i.i.d. customers with service times {S_i⁺} (so-called positive ones), and according to a Poisson process with rate λ⁻ i.i.d. customers with service times {S_i⁻} (so-called negative). The system works as follows. As earlier, we assume a work-conserving discipline. Negative customers require no service, but at their arrival, a stochastic work is instantly removed from the system. Such systems were introduced by Gelenbe [5] and subsequently studied by Boucherie, Boxma, and Sigman [3], among others. In this later system, it was demonstrated the stationary workload is

where

Proposition 4.3:

Proof: From Proposition 3.4. █

To use Proposition 3.4(iii), we have to derive a criterion for an idcv comparison of stochastic processes like (4.4).

Proposition 4.4: If S_j^−′ ≤_icv S_j^−′′ and λ^−′ ≤ λ^−′′, then dC′ ≤_idcv dC′′. Hence, V(C′) ≥_icx V(C′′).

Proof: The first part is analogous to the proof of Lemma 4 from Rolski [12]. █