2.1. Functions with Isotone Differences and Related Orderings

Assume that E_i, i = 1,…, n, are lattice ordered Polish spaces with Borel σ-algebra

and a closed partial ordering [pr ]_i. Then (E⁽ⁿ⁾,[pr ]⁽ⁿ⁾) is a lattice and, hence, for any x,y ∈ E⁽ⁿ⁾, there exists a unique largest lower bound x ∧ y ∈ E⁽ⁿ⁾ and a smallest upper bound x ∨ y ∈ E⁽ⁿ⁾. In this article we use the following particular cases:

(i) Let

for i = 1,…, n, with ≤ the standard linear order in

. Then for x = (x₁,…, x_n),y = (y₁,…, y_n) ∈ Eⁿ, we have x ∧ y = (x₁ ∧ y₁,…, x_n ∧ y_n) and x ∨ y = (x₁ ∨ y₁,…, x_n ∨ y_n) with x_i ∧ y_i = min{x_i,y_i}, i = 1,…, n, and x_i ∨ y_i = max{x_i,y_i}, i = 1,…, n.

(ii) Let

be its power set. Taking

, with ⊆ being inclusion ordering, we have for A_i,B_i ∈ E_i that A_i ∧ B_i = A_i ∩ B_i and A_i ∨ B_i = A_i ∪ B_i, i = 1,…, n. It is clear that (E,⊆) and (Eⁿ,⊆ⁿ) are lattices.

We denote by

the set of all real-valued [pr ] -increasing (decreasing) functions on

. Moreover, by

we denote the class of all real-valued supermodular functions on E⁽ⁿ⁾ as defined by Eq. (1.1). Related to this class is the class of functions with isotone differences, defined by Eq. (1.2). We denote this class by

. Note that the definition of a function with isotone differences does not require that E_i be lattices. If, additionally, f is taken to be increasing, we write

. If it is clear which space and which ordering we mean, we omit (E⁽ⁿ⁾,[pr ]⁽ⁿ⁾) in these notations. The following lemma (for a proof, see Heyman and Sobel [8, Thm.8-1, p.375]) implies that in the case of totally ordered spaces, both notions coincide. This is not the case when E_i, i = 1,…,n, are only partially ordered lattices.

Lemma 2.1:

For

classes it is easy to prove preservation results that are parallel to the totally ordered case (cf. Müller and Stoyan [14, Thm.3.9.3]); see [3] for a list of such properties. In particular, we have the following lemma.

Lemma 2.2: Let

and assume that E_i, i = 1,…, n, are partially ordered.

(i) If

are [pr ]_i-increasing, then

.

(ii) If

are nonnegative, then

. In particular, if

with nonnegative values, then for fg defined on E⁽²⁾ = E₁ × E₂ by (fg)(x,y) = f (x)g(y) for x ∈ E₁,y ∈ E₂ holds

. Further, for nonnegative

holds.

The following example shows, however, that increasing transformations do not preserve supermodularity and a product of increasing functions need not to be supermodular on lattice ordered spaces that are not totally ordered.

Example 2.1: Let E₁ = E₂ = {{0},{0,1},{0,2},{0,1,2}} with standard ordering [pr ]:=⊆. Define g({0}) = {0,1}, g({0,1}) = g({0,2}) = g({0,1,2}) = {0,1,2}, and h(B) = B for each B ∈ E₁. Both functions are increasing. The function

for C = {0,1,2} is supermodular on (E⁽²⁾,[pr ]⁽²⁾). Define

. The function

is not supermodular. Indeed, for A₁ = {0,1}, A₂ = {0,2}, and B₁ = B₂ = {0,1,2}, we have

In the above setting, a sufficient condition for

to be supermodular is k(A₁) ∩ k(A₂) = k(A₁ ∩ A₂) for both k = h and k = g. This is not the case here. Moreover, since

is a product of increasing functions not being supermodular. However, using Lemma 2.2(ii),

has isotone differences. Therefore, we also showed that there exists a function that has isotone differences but is not supermodular.

From the above example it follows that supermodular ordering on lattice ordered state spaces in general is not preserved under increasing transformations. Therefore, the class of supermodular functions is restrictive in the study of dependence orderings of random processes on general partially ordered spaces. Hence, we limit our investigations to functions with isotone differences and we call the corresponding ordering the isotone differences ordering.

Definition 2.1: Let

be random vectors with values in

.

(i) Y is smaller than

in the isotone differences ordering

if

for all

such that both expectations exist.

(ii) Let

, be stochastic processes. Then we write

if for all n ≥ 2 and all t₁ < ··· < t_n ∈ T we have

.

For simplicity, we skip ([pr ]⁽ⁿ⁾) in the above notations if it is clear which orderings are used. We also skip the necessary assumption that the expectations exist in statements similar to the above.

2.2. Continuous-Time Markov Chains

Let

be stationary homogeneous continuous-time Markov processes with a countable lattice ordered state space

and transition kernel families

, respectively.

are transition families for the time-reversed processes.

are the corresponding infinitesimal generators. We always assume that all processes are uniform (i.e., their generators are bounded and conservative).

A transition kernel family

is [pr ]-monotone if all the P_t are [pr ]-monotone. Recall that a transition kernel P_t is [pr ]-monotone if the map x → ∫_E P_t(x,dy) f (y) is [pr ]-increasing provided f is [pr ]-increasing. From now on we assume that either

are families of [pr ]-monotone kernels (and refer to this property as to the monotonicity assumption).

The proof of the characterization theorem needs the following property of the isotone differences order, which is proved in [3, Lemma2.7]; see [14, Lemma5.2.17] for supermodular order on totally ordered spaces.

Lemma 2.3: Assume that kernel P_t is [pr ]-monotone and f has isotone differences on (Eⁿ⁺¹,[pr ]ⁿ⁺¹). Then a function

defined by

has isotone differences on (Eⁿ,[pr ]ⁿ).

Using Lemma 2.3, the proof of the characterization theorem follows the same arguments as Theorem 3.6 in Daduna and Szekli [5] for concordance ordering.

Theorem 2.1: Under the above assumptions (recall especially the monotonicity assumption) the following properties are equivalent:

(i)

.

(ii)

for all t ≥ 0.

(iii) For any

, we have

2.3. ε Transformation

Consider a stationary Markov process Y with intensities q^Y(x,y) and stationary distribution π. For x₁ [pr ] x₂, y₁ [pr ] y₂, and fixed ε > 0 such that the quantities in Eq. (2.2) define a new intensity matrix of a Markov process

(called the ε transformation of Y) set

Both Markov processes

and Y have the same stationary distribution (see Lemma 2.4). Furthermore,

is more likely to stay in the same state compared to Y. Thus,

has a longer memory and intuitively should be greater than Y according to suitably defined dependence orderings. This will be proved in Proposition 2.1.

Lemma 2.4: The Markov processes

with the transition intensities given by Eq. (2.2) have equal invariant distribution π.

Proof: For the intensity matrix of Y, we have πQ^Y = 0, where 0 is the null vector. It means that for any y ∈ E, we have

Now, for y ≠ y₁,y₂, we have

Moreover, for y = y₁,

It follows analogously that

. █

Proposition 2.1: Consider Markov processes

(with intensities given by Eq. (2.2)). Under the monotonicity assumption,

.

Proof: From Theorem 2.1 it is sufficient to prove that for all

,

holds. The difference between the left-hand side and the right-hand side is

being nonnegative due to the assumptions on f. █

3.1. Degradable Jackson Networks with Unreliable Nodes and Repair

Consider a Jackson network of J numbered nodes, denoted by J = {1,…, J}. Station j ∈ J, is a single-server queue with infinite waiting room under the first come–first served (FCFS) regime. Indistinguishable customers arrive in a Poisson stream with intensity λ > 0 and are sent to node j with probability r_0j, and

. r₀₀ := 1 − r is the rejection probability for customers at their arrival. Customers arriving at node j from the outside or from other nodes request a service that is exponentially distributed with mean 1. Service at node j is provided with intensity μ_j > 0. We denote by n_j the number of customers at node j, including the one being served. All service times and arrival processes are assumed to be independent.

A customer departing from node j immediately proceeds to node i with probability r_ji ≥ 0 or departs from the network with probability r_j0. The routing is independent of the past of the system given the momentary node where the customer is. Let J₀ := J ∪ {0}. We assume that the matrix R := (r_ij,i,j ∈ J₀) is aperiodic and irreducible.

The servers at the nodes in the Jackson network are unreliable; that is, the nodes might break down. Nodes might break down as an isolated event or in groups simultaneously; repair of nodes might end for each node individually or in groups as well. Nodes that broke down simultaneously need not return to service at the same time. We assume that the breakdown occurs independent of the load (queue lengths) of the nodes and that the repair is independent of the queue lengths as well. For more general behavior, we refer to Sauer and Daduna [15].

The control of breakdowns and repairs is as follows: Let I ⊂ J be the set of nodes in down status and H ⊂ J[setmn ]I, H ≠ [empty ], be some subset of nodes in up status. Then the nodes of H break down concurrently with intensity α(I,I ∪ H).

Nodes in down status neither accept new customers nor continue serving the old customers who will wait for the server's return. Therefore, the routing has to be changed so that customers waiting to join a node in down status are rerouted to nodes in up status or to the outside. We will give three rerouting schemes below. These originate from mechanisms applied (e.g., in production theory or in the theory of information blocking).

Assume that the nodes in I are under repair, I ⊂ J, I ≠ [empty ]. Then the nodes of H ⊂ I, H ≠ [empty ], return from repair as a batch with intensity β(I,I[setmn ]H) and immediately resume services. Routing then has to be updated anew, as will be described later.

The intensities for occurrence of breakdowns and repairs have to be set under constraints. A versatile class of intensities is defined as follows.

Definition 3.1: Let I be the set of nodes in down status. The intensities for breakdowns, resp. repairs for H ≠ [empty ], are defined by

where a and b are any functions,

with a([empty ]) = b([empty ]) = 1. We set 0/0 := 0.

The above intensities are assumed to be finite.

Rerouting matrices of interest are as follows; for details see Sauer and Daduna [15].

Definition 3.2 (Blocking): Assume that the routing matrix of the original process is reversible. Assume that the nodes in I are presently under repair. Then the routing probabilities are redefined on J₀[setmn ]I according to

Definition 3.3 (Stalling): If there is any breakdown of some node, then the arrival stream to the network and all service processes are completely interrupted and resumed only when all nodes are repaired again.

Definition 3.4 (Skipping): Assume that the nodes in I are the nodes presently under repair. Then the routing matrix is redefined on J₀[setmn ]I according to

The state space and Markov process describing the time evolution of the degradable Jackson network are constructed as follows: Let X_j(t) be the number of customers present at node j at time t ≥ 0. Then X(t) = (X₁(t),…, X_J(t)) is the joint queue length vector at time t ≥ 0 and X := (X(t),t ≥ 0) is the joint queue length process on state space

(where ≤^J denotes the standard coordinatewise ordering).

The availability status of the network at time t ≥ 0 is indicated by Y(t) = I if I ⊆ J is the set of nodes that are broken down (under repair). Y := (Y(t),t ≥ 0) is the availability (breakdown/repair) process.

From this description it is easy to see that the joint process

is a strong Markov process on state space

. We refer to Z = (X,Y) as the queue length/availability or queuing/reliability process. States of Z are

where I is the set of nodes under repair. The numbers

indicate for nodes j ∈ J[setmn ]I, which work in up status, that there are n_j customers present; for nodes j ∈ I in down status, the numbers

indicate that there are n_j customers waiting for the return of the repaired server at node j.

For these general models with breakdowns and repairs and with the above rerouting principles, it was shown in Sauer and Daduna [15] that on the state space E, the steady-state distribution for Z is of product form.

Theorem 3.1: For the degradable Jackson network with breakdown and repair intensities given by Eq. (3.1) and rerouting according to either blocking, stalling, or skipping, the traffic equation for the network in up status is

with unique solution η = (η₁,…, η_J).

If, for all j ∈ J, we have η_j < μ_j, then the joint queue length/availability process

is ergodic and has a stationary distribution of product form given by

for

with

and with

The marginal steady state π₀(n₁,n₂,…, n_J) of the non-Markovian process X coincides with the equilibrium distribution in a standard (completely reliable) Jackson network; see Eq. (4.1). Nevertheless, the behavior of the queuing process X is completely different in all cases (standard Jackson, blocking, stalling, and skipping). Moreover, it is possible to vary the breakdown/repair intensities without changing the stationary distribution for the process Z. Thus, the behavior over time presents itself for comparison in dependence orderings.

3.2. Comparison Results for Degradable Jackson Networks with Unreliable Nodes and Repair

The breakdown/repair process Y is Markov on the state space

of all subsets of J, but the joint queue length process (network process) X in this setting is not a Markov process for itself. Applying the theory of dependence ordering for Markov processes, we can directly investigate Y, but direct application to X is not possible. We first investigate both processes separately and then discuss the joint process Z.

3.2.1. Comparison of Breakdown/Repair Processes

For a set K, we denote the sets of its ancestors, descendants, and relatives as follows:

The Markov process Y = (Y(t),t ≥ 0) on the state space

describes the availability of the network's nodes over time; that is, Y(t) = K means that at time t, the set K consists of the nodes which are under repair. We have

According to Eq. (2.2), for fixed I₁ ⊂ I₂, J₁ ⊂ J₂ we define new intensities by

Applying Proposition 2.1 for

, we have the following comparison.

Proposition 3.1: Assume that the breakdown/repair intensity process Y and the time inverse of

with intensity matrices

are stochastically monotone. Then

.

Recall that a family

is ⊆-increasing if

implies

, and for

.

Example 3.1:

1. Let

, where

are ⊆-increasing. Then f has isotone differences on

. By Proposition 3.1 we obtain

2. Let g(K,H) = f (|K|,|H|) with

. Then

. Especially, by Proposition 3.1 we obtain, by taking f (|K|,|H|) = |K||H|,

3. Let

for some

. Then

and hence

that is, the set of nodes in the first network that are under repair at time instants t₁,…, t_k is smaller (in the stochastic sense) than the corresponding set for the second network. On the other hand, because

has isotone differences as well, we obtain

that is, the set of nodes in the first network that are under repair at least in one of the time instants t₁,…, t_k is larger (in the stochastic sense) than the corresponding set for the second network.

Now take the transition intensities in the special form

Here, the nodes in K are under repair and λ(K) is the intensity of having a jump in Y and δ(K,H) is the conditional probability that after the jump the set H is under repair. Especially, we put

and λ(K) = |{K}^{[pr ]}|. If {T_n} is a sequence of jump points of Y, then it means that Y(T_n) is uniformly distributed on the set {K}^{[pr ]} given that Y(T_n−) = K. Then q^Y(K,H) = 1 if and only if H ∈ {K}^{[pr ]}. Note that in this case, π^Y is uniformly distributed on

. Note that we can also represent our intensities as

Here, |{K}₋^↓| and |{K}₊^↑| play the role of the repair and breakdown intensity, respectively. Then, for instance,

serves as repair probability for the set of nodes K[setmn ]H given that we have repair. Now we take another Markov process

with the same jump intensity λ(K) and modified transition probabilities. Let I₁ ⊂ I₂, J₁ ⊂ J₂. Then we put

From Proposition 3.1, both of these models are <_idif-comparable under the monotonicity assumption.

3.2.2. Comparison of Queue Length Processes

Now, we turn our attention to the (joint) queue length process X, which is not directly amenable to the theory of the previous sections because it is non-Markovian. We have to operate on the joint queuing/reliability process Z = (X,Y). In the sequel, we study unreliable networks with the same routing matrices but different breakdown/repair processes

, as in Proposition 3.1. We denote the resulting processes by Z = (X,Y) and

. For the queuing processes

, of main interest in this subsection, we can consider the reliability processes

as environment processes that strongly influence the behavior of

.

As we will see in Section 3.2.3, there occur severe problems with the full monotonicity of Z. However, for comparison of

only, we can overcome the problems by suitably selecting the order structure for

to apply Theorem 2.1. This will eventually result in the following theorem.

Theorem 3.2: Assume that two Jackson networks have the same arrival intensities and the same rerouting matrices according to either blocking, stalling, or skipping. The breakdown/repair intensity matrices are given by Eqs. (3.5) and (3.6). Assume also that breakdown/repair process and its time-reversal are stochastically monotone. Then we have

that is, for all n ≥ 2, t₁ ≤ ··· ≤ t_n, and all functions f with isotone differences on

, the following holds:

The rest of this subsection is dedicated to the proof of the theorem, which is mainly by a lemma and a proposition that is of some independent interest. The first part is direct; the lengthy proof of the lemma is given to the Appendix.

Lemma 3.1: Assume that the inequality (2.1) of Theorem 2.1 for the intensities of

holds. Then this intensity inequality (2.1) holds for

as well.

Now we consider the following order: (I₁,n₁) [pr ] (I₂,n₂) if and only if I₁ ⊆_e I₂ and n₁ ≤^J n₂. Here I₁ ⊆_e I₂ if and only if I₁ = I₂. Z is clearly monotone w.r.t. to this ordering because standard Jackson networks with reliable nodes are monotone under the usual order on

. The same holds for its time-reversal. Further, a function f that has isotone differences on (Eⁿ,(⊆ × ≤^J)ⁿ) has isotone differences on (Eⁿ,(⊆_e × ≤^J)ⁿ). Therefore, from Lemma 3.1, the inequality (2.1) holds for all functions with isotone differences on (Eⁿ,(⊆_e × ≤^J)ⁿ). Because of the above-mentioned monotonicity we have the following result.

Proposition 3.2: Under the assumptions of Theorem 3.2 and with the ordering introduced above for the queuing/availability process, the following holds:

that is, for all n ≥ 2, t₁ ≤ ··· ≤ t_n, and all functions f with isotone differences on (Eⁿ,(⊆_e × ≤^J)ⁿ), the following holds:

In particular, because a function g with isotone differences on (Eⁿ,(⊆_e × ≤^J)ⁿ) has clearly isotone differences on

, we now obtain the statement of Theorem 3.2 for the queue length process in a network with unreliable nodes.

Example 3.2: As for standard Jackson networks (Section 4), we can prove inequalities like (4.2) for the queue length process in networks with breakdowns and repairs.

3.2.3. Monotonicity Problems for Queuing/Reliability Processes

Since we are able to compare queuing processes in the standard Jackson networks (see Section 4) and breakdown/repair processes as demonstrated in Section 3.2.1, we could expect to be able to compare two networks with the same routing matrices and different breakdown/repair processes. Lemma 3.1 indicates this. However, the joint network process Z = (Y,X) is not monotone with respect to the standard orderings.

Example 3.3: Consider

, inclusion ordering on

, coordinatewise ordering on

, and [pr ]-coordinatewise ordering on E. The Markov processes

have the following intensities:

Here q_I(n₁,n₂) are intensities of a standard Jackson networks according to Theorem 4.1 in Section 4 with valid node set J[setmn ]I, in which the routing matrix depends on the current state I of

and is restricted to the set J[setmn ]I according to blocking, stalling, or skipping.

In order to prove [pr ]-monotonicity we have to check (among others) that for I₁ ⊆ I₂, n₁ ≤^J n₂, the infinitesimal generator of the network fulfills

for any increasing sets

, whereas

Assume that

. We have

Equation (3.7) is clearly monotone w.r.t n since Q_I is a generator for a standard Jackson network with nodes J[setmn ]I without breakdowns. Take

. Then the first part in the above expression is zero. Assume that stalling is applied. Then Q_I is a zero matrix unless I = [empty ]. For I = [empty ], the latter part in the above expression can be either positive or negative according to the choice of

. Therefore, (3.7) is not monotone w.r.t. I and the network process Z is not [pr ]-monotone. With blocking or skipping as the rerouting rule, the situation is more involved but does not lead to monotonicity.