F Baccelli

J Mairesse

Ergodic Theorems for Stochastic Operators and Discrete Event Networks

We present a survey of the main ergodic theory techniques which are used in the study of iterates of monotone and homogeneous stochastic operators. It is shown that ergodic theorems on discrete event networks (queueing networks and/or Petri nets) are a generalization of these stochastic operator theorems. Kingman's subadditive ergodic Theorem is the key tool for deriving what we call rst order ergodic results. We also show how to use backward constructions (also called Loynes schemes in network theory) in order to obtain second order ergodic results. We will propose a review of systems entering the framework insisting on two models, precedence constraints networks and Jackson type networks.

Introduction Many systems appearing in manufacturing, communication

or computer science accept a description in terms of discrete event systems. A usual characteristic of these systems is the existence of some sources of randomness a ecting their behaviour. Hence a natural framework to study them is the one of stochastic discrete event systems.

In this survey paper, we are concerned with two di erent types of models.

First, we consider the study of the iterates T n T n?1 T 0 , where T i : R k ! R k is a random monotone and homogeneous operator. Second, we introduce and study stochastic discrete event networks entering the so-called monotone-separable framework. A subclass of interest is that of stochastic open discrete event networks. It will appear that these models, although they have been studied quite independently in the past years, have a lot of common points. They share the same kind of assumptions and properties : monotonicity, homogeneity and non-expansiveness. In fact, we are going to show that monotone-separable discrete event networks are a generalization of monotone-homogeneous operators. However, when a system can be modelled as an operator, it provides a more precise description and stronger results.

In both types of models, we are working with daters. Typically, we have to study a random process X(n) 2 R k , where X(n) i represents the n ? th occurrence of some event in the system. We are going to propose two types of asymptotic results :

1. First order results, concerning the asymptotic rates lim n X(n) i =n.

2. Second order results, concerning the asymptotic behaviour of di erences such as X(n) i ? X(n) j .

The main references for the results proposed in the paper are the following ones. First order results for operators appear in Vincent 43]. Second order results for operators are new. First and second order results for open discrete event networks are proved in Baccelli and Foss 5]. First order results for general discrete event networks are new. A more complete presentation will be done in a forthcoming paper 7].

The paper is organized as follows. In Part I, we treat rst order results and in Part II, second order ones. In each part, we consider operators and discrete event networks separately. In a last part, we propose a review of systems entering the frameworks insisting on two models, precedence constraints networks and Jackson type networks.

We aim at emphasizing how theorems on stochastic systems are obtained as an interaction between structural properties of deterministic systems and probabilistic tools. In order to do so, we introduce rst the probabilistic tools ( 1 and 5). Then we present some properties on deterministic systems. At last, we prove the main theorem for stochastic systems.

Part I First Order Ergodic Results 1 Probabilistic Tools

We consider a probability space ( ; F; P). We consider a bijective and bimeasurable shift operator : ! . We assume that is stationary and ergodic with respect to the probability P.

Lemma 1.1 (Ergodic lemma). If A 2 F is such that (A) A then PfAg = 0 or 1. Theorem 1.2 (Kingman's subadditive ergodic theorem 32]). Let us consider X l;n ; l < n 2 Z; a doubly-indexed sequence of integrable random variables such that stationarity : X n;n+p = X 0;p n ; 8n; p; p > 0.

boundedness : E X 0;n ] > ?Cn; 8n > 0, for some nite constant C > 0. subadditivity : X l;n 6 X l;m + X m;n ; 8l < m < n.

Then there exists a constant such that the following convergence holds both in expectation and a.s. lim n!1 E X 0;n ] n = ; lim n!1 X 0;n n = P a:s:

(1.1)

Remark 1.1. The convergence in expectation is straightforward. In fact, we have by subadditivity, E(X 0;n ) 6 E(X 0;m ) + E(X m;n ). By stationarity, it implies E(X 0;n ) 6 E(X 0;m ) + E(X 0;n?m ). The real sequence u n = fE(X 0;n )g is subadditive, hence u n =n converges in R f?1g. Because of the boundedness assumption, we conclude that the limit is nite.

Remark 1.2. If we have additivity instead of subadditivity, then the previous theorem reduces to the following result:

lim n!1 n i=0 X i;i+1 n n!1
?! E(X 0;1 ) P a:s:

When the sequence fX n;n+1 ; n 2 Ng is i.i.d., this is simply the Strong Law of Large Numbers. More generally, when the sequence fX n;n+1 ; n 2 Ng is stationary ergodic (i.e. X n;n+1 = X 0;1 n ), it is Birkho 's ergodic theorem.

2 Application to Operators

Subadditivity

We call (deterministic) operator a map T : R k ! R k which is measurable with respect to B, the Borel -eld of R k . Let fT n ; n 2 Ng be a sequence of operators. We associate with it and an initial condition x 0 2 R k , a sequence on R k :

x

(n + 1) = T n (x(n)) = T n T 0 (x(0)) x(0) = x 0 : (2.1)
We will sometimes use the notation x(n; x 0 ) to emphasize the value of the initial condition.

We consider a probability space ( ; F; P; ) as de ned above. We call random (or stochastic) operator a map T : R k ! R k which is measurable with respect to B F. As usual, we will often write T(x) for T(x; !); x 2 R k ; ! 2

. A stationary and ergodic sequence of random operators is a sequence fT n ; n 2 Ng verifying T n (x; !) = T 0 (x; n !). In the same way as in Equation (2.1), we associate with fT n ; n 2 Ng and a (possibly random) initial condition x 0 , a random process fx(n); n 2 Ng taking its values in R k .

In what follows, de nitions apply to deterministic and random operators. For random operators, the properties have to be veri ed with probability 1.

De nition 2.1.

1. Homogeneity T is homogeneous if for all x 2 R k and in R, T(x + 1) = 1 + T(x), where 1 is the vector of R k with all its coordinates equal to 1.

2. Monotonicity T is monotone if x 6 y implies T(x) 6 T(y) coordinatewise.

For a physical interpretation of these conditions, see Remark 2.1. The next theorem is a key tool in understanding the importance of homogeneity and monotonicity in what follows.

Theorem 2.2 (Crandall-Tartar 19]). We consider an operator T : R k ! R k and the following properties H: T is homogeneous. M: T is monotone. NE: T is non-expansive with respect to the sup-norm, i.e 8x; y 2 R k ; we have jjT(x) ? T(y)jj 1 6 jjx ? yjj 1 .

If H holds, then there is equivalence between M and NE. Such operators will be referred to as monotone-homogeneous operators.

Corollary 2.3. Let us consider a sequence T n : R k ! R k ; n 2 N; of monotone-homogeneous operators. If 9x 2 R k ; 9i 2 f1; : : : ; kg such that lim n T n T 0 (x) i =n exists then :

8y 2 R k ; lim n T n T 0 (y) i n = lim n T n T 0 (x) i n :
(2.2) operators. We de ne e = (0; : : : ; 0) 0 and for l < n; x l;n = T n?1 T l (e). The maximal (resp. minimal) coordinate of x l;n forms a subadditive (resp. super-additive) process, i.e. 8l < m < n 2 N; max i (x l;n ) i 6 max i (x l;m ) i + max i (x m;n ) i min i (x l;n ) i > min i (x l;m ) i + min i (x m;n ) i : (2.3)

Proof. We have 8l < m < n 2 N,

x l;n = T n?1 T m T m?1 T l (e) = T n?1 T m (x l;m ) 6 T n?1

T m e + (max i (x l;m ) i ) 1 (monotonicity)

T n?1

T m (e) + (max i (x l;m ) i ) 1 (homogeneity):

Therefore, max i (x l;n ) i 6 max i (x l;m ) i + max i (x m;n ) i : The proof of the super-additivity of the minimal coordinate is equivalent. u t

We are now ready to prove the following theorem on stochastic operators.

Theorem 2.5 (Vincent 43]). Let fT n ; n 2 Ng be a stationary ergodic sequence of monotone-homogeneous random operators. We de ne the process x(n; y); y 2 R k ; as in Equation (2.1). If, for all n, the random variable T n T 1 (0) is integrable and such that E(T n T 1 (0)) > ?Cn, for some positive C, then 9 ; 2 R such that 8y 2 R k , lim n max i x(n; y) i n = P a:s:; lim n E(max i x(n;y) i ) n = (2.4) lim n min i x(n; y) i n = P a:s:; lim n E(min i x(n;y) i ) n = (2.5)

Proof. We de ne as previously the doubly-indexed sequence x l;n = T n?1 T l (e) i ; l < n. Using Prop. 2.4, the sequences max i (x n;m ) i and ? min i (x n;m ) i are subadditive. Hence they satisfy the conditions of Theorem 1.2. So Equation (2.4) holds for y = e = (0; : : : ; 0) 0 . For any other initial condition y, we obtain lim n x(n; y)=n = lim n x(n; e)=n using the non-expansiveness as in Corollary 2.3.

u t

The convergence for the maximal and minimal rates does not imply that of the coordinates. Here is a counter-example borrowed from 43].

Example 2.6. We consider a random operator T 0 : R 3 ! R 3 verifying:

x = (x 1 ; x 2 ; x 3 ) 0 ; T 0 (x) = (x 1 + 1; x 2 + 2; U 0 x 1 + (1 ? U 0 )x 2 ) 0 ;

where U 0 is a 0; 1]-uniform random variable. We have lim inf(T n : : : T 0 (x) 3 )=n = 1 and lim sup(T n : : : T 0 (x) 3 )=n = 2.

Here is another example of the same kind:

T 0 (x) = ( 0 (max(x 1 ; x 2 ) + 2) + (1 ? 0 )(min(x 1 ; x 2 ) + 1); (1 ? 0 ) (max(x 1 ; x 2 ) + 2) + 0 (min(x 1 ; x 2 ) + 1); U 0 x 1 + (1 ? U 0 )x 2 ) 0 ;

where U 0 is a 0; 1]-uniform random variable and 0 is a (0; 1) Bernouilli random variable. The random variables U 0 and 0 are independent.

Projective boundedness

In order to complete Proposition 2.4 or Theorem 2.5, the two main questions are :

i: Does a limit exist for (T n T 0 (y) 1 =n; : : : ; T n T 0 (y) k =n) ? ii: Is this limit equal to a constant ( ; : : : ; ) ?

The general answers to these questions are not known (even for deterministic operators). We are going to propose a su cient condition to answer positively i: and ii: Let us introduce some de nitions.

De nition 2.7 (PR k ). We consider the parallelism relation :

u; v 2 R k u ' v () 9a 2 R such that 8i; u i = a + v i :
We de ne the projective space PR k as the quotient of R k by this parallelism relation. Let be the canonical projection of R k into PR k .

De nition 2.8. Let T be an operator of R k into R k . 1. T is projectively bounded if 9K a compact of PR k such that the image of T is included in K, i.e. (Im(T)) K.

2. T has a generalized xed point if 9 2 R; x 0 2 R k such that T(x 0 ) = 1+x 0 . Theorem 2.10. Let fT n ; n 2 Ng be a stationary and ergodic sequence of random operators. We assume that there exist l 2 N and K a compact of PR k such that :

E = f (Im(T l?1
T 0 )) Kg ; P(E) > 0 :

(2.6)

Then 9 2 R, such that 8x 2 R k ; lim n T n T 0 (x) n
= ( ; : : : ; ) 0 :

Proof. We de ne recursively the random variables N 1 = minfn 2 N j T n+l?1 T n 2 Eg; N i+1 = minfn 2 N j n > N i + l; T n+l?1

T n 2 Eg :

First of all, let us prove that the random variables N i are almost surely nite. Let us consider the event A 1 = fN 1 < +1g. It is easy to see that A 1 is invariant by the shift . In fact N 1 ( ?1 !) = N 1 (!) + 1 or 0. Hence fN 1 (!) < +1g ) fN 1 ( ?1 !) < +1g, i.e. (A) A. By Lemma 1.1, it implies that A is of probability 0 or 1. But (fN 1 = 0g = E) A and by assumption P(E) > 0. We conclude that P(A) = 1. A similar argument can now be applied to N 2 . For A 2 F, we de ne the indicator function 1 A : ! ; 1 A (!) = 1 i ! 2 A. We have

P(N 2 < +1) = E(1 fN 2 <+1g ) = E( X k 1 fN 1 =kg 1 fN 2 <+1g ) = E( X k 1 fN 1 =kg 1 fN 1 k+l <+1g ) = E( X k 1 fN 1 =kg ) = 1 :
We conclude the proof by induction.

Let and be the maximal and minimal rates as de ned in Prop. 2.4.

Let us assume that 6 = . It implies, 8x 2 R k , lim inf n (max i x(n) i ? min i x(n) i ) = +1 :

(2.7)

But we also have that 8i 2 N; (x(N i +l)) K. It implies that (max j x(N i + l) j ? min j x(N i + l) j ) K 0 where K 0 is a compact of R. Hence there exists a subsequence N (i) such that (max j x(N (i) +l) j ?min j x(N (i) +l) j ) converges to a nite limit. This is in contradiction with (2.7).

u t Remark 2.1. In many applications, the operator will be applied on a vector of dates for a physical system. The vectors x(n) and x(n+1) = T n (x(n)) will represent the dates of the n th and (n + 1) th occurrences of some events in a system. In such a case, the homogeneity property can be interpreted as the fact that changing the absolute origin of times does not modify the dynamic of the system. Hence it becomes a very natural assumption. The monotonicity is interpreted as the fact that delaying an event delays all following events.

3 Application to Discrete Event Networks

Discrete event networks

A discrete event network is characterized by 1. A sequence N = N ?1;1] = f (k); M(k); k 2 Zg; where (k) 2 R + and fM(k)g is a sequence of F-valued variables, where F is some measurable space. With N and n 6 m 2 Z, we associate the sequence N n;m] de ned by:

N n;m] def = f n;m] (k); M(n + k); k 2 Ng;
where n;m] (k) def = (n + k), for 0 6 k 6 m ? n, and n;m] (k) def = 1, for k > m ? n.

Measurable operators (k; :) and (:)

: (R + F) N ! R f1g, k 2 N , through which are de ned X n;m] = (N n;m] ); n 6 m; X ? n;m] (k) = (k; N n;m] ); k > 1:
Remark These variables receive the following interpretations: X ? n;m] (k) is the initiation date of the k-th event on some reference node, for the driving sequence N n

;m] . X + n;m] (k) def = X ? n;m] (k) + n;m] (k); n 6 m; k > 0
is the completion date of this event. X + n;m] (k) and X ? n;m] (k) are called internal daters. X n;m] is the maximal dater, i.e. the date of the last event in the network, for the sequence N n;m] .

The monotone separable framework

Let N and e N be two driving sequences such that (k) 6 e (k) < 1 for all k, and with M(k) = f M(k) for all k. We denote X ? 1;m] (k); X + 1;m] (k) and X 1;m] the daters associated with N 1;m] and e X ? A network is said to be monotone-separable if it satis es the following properties for all m > 1; k > 1 and for all N and e N as above:

causality X ? 1;m] (m + 1) 6 X 1;m] < 1. monotonicity X ? 1;m] (k) 6 e X ? 1;m] (k) and X 1;m] 6 e X 1;m] . non-expansiveness 1 e X ? 1;m] (k)?X ? 1;m] (k) 6
x and e X 1;m] ?X 1;m] 6 x, if e (k) = (k) for all k 6 = l, and e (l) = (l) + x, x > 0. separability For 1 6 l < m, if X 1;l] 6 X + 1;m] (l +1) then X 1;m] 6 X ?

1;m] (l + 1) + X l+1;m] .

Proposition 3.1. Under the above assumptions, the sequence X m;n] satises the sub-additive inequality X m;n] 6 X m;l] + X l+1;n] ; 8m 6 l < n:

Proof. It is enough to prove the property for m = 1, since the general relation will then be obtained by applying the relation for m = 1 to the variables associated with some adequate sequence. Let 1 6 l < n. There are two cases:

Case 1: X 1;l] 6 X + 1;n] (l + 1). Then, in view of separability X 1;n] 6 X ? 1;n] (l + 1) + X l+1;n] 6 X 1;l] + X l+1;n] ; where we used the fact that X 1;l] > X ? 1;l] (l + 1) > X ? 1;n] (l + 1); which follows from causality and monotonicity (X ? 1;l] (l +1) = e X ?

1;n] (l +1) with e (k) = (k)

for 1 6 k 6 l and e (k) = 1 for k > l).

Case 2: X 1;l] > X + 1;n] (l + 1). Consider the two sequences f (k)g and fe (k)g, which only di er in their (l + 1)-st coordinate, for which we take e (l + 1) = (l + 1) + x, x > 0. In view of monotonicity, X 1;n] 6 e X 1;n] : In particular, if we take x = x with x = X 1;l] ? X + 1;n] (l + 1) > 0, then e X + 1;n] (l + 1) = e X ? 1;n] (l + 1) + (l + 1) + x = e X ?

1;n] (l + 1) + (l + 1) + X 1;l] ? X + 1;n] (l + 1) = X 1;l] + e X ?

1;n] (l + 1) ? X ? 1;n] (l + 1):

(3.1) But X 1;l] does not depend on (l + 1), and so X 1;l] = e X 1;l] . Therefore e X + 1;n] (l + 1) = e X 1;l] + e X ?

1;n] (l + 1) ? X ?

1;n] (l + 1) > e
X 1;l] (monot.):

We nally obtain that, for x = x e X 1;n] 6 e X ?

1;n] (l + 1) + e X l+1;n] ; (separability) = e X + 1;n] (l + 1) + X ?

1;n] (l + 1) ? X 1;l] + e X l+1;n] ; (Equation (3:1))

6 e X + 1;n] (l + 1) + X ?

1;n] (l + 1) ? X 1;l] + x + X l+1;n] ; (non ? exp:)

= e X + 1;n] (l + 1) + X ? 1;n] (l + 1) ? X 1;l] + X 1;l] ? X + 1;n] (l + 1) + X l+1;n] = e X + 1;n] (l + 1) ? X + 1;n] (l + 1) + X ? 1;n] (l + 1) + X l+1;n] 6 x + X ? 1;n] (l + 1) + X l+1;n] ; (non ? exp:) = X ? 1;n] (l + 1) ? X + 1;n] (l + 1) + X 1;l] + X l+1;n]
6 X 1;l] + X l+1;n] : u t Remark 3.1. Under the additional assumption that X ? 1;m] (l + 1) is a function of f (k); 1 6 k 6 l; and M(p); 1 6 p 6 mg only, non-expansiveness can be replaced by the following property: sub-homogeneity e X 1;m] 6 X 1;m] + , if e (1) = (1) + and e (k) = (k) for all k > 1, > 0 and m > 1.

The proof is exactly the same for case 1. For case 2, taking x as in the proof of Proposition 3.1 gives e X + 1;n] (l + 1) = X 1;l] and e X 1;n] 6 e X ?

1;n] (l + 1) + e X l+1;n] ; (separability) = X ? 1;n] (l + 1) + e X l+1;n] 6 X ? 1;n] (l + 1) + X l+1;n] + X 1;l] ? X + 1;n] (l + 1); (sub ? homog:) 6 X 1;l] + X l+1;n] : Remark 3.2. Some generalizations of the framework, with internal daters, will be proposed in 7]. See also the Jackson network example of 8.2. The comments on the physical interpretation of homogeneity or monotonicity made in Remark 2.1 also apply to discrete event networks.

Open discrete event networks

A discrete event network is said to be open if the following additional assumption holds for all m > 1: 81 6 k 6 m; X ?

1;m] (k + 1) = X ? 1;1] (k + 1) = X + 1;m] (k); and X ? 1;m] (1) = 0:
One can then de ne a point process fA k g k>1 by A k = A 1 + X ?

1;1] (k): The origin of this point process is arbitrary. It is then possible to interpret fA k g as an external arrival process, the inter-arrival times being the sequence f (k)g. To summarize, an open discrete network is described by a sequence N = N ?1;1] = fA k ; M(k); k 2 Zg.

The conditions of the monotone separable framework take the following form for an open network (which corresponds to the conditions of 5]) : for all m > 1, the following properties hold: causality A m 6 A 1 + X 1;m] < 1. monotonicity e X 1;m] > X 1;m] ; for e N and N with e (k) > (k) for all k.

homogeneity Let e N be the point process obtained by shifting the points of N A k , k > 1, of > 0 to the right. Then e X 1;n] = X 1;n] .

separability A 1 + X 1;m] 6 A l+1 + X l+1;m] for all 1 6 l < m such that A 1 + X 1;l] 6 A l+1 .

For an open network, monotonicity can be interpreted as the fact that delaying an arrival delays all forthcoming events in the network. For a possible interpretation of separability, see Remark 6.1.

Stochastic discrete event networks

We consider a probability space ( ; F; P; ) as in 1. The following stochastic assumptions are made: compatibility ( (k); M(k)) = ( (0); M(0)) k for all k 2 Z. integrability 9C > 0, ?Cm 6 E X 1;m] ] < 1 for all m > 0. Theorem 3.2. For all discrete event network which satis es the monotoneseparable assumptions and the above stochastic assumptions, we have

lim n!1 X 1;n] n = a:s: and lim n!1 E X 1;n] ] n = (3.2)
for some nite constant .

Proof. We have X m;m+p] = X 0;p] m , for all m 2 Z and p > 0. For m 6 Let us investigate the relation between the operator framework considered in 2 and the monotone-separable framework considered above. Let fT n g be a sequence of monotone-homogeneous operators. Let (n) 0 and M(n) = T n . Let x(n; 0) be the variables associated with the operator recurrence equation (2.1) with initial condition x 0 = 0. With these variables, we associate X ? 0;n] (k) = X + 0;n] (k) = max i x(k?1; 0) i ; k > 1; and X 0;n] = max i x(n; 0) i ; Note that these variables are functions of fM(l)g. We have X ? 0;n] (n + 1) = X 0;n] < 1, so that causality holds.

Monotonicity and non-expansiveness trivially hold as neither X ? 0;n] (k) nor X 0;n] depend upon f (l)g.

Separability holds because it is always true that X 0;l] = X ? 0;m] (l + 1) and X 0;m] = max i (T m : : : T l+1 (x(l; 0))) i = max i T m : : : T l+1 (x(l; 0) + (X 0;l] ? X 0;l] ) 1) i = X 0;l] + max i T m : : : T l+1 (x(l; 0) ? X 0;l] 1) i ; (homog:) 6 X 0;l] + max i (T m : : : T l+1 (0)) i ; (monotonicity) = X ? 0;m] (l + 1) + X l+1;m] :

Hence, monotone separable operators are a special case of monotone separable discrete event networks. On the other hand, it should be remarked that an operator can not be represented as an open discrete event network. A representation in terms of operators is interesting as it is more precise than the corresponding discrete event network one. In particular, we will see that we are able to obtain second order results for operators, 7, and not for nonopen discrete event networks, 6.2.

Part II

Second Order Ergodic Results

We will introduce a construction which is known as the Loynes scheme. This type of construction will be used for both types of models, discrete event networks and operators, but in a rather di erent way.

Basic Example and Probabilistic Tools

The basic construction was introduced by Loynes in 34] to study the stability of the G=G=1=1 queue. A G=G arrival process is a stationary and ergodic marked point process N = f( n ; n )); n 2 Zg, where n 2 R + is the service time required by customer n and n = A n+1 ? A n the inter-arrival time between customers n and n + 1. The 1=1 part describes the queueing mechanism. There is a single server and an in nite waiting room or bu er.

Upon arrival at instant A n , customer n is served immediately if the server is idle at A ? n and is queued in the bu er otherwise. The server operates at unit rate until all customers present in the bu er have been served. Let X l;n] be the time of last activity in the system, i.e. the departure of the last customer, for the restriction N l;n] . Here are two equivalent ways to describe the system :

As a stochastic operator,

A n+1 X l;n+1] = n + A n max( n + n+1 + A n ; n+1 + X l;n] ) (5.1) = n " n n+1 n+1
A n X l;n]

(5.2) Equation ( 5.1) can be written X l;n+1] = max(A n+1 ; X l;n] )+ n+1 . The meaning is that the server starts working on customer n+1 as soon as this customer has arrived (A n+1 ) and the server has completed the services of the previous customers (X l;n] ). Equation (5.2) is just a re-writing using the (max,+) notations, see also 8.1. It is easy to verify that this operator is monotone and homogeneous.

As an open network, by means of the function of 3.

X l;n] = ( i ; i ; i 2 fl; : : : ; ng)

= (A n ? A l ) + n + max(0; n?l max k=1 k X i=1
( n?i ? n?i )) : (5.3)

The easiest way to understand Equation (5.3) is to look at Figure 1 Let us consider the sequence of variables fZ l;n] ; l 6 n 2 Zg de ned by Z l;n] = X l;n] ? (A n ? A l ): The variables Z l;n] verify Lindley's equation2 Z l;n+1] = (Z l;n] ? n ) + + n+1 . Theorem 5.1 ( Loynes 34]). The sequence Z ?n;0] is increasing in n, i.e. Z ?n?1;0] > Z ?n;0] . The limit Z = lim n Z ?n;0] veri es PfZ < +1g = 0 or 1. Furthermore Z is a stationary solution of Lindley's equation, i.e. Z( !) = (Z(!) ? 0 ) + + 1 . When PfZ < +1g = 1, the sequence fZ 0;n] ; n 2 Ng couples in nite time with the stationary sequence fZ n g.

Proof. The monotonicity of Z ?n;0] is easy to obtain from Equation (5.3). It is also illustrated in Figure 1. Hence the limit Z = lim n Z ?n;0] exists. Let us denote A = fZ < +1g. From Z ?n;1] = (Z ?n;0] ? 0 ) + + 1 and the fact that 1 is a.s. nite, we obtain Z(!) < +1 , 9K 8n; Z ?n;0] (!) < K ) 9K 0 8n; Z ?n;1] (!) < K 0 : But we also have Z ?n;1] (!) = Z ?n?1;0] ( !) :

(5.4)

We conclude that Z( !) < +1. We have proved that (A) A which implies, Ergodic Lemma 1.1, that PfAg = 0 or 1. From Equation (5.4), letting n go to 1, we deduce that Z( !) = (Z(!) ? 0 ) + + 1 . For a proof of the remaining point, see 34] or 1].

u t

The limit Z is usually referred to as Loynes variable. We can obtain, using Equation (5.3), PfZ < +1g = 1 , E( ) < E( ). The condition E( ) < E( ) is called the stability condition and is usually written under the form = E( )=E( ) < 1. We will see a similar type of stability condition in Theorem 6.2.

6 Application to Discrete Event Networks

Open discrete event networks

The assumptions and notations are those of 3.3 but we replace the separability assumption by strong separability For 1 6 l < m, if A 1 + X 1;l] 6 A l+1 then A 1 + X 1;m] = A l+1 + X l+1;m] . Remark 6.1. Strong separability can be interpreted as follows. If the arrival of customer l + 1 takes place later than the last activity for the arrival process 1; l], then the evolution of the network after time A l+1 is the same as in the network which starts empty at this time.

We de ne = E(A n+1 ? A n ) ?1 interpreted as the arrival rate and Z l;n] = X l;n] ? (A n ? A l ); l 6 n : (6.1) Proposition 6.1 (Internal monotonicity). Under the above assumptions, we have Z l?1;n] > Z l;n] ; l 6 n:

Proof. Consider the point process e

N with e (l ? 1) = (l ? 1) + Z l?1;l?1] and e (k) = (k) everywhere else. For e N l?1;n] , we have separability in l so that e X l?1;n] = e X l;n] + e A l ? e A l?1 = X l;n] + e A l ? e A l?1 (strong ? separability) = X l;n] + A l ? A l?1 + Z l?1;l?1] : (6.2) Therefore Z l?1;n] = X l?1;n] ? (A n ? A l?1 ) = X l?1;n] ? (A n ? A l ) ? (A l ? A l?1 ) = X l?1;n] ? (A n ? A l ) + X l;n] ? e X l?1;n] + Z l?1;l?1] (by (6:2)) = Z l;n] + X l?1;n] ? e X l?1;n] + Z l?1;l?1] > Z l;n] ; (non ? expansiveness): u t

Let Z = lim n Z ?n;0] (N), which exists by internal monotonicity of Z ?n;0] (N). We de ne a c-scaling of the arrival point process N in the following way : 0 6 c < +1; cN = fcA n ; M(n); n 2 Zg :

From Equation (6.1) and Prop. 3.1 , we obtain that Z 1;n] is subadditive. Applying Theorem 3.2, we obtain the existence of the limits

lim n Z 1;n] (cN) n = lim n Z ?n;0] (cN) n = (c) :
From Equation (6.1), we obtain lim n X 1;n] (cN) n = lim n X ?n;0] (cN) n = (c) + c :

For c > c, we have cN > cN. We obtain by internal monotonicity and by monotonicity respectively :

1. Z ?n;0] (cN) is decreasing in c =) (c) is decreasing in c. 2. X 0;n] (cN) is increasing in c =) (c) + c= is increasing in c.

We deduce the existence of a constant (0) de ned by :

lim c!0 & (c) + c = (0) = lim c!0 % (c) : (6.3)
The intuitive interpretation is that (0) ?1 is the throughput of the network when we saturate the input, i.e. when A n = 0; 8n. It is the maximal possible throughput.

Theorem 6.2. Let N = fA n ; M n ; n 2 Zg be a stationary ergodic point process. We set = (0). If > 1, then P(Z = +1) = 1. If < 1, then P(Z < +1) = 1 and fZ 0;n] ; n 2 Ng couples in nite time with the stationary sequence fZ n g.

Proof. The rst part of the theorem is immediate. In fact relation (6.3) implies (1) + 1= > (0). We have : lim n Z ?n;0] n = (1) > (0) ? 1 = ? 1 : Therefore ? 1 > 0 implies P(Z = +1) = 1. For a complete proof of the result, the reader is referred to 5]. u t Remark 6.2. For < 1, Z is the smallest stationary regime for the response time of the system (which is de ned as the time to the last activity under the restriction ?1; 0] of N). Intuitively it is the stationary regime corresponding to an empty initial condition as it is the limit of the systems starting empty and fed up with the restrictions ?n; 0] of N. In many cases, there will be multiple stationary regimes depending on the initial condition. A simple example of a monotone and separable open network having multiple stationary regimes is proposed in 1], p.83. It is a G=G=2=1 queue with a shortest workload allocation rule (see also Theorem 7.5).

General discrete event networks

For discrete event networks which are not open, there are no general results.

The reason is the absence of internal monotonicity of the variables Z ?n;0] = X ?n;0] ?X ? ?n;0] . We illustrate the phenomenon on Figure 2 where we compare the case of a general network and the case of an open network.

For open and general networks, we consider successively the restrictions ?n; 0] and ?n ? 1; 0]. In the open case, the internal monotonicity has been illustrated in Figure 2. In the general case, the variables X ? are internal A ?n A 0 A 0 A ?n?1 A ?n Z ?n?1;0] X ? ?n?1;0] (0) X ? ?n;0] (0) X ? ?n;0] (?n) Z ?n;0] Z ?n;0] Z ?n?1;0] X ? ?n?1;0] (?n)

Open network : Z ?n?1;0] > Z ?n;0] General network X ? ?n?1;0] (?n ? 1) Figure 2: Loynes scheme for monotone-separable networks. variables, hence their value are modi ed when we go from the restriction ?n; 0] to ?n?1; 0]. As a consequence, there is no internal monotonicity. On Figure 2, for the ease of comparison, we have assumed that X ? ?n?1;0] (?n) = X ? ?n?1;0] (?n) (these quantities are de ned up to an additive constant).

Application to Operators

We propose in Sections 7.1 and 7.2 two very di erent approaches. They correspond to two di erent types of operators, see Remark 7.1. The rst approach is directly based on the Loynes scheme. The second one uses xed points results.

Monotonicity

De nition 7.1. We say that the operator T : R k ! R k has a minimal value if there exists x 0 2 R k such that 8y > x 0 ; T(y) > x 0 .

Let us consider a sequence of monotone operators fT n ; n 2 Zg. If all the operators have a common minimal value x 0 , then we are able to construct a Loynes scheme, in the same way as in 5. In fact, we have T 0 (x 0 ) > x 0 and T 0 T ?1 (x 0 ) > T 0 (x 0 ) > x 0 using monotonicity. We obtain that 9Z 2 (R f+1g) k ; lim n T 0 T ?1 T ?n (x 0 ) = Z :

(7.1)
The main question is whether the limit Z is nite or not, the nite case being the interesting one. In particular, if we consider a sequence of monotonehomogeneous operators, then the limits and as de ned in Proposition 2.4

exist. Because of the existence of the minimal value x 0 , we have > > 0.

If > 0 then there exists i such that Z i = +1 (the proof is immediate).

For this reason, it is usually not interesting to construct a Loynes scheme directly on the sequence of operators T n . For example, in the case of the operator of the G/G/1 queue, see Equation (5.1), the Loynes scheme was not built on (A n ; X l;n] ) 0 but on the di erences Z l;n] = X l;n] ? A n . In order to generalize the construction, the good approach is to consider the operators T n in a projective space.

We have already de ned the projective space PR k in De nition 2.7. The space PR k is isomorphic to R k?1 . Here are di erent possible ways to map PR k onto R k?1 . Let i 2 f1; : : : ; kg, we de ne :

i : R k ?! R k?1 ; i (x) = (x 1 ? x i ; : : : ; x i?1 ? x i ; x i+1 ? x i ; : : : ; x k ? x i ) 0 i : PR k ! R k?1 ; i = i ?1 ;

where was de ned in De nition 2.7. It is easy to verify that i is de ned without ambiguity and is bijective.

De nition 7.2. Let x 2 R k . We de ne jxj P = max i x i ? min i x i . Let u 2 PR k (resp. u 2 R k?1 ) and x be a representative of u, i.e. (x) = u (resp. i (x) = u) We de ne juj P = max i x i ? min i x i . The function j:j P is a semi-norm on R k as jxj P = 0 ) x i = ; 8i. On the other hand, it de nes a norm on PR k or R k?1 . We call it the projective norm. We use the same notation for the semi-norm on R k and the norms on PR k and R k?1 in order not to carry too many notations. Form now on, we are going to work on R k?1 equipped with the projective norm. Without loss of generality, we will restrict our attention to 1 ; 1 .

Working on R k?1 rather than on PR k enables us to have a natural partial order. The projective norm is indeed compatible with the coordinatewise partial ordering on R k?1 , i.e. u; v 2 R k?1 ; u > v ) juj P > jvj P . Let T : R k ! R k be an homogeneous operator. We de ne T : R k?1 ! R k?1 T(u) = 1 (T(x)); x 2 ?1 1 (u) :

Because of homogeneity, T(u) is unambiguously de ned. We can write with abbreviated notations T = 1 T ?1 1 .

Lemma 7.3. We consider an homogeneous operator T : R k ! R k and the associated operator T : R k?1 ! R k?1 , satisfying the following assumptions:

A. T is monotone. B. T(x) 1 ? x 1 is independent of x 2 R k .
C. 9x 0 such that T(x 0 ) 1 ? (x 0 ) 1 = min i (T(x 0 ) i ? (x 0 ) i ).

Under Assumption A, T is non-expansive. Under Assumptions A + B, T is monotone. Under Assumptions A+B+C, T has minimal value x0 = 1 (x 0 ).

Proof. We consider u; v 2 R k?1 verifying u > v. Let x; y 2 R k be such that 1 (x) = u; 1 (y) = v and x 1 = y 1 .

1. A ) T is non-expansive. The representatives x and y are such that ju ? vj P = jx ? yj P = jjx ? yjj 1 . By monotonicity of T, we have T(x) > T(y), hence jT(x) ? T(y)j P 6 jjT(x) ? T(y)jj 1 . By non-expansiveness of T (Theorem 2.2), we have jjT(x) ? T(y)jj 1 6 jjx ? yjj 1 . We conclude that : j T (u) ? T(v)j P = jT(x) ? T(y)j P 6 jjT(x) ? T(y)jj 1 6 jjx ? yjj 1 = ju ? vj P :

2. A + B ) T is monotone. Let the representatives x and y verify x 1 = y 1 . Hence by Assumption B, we have T(x) 1 = T(y) 1 . We conclude that T(x) > T(y) ) T(u) > T(v). 3. A + B + C ) T has minimal value x0 = 1 (x 0 ). We have T0 (x 0 ) i = T(x 0 ) i ? T(x 0 ) 1 = T(x 0 ) i ? (x 0 ) i + (x 0 ) i ? T(x 0 ) 1 > T(x 0 ) 1 ? (x 0 ) 1 + (x 0 ) i ? T(x 0 ) 1 = (x 0 ) i :

We conclude with the monotonicity of T that 8y 2 R k?1 ; y > x0 ) T (y) > x0 .

u t

The operator T is not homogeneous in general. Hence the conditions ensuring monotonicity and non-expansiveness are not the same (to be compared with Theorem 2.2).

Remark 7.1. Assumption B. can be easily weakened and replaced by : B 0 : 8x; y 2 R k ; x 1 ? y 1 = min i x i ? y i ) T(x) 1 ? T(y) 1 = min i T(x) i ? T(y) i :

In Lemma 7.3, we have presented the assumptions which appear naturally in physical systems. In particular, Assumption B is veri ed when the rst coordinate of T is the dater of an exogeneous arrival process. Assumption C is veri ed if the other coordinates of T correspond to events which are induced by the arrivals (hence occur later on). It was the case for the operator associated with the G=G=1=1 queue, see Equation (5.1). In that example, the minimal value was e = (0; : : : ; 0) 0 .

These assumptions are of course restrictive. Roughly speaking, they will apply only to some operators associated with `open systems'. For operators associated with `closed systems', the conditions and results of Section 7.2 are more appropriate. Theorem 7.4. Let fT n ; n 2 Ng be a stationary and ergodic sequence of homogeneous random operators on R k and f Tn ; n 2 Ng the associated sequence on R k?1 . We assume that Assumptions A,B and C of Lemma 7.3 are veri ed with probability 1 by the operators fT n g (in particular they have a constant minimal value x 0 ). We set x0 = 1 (x 0 ). Then the limit Z = lim n T0 T?n(x 0 ) exists and veri es PfZ < +1g = 0 or 1. Furthermore Z is a stationary solution, i.e. Z( !) = T1 (Z(!)). When PfZ < +1g = 1, the sequence fT n T 1 (x 0 )g couples in nite time with the stationary sequence fZ n g.

Proof. It is exactly similar to the one of Loynes Theorem 5.1.

u t

The main di culty is often to prove the niteness of Z. Moreover, when nite, Z is usually not the unique stationary solution. Indeed, we have that 8 2 R; x0 + 1 is a minimal value for the operators Tn . Hence by Theorem 7.4, the limits Z = lim n T0 T?n(x 0 + 1) exist and are stationary solutions. The variables Z are increasing in by monotonicity of Tn . Hence we can de ne the limit

Z 1 = lim !+1 Z : (7.2)
Next Theorem was originally proved by Brandt for a special operator associated with the G=G=k=1 queue.

Theorem 7.5 (Brandt 14]). We have PfZ 1 < +1g = 0 or 1. If we have PfZ 1 < +1g = 1, then Z 1 is the maximal nite stationary solution, i.e Z( !) = T1 (Z(!)) and Y ( !) = T1 (Y (!)); PfY < +1g = 1 ) PfZ 1 > Y g = 1 :

Proof. The essential ingredient is the non-expansiveness of Tn . For more details, the reader is referred to 14] or 15], Theorem 1.3.2. u t Remark 7.2. The results presented in this section 7.1 are just a specialization to operators of nite dimension of more general results. Let (E; E) be a Polish space (complete separable metric space) equipped with its Borel -eld. We consider f n ; n 2 Z} a stationary and ergodic sequence of measurable random functions n : E ! E. The recursive equations x(n + 1) = n (x(n)); x(0) = x 0 de ne a Stochastic Recursive Sequence, following the terminology of Borovkov 12]. If the functions n are monotone and verify n (x 0 ) > x 0 then the results of Theorem 7.4 hold (replace just T n by n ). If we assume furthermore that the functions n are non-expansive (with respect to the metric of E) then the results of Theorem 7.5 hold. For a detailed presentation of this framework, see 15] 13].

Fixed point

We will see, in this section, a rather di erent use of Loynes backward construction.

Here is a result generalizing Proposition 2.9. The proof of A ) B in Prop. 2.9 was using only the continuity of the operator T. In fact, using the non-expansiveness of T, we can get stronger results. Theorem 7.6 (Weller 44], Sine 42]). Let C be a compact of R k . We consider an operator T : C ! C, non-expansive with respect to the sup-norm jj:jj 1 . Then we have : 8x 2 C; 9p 2 N; 9u 2 C : lim n!1 T np (x) = u and T p (u) = u :

(7.3)
The following corollary is the essential result in what follows.

Corollary 7.7. Let T be de ned as in Theorem 7.6. We assume that 8n > 1; T n has a unique xed point u. Then 8" > 0; 9N 2 N such that 8n > N : sup x2C jjT n (x) ? ujj 1 6 " :

In other words, there is uniform convergence of T n to u.

Proof. Let us prove rst that T n converges simply to u. Let x belong to C. As u is the unique xed point of the powers of T, we obtain by application of Theorem 7.6 : 8x 2 C; 9p 2 N; 8" > 0; 9M(x; ") 2 N; 8n > M(x; ") : jjT np (x)?ujj 1 6 ":

By non-expansiveness, we have ? jjT T np (x) ? T(u)jj 1 = jjT np+1 (x) ? ujj 1 6 jjT np (x) ? ujj 1 and by induction, 8q 2 N; jjT np+q (x)?ujj 1 6 jjT np (x)?ujj 1 . It implies that : 8x 2 C; 8" > 0; 9N(x; ") 2 N; 8n > N(x; "); jjT n (x) ? ujj 1 6 " :

We are now ready to prove that the convergence is uniform. Let us denote by B(x; ") the open ball of center x and radius " for the sup-norm. Using non-expansiveness, we have that 8y 2 B(x; "); 8n > N(x; "), jjT n (y) ? ujj 1 6 jjT n (y) ? T n (x)jj 1 + jjT n (x) ? ujj 1 6 2" : (

Using Borel-Lebesgue's characterization of compact sets, there exists a nite number of points x i such that C S i B(x i ; "). Using Equation (7.5), we obtain :

8" > 0; 8n > max i N(x i ; "); 8x 2 C : jjT n (x) ? ujj 1 6 2" :

This completes the proof.

u t

We are now ready to prove the main theorem of this section which generalizes the approach proposed in 35] 36].

Theorem 7.8. Let fT n ; n 2 Ng be a stationary ergodic sequence of monotone homogeneous random operators on R k and f Tn g the associated sequence on R k?1 . We assume that there exists a deterministic monotone homogeneous operator S on R k ( S on R k?1 ) such that i. S is bounded i.e. there exists a compact K of R k?1 such that Im( S) K.

ii. 8n > 1; Sn has a unique xed point.

iii. There exists a deterministic constant l such that S belongs to the support of the random operator Tl T1 and 8n > 0; Sn belongs to the support of Tnl T1 , with the following precise meaning :

8" > 0; Pf sup x2R k?1 j Tl : : : T1 (x) ? S(x)j P 6 "g > 0;

Pf sup x2R k?1 j Tnl : : : T1 (x) ? Sn (x)j P 6 "g > 0 :

Then 8x 2 R k?1 ; x(n) = Tn?1 T0 (x) converges weakly to a unique stationary distribution.

Proof. We rst prove the theorem when replacing Assumption iii: by the stronger assumption : iv: 9l s.t. Pf Tl T1 = Sg > 0 and 8n > 0, Pf Tnl T1 = Sn g > 0.

For x 2 R k?1 , we de ne the variables : Z ?n;0 (x) = T0 T?n (x) = x(n; x) ?n : (7.6) We now prove that Z ?n;0 (x) admits P:a:s: a limit which is independent of x. The compact K of Assumption i: is stable by S, and from Assumption ii:, there is a unique xed point u 2 R k?1 for the powers of S. From Lemma 7.3, S is non-expansive with respect to the projective norm. Hence Corollary 7.7 can be applied to S on (R k?1 ; j:j P ). It implies 8" > 0; 9N("); 8n > N("); 8x 2 R k?1 ; j Sn (x) ? uj P 6 " :

(7.7)
We de ne the random variables 8" > 0; M(") = minfn > N(")l j T?n T?n?N(")l+1 = SN(") g ; (7.8) where N(") and l are de ned in Equation (7.7) and in Assumption iv: respectively. Assumption iv: also implies that PfM(") < +1g > 0. We obtain PfM(") < +1g = 1 ; (7.9) in exactly the same way as we obtained PfN 1 < +1g = 1 in the proof of Theorem 2.10.

Let us x " = 1. We de ne the events A n = fM(1; !) = ng which form a countable partition of .

Let us work for a moment on the event A = A m for a given integer m. Let us consider the variables Z ?n;?m (x) = T?m : : : T?n (x); n > m. We have 8n > m + N(1)l; Z ?n;?m (x) = SN(1) ( T?m?N(1)l T?n (x)) :

(7.10)

Hence on A m , the image of Z ?n;?m is included in the closed ball of center u and radius " = 1 (Equation (7.7)) that we denote by K(1), 8n > m + N(1)l; Im(Z ?n;?m ) K(1) : (7.11) We consider the sequence of random variables fM(1=i); i 2 Ng. By de nition of the variables M("), (7.8), the sequence M(1=i) is increasing in i in particular M(1=i) > M(1). We have, for all n > M(1=i) + N(1=i)l (note that we consider the variables Z with respect to an unchanged ending point ?m). Using Equation (7.7), we have that SN(1=i) T?M(1=i)?N(1=i)l

T?n (x)
is included in the closed ball of center u and radius 1=i. Using the nonexpansiveness of the operators, we obtain the existence of a compact set, denoted K(1=i) such that 8n > M( 1 i ) + N( 1 i )l; Im(Z ?n;?m ) K( 1 i ) :

(7.12)

We have built a decreasing sequence of compact sets K(1=i) whose radius goes to zero. By a classical theorem on decreasing sequences of compact sets (Borel-Lebesgue Theorem), the intersection of the sets K(1=i) is a single point. It means precisely that the limit of Z ?n;?m (x); n ! +1; exists and is independent of x. We de ne the following notations 8! 2 A m ; 8x 2 R k?1 ; lim n!1 Z ?n;?m (x) = Z 1;m ; Z = T0 T?m+1 (Z 1;m ) :

It is straightforward to prove that Z = lim n!+1 Z ?n;0 (x). By applying the same construction to all the events A m ; m 2 N, we prove the a.s. existence of Z = lim n Z ?n;0 (x), the limit being independent of x. By analogy with 5, we call Z the Loynes variable.

We are now going to prove the existence of the Loynes variable Z under the weaker Assumption iii:

We de ne the random variables N(") as previously, (7.7). On the other hand, the de nition of the variables M(") is modi ed 8"; M(") = minfn > N(")l j sup x2R k?1 j T?n+N(")l : : : T?n (x) ? SN(") (x)j P 6 "g : (

From Assumption iii: and the Ergodic Lemma 1.1, we obtain PfM(") < +1g = 1.

We de ne the variable M(1), then the partition A n , the event A and the variables M(1=i) as before. We de ne the variables :

Ẑi ?n;?m (x) = T?m : : : T?M(1=i)+1 SN(1=i) T?M(1=i)?1?N(1=i)l : : : T?n (x) (7.14) There exists a sequence of compacts K(1=i) of radius 1=i such that (see the rst part of the proof) 8n > M(1=i) + N(1=i)l; Im( Ẑi ?n;?m ) K(1=i) :

(7.15)
From the de nition of M(1=i), Equation (7.13), we get 8n > M(1=i) + N(1=i)l; 8x 2 R k?1 ; jZ ?n;?M(1=i) (x) ? Ẑi ?n;?M(1=i) (x)j P 6 1 i :

Using non-expansiveness, we obtain 8n > M(1=i) + N(1=i)l; 8x 2 R k?1 ; jZ ?n;?m (x) ? Ẑi ?n;?m (x)j P 6 1 i :

We conclude that 8n > M(1=i) + N(1=i)l; 8x; y 2 R k?1 jZ ?n;?m (x)? Z ?n;?m (y)j P 6 jZ ?n;?m (x) ? Ẑi ?n;?m (x)j P + j Ẑi ?n;?m (x) ? Ẑi ?n;?m (y)j P + j Ẑi ?n;?m (y) ? Z ?n;?m (y)j P 6 3 i :

Hence there exists a sequence of compacts K(1=i) of radius 3=i such that 8n > M(1=i) + N(1=i)l; Im(Z ?n;?m ) K(1=i). We conclude as in the rst part of the proof.

Our aim is now to prove that we have weak convergence of the process x(n) = Tn T0 (x(0)) to the stationary distribution of Z. We consider a function f : R k ! R, continuous and bounded. We have, using the stationarity of f Tn g

E ( f(x(n; x(0))) ) = E( f( Tn?1 T0 (x(0)) ) = E( f( T0 T?n+1 (x(0)) ) n ?! E f(Z) (7.16)
The convergence in (7.16) is obtained from Lebesgue's dominated convergence theorem (f is bounded). It proves weak convergence. u t Remark 7.3. It would be nice to replace Assumption iii: by the following weaker Assumption v: 8" > 0; 8K compact ; Pfsup x2K j Tl : : : T1 (x) ? S(x)j P 6 "g > 0; Pfsup x2K j Tnl : : : T1 (x) ? Sn (x)j P 6 "g > 0 :

Assumption v: means precisely that S is in the support of T0 for the topology of weak convergence on the functional space C 0 (R k?1 ; R k?1 ) (continuous functions of R k?1 ). However, Theorem 7.8 is not true under Assumption v: Here is a counterexample. We consider a; b 2 R + and we de ne the monotone homogeneous operators on R 2 : T A (x) =

x 1 x 2 + a (7.17) 8i 2 N + ; T B i (x) = x 1 max(x 2 ? ib; x 1 ) (7.18) We consider a sequence of i.i.d. random operators fT n ; n 2 Ng with the following distribution : PfT 0 = T A g = 1 2 ; PfT 0 = T B i g = 1 2 i+1 ; i 2 N + : We de ne the monotone homogeneous operator S : R 2 ! R 2 ; S(x) = (x 1 ; x 1 ) 0 . It is clear that S veri es the Assumptions i: and ii: as S is constant.

Let K be a compact set of R and n be such that K ?n; n]. We obtain immediately that 8x 2 K; TB i (x) = S(x) as soon as ib > n. Hence S veri es also Assumption v:

The description of the process x(n) = Tn?1 T0 (0) is very easy. It is a random walk on the real line with an absorbing barrier at 0. The drift of the random walk is = a 2 ?

1 X i=1 ib 2 i+1 = a 2 ? b :
We conclude that the process x(n) is transient if a > 2b which provides the announced counter-example.

Practically speaking, the main di culty consists in nding a deterministic operator S verifying the assumptions of Theorem 7.8. We discuss this point for some speci c models in 8.1.

8 Models Entering the Framework

Operators

Let A and B be two arbitrary sets. We de ne applications (M k denotes the set of matrices of dimension k k)

P : A B ! M k (R); A : A B ! M k (R f?1; +1g) ;
where the matrices P( ; ) are Markovian , i.e. verify 8i 2 f1; : : : ; kg; p ij ( ; ) > 0; T(x) i is nite (8x8i) then it de nes a monotone-homogeneous operator. For example, let us prove homogeneity. We have for x 2 T k ; 2 R; T

(x + 1) i = inf sup k X j=1 p ij ( ; ) (x j + + a ij ( ; )) = inf sup ( k X j=1 p ij ( ; ) ) + k X j=1
p ij ( ; ) (x j + a ij ( ; )) = + T(x) i :

The following representation theorem provides a precise idea of the degree of generality of the class of monotone-homogeneous operators. Theorem 8.1 ( Kolokoltsov 33]). Let T : R k ! R k be a monotone and homogeneous operator. Then it can be represented in the form of Equation (8.2).

The next lemma which is based on this representation, is proved in 33]. It can be coupled with Theorem 7.8 to obtain second order results for some stochastic operators. Lemma 8.2. Let T : R k ! R k be a monotone-homogeneous operator, written in the form of Equation (8.2). Let us assume that 9 > 0 : 8i; j9l : 8 ; ; p il ( ; ) > ; p jl ( ; ) > : Then the operators T n ; n 2 N, have a unique generalized xed point.

From the point of view of applications, the interesting case is when the sets A and B are nite. Here are some specializations of Equation (8.2).

(+, ) linear systems The operator T is just a markovian matrix P, see Equation (8.1). We have T(x) = Px (matrix-vector multiplication in the usual algebra). Matrix P can be interpreted as the matrix of transition probabilities of a Markov Chain (MC) having state space f1; : : : ; kg. The most interesting operator for a MC is S(y) = yP where y is a row vector. It is well known that the limit of S n (y); y > 0; P i y i = 1 is the stationary distribution of the MC. But the operator T(x) = Px is also interesting from the point of view of applications. It appeared in 21] to model the problem of reaching agreement on subjective opinions. More generally, it has been studied as a special case of the general theory of products of non-negative matrices, see for example 41], Chapter 4.6.

For any markovian matrix P, we have T( 1) = P 1 = 1. Hence the vector 1 is a generalized xed point (Def. 2.8) of operator T. By application of the Perron-Frobenius Theorem, it is the only one. Hence, applying the ergodic results of this paper to a stochastic sequence of matrices P n , is going to yield trivial results (the convergence of (P n : : : P 0 x) to ( 1) ). In fact much stronger results are known for such models. The necessary and su cient conditions of convergence of (P n : : : P 0 x) to ( 1), are known for a general sequence of matrices P n , without any stochastic assumptions, see 41], Th. (max,+) linear systems Such operators have the following form x 2 R k ; i 2 f1; : : : ; kg; T(x) i = max j (x j + a ij ) ; (8.3) T(x) = A x : (8.4) Equation ( 8.3) can be interpreted as a matrix-vector product in the (max,+) algebra. Equation (8.4) is simply a rewriting of Equation (8.3) using (max,+) notations. The (min,+) linear case boils down to the (max,+) case by switching to operator ?T.

Such systems appear in many domains of applications, under various forms. Among the very large and complete literature on the theoretical aspects of deterministic (max,+) systems, let us quote only 3] 37] and the references therein. As far as we know, the rst references on stochastic (max,+) linear systems are 18] and 39]. Thanks to the rich deterministic theory, Theorems 2.5, 7.8 become very operational for (max,+) systems. The di erent assumptions in these theorems can be interpreted as properties of the underlying graph structure of the model. For more details, see 35].

(min,max,+) linear systems These systems can be represented in one of the following dual forms. We use the symbol for the (max,+) matrix-vector product, see (8.4), and the symbol for the (min,+) matrix-vector product.

x 2 R k ; T(x) = min (A 1 x; A 2 x; : : : ; A l x) ; T(x) = max (B 1 x; B 2 x; : : : ; B p x) :

Here are some domains of application where such systems appear Minimax control in dynamic game theory, see 11]. Study of timed digital circuits, see 26]. The (min,max) structure arises from the (and,or) operations of logical circuits. Queueing theory. G/G/s/1 le, resequencing le, see for example 1].

Parallel processing systems 9] : there are k processors. A customer requires to use concurrently p out of the k processors to be executed. Motion of interfaces in particle systems 22]. As an illustration, let us describe a little bit more precisely a special case known as the marching soldier model. There is a row of k soldiers which advance in the same direction. In order to try to keep a common pace, they adopt the following strategy. At regular instants of time, each soldier checks the position of his right and left neighbours. He advances of 1 if they both are ahead of him and stays at the same position otherwise. Let x 2 R k denote the position of the soldiers at instant 0. Their position at instant 1, will be (with the convention x 0 = x k+1 = +1) T(x) i = max (min(x i?1 ; x i ; x i+1 ) + 1; x i ) :

The study of deterministic (min,max,+) systems (existence of generalized xed points, projective boundedness,...) has been considered in several papers 38] 25]. However, it is far from being complete. For this reason, the only references on stochastic (min,max,+) systems concern rst order results 22] 30].

(max,+, ) linear systems These systems can be represented under the following form x 2 R k ; T(x) i = max 2A k X j=1 p ij ( ) (x j + a i ( )) :

(8.5) Equation ( 8.5) appears in many domains of applications like operational research, management science and engineering. It is in fact one of the optimality equation of stochastic3 dynamic programming in discrete time, on a nite

1

  ;m] (k), etc. those associated with e N 1;m] .

Figure 1 :

 1 Figure 1: Loynes scheme for the G=G=1=1 queue.

  1=i)+1 SN(1=i) T?M(1=i)?N(1=i)l T?n (x) :

  the following (min,max,+, ) function x 2 R k ; i 2 f1; : : : ; kg; T(x) i = inf 2A sup arises in stochastic control of dynamic games,see 11]. If

4. 18 .

 18

  For example (without any kind of exhaustivity) Computer science : parallel algorithms, shared memory systems, PERT graphs, see 43] or 23]. Queueing theory : G=G=1=1 queue (see 5), queues in series, queues in series with blocking, fork-join networks 3]. Operations research and manufacturing : Job-shop models, event graphs (a subclass of Petri nets), see 17] 28] and 3]. Economy or control theory : dynamic optimization, see 46]. Physics of crystal structures : Frenkel-Kontorova model, see 24].

It is equivalent to say that T has a xed point in the projective space (see

	Proof. 1. A ) B. Let K be a compact of PR k such that (T(R k )) K. It implies that (T) : K ! K. Hence (T) is continuous on a compact and has a xed point by application of Brouwer's Theorem.
	2. B ) C. Let x 2 R k be a generalized xed point of T, i.e T(x) = 1+x. It implies T n (x) = n 1 + x and lim n T n (x)=n = ( ; : : : ; ) 0 . From Corollary 2.3, we have 8y 2 R k ; lim n T n (y)=n = ( ; : : : ; ) 0 .
	3. B 6 ) A and C 6 ) A. An easy counter-example is obtained by considering the identity operator I : R k ! R k ; I(x) = x.
	4. C 6 ) B There exist counter-examples of dimension 2, 27].	u t
	This Proposition has an interesting application for stochastic operators.
	Def. 2.7).
	Proposition 2.9. Let us consider T : R k ! R k a monotone-homogeneous operator. Let us consider the following assumptions. A. T is projectively bounded. B. T has a generalized xed point. C. 8x; lim n T n (x)=n = ( ; : : : ; ) 0 . The following implications hold : A ) B ) C. The other implications are false, C 6 ) B 6 ) A and C 6 ) A.

  . Function is monotone, homogeneous and separable.

	?3
					Z ?3;0]
		A ?3	?3	A ?2	A ?1 A 0
					Z ?4;0] > Z ?3;0]
					Z ?4;0]
	A ?4	A ?3	A ?2	A ?1 A 0

If one sees ( (:); (k; :); k > 1) as an operator: (R + ) N ! (R f1g) N the sequence fM(k)g being xed this is indeed non-expansiveness when taking a L 1 norm on (R + ) N and a L 1 norm on (R f1g) N .

It is more classical, but equivalent, to work with the workload variable W n = X 0;n] ? A n ? (n), yielding equation W n+1 = (W n + n ? n ) + .

The term stochastic refers here to the markovian interpretation of matrices P( ).According to our terminology, Equation (8.5) is that of a deterministic operator.

Acknowledgment The authors would like to point out the importance of the Idempotency workshop organized by Jeremy Gunawardena for the maturation of this paper. The second author would also like to thank Jean-Marc Vincent for fruitful discussions on the subject.

state space and with undiscounted rewards. A controller observes a system which evolves in a state space f1; : : : ; kg. The set of possible decisions for the controller is A. Under decision 2 A, the system evolves from a state i to a state j according to the transition probabilities p ij ( ). Also, under decision 2 A, there is an immediate reward for being originally in state i which is a i ( ). It is well known that the optimal decision and the reward vector are obtained as lim n T n (x), see for example 45], Chapter 3.2.

There is a very important literature on deterministic operators of type (8.5), see 40] or 45] and the references there. The next theorem is classical, for a proof see for example 45] Chapter 4.3. Theorem 8.3. Let T be an operator verifying Equation (8.5). A su cient condition for the existence of a unique generalized xed point for T is : 8 2 A, matrix P( ) is ergodic, i.e. the graph of the non-zero terms of P( ) is strongly connected and aperiodic. Remark 8.1. A (max,+) system can be viewed as a (max,+, ) system with A = f1; : : : ; kg and P( ) is de ned by P ij ( ) = 1 if j = and P ij ( ) = 0 otherwise. Such matrices do not verify the assumption of Theorem 8.3.

The theorems presented in this paper when coupled with results like Theorem 8.3, can be used in an e cient way for systems verifying (8.5) when the rewards a( ) and/or the transition matrices P( ) become random. The authors do not know of any reference on the subject.

Discrete event networks

We are now going to review some classes of discrete event networks. We restrict our attention to systems which can not be modeled as monotonehomogeneous operators. The references that are quoted are only the ones using the monotone separable framework or similar approaches. Let us detail two of these models. First we propose a simple example of precedence constraint system and second Jackson networks.

Precedence constraints models There is a stream of customers j(n); n 2 N. Each customer j(n) has a service time requirement t(n) and precedence constraints under the form of a list L(n) of customers. More precisely, we have L(n) = fj(i 1 ); j(i 2 ); : : : j(i l n )g with n > i 1 > i 2 > > i l n > 0. Job j n starts its execution as soon as all the customers of the list L(n) have completed their execution. The execution of customer j(n) takes t(n) units of time.

Let us distinguish two cases.

1. We assume that the length of the precedence list is uniformly bounded by k, i.e. 8n 2 N; l n 6 k. We de ne the vector x(n) 2 R k such that x(n) i is the instant of completion of customer j(n?i). From the dynamic described above, we have x(n + 1) = T n (x(n)), where the operator T n : R k ! R k is de ned as follows T n (x) 1 = max fi j j(n?i)2L(n)g x i + t(n) T n (x) i = x i?1 ; i = f2; : : : ; kg This operator is monotone homogeneous. It is in fact a (max,+) linear system, see 8.1.

2. Let us assume now that the length l n is not uniformly bounded. It is not possible to describe the system as an operator of nite dimension. Let X 1;n] be the last instant of completion of one of the customers j(i); i 2 f1; : : : ; ng.

It is easy to verify that X 1;n] veri es the properties of the monotoneseparable framework for discrete event networks, see 3.

In both cases, when ft(n); L(n); n 2 Ng forms a stationary ergodic sequence of random variables, we can apply the ergodic theorems presented in this paper.

Jackson networks A Jackson network (introduced in 29]

) is a queueing network with I nodes, where each node is a single server FIFO queue (cf 5).

Customers move from node to node in order to receive some service there. The data are (2I) sequences f i (n); n 2 Ng; f i (n); n 2 Ng; i 2 f1; : : : ; Ig; where i (n) 2 R + and i (n) 2 f1; : : : ; I; I + 1g.

In the nominal network, the n-th, n > 1, customer to be served by node i after the origin of time requires a service time i (n); after completion of its service there, it moves to node i (n), where I + 1 is the exit. We say that i (n) is the n-th routing variable on node i.

We are going to describe the closed (resp. open) Jackson network as a discrete event network (resp. open discrete event network), using the notations of 3.

1. Closed case: the state at the origin of time is that with all customers in node 1, and service 1 is just starting on node 1. There are no external arrivals and i (n) 2 f1; : : : ; Ig, for all i and n. The total number of customers in the network is then a constant. We take

The internal daters X i?

1;1] (n) and X i+ 1;1] (n), n > 1, i 2 f1; : : : ; Ig, are the initiation and completion instants of the n-th service on node i. We take

so that X ?

1;1] (1) = 0.

2. Open case: the state at the origin of time is that with all queues empty and a customer is just arriving in the network. There is an external arrival point process fA n ; n > 1g, with A 1 = 0, or equivalently an additional saturated node (numbered 0), which produces customers with inter-arrival times 0 (n) = A n+1 ? A n ; n > 1, regardless of the state of the network.

The n-th external arrival is routed to node 0 (n) 2 f1; : : : ; Ig. We take

We can extend the de nition of internal daters, which is the same as above, to i = 0 by taking X 0? 1

We take X ? 1;1] (n) def = X 0? 1;1] (n) ; so that X ? i (n) for all n > 1 and i 6 = 1 (resp: i 6 = 0); i (n) for all 1 6 n 6 m and i = 1 (resp: i = 0); 1 for all n > m and i = 1 (resp: i = 0):

The corresponding variables are denoted X ?

1;m] (n); X + 1;m] (n). In both cases, the maximal dater is de ned as

where the supremum bears on n > 1 and i 2 f1; : : : ; Ig (resp. i 2 f0; : : : ; Ig) in the closed (resp. open) case.

The following lemma follows from results proved in 2]. Lemma 8.4. For all i 2 f1; : : : ; Ig and l > 1, there exist nite sets A(i; l) N, B(i; l; p) N where p 2 A(i; l) and C(i; l; p; q) N N where q 2 B(i; l; p), which depend on the routing sequences only (not on the service sequences). These sets are such that 8m; n > 1; X i? 1;m] (n) = inf l2A(i;n) max p2B(i;n;l) X (i q ;n q )2C(i;n;l;p) i q 1;m] (n q ): (8.6)

A pair (i; n) appears at most once in each set C(i; n; l; p).

This lemma has to be interpreted as the fact that Jackson networks have a (min,max,+) structure, although a very complicated one. Hence, it should come as no surprise that they enter the monotone separable framework. Let us prove it.

Causality In both cases, the assumption is that X 1;m] is a.s. nite for all m. Note that this implies causality as de ned in 3. Lemma 8.5. Causality is satis ed whenever the routing sequences f i (n)g n2N are i.i.d. and independent of the service times, and the routing matrix P = (p ij ); p ij = P( i (1) = j); i; j 2 f1; : : : ; Ig is without capture in the open case, and irreducible in the closed case.

Proof. The proof is based on the following coupling idea: consider a Kelly network (i.e. a route is attached to a customer, see 31]) where the routes are independent and sampled according to the stopped Markov chain with transition matrix P. By this we mean that in the 1; m]-network, the route of the rst customer to leave node 1 (resp. 0) is fN 0 = 1; N 1 ; : : : ; N U 1 g in the closed case fN 0 = D; N 1 ; : : : ; N U I+1 g in the open case; where fN p g is a path of the Markov chain P, U i is the return time to state i, and D is an independent random variable on f1; : : : ; Ig, with distribution (i) = P( 0 (1) = i). The routes of the m rst customers to be served at node 1 (resp. to arrive from node 0) are assumed to be independent and identically distributed. In this Kelly network, the routes of these m customers are not a ected by the service times (in contrast with what happens in the initial network). Thus, in the closed (resp. open) case, all m customers eventually return to node 1 (resp. leave) provided P is irreducible (resp. P is without capture). In addition, such a Kelly network is identical in law to the 1; m] restriction of the original network. So P(X 1;m] < 1) = 1.

u

t

In what follows, we will adopt the assumptions of Lemma 8.5 and assume in addition that the service times are integrable.

Monotonicity As an immediate corollary of Lemma 8.4, for all xed routing sequences, for all m; n > 1 and i, the variable X i?

1;m] (n) (and therefore X i+ 1;m] (n) as well) is a monotone non-decreasing function of f j (n); j 2 2; : : : ; I]; n > 1; 1 (n); 1 6 n 6 mg (resp. f j (n); j 2 1; : : : ; I]; n > 1; 0 (n); 1 6 n 6 mg). This monotonicity extends to the maximal dater as well.

Non-expansiveness Let j 6 I and l > 1 be xed. Consider j (l) as a variable and all other service times as constants. Then, it follows from Lemma 8.4 that X i? 1;m] (n) is a (min; max) function of j (l). Thus non-expansiveness as de ned in 3 holds.

Separability Let ' i 1;m] = supfn > 1 j X i+ 1;m] (n) < 1g; m > 1; (the total number of events which ever complete on station i in the 1; m]-network). Of course ' 1 1;m] = m in the closed case, and ' 0 1;m] = m in the open case.

The following two properties hold:

1. For all i and m, ' i 1;m] does not depend on the ( nite) values of the variables f j (n); j 2 2; : : : ; I]; n > 1; 1 (n); 1 6 n 6 mg (resp. f j (n); j 2 1; : : : ; I]; n > 1; 0 (n); 1 6 n 6 mg) this follows from Lemma 8.4.

2. For all m > 1, the random variables f' i 1;m] ; i 6 Ig form a stopping time of the sequences f i (n); i 6 I; n > 1g in the sense that f' i 1;m] 6 n i ; i 6 Ig 2 Ff i (l); l 6 n i ; i 6 Ig; where F(u) denotes the -algebra generated by the random variable u. We are now in a position to complete the de nition of N = f (n); M(n); n 2 N g (see 3) for this network, by taking M(n) def = f i (l); i (l); l = ' i 1;n?1] + 1; : : : ; ' i 1;n] ; i 6 Ig; n > 1;

with the convention ' i 1;0] = 0.

With this de nition, the m; 1]-network, 1 6 m, is a Jackson network as de ned above, but with the driving sequences

From the i.i.d. assumptions on the sequences f i (n); i (n); n 2 Ng and the fact that the r. v. ' i 1;m?1] are stopping times, we obtain that the m; 1]network is equal in distribution to the original 1; 1]-network. Separability is now clear:

Open case: if A l+1 > A 1 + X 1;l] , then from monotonicity, for all i, A l+1 > A 1 + X i+ 1;l] (' i 1;l] ) > A 1 + X i+ 1;n] (' i 1;l] ); and so, the (l + 1)-st external arrival nds an empty network (we know that if there are l external arrivals and ' i 1;l] departures from node i, then the network is empty). In addition, the next customer to be served on node i is that with index ' i 1;l] + 1, i 6 I. Thus A 1 + X 1;m] = A l+1 + X l+1;m] .

Closed case: if X + 1;m] (l + 1) > X 1;l] , then X + 1;m] (l + 1) > X i+ 1;l] (' i 1;l] ) > X i+ 1;m] (' i 1;l] ); and so, by the same argument as above, when the (l +1)-st service ends on node 1, all customers are present in node 1. Separability follows in a way which is similar to that of the previous case.

First order ergodic theorem

Compatibility is immediate from Property 2 of f' i 1;m] g. To prove Integrability, it is enough to prove that X 1;1] is integrable. This follows from the fact that the stopping times U 1 (resp. U I+1 ) of P are integrable and from the assumption that service times are integrable. Therefore, Theorem 3.2 applies and lim m!1 X 1;m] m = ; a:s:

for some positive and nite constant, both in the open and closed case. More generally, it can be shown that the above limit implies that there exist nite constants rates i such that lim X i?

1;m] m = i ; a:s:; i 6 I;

both in the open and closed cases. For more details on the computation of these rates see 4] and 7].


Edouard Cavène

Sébastien Durif

Abdelhamid Bouchaïr

Evelyne Toussaint

Experimental study of cover-plate bolted joints with large or slotted holes

Keywords: experimental tests, cover-plate joints, grid method, numerical model, Eurocode 3

Connections in steel structures are of main importance in the design process. Cover-plate connections with circular or slotted holes are of common use in steel structures. The behavior of such connections is characterized by various failure modes. Bearing mode is one of the most complex due to the distribution of stresses and strain around the loaded holes. This paper deals with the characterization of the behavior of cover-plate bolted joints with slotted holes. Numerical simulations using the Cast3M FE package are performed in association with an original experimental method based on full-field measurements. The strain fields obtained with these methods (grid method and Digital Image Correlation (DIC)) give the possibility to observe the evolution of the local deformations in the loaded zones of the connections. These evolutions are compared to those given by the Finite Element model for each configuration at different loadings stages. Thus, the experimental results are used to validate the numerical model. The comparisons are based on the load-displacement curves, the failure modes and the local deformations in the zones around the bolts holes. Six different geometrical parameters of the holes and their positions are considered in the tests. The validated numerical model is used to evaluate the influences of the dimensions of the slotted hole. The results showed that the geometry has a significant influence on the failure mode of the connections such as net section and bearing. Both numerical and experimental results are compared to those given by the analytical approach of Eurocode 3 to evaluate the accuracy of the analytical prediction. The study shows the influence of various geometrical parameters on the resistance and the failure mode of the connections with slotted holes. The strain fields obtained with the grid method and DIC are observed in the plate around the bolt in the elastic and plastic phases. They give the possibility to observe experimentally the evolution of strains in a wide area of the most stressed zones in order to develop more accurate analytical models based on experimental evolutions of strains.

INTRODUCTION

The slotted holes are often used in structure to allow displacements along a direction to control the transfer of forces between structural elements or to avoid thermal expansion or limit the effects of dynamic load [START_REF] Law | Analytical model of a slotted bolted connection element and its behaviour under dynamic load[END_REF]. Indeed, if the direction of the hole is parallel to the load, the mobilization of friction along the hole dissipates a part of the energy due to horizontal seismic load. The paper [START_REF] Law | Analytical model of a slotted bolted connection element and its behaviour under dynamic load[END_REF] proposes an analytical model to quantify the energy dissipation. However, slotted hole can be used to allow displacement along the perpendicular direction of the hole. In civil engineering, this solution is present to connect steel structures with glasses structure for example. In this case, the load is perpendicular to the direction of the hole. A lack of studies concerns this behavior on steel plates. A study is presented on cover-plate connection with slotted hole in [START_REF] Wald | Stiffness of cover plate connections with slotted holes[END_REF]. In the present work, the behavior is compared to finite element method results and the experimental behavior is measured by full field measurement. Moreover, Eurocode presents limited information concerning the bolted connections with slotted holes. The aim of this study is to characterize the connections with slotted holes, using both numerical simulation and experimental analysis. An attention on the geometry of the connection is an important part of the work in the same spirit of work made on circular hole [3] [4].

Firstly, the present paper describes the test set up and the different tested geometrical configuration. When the support of the present work is defined, the analytical model proposed by EC3 bring a first values of strength. Then a numerical model is developed and allows to characterize the behavior for the connections. Finally, an experimental study is performed and result in term of strain fields and strengths and compared to both analytical and numerical results.

GEOMETRY AND MATERIAL SPECIFICATIONS

Geometry

Three configurations have been tested. These configurations have been designed with dimensions apart from Eurocode design recommendations, EN-1993-1-8 (see Table 1). Indeed, the end distance (e 3 ) is lower than the recommended values, however, no limitation are defined in the Eurocode. Besides, among the three specimens, two have a shifted hole regarding the axis of the plate.

The corresponding geometrical characteristics of the three tested configurationsE1, E2 and E3 are defined in Fig. 1 and2. To represent various situations which can be present in the practice, the plates are designed with shifted hole to allow observing the behavior of the connection with slotted hole and load not applied in the center of the hole.

Material specifications

Specimens were taken from flat plate of 6mm thickness made of S235 steel grade. The real values obtained from tensile tests are 290 MPa and 380MPa respectively for the yield stress and maximal stress value. The strain at failure is about of 30%. The corresponding stress-strain curve is represented in Fig. 3.

Analytical strength

All the specimens are characterized by a large edge distance (e 4 in Fig. 1) compared to end distance (e 3 ). This choice is done to avoid a failure mode in the net section. Thus the expected failure mode is bearing. Indeed, in comparison to net section strength, the bearing strength is rather complex to define. The analytical model presented in Eurocode 3 [reference] to predict the bearing strength does not consider the hole length.

In Eurocode 3, the failure modes to be considered for the plate are the net-section and bearing. For the bolt, the failure mode is shearing. The three corresponding strengths, according to the table 3.4 in EC3-1.8 are given in Table 3 with : f u : ultimate strength of the steel plate f ub : ultimate strength of the bolt t : thicnss of the plate d : diameter of the bolt : coefficients depending on various parameters given in Eurocode. : net section of the bolt.

Failure mode Formula

Bearing Shearing Net-section

In Table 3, represents the, when is the thickness of the plate and the diameter of the bolt. The bearing strength, given for bolts in normal circulaire holes, has to be reduced by about 40% when direction of the force transfer is perpendicular to the longitudinal axis of the slotted hole. Consequently, a coefficient of 0.6 has to be applied to . Besides, the eccentricity of the effort with regards to the center of the hole is not considered in the formulas proposed by Eurocode 3. The standard defines the edge dimension (e 4 ) for slotted hole as the smallest dimension between each side of the hole. The determination of the strength is done considering and because for E2 the bolt is positioned at the opposite side of the hole with . Because of that, using this geometrical characteristic seems to be questionable. The strains are going to be concentrated near the contact point between the bolt and the hole edge. So, could be more representative of the experimental behavior. Concerning the net section strength, values for specimens E1 to E3 are given in Table 5. The failure mode of the bolt is shearing. Concerning the shearing strength is a constant and its value is equal to 49 kN with a M12 bolt of grade 12.9. Comparing strength values, the maximum is obtained for the shearing or net section mode, depending on the specimen studied. The bearing mode presents the lowest values of strength for all the specimens. It is the predominant failure mode. Cover-plates connections was designed to favor this behavior. The values of strength given in Table 4 and Table 5 are out of the framework of the standard because of the end distance that is lower than 1.5d 0 . However, it is interesting to confront these analytical values to those obtained from experimental tests in Table 6.

NUMERICAL SIMULATION

Model

A finite element model has been developed using the FEM software CAST3M with 2D triangular linear elements and contact elements (IMPO operator) with friction. All plates were modeled considering elastoplastic behavior with isotropic hardening. The stress-strain curve used to model the plates is presented in Fig. 4. The mechanical model of the bolt is considered elastic with a Young modulus of 210 GPa.

The plate is submitted to an axial tension by imposed displacement while the bolt is fixed (see Fig. 5). The contact between bolt and plate is set with specifics elements. These finite elements manage the non-linearity of the contact. A suitable mesh is set to have the best compromise between convergence and time [START_REF] Champaney | Une nouvelle approche modulaire pour l'analyse d'assemblages de structures tridimensionnelles[END_REF]. The model is presented in Fig. 5.

Uniaxial tension tests

Tension tests were performed using a ± 200kN Zwick testing machine. The tests were displacement controlled with a cross-head speed of the machine equal to 0.04mm/s. Each geometric configuration was tested with two specimens.

Instruments

A connection was necessary to perform the test. It induces displacements that are not representative of the displacement of the specimen. Clearance take-up should be taken into account correct this artefact. Consequently, the displacement of the grip cannot be used to characterize the connection. That is why a displacement sensor was used to record the relative displacement (see Fig. 6.a).

Fig. 6. Setting system a) back view b) front view

The distance d has been chosen to be coherent with the global displacement imposed in the numerical model. By this way, both numerical and experimental global behaviors can be compared.

Digital image correlation

Heterogeneous strain fields are expected around the bolt due to local transfer mechanics. On the present work, Digital Image Correlation (DIC) method [START_REF] Hild | Digital image correlation: from displacement measurement to identification of elastic properties-a review[END_REF] is used as a noncontact method to detect and quantify displacement and strain field that occurs in the tested specimens. Another noncontact measurement method used in a previous experimental campaign [START_REF] Champaney | Une nouvelle approche modulaire pour l'analyse d'assemblages de structures tridimensionnelles[END_REF], with accurate results, could be used to obtain local deformations of specimen using grid method [START_REF] Toussaint | Strain measurements and analyses around the bolt holes of structural steel plate connections using full-field measurements[END_REF]. However, as the strain levels induced around the slotted hole are high, DIC method was chosen. DIC consists in comparing reference image and a deformed one.

Ncorr software [START_REF] Pan | A fast digital image correlation method for deformation measurement[END_REF] is used in the present study. Displacement and strain values are calculated at the center of each zone of interest . The grid step is about of 5 pixels. For that purpose, for the loaded specimen, a speckle pattern is painted on the surface of the specimen. This pattern is presented in Fig. 7 a). The corresponding histogram of grey level is also presented in Fig. 7 b). It is important for a good correlation between images to maximize the dynamic of the camera but avoiding grey level saturation. The camera employed here is a PCO2000 camera. It features a 16-bit CCD sensor and is equipped with a 105mm lens. The surface was illuminated using a cold light source that provides a quasi-uniform lighting of the surface with good contrast. The camera captures 0.91 frame/s.

RESULTS AND DISCUSSION

Global behavior

Force-displacement numerical curves of E1, E2 and E3 specimens given by the numerical model are shown in Fig. 8. Experimental force-displacement curves. The three curves present two phases. The first phase corresponds to the elastic behavior of the connection. The second is due to the appearance of plastic deformation on the both sides of the end dimension. Moreover, the curve corresponding to specimen E1 presents an inflexion point corresponding to a third behavior at the end of the curve. The necking in the plate around the contact point with the bolt induces a loss of strength before failure but the parameters of the model do not take account of it. Figure Fig. 8 give the load-displacement curves for the three configurations, obtained with both experimental (continue lines) and numerical results (dote lines).

Fig. 8. Experimental force-displacement curves

The experimental displacement corresponds to the elongation of distance "d" in Fig. 6. It can be seen in Fig. 8 that numerical and experimental curves show similar tendency, mainly for the two phases (elastic and plastic). However, some differences can be observed. The first change in slope in experimental curves is due to clearance take-up in the system. That is why it can not be seen on numerical results. Moreover, a difference between the strength at the beginning of plastic behavior of the connection for numerical and experimental curves is present. Experimental values are higher than numerical ones. It can be due to concentration of stress in numerical model.

Local results

Strain gradients are concentrated in the loaded zone of the plate under the hole (Fig. 9). The tendency of strain distributions are similar comparing experimental and numerical strain maps for the specimens E1 and E3. However, some large differences are observed in term of strain values for the specimen E2. Gradient numerical strain values are higher for the E1 and E3 specimens. It may be explained by the fact that the finite element model is a 2D model. Because of that, it presents a concentration of the strain on a few elements. The diffusion of the stress is not as important as the experimental model. Strain localization between numerical and experimental maps are similar. However, the maximum values present an important differential. Concerning E2, all the strain and the stress are concentrated on the side of the hole. The 2D model presents its limits in that situation. A 3D model is in progress to improve the diffusion of the stress in numerical results.

Experimental strength

Experimental results allow to obtain the strength values for each specimen. Values are given in Table 6. They correspond to the average of two values obtained with the two specimens tested for each specimen.

CONCLUSION

The study presented in this paper shows that Eurocode is conservative. It has been shown that the location of the bolt in the hole has an impact on the strength value. This is not considered in the available analytical approaches. Some differences between numerical and experimental global load-displacement curves have been observed. The stress distribution at the contact surface may be one of the explanation of these differences. A 3D numerical model should confirm the hypothesis. Finally, full field measurement technique allows to clearly visualize strain gradients around the bolt and to obtain both qualitative and quantitative information at each stage of the loading. They are also of great importance to improve a numerical model.

Fig. 1 .Fig. 2 .

 12 Fig. 1. Geometrical specifications of an slotted hole (EN1993-1-8)

Fig. 3 .

 3 Fig. 3. Tension curve of steel

Fig. 4 .

 4 Fig. 4. Stress-strain curve used in the model (steel plate)

Fig. 5 .

 5 Fig. 5. Finite element model of specimen E1

Fig. 7 .

 7 Fig. 7. a) Speckle pattern on E1 b) corresponding grey level histogram

Fig. 9 .Fig. 11 .Fig. 12 .

 91112 Fig. 9. Strain map a)  xx on E1 b)  xx on E2 c)  xx on E3For all the specimens E1 and E3, plastic deformation is localized in the zones represented by the points (A, B, E, F points) appear on both sides of the hole. The shifting of the bolt induces an asymmetry of the strain distribution around the hole. Due to the shifting of the bolt for specimen E2, a large strain zone is visible in  xx map (see point C, Fig.9). Concerning specimen E2, the bolt is pressed down on the side of the hole. Because of that, the shearing is very important around point C. In this case, the flexion of the end distance of the plate develops a plastic hinging point at the opposite hole's side of the contact point (point D).

Table 1 .

 1 Geometrical limits of the Eurocode

	Dimension	Minimum
	End-plate dimension
	Transversal-plate dimension

Table 2 .

 2 Geometrical characteristics of specimens

	Specimens	Length hole (mm)
	E1	13	13	26	26
	E2	19.5	13	13	32.5
	E3	19.5	13	19.5	26

Table 3 .

 3 Strength formula

Table 4 .

 4 Values of strength in bearing mode

			(kN) with coefficient 0.6		(kN) without coefficient 0.6
	Specimen
	E1		11		18
	E2	5	11	8	18
	E3	11	11	18	18

Table 5 .

 5 Values of strength in net-section mode

	Failure mode	Net-section (kN)
	E1	64
	E2	21
	E3	43

Table 6 .

 6 Experimental values of strengthComparing these values to the analytical ones (Eurocode) allows to conclude that values are similar if analytical values without 0.6 coefficient are taken into account. The maximum differential of about 24% is obtained for specimen E1 while a difference of about 3.4% and 5% is obtained for specimens E2 and E3 respectively.

	Specimen	Strength (kN)
	E1	24,20 ± 0.1
	E2	18,95 ± 0.43
	E3	19,14 ± 0.05

ACKNOWLEDGEMENT :

The authors are grateful to the AUGC: « Association Universitaire de Génie Civil » for its financial support.


B Odounga

R Moutou Pitti
email: rostand.moutou_pitti@uca.fr

E Toussaint

M Grédiac

STUDYING THE FRACTURE OF TROPICAL WOOD SPECIES WITH THE GRID METHOD

Keywords: Crack growth, fracture mechanics, grid method, tropical wood species, compliance method

The present study consists in studying the initiation and propagation of cracks at room temperature of three tropical species: Okume (Aucoumea Klaineana), Iroko (Pterocarpus Soyauxii) and Padouk (Malicia Excelsa). A short review of the literature shows that only few studies dealing with the fracture mechanics properties of this type of wood species are available. Similar studies are however routinely performed on temperate wood species such as Beech and Douglas, using mixed-mode crack growth (MMCG) specimens for instance [START_REF] Pitti | Mixed mode fracture separation in viscoelastic orthotropic media: numerical and analytical approach by the Mtv-integral[END_REF][START_REF] Pitti | On a specimen providing stable mixed mode crack growth in wooden material. Original Research Article[END_REF]. In this paper, tropical wood specimens are studied using the grid method [START_REF] Grédiac | The Grid Method for In-plane Displacement and Strain Measurement: A Review and Analysis[END_REF] and such MMCG specimens, but made of the three aforementioned tropical species. This paper describes the wood specimens, which are subjected to an opening mode, the experimental device and the background of the grid technique used for tracking the location of the crack tip during the test. The origin and characteristics of the tropical wood species studied here are also given. The experimental results are given and compared in terms of force-displacement curves, but also in terms of energy release rate -crack length curves.

Typical MMCG specimens made of each of the three different species are shown in Figure 1. The main difference between the three species is their density: Okume (density = 0.44) is less dense than Iroko (density = 0.64) and Padouk (density = 0.79). For all the specimens, the initial crack length is the same: a=20 mm. It is located at mid-height and oriented along the fiber direction, which is horizontal here. The initial crack is completed by a notch (length: 2 mm) made with a cutter in order to initiate correctly crack propagation. A grid, with a regular pitch of 200 microns, was transferred on one face of the specimens, see Figure 1 (d). The technique presented in [START_REF] Piro | Producing and transferring low-spatial-frequency grids for measuring displacement fields with moiré and grid methods[END_REF] is used for this purpose. The experimental device is shown in Figure 2. A 200 kN Zwick / Roel testing machine was used for the tests. A camera was fixed on a tripod at a distance of 67.5 cm from the specimens in order to take images of the grid during the tests. A small sized steel Arcan fixture was used to load the specimens. The lower part was fixed and the upper part was subjected to an imposed displacement. The testing machine was equipped with a force transducer in order to obtain the force-displacement curves, the displacement being obtained with the full-field measurements. The cross-head speed was 0.005 mm/s, and the acquisition rate of the camera was 1.35 frames/second. The specimens were illuminated by three flexible optical arms powered by a cold light source KL 2500 LCD. A SIGMA 105 mm objective was mounted on the camera. To minimize image noise, each image was averaged over 8 frames.

Two specimens per specie were tested. Figure 3 (a) shows the force-displacement curves obtained for the three species, thus for the 6 tested specimens. Although the curves are somewhat scattered, a clear trend appears. Indeed, there is a link between force at failure and density. For Okume the mean force at failure is nearly 𝐹 "($%&'() = 600 𝑁, causing an opening of the crack 𝑑 $%&'( = 0.035 𝑚𝑚. For Iroko this mean value is a slightly greater since 𝐹 "(456%6) = 1000 𝑁, with 𝑑 456%6 = 0.034 𝑚𝑚. For Padouk, we have 𝐹 "(9:;6&%) = 1400 𝑁 and 𝑑 9:;6&% = 0.031 𝑚𝑚. The results obtained during these tests were then used in order to obtain the critical energy release rate G, which writes as follows:

𝐺 = = > ? @ A•C • ∆E ∆: ; (1)
where 𝐹 E is the so-called critical force corresponding to an increase da of the crack length 𝑎, 𝑏 is the thickness of the specimen. 𝐶 = 𝑈/𝐹 is the compliance, where 𝑈 is the crack opening, and ∆𝐶 is the increase in compliance between after and before the crack length has increased by a quantity denoted ∆𝑎. Figure 3 (a) shows the value of F as a function of the crack opening U obtained by the grid method. Figure 3 (b) shows the value of G as a function of the length of crack a. The first values of G, which induce the onset of crack propagation in the material, confirm the impact of density on the fracture for the three tropical species. Much more energy is needed to initiate a crack propagation in Iroko than in Okume and still more in Padouk. Indeed, the average of G of the two test pieces of each tested of the species showed that the initiation of a crack propagation in Okume requires an energy equal to 𝐺 = 6 𝐽/𝑚 A . For Iroko, this value is 𝐺 = 14 𝐽/𝑚 A and for Padouk, 𝐺 = 15 𝐽/𝑚 A . When we consider the mean of the extreme G values, let us say to failure, we observe that the difference between the three species is no longer significant. Therefore the effect of the density is no longer observable. They revolve around 𝐺 = 350 𝐽/𝑚 A .

Tests were carried out on three tropical species: Okume, Iroko and Padouk. The grid method was applied in order to track the crack tip during the test performed in opening mode. The results showed the influence of the density on the identified fracture parameters, since the denser the material, the greater the force at failure. These results also highlight the influence of the density on the energy which is necessary to initiate the propagation of the crack in these wood species. Indeed, we observed that the first value initiating the propagation of the crack increases with the density.

Figure 1 .

 1 Figure 1. Wooden specimens: Okume (a), Iroko (b), Padouk (c) and the specimen Iroko equipped grid (d).

Figure 2 :

 2 Figure 2: Experimental device

Figure 3 .

 3 Figure 3. Force-crack opening curves (a), evolution of G vs. crack length a (b) for the three woods species.