Florian Simatos
email: florian.simatos@inria.fr

Danielle Tibi
email: danielle.tibi@math.jussieu.fr

SPATIAL HOMOGENIZATION IN A STOCHASTIC NETWORK WITH MOBILITY

Keywords: July 8, 2008 Fluid limits, multiple time scales, transient behavior, stability

A stochastic model for a mobile network is studied. Users enter the network, and then perform independent Markovian routes between nodes, where they receive service according to the Processor-Sharing policy. Once their service requirement is satisfied, they leave the system. The stability region is identified via a fluid limit approach, and strongly relies on a "spatial homogenization" property: At the fluid level, customers are instantaneously distributed across the network according to the stationary distribution of their Markovian dynamics and stay distributed as such as long as the network is not empty. In the unstable regime, spatial homogenization almost surely holds asymptotically as time goes to infinity (on the normal scale), telling how the system fills up. One of the technical achievements of the paper is the construction of a family of martingales associated to the multidimensional process of interest, which makes it possible to get crucial estimates for certain exit times.

Introduction

Recent wireless technologies have triggered interest in a new class of stochastic networks, called mobile networks in the technical literature [START_REF] Borst | Capacity of wireless data networks with intra-and inter-cell mobility[END_REF][START_REF] Grossglauser | Mobility increases the capacity of ad-hoc wireless networks[END_REF]. In contrast with Jackson networks where users move upon completion of service at some node, in these mobile networks, transitions of customers within the network occur independently of the service received. Moreover, at any given time, each node capacity is divided between the users present, whose service rate thus depends on the capacity and on the state of occupancy of the node. Once his initial service requirement has been fulfilled, a customer definitively leaves the network. In [START_REF] Borst | Capacity of wireless data networks with intra-and inter-cell mobility[END_REF], complex capacity sharing policies are considered, but in the simplest setting, which will be of interest to us, nodes implement the Processor-Sharing discipline by dividing their capacity equally between all the users present. Previous works [START_REF] Borst | Capacity of wireless data networks with intra-and inter-cell mobility[END_REF][START_REF] Grossglauser | Mobility increases the capacity of ad-hoc wireless networks[END_REF] have mainly focused on determining the stability region of such networks, and it has been commonly observed that the users' mobility represents an opportunity for the network to increase this region. Indeed, because of their mobility, users offer a diversity of channel conditions to the base stations (in charge of allocating the resources of the nodes), thus allowing them to select the users in the most favorable state. Such a scheduling strategy is sometimes referred to as an opportunistic scheduling strategy, see [START_REF] Borst | User level performance of channel-aware scheduling algorithms in wireless data networks[END_REF] and the references therein for more details.

In the present paper, we investigate from a mathematical standpoint a basic Markovian model for a mobile network, derived from [START_REF] Borst | Capacity of wireless data networks with intra-and inter-cell mobility[END_REF]. In this simple setting, customers arrive in the network according to a Poisson process with intensity λ, and move independently within the network, according to some Markovian dynamics with a common rate matrix Q. Service requirements are exponentially distributed with mean 1, and customers are served at each node they visit according to the Processor-Sharing discipline, until their demand has been satisfied. The total capacity of the network, defined as the sum of all the individual capacities of the nodes, is denoted by µ. It corresponds to the instantaneous output rate of the network when no node is empty, i.e., when there is at least one customer at each node.

It is of particular interest to note that, even if Q is reversible, because of the arrival and departure processes, the system is not reversible. This contrasts with earlier works in which particle systems with similar dynamics have been investigated under reversibility assumptions. In [START_REF] Caputo | Entropy dissipation estimates in a zero-range dynamics[END_REF], the authors look at a closed system (i.e., with parameters λ = µ = 0) where transition rates are chosen such as to yield a reversible dynamics. In this case, the stationary distribution of the system has a product form, and the authors are interested in showing that the convergence to equilibrium is exponentially fast. Their approach essentially relies on logarithmic Sobolev type inequalities.

In our case however, a different set of questions is addressed, involving different tools. Since the system under consideration is open, it may be unstable, so that the first issue is to determine the stability region. We prove, as was conjectured in [START_REF] Borst | Capacity of wireless data networks with intra-and inter-cell mobility[END_REF], that the intuitive, simple condition λ < µ is indeed the stability condition (the critical case λ = µ is not considered). In contrast with Jackson networks for which the stability condition is local, in the sense that each node has to satisfy some constraint, here only the global quantities λ and µ matter. This shows that mobility allows to make the most of the potential service capacity of the network, corroborating the results previously mentioned. Note that λ < µ being a necessary condition is obvious, since µ is the maximal output rate. But surprisingly, proving that it is sufficient requires very technical tools, among which the use of fluid limits and martingale techniques. In particular, the long and tedious Appendix A is solely devoted to the construction of a martingale which provides key estimates for showing that λ < µ corresponds to a stable system. This martingale is a multidimensional (therefore complicated) generalization of the martingale built in [START_REF] Fricker | On the rates of convergence of Erlang's model[END_REF] for the M/M/∞ queue, and this is not completely surprising, since as will be seen, the model inherits salient properties of the M/M/∞ queue. Besides, the construction of a martingale associated to a multidimensional process represents one of the technical achievements of this paper: such examples are indeed pretty scarce in the literature. Similarly as in [START_REF] Fricker | On the rates of convergence of Erlang's model[END_REF], the approach relies on building a family of space-time harmonic functions indexed by some parameter c ∈ Ê n , and then on integrating over c in such a way as to preserve the harmonic property.

Through studying both the stability region and the unstable regime, a detailed description of the behavior of the system is given, resulting in two versions (stable and unstable) of the following rough property: When many users are present in the network, they get approximately distributed among the nodes according to the unique invariant distribution π associated to Q, the latter being assumed irreducible. It must be emphasized that yet, contrary to [START_REF] Borst | Capacity of wireless data networks with intra-and inter-cell mobility[END_REF], customers' movements are not assumed stationary.

As a first argument for this spatial homogenization, the law of large numbers suggests that, when the total number of users initially present in the network is large, the proportions of users at the different nodes should be close to π after some time, related to the convergence to π of the Markov process associated to Q. The more delicate question, that next arises, of how long these proportions stay close to π constitutes the main challenging issue of the paper, that requires martingale techniques for estimating the deviation time from π.

The short term reach of π is understandable from an analogy with the M/M/∞ queue: indeed, independence of the customers' trajectories yields that, similarly to the M/M/∞ queue, the output rate from any node due to inner transitions is directly proportional, through Q, to the number of customers at this node. When the network is overloaded, the relative occupancies of the nodes should then, after a while, be close to the internal traffic balance ratios, given by π.

A more explicit analogy with another classical queueing model is provided by the following simple but crucial observation: As long as no node is empty, the total number of customers simply evolves as an M/M/1 queue with input rate λ and output rate µ. And this is in particular the case when the distribution of customers is close to π. This interplay between, on one hand the proportions of customers at the different nodes, and on the other hand their total number, will underly the analysis all along the paper.

While the short term behavior, which results in the spreading of customers according to π, is dominated by the M/M/∞ dynamics, the long term behavior is essentially driven by the M/M/1 dynamics of the total number of customers. This naturally suggests that two different scalings have to be considered: one, corresponding to the M/M/∞ dynamics, where only space is scaled, and not time; and a second one, where both space and time are scaled, corresponding to the fluid scaling of the M/M/1 queue. Note that the natural scaling for the M/M/∞ queue is the so-called Kelly scaling, in which space and input rate are scaled. Here, since the input rate at each node due to inner transitions is a linear function of the numbers of customers at the different nodes, there is no need to scale the external input rate λ. Inner movements dominate the dynamics and the space scaled process converges, analogously to the M/M/∞ queue under Kelly's scaling, to some deterministic trajectory, with limit point at infinity here given by π.

The coexistence of these two different scalings makes the use of fluid limits both original and challenging. Fluid limits are a standard tool in the analysis of complicated stochastic networks. Rybko and Stolyar [START_REF] Rybko | On the ergodicity of random processes that describe the functioning of open queueing networks[END_REF] is one of the first papers using this technique together with Dai [START_REF] Dai | On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models[END_REF]. Dupuis and Williams [START_REF] Dupuis | Lyapounov functions for semimartingale reflecting Brownian motions[END_REF] presented similar ideas in the context of diffusions. In a series of papers Bramson [START_REF] Bramson | Convergence to equilibria for fluid models of FIFO queueing networks[END_REF][START_REF] Bramson | Convergence to equilibria for fluid models of head-of-the-line proportional processor sharing queueing networks[END_REF] describes the precise evolution of fluid limits for various queueing networks. See also the books by Chen and Yao [START_REF] Chen | Fundamentals of queueing networks[END_REF] and Robert [START_REF] Robert | Stochastic Networks and Queues[END_REF]. In the context of networks, fluid limits have been used mainly for Markov processes which behave locally as random walks. For this reason, results related to fluid limits are sometimes presented as functional laws of large numbers. Because of the mixture of two different dynamics, given by the M/M/1 and M/M/∞ models, our framework is somewhat different. A second important difference with the existing literature concerns tightness results which are usually easy to obtain, mainly because transition rates are generally bounded: this not the case here.

The long term analysis is twofold. Deriving fluid limits requires a control on the process over time periods of the same order as the initial number of customers (since the fluid scaling parameter is the same for time and space). In the stable case this is obtained by showing that the deviation time from π is essentially larger than the time for the underlying M/M/1 queue to empty. The unstable case exhibits a more striking behavior: the deviation time from π is not only large compared to the initial number of customers, but is even infinite with high probability. This amounts to a control of the whole trajectory: the distribution of users among nodes stays trapped in any neighborhood of π with high probability as the initial state is large. This result is related to a strong convergence result stating that, for any fixed (non scaled) initial state, the system almost surely diverges along the direction of π. Note that a similar phenomenon has been exhibited in [START_REF] Borst | User level performance of channel-aware scheduling algorithms in wireless data networks[END_REF], in the context of branching Markov chains, i.e., Galton-Watson branching processes where individuals located at some countable set of sites move at their birth time.

These various remarks and outline of results lead to the following organization for the paper. Section 2 gives a precise description of the stochastic model and introduces the notations that will hold throughout the paper. We have already mentioned the construction of a martingale which gives important estimates through optional stopping techniques: Section 3 introduces this martingale, and provides the main estimate that will be used. Due to its technicality, the construction of the martingale is postponed to Appendix A.

Section 4 establishes a decomposition of the process as, mainly, the difference between two processes of the same type but with no departures. For such a process (with null service capacity), a representation involving labelled particles is given. Both representations will help derive the almost sure convergence result of Section 6.

The three last sections are devoted to analyzing the behavior of the system. Section 5 deals with the short term behavior, thus studying the only space renormalized process. Section 6 studies the supercritical case λ > µ, establishing among other results the almost sure convergence of the proportions to the equilibrium distribution π as t → ∞. Finally, Section 7 proves the stability of the system in the subcritical case λ < µ.

Framework and notations

This section gives a precise description of the model under consideration and introduces the main notations. The network is described by a Markov process X = (X(t), t ≥ 0) characterized by its infinitesimal generator, given by (1) below. Section 6 will make use, in the particular case of null service capacity, of a more explicit representation of X involving a sequence of Markov jump processes that represent the trajectories of the successive customers entering the network. The general description of the system through its Markovian dynamics provided in the present section is however sufficient for most results of the paper, especially for building a family of martingales and for determining the stability condition.

The network consists of n nodes between which customers perform independent (continuous time) Markovian routes during their service. In this setting, transitions of customers from one node to another are driven by some rate matrix Q = (q ij , 1 ≤ i, j ≤ n) and are thus not triggered by service completion.

New customers arrive at node i = 1, . . . , n according to a Poisson process with intensity λ i ≥ 0, and then move independently according to the Markovian dynamics defined by Q. The arrival processes at the different nodes are independent, so that the global arrival process is Poisson with intensity λ = n 1 λ i . The case λ = 0 corresponds to a system with only initial customers, and no new arrivals.

Upon arrival, or at time t = 0 for those initially present, customers generate a service requirement which is exponentially distributed with mean 1. All service requirements, arrival processes and Markovian routes are assumed to be mutually independent.

Node i, 1 ≤ i ≤ n, has service capacity µ i ≥ 0, which is divided at any time between the customers present, according to the Processor-Sharing discipline: If N is the number of customers present at node i, then each of these N customers is served at rate µ i /N . The service rate of a given customer thus evolves in time, depending on his current position and on its occupancy level. Once a customer has received a service that meets his initial requirement, he leaves the network.

The total service capacity of the network is defined as µ = n 1 µ i . Notice that, due to the exponential nature of the services, the mechanism of departure from one node by completion of service does not distinghish the present Processor-Sharing discipline from the FIFO discipline: the instantaneous output rate from the system at node i is µ i provided that node i is not vacant. The total output rate is then µ when no node is empty.

The process of interest is X = (X(t), t ≥ 0) defined by

X(t) = (X 1 (t), . . . , X n (t)), t ≥ 0,
where X i (t), for i = 1, . . . , n, is the number of customers present at node i at time t. The Markovian nature of the movements together with the exponential assumption for the service distribution imply that X is a Markov process in AE n with infinitesimal generator Ω given, for any function f : AE n → Ê and any x = (x 1 , . . . , x n ) ∈ AE n , by

(1) Ω(f )(x) = n i=1 λ i f (x + e i ) -f (x) + n i=1 ½ {xi>0} µ i f (x -e i ) -f (x) + 1≤i =j≤n q ij x i f (x + e j -e i ) -f (x) ,
where e i ∈ AE n has all coordinates equal to 0, except for the ith one, equal to 1.

The introduction has highlighted that this system is a mixture of two classical models in queueing theory, the M/M/1 and the M/M/∞ queues. This is readable in the expression of the generator given in [START_REF] Borst | User level performance of channel-aware scheduling algorithms in wireless data networks[END_REF], where the two first sums are reminiscent of the M/M/1 queue, and the last one of the M/M/∞ queue.

The rate matrix Q is assumed to be irreducible, admitting π = (π i , 1 ≤ i ≤ n) as its unique stationary distribution, characterized by the relation

πQ = 0.
For technical reasons related to the construction of the martingale introduced in Section 3 (see Appendix A), we require the additional assumption that Q is diagonalizable. This assumption is satisfied if Q is reversible with respect to π, but it is in general a much less restrictive constraint.

For any t ≥ 0, the random vector X(t) will often be described in terms of the total number of customers L(t) and the proportions of customers at the different nodes χ(t) = (χ i (t), 1 ≤ i ≤ n). More formally, define

L(t) = n j=1 X j (t) = |X(t)| and χ i (t) = X i (t) L(t) , 1 ≤ i ≤ n, t ≥ 0,
with the convention that χ(t) = e 1 when L(t) = 0. Here, and more generally for

any x = (x 1 , . . . , x n ) ∈ Ê n , |x| denotes the ℓ 1 norm in Ê n : |x| = n 1 |x i |.
The vector χ(t) can be identified with a probability measure on {1, . . . , n}: namely, the empirical distribution of the positions of the L(t) customers present in the network at time t. Denote by

P = ρ ∈ [0, +∞[ n : n i=1 ρ i = 1
the state space of χ(t). The interior set of P is P = {ρ ∈]0, +∞[ n : n 1 ρ i = 1}. As emphasized earlier, the deviation of χ(t) from π will be of particular interest in the forthcoming analysis. It will be measured, depending on circumstances, by the ℓ ∞ distance χ(t)π :

x = max 1≤i≤n |x i |, x = (x 1 , . . . , x n ) ∈ Ê n ,
or by the relative entropy H(χ(t), π), where H(•, π) is defined on the set P of probability measures on {1, . . . , n}, by

H(ρ, π) = n i=1 ρ i log ρ i π i ∈ [0, +∞[, ρ ∈ P.
For t ≥ 0, the quantity H(χ(t), π) will also be more simply denoted H(t). The process (H(t), t ≥ 0) will spontaneously appear in the expression of the key martingale J α introduced in the next section.

The different deviation times of χ(t) from π, or conversely, the time needed for χ(t) to reach a given neighborhood of π, will be of particular interest. For ε > 0, T ε (resp. T ε ) denotes the first time when the ℓ ∞ distance between χ(t) and π is smaller (resp. larger) than ε:

T ε = inf{t ≥ 0 : χ(t) -π ≤ ε} and T ε = inf{t ≥ 0 : χ(t) -π > ε}.
Most results will be written down in terms of these two stopping times, but it will be sometimes more convenient to work with the deviation time T ε H from π in terms of the relative entropy:

T ε H = inf{t ≥ 0 : H(t) > ε}.
All results on deviation times of χ(t) from π defined in terms of the ℓ ∞ distance χ(t)-π can be translated into analogous estimates in terms of the relative entropy H(t) thanks to the following classical result: Lemma 2.1. There exist two π-depending positive constants C 1 and C 2 such that, for all ρ ∈ P:

C 1 ρ -π 2 ≤ H(ρ, π) ≤ C 2 ρ -π 2 .
In particular, for any ε > 0,

T C1ε 2 H ≤ T ε ≤ T C2ε 2 H .
Another stopping time will play a central role: namely the first time, denoted by T 0 , when the system has an empty node. Formally,

T 0 = inf{t ≥ 0 : ∃i ∈ {1, . . . , n}, X i (t) = 0}.
Indeed, the martingale property for the family of integrals presented in Section 3 will hold only up to time T 0 , i.e., as long as the output rate at each node i is exactly equal to µ i . In the same way, it will be easily shown that, for t < T 0 , L(t) behaves exactly like the M/M/1 queue with input rate λ and output rate µ.

A last useful remark concerning these stopping times is that, when T 0 is finite, χ(T 0 )π ≥ min π i (> 0). Together with Lemma 2.1, this immediately gives the following result: Lemma 2.2. There exists ε 0 > 0 such that T ε ∨ T ε H ≤ T 0 holds for any ε ≤ ε 0 .

Martingale

The results of this section are twofold: Theorem 3.1 gives the (almost) explicit expression of a local martingale J α (• ∧ T 0 ), indexed by some positive parameter α, and Proposition 3.2 derives the main estimate on deviation times T ε H of χ(t) from π, that will be used in Sections 6 and 7. Concerning the construction of J α , the present section only aims at giving the main lines. The (numerous) technical details are postponed to Appendix A.

The approach for constructing the martingale J α is similar to the approach used in [START_REF] Fricker | On the rates of convergence of Erlang's model[END_REF] for the M/M/∞ queue. The idea is to first exhibit a family of space-time harmonic functions (h v (t, x), v ∈ Ê n ) for the generator Ω given by (1), and then to integrate h v (t, x)f (v) with respect to v for some suitable function f , on some well chosen time dependent domain. The last step is then to make a change of variables so that the new harmonic function is splitted into two factors, respectively depending on time and space. The resulting local martingale is then adapted for an optional stopping use, leading to hitting times estimations. Some notations are required at this point. Denote by (P t , t ∈ Ê) the Q-generated Markov semi-group of linear operators in Ê n : P t = e tQ , extended to all real indices t into a group. For v ∈ Ê n and t ∈ Ê, define

φ(v, t) = (φ i (v, t), 1 ≤ i ≤ n) = P -t v.
Theorem 3.1 below requires the technical assumption that Q is diagonalizable. Let θ be the trace of -Q, so that θ > 0, and let S ⊂ Ê n-1 be the projection on the n -1 first coordinates of P ⊂ Ê n , i.e.,

S = u = (u 1 , . . . , u n-1 ) ∈ Ê n-1 : ∀i = 1, . . . , n -1, u i > 0 and n-1 i=1 u i < 1 .
For any u ∈ S, denote by ũ ∈ P the nth dimensional vector which completes u into a probability distribution, i.e., ũi = u i for any 1 ≤ i ≤ n -1 and ũn = 1 -n-1 1 u i . The following proposition describes a family of space-time harmonic functions. Proposition 3.1. Let v ∈ Ê n be fixed and let ϕ(v, •) be any primitive of

n i=1 µ i φ i (v, •) 1 + φ i (v, •) -λ i φ i (v, •)
on any open subset V of {t ≥ 0 : 1 + φ i (v, t) = 0 for i = 1, . . . , n}. The function

h v (t, x) = e ϕ(v,t) n i=1 (1 + φ i (v, t)) xi , t ∈ V, x ∈ AE n ,
is space-time harmonic with respect to Ω in the domain V × AE * n .

Proof. It must be shown that ∂h v (t, x)/∂t+Ω h v (t, •) (x) = 0 on the above domain.

For x ∈ AE * n and t ∈ V , h v (t, x) = 0, and one easily computes:

1 h v (t, x) ∂h v ∂t (t, x) = ∂ϕ ∂t (v, t) + n i=1 x i ∂φ i (v, t)/∂t 1 + φ i (v, t) and 1 h v (t, x) Ω h v (t, •) (x) = n i=1 λ i φ i (v, t) - n i=1 µ i φ i (v, t) 1 + φ i (v, t) + 1≤i =j≤n x i q ij φ j (v, t) -φ i (v, t) 1 + φ i (v, t) .
The last term in the right-hand side is equal to

n i=1 x i 1 + φ i (v, t) (Qφ(v, t)) i .
By definition φ satisfies ∂φ(v, t)/∂t = -Qφ(v, t) and the result follows.

Remark 3.1. The product form of these space-time harmonic functions is quite similar to that of the harmonic functions introduced in [START_REF] Fricker | On the rates of convergence of Erlang's model[END_REF] for the M/M/∞ queue.

In addition, it is easily checked that, choosing v = (u -1, . . . , u -1) for some u = 0, so that v is some eigenvector of P t , t ∈ Ê, associated to eigenvalue 1, yields h v (t, X(t)) = u L(t) e [λ(1-u)+µ(1-1/u)]t , which is the martingale associated to an M/M/1 queue L with arrival rate λ and service rate µ (see for example [START_REF] Robert | Stochastic Networks and Queues[END_REF]).

Starting from h v (t, x), two steps lead to J α : (i) integration of h v (t, x) over v against some function f (v) on a suitable time-dependent domain D(t); (ii) change of variables. These two steps are detailed and justified in Appendix A, yielding the following family of local martingales: Theorem 3.1. There exist two positive, continuous, bounded functions F and G on P such that for any α > 0, u → F (ũ) α-1 is integrable on S and (J α (t ∧ T 0 ), t ≥ 0) is a nonnegative local martingale, where J α (t) is defined for α > 0 and t ≥ 0 by:

J α (t) = e -αθt S n i=1 ũi π i Xi(t) G(ũ)F (ũ) α-1 du,
or equivalently:

J α (t) = e -αθt S e L(t)(H(t)-H(χ(t),ũ)) G(ũ)F (ũ) α-1 du. (2) Moreover, F satisfies sup 0<α≤1 α n S F (ũ) α-1 du < +∞. ( 3
)
The advantage of J α (t) (as compared to h v (t, X(t))), is that the dependence in time is there splitted into two factors: e -αθt is a direct function of time, and the integral is a function of the state of the system at time t, X(t) or equivalently (L(t), χ(t)).

The next proposition gives the fundamental estimate obtained through optional stopping and used several times throughout the paper. Proposition 3.2. For any δ such that 0 < δ < ε 0 , where ε 0 is given by Lemma 2.2, there exists some constant C δ such that

x e -αθT ε H ; L(T ε H ) ≥ ℓ ≤ C δ α -n e |x|H(x/|x|,π)-(ε-δ)ℓ
holds for any initial state x ∈ AE n and any

ε ∈]δ, ε 0 [, ℓ > 0 and α ∈]0, 1].
Proposition 3.2 is derived from the two following lemmas by choosing T = T ε H (so that, by Lemma 2.2, T ∧ T 0 = T when ε < ε 0 ). Note that only Lemma 3.1 uses the fact that J α is a local martingale, whereas Lemma 3.2 stems directly from the expression of J α provided by (2).

Lemma 3.1.

There exists some constant C 3 > 0 such that, for any α ∈]0, 1], any initial state x ∈ AE n and any stopping time T , the following inequality holds:

x [J α (T ∧ T 0 )] ≤ C 3 α -n e |x|H(x/|x|,π) . Proof. Fix α ∈]0, 1] and x ∈ AE n . Since J α (• ∧ T 0 ) is a nonnegative local martingale,
it is a supermartingale, and so is (J α (t ∧ T ∧ T 0 ), t ≥ 0) by Doob's optional stopping theorem. In particular, for any t ≥ 0:

x J α (0) ≥ x J α (t ∧ T ∧ T 0 ) , and Fatou's lemma gives:

x J α (0) ≥ lim inf t→+∞ x J α (t∧T ∧T 0 ) ≥ x lim inf t→+∞ J α (t∧T ∧T 0 ) = x J α (T ∧T 0 ) ,
(where J α (T ∧ T 0 ) makes sense a.s. when T ∧ T 0 = +∞ since any nonnegative supermartingale almost surely converges to some variable at infinity).

From the definition of J α given by ( 2), using e -y ≤ 1 for y ≥ 0, one gets

x [J α (0)] ≤ sup P (G) e |x|H(x/|x|,π) S F (ũ) α-1 du ≤ C 3 e |x|H(x/|x|,π) α -n
where

C 3 = sup P (G) sup α≤1 α n S F (ũ) α-1
du is finite by [START_REF] Bramson | Convergence to equilibria for fluid models of FIFO queueing networks[END_REF], which proves the lemma. Lemma 3.2. For any positive δ, there exists some positive constant B δ such that the following implication holds for any α ∈]0, 1], ℓ > 0, ε > δ and t ≥ 0:

L(t) ≥ ℓ and H(t) ≥ ε =⇒ J α (t) ≥ B δ • e -αθt+(ε-δ)ℓ . Proof. Fix ε > δ, α ∈]0, 1], ℓ > 0 and t ≥ 0. A lower bound on the integral part of (2) is obtained when L(t) ≥ ℓ and H(t) ≥ ε. For v ∈ P, define the set S δ (v) ⊂ S by S δ (v) = {u ∈ S : H(v, ũ) ≤ δ} . If H(t) ≥ ε and L(t) ≥ ℓ, then S e L(t)(H(t)-H(χ(t),ũ)) G(ũ)F (ũ) α-1 du ≥ β e ℓ(ε-δ) S δ (χ(t)) G(ũ)du,
where β = min{(sup P F ) -1 , 1}. Indeed, α being smaller than 1, β is a lower bound for F (ũ) α-1 on S. Consider now the function Φ δ : P → Ê + defined by

Φ δ (v) = S δ (v) G(ũ)du.
Since G is bounded, Φ δ is easily shown to be continuous (using for example Lebesgue's theorem). Moreover, Φ δ (v) > 0 for any v ∈ P (because G > 0 and the interior of S δ (v) is not empty), and since P is compact, inf P Φ δ > 0. Setting B δ = β inf P Φ δ achieves the proof.

Two key representations

The Markov process (X(t), t ≥ 0) with infinitesimal generator Ω defined by (1) can be seen as a particle system involving three types of transitions: births (at rate λ i at site i), deaths (at rate µ i ½ {xi≥1} at site i) and migrations of particles from one site to another (at rate q ij x i from site i to site j). The main purpose of this section is to show that X can be decomposed into the difference of two pure birth and migration processes, up to some reflection term (Theorem 4.1). A first, simpler result (Proposition 4.1) tells that, as long as X does not hit the axis, the process L of the total number of particles just behaves as a random walk (or equivalently as an M/M/1 queue). Finally, a representation of process X involving labelled particles is given in the case of null death rates.

Theorem 4.1, together with the latter representation, will be crucial for describing the unstable regime in Section 6, while Proposition 4.1 will be repeatedly used in the study of both the super and subcritical regimes.

The idea for decomposing X is the following: when µ = 0, the system consists of immortal particles generated at rate λ and performing independent Markov trajectories. Introducing some death procedure, i.e., some positive µ, amounts to eliminating, if possible, particles at site i at rate µ i (1 ≤ i ≤ n). Up to some correction due to the fact that no death can actually occur at an empty site, this is equivalent to substracting some analogous process with birth rates µ i (1 ≤ i ≤ n), zero death rates and migration rate matrix Q.

This can be formalized by introducing an enlarged Markov process, involving different types of particles. "Real" (mortal) particles are generated at each node i, 1 ≤ i ≤ n, at rate λ i , and then move according to the rate matrix Q. The death process is represented through inhibiting particles, generated at each site i, 1 ≤ i ≤ n, at rate µ i : Such a particle immediately aggregates with some real particle present, if any, so as to convert it into a "ghost" particle, that goes on moving forever according to Q. Otherwise (i.e., if no real particle is present), it yields some "virtual" particle, that also stays moving forever in the system according to Q. The Markov process considered will keep track of the three different types of particles: real ones (those described by process X), ghost ones and virtual ones.

Formally, define (X, Y, Z) as a Markov process in AE 3n with generator Γ characterized by the following transitions and rates: for any (x, y, z) ∈ AE 3n and i, j ∈ {1, . . . , n} such that i = j,

(x, y, z) -→                (x + e i , y, z) at rate λ i (x -e i , y + e i , z) µ i ½ {xi≥1} (x, y, z + e i ) µ i ½ {xi=0} (x -e i + e j , y, z) q ij x i (x, y -e i + e j , z) q ij y i (x, y, z -e i + e j )
q ij z i X holds for the real particle process, Y for the ghost particle process and Z for the virtual particle process. The first transition is a birth of some real particle at i, the second one is a transformation of some real particle into a ghost, the third one is a birth of some virtual particle at i; the three last transitions are just movements of particles of the three possible types.

It is clear from these transitions and rates that, indexing generator Ω by its birth and death rate vectors:

λ = (λ i , 1 ≤ i ≤ n) and µ = (µ i , 1 ≤ i ≤ n) (λ, µ ∈ [0, +∞[ n ) and denoting by 0 the null vector in Ê n : (i) X is a Markov process in AE n with generator Ω λ,µ , (ii) X + Y is also Markov in AE n , with generator Ω λ,0 , (iii) Y + Z is Markov in AE n with generator Ω µ,0 , (iv) |X| + |Y | -(|X(0)| + |Y (0)|) is some Poisson process with intensity λ, (v) |Y | + |Z| -(|Y (0)| + |Z(0)|)
is some Poisson process with intensity µ, (vi) these two Poisson processes are independent. Now from (i), any process X with generator Ω can be considered as the first component of some Markov process with generator Γ and with initial state (X(0), 0, 0).

The two major results of this section are easily derived from this construction of process X and from remarks (i) to (vi). The first result, which is intuitively clear, constitutes one of the key ingredients for deriving the fluid limits in Sections 6 and 7.

Proposition 4.1. For all t ≤ T 0 , the following equality holds:

L(t) = L(0) + N λ (t) -N µ (t),
where N λ and N µ are independent Poisson processes with respective intensities λ and µ. Moreover, L(t) ≥ L(0) + N λ (t) -N µ (t) holds for any t ≥ 0.

Proof. Using the above construction of process X, write

L(t) = |X(t)| = |X(t)| + |Y (t)| -(|Y (t)| + |Z(t)|) + |Z(t)| = |X(0)| + N λ (t) -N µ (t) + |Z(t)| -|Z(0)|,
where N λ and N µ are obtained from (iv) and (v), and are independent by (vi).

Since |Z(0)| = 0 and, as can be seen on Γ, |Z| is nondecreasing and increases only at times at which some X i is zero, it follows that |Z(t)| = 0 for t ≤ T 0 , which gives the first part of the proposition.

The inequality (for all t ≥ 0) results from the fact that |Z(t)| is nonnegative.

In order to state the next result, it is convenient to index the process X both by its initial state and by its birth and death parameters, writing X x λ,µ for the process X with initial state x ∈ AE n , migration rate matrix Q and birth (resp.

death) parameters λ = (λ i , 1 ≤ i ≤ n) (resp. µ = (µ i , 1 ≤ i ≤ n)).
Theorem 4.1. For any x ∈ AE n and λ, µ ∈ [0, +∞[ n , there exist versions of X x λ,µ X x λ,0 and X 0 µ,0 such that

X x λ,µ = X x λ,0 -X 0 µ,0 + Z,
where Z is an AE n -valued process such that |Z| is nondecreasing and increases only at times when some X i (t), 1 ≤ i ≤ n, is zero.

Proof. In the same way as in the previous proof, write

X = X + Y -(Y + Z) + Z,
where (X(0), Y (0), Z(0)) = (x, 0, 0) and (X, Y, Z) is Markov with generator Γ, so that X is some version of X x λ,µ , and by (ii) and (iii), X + Y is some version of X x λ,0

and Y + Z some version of X 0 µ,0 . The theorem is proved since |Z| has the stated properties, as already mentionned in the proof of the previous proposition.

Remark 4.1. The process Z in Theorem 4.1 appears as a reflection term: it guarantees that X stays nonnegative, compensating by adding some virtual particle for a jump of X 0 µ,0 that would get some X i to the value -1. However, contrary to usual multidimensional Skorokhod reflection terms, here, due to the movements of particles (namely, virtual ones), components Z i 's are not necessarily nondecreasing in time: only their sum is. For the same reason, Z i can increase at times when X i is not zero (due to arrival at i of some virtual particle from another site).

We conclude this section with a representation of process X x λ,0 that will be used in Section 6, in conjunction with Theorem 4.1, for analyzing the unstable regime. X x λ,0 is here obtained as function of a Poisson process with intensity λ and a sequence of Markov processes with infinitesimal generator Q. The latter represent the trajectories of the successively generated particles, that are here labelled (contrary to the previous representations involving undiscernable particles).

More precisely, X x λ,0 admits the following representation:

X x λ,0 (t) = k≥1 ½ {ξ k (t-σ k )=i, σ k ≤t} , 1 ≤ i ≤ n , t ≥ 0, where (4)
-

σ k = 0 for 1 ≤ k ≤ |x|, -N λ = (σ k , k ≥ |x| + 1) is a Poisson process with parameter λ, -ξ k , k ≥ 1, are Markov jump processes in {1, . . . , n} with generator Q and initial distribution - n i=1 (λ i /λ) δ i for k ≥ |x| + 1, -the Dirac mass at i (1 ≤ i ≤ n) for x i arbitrarily chosen indices k with 1 ≤ k ≤ |x|,
-N λ and the ξ k , k ≥ 1, are mutually independent.

N λ can be interpreted as the global birth process: for k ≥ |x| + 1, particle k is generated at time σ k (while for k ≤ |x|, particle k is in the system from time σ k = 0). (ξ k , 1 ≤ k ≤ |x|) hold for the trajectories of the initial particles and (ξ k , k ≥ |x| + 1) for those of the successive newborn particles. For any k ≥ 1 and t ≥ σ k , ξ k (tσ k ) is then the position of particle k at time t, so that the sum in the right hand side of (4) counts the number of particles present at each site at time t.

Similarly as in the previous construction of X from process (X, Y, Z), a formal proof of Equation ( 4) can be provided by constructing X x λ,0 as function of a more complete process (that also contains N λ and the ξ k 's, k ≥ 1), characterized through its infinitesimal generator and describing the list of current positions of particles present in the system, ordered according to their birth rank. ( 4) is then obtained via elementary Markov techniques.

The space renormalized process

The stability property of the system for λ < µ will be derived in Section 7 from a fluid scaling analysis, that is, from the study of the space-time renormalized process

X x (t) = X x (|x| t) |x| , t ≥ 0,
as |x| goes to infinity, where X x is the Markov process X initiated at x. It will be underlain by the M/M/1 behavior of the total occupancy process L (only valid as long as no X i is zero, hence the intricacies of the analysis).

The particular behavior of X x at t = 0 + will result from the short term behavior of the only space renormalized process X, defined as the the family of processes

X x (t) = X x (t) |x| , t ≥ 0, for x ∈ AE n \ {0}.
(The simpler notation X(t), where X(t) = X(t)/|X(0)|, will also be used in situations where |X(0)| is clearly non zero.) As highlighted in the introduction, this scaling is natural and analogous to Kelly's scaling for the M/M/∞ queue. This analogy will appear in Proposition 5.1 below, that states convergence of X x as |x| → +∞ to some dynamical system having π as its unique limiting point. This result implies that for large |x|, X x reaches any neighborhood of π in a quasi-deterministic finite time. And this will show (Sections 6 and 7) that asymptotically, X

x is instantaneously at π.

The results of this section are quite standard, essentially based on law of large numbers principles. The simple underlying idea is that, as far as X x is only observed over a finite time window, since the number |x| of initial particles goes to infinity while the numbers of births and deaths within the given window remain the order of 1 (time is not rescaled here), the initial particles asymptotically dominate the system and mostly stay alive all along the time window, thus behaving as |x| independent Markov processes with generator Q.

For the same reasons, the process X is not different, in the limit |x| → +∞, from the process χ = X/L of the spatial distribution of particles: The same convergence results hold for both processes; once proved for X, they easily extend to χ.

Formalizing the above argument, the following coupling is intuitively clear. It compares the general model to the "closed" one (with no births nor deaths, but only initial particles). Here again, generator Ω is indexed by its birth and death parameters λ and µ. Lemma 5.1. For any x ∈ AE n , there exists a coupling between the process X x with initial state x and generator Ω λ,µ , and the process U x with initial state x and generator Ω 0,0 , such that, for t ≥ 0 and i = 1, . . . , n:

U x i (t) -N µ (t) ≤ X x i (t) ≤ U x i (t) + N λ (t)
, where N λ and N µ are two Poisson processes with respective parameters λ and µ.

X x moreover satisfies

|x| -N µ (t) ≤ |X x (t)| ≤ |x| + N λ (t).
Proof. The case µ = 0 is a straightforward consequence of the representation (4) of X from Section 4. Indeed if µ = 0, (4) gives for 1 ≤ i ≤ n,

U x i (t) ≤ X x i (t) = 1≤k≤|x| ½ {ξ k (t)=i} + k≥|x|+1 ½ {ξ k (t-σ k )=i, σ k ≤t} ≤ U x i (t) + N λ (t),
where U x (t) is constructed as

|x| k=1 ½ {ξ k (t)=i} and N λ = (σ k , k ≥ |x| + 1). One moreover gets |U x (t)| ≤ |X x (t)| ≤ |U x (t)| + N λ (t)
by summing up over i the previous first inequalities. The lemma is proved in this case since |U x (t)| = |x| for any t ≥ 0 .

The general case is then derived, using the first part of Section 4. Indeed, as in Section 4, X x can be considered as the first component of a random process

(X x , Y, Z) in AE 3n such that Y (0) = Z(0) = 0, X x + Y is some process with
generator Ω λ,0 and |Y | + |Z| is some Poisson process N µ with intensity µ . The first part of the proof then applies to X x + Y and gives for t ≥ 0:

U x (t) ≤ X x (t) + Y (t) ≤ U x (t) + N λ (t) componentwise, as well as |x| ≤ |X x (t)| + |Y (t)| ≤ |x| + N λ (t).
The lemma follows by noticing that

0 ≤ Y i (t) ≤ |Y (t)| ≤ |Y (t)| + |Z(t)| = N µ (t), 1 ≤ i ≤ n.
The following result describes the asymptotic dynamics, as |x| → +∞, of the empirical distribution of the particles: it evolves as the distribution, as function of time, of a Markov process with generator Q.

As introduced in Section 3, (P t , t ≥ 0) denotes the transition semi-group associated to Q. Proposition 5.1. Consider the processes ( X xN (t), t ≥ 0) associated to some sequence (x N , N ≥ 1) of initial states satisfying: lim

N →+∞ x N N
= ρ for some ρ ∈ P.

For any T > 0, as N → +∞, ( X xN (t), t ≥ 0) converges in distribution with respect to the uniform norm topology on [0, T ], to the deterministic trajectory:

ρ(t) = ρ P t .
In other words, for any positive δ:

lim N →+∞ È sup 0≤t≤T X xN (t) -ρP t > δ = 0.
The same convergence holds for the corresponding processes (χ xN (t), t ≥ 0), N ≥ 1.

Proof. The proof is fairly standard, and (not surprisingly) similar to the proof of convergence of the M/M/∞ queue under Kelly's scaling (see [START_REF] Robert | Stochastic Networks and Queues[END_REF]). It uses a representation of X x as the solution of a stochastic integral equation involving different Poisson processes.

Let N λi and N µi , for i = 1, . . . , n, be Poisson processes with respective parameters λ i and µ i . And for (i, j) ∈ {1, . . . , n} 2 such that i = j, let (N k qij , k ≥ 1) be a sequence of Poisson processes with parameter q ij . All these processes are assumed independent. A version of X xN is then given by the solution of the system of integral equations:

(5) X i (t) = x N,i + N λi (t) - t 0 ½ {Xi(s -)≥1} dN µi (s) + j =i t 0 Xj (s -) k=1 dN k qji - j =i t 0 Xi(s -) k=1 dN k qij , 1 ≤ i ≤ n.
For i, j ∈ {1, . . . , n} with i = j and k ≥ 1, N λi can be interpreted as the birth process at node i, N µi as the death process at node i (which points are taken into account only when node i is not empty), and N k qij as the process of transfers from node i to node j of the kth particle at node i (taken into account only when at least k particles are present at node i).

Through space scaling, the terms involving N λi and N µi vanish in the limit. Writing each process N k qij as the sum of its deterministic increasing process (q ij t, t ≥ 0) and of a martingale, Doob's inequality allows one to show that the scaled martingale terms vanish in the uniform norm on [0, T ].

Next substract from the rescaled Equation (5) (i.e., [START_REF] Caputo | Entropy dissipation estimates in a zero-range dynamics[END_REF] divided by |x N |) the corresponding equation of the limiting trajectory:

ρ i (t) = ρ i + t 0 j =i (q ji ρ j (s) -q ij ρ i (s)) ds, 1 ≤ i ≤ n.
(These equations are indeed equivalent to

ρ(t) = ρ + t 0 ρ(s)Q ds,
or to the forward Kolmogorov equation ρ ′ (t) = ρ(t)Q associated to the initial condition ρ(0) = ρ, that characterize the family of distributions: ρ(t) = ρP t , t ≥ 0.) Gronwall's lemma then applies to the quantity

sup 0≤t≤T X xN (t) -ρ(t) ,
proving the stated convergence in distribution of ( X xN (t), t ≥ 0) to (ρ(t), t ≥ 0). Using the last assertion of Lemma 5.1, it is not difficult to show that the same convergence then holds for the process χ xN .

The following corollary concerns the hitting time of some neighborhood of π by the space renormalized process X: namely, for any positive δ,

T δ = inf t ≥ 0 : X(t) -π ≤ δ .
Recall that the analogous time with χ in place of X is denoted by T δ .

Corollary 5.1. For any positive δ, there exists some deterministic time t δ ≥ 0 such that, if (x N , N ≥ 1) satisfies lim

N →+∞ x N N = ρ for some ρ ∈ P, then lim N →+∞ È xN ( T δ > t δ ) = 0.
The same result holds for the stopping time T δ .

(The subscript x N refers to the initial state of process X).

Proof. Q being irreducible, the ergodic theorem for finite state space Markov processes shows that, for any δ > 0, there exists some time t δ such that sup ρ∈P ρP t δπ < δ/2. The corollary is then easily obtained by using the pointwise convergence in distribution of X xN (t δ ) to ρP t δ implied by Proposition 5.1 and the inclusion:

{ T δ > t δ } ⊂ { X(t δ ) -π > δ}.
The same arguments hold with χ in place of X (since Proposition 5.1 states convergence for both processes), yielding the same result for T δ .

Remark 5.1. Note that Proposition 5.1 is not here essential in its whole trajectorial sense. Pointwise convergence in distribution at time t δ is enough and could be directly obtained from the ordinary law of large numbers, along the same lines as Proposition 5.2 below. This would moreover yield the uniform result:

lim |x|→+∞ È x ( T δ > t δ ) = 0.
The last proposition states a more accurate result required for analyzing the subcritical case λ < µ.

È x T δN > t N = 0, where t N = - 1 η log δ N A .
The same result holds for the stopping time T δN .

Proof. First consider a closed system, i.e., assume λ = µ = 0. As in Lemma 5.1, let U x be the closed process with initial state x ∈ AE n , where |x| = N . In this case (4) becomes:

U x i (t) = N k=1 ½ {ξ k (t)=i} , 1 ≤ i ≤ n, t ≥ 0,
where ξ k , 1 ≤ k ≤ N , are independent Markov processes with the same generator Q and different initial conditions: for any i,

1 ≤ i ≤ n, ξ k (0) = i for x i of the N indices k = 1, . . . , N .
The exponentially fast convergence of any irreducible finite state space Markov semi-group to its stationary distribution, tells existence of B > 0 and η > 0 such that max 1≤i,j≤n

|P t (j, i) -π i | ≤ Be -ηt , t ≥ 0.
In particular max 1≤i,j≤n

|P sN (j, i) -π i | ≤ δ N /2 for s N = - 1 η log δ N 2B .
The outline of the proof for the closed case is the following (the general case will then be deduced from Lemma 5.1): At time s N , all trajectories ξ k , 1 ≤ k ≤ N are very close to π in distribution (by the order of δ N ). Since U x (t) represents the empirical distribution of the N particles at time t, the law of large numbers shows that U x (s N ) is also close to π (by the same order) for large N . (Indeed δ N tends to 0 not too fast, so that this law of large numbers argument, valid for some constant δ, still holds with δ N . Notice by the way that the argument for constant δ leads to the result mentioned in Remark 5.1).

Precisely, for any N ≥ 1 and x ∈ AE n such that |x| = N :

x U(s N ) -π = x U (s N ) N -π = 1 N N k=1 È(ξ k (s N ) = •) -π < δ N 2 .
Thus, for any N ≥ 1, using Chebychev's inequality for the last step:

È x U(s N ) -π > δ N ≤ È x U (s N ) -U (s N ) > δ N 2 ≤ n i=1 È x U i (s N ) -U i (s N ) > δ N 2 ≤ n i=1 Îar x (U i (s N )) δ 2 N N 2 /4
.

Independence of the processes (ξ

k , 1 ≤ k ≤ N ) yields Îar x (U i (s N )) = N k=1 Îar ½ {ξ k (sN )=i} ≤ N 4
(bounding the variance of any Bernoulli random variable by 1/4). Finally max

x∈AE n :|x|=N È x U(s N ) -π > δ N ≤ n δ 2 N N . (6)
Now consider the process X x associated to any family (λ i , µ i , 1 ≤ i ≤ n) of parameters and any initial state x such that |x| = N . Still denote by U x the associated closed process with the same initial state x.

Define t N = - 1 η log δ N 4B
. The first part of Lemma 5.1 implies that, for any N ≥ 1,

X x (t N ) -π ≤ U x (t N ) -π + 1 N N λ (t N ) + N µ (t N ) , so that È x ( T δN > t N ) ≤ È U x (t N ) -π > δ N 2 + È N λ (t N ) + N µ (t N ) > N δ N 2 .
By (6) the first term tends to zero uniformly in x as N goes to infinity, since t N is associated to δ N /2 in the same way as s N was to δ N . The second one is also easily shown to converge to zero, using Chebychev's inequality for the Poisson variable N λ (t N ) + N µ (t N ), together with the relation δ

N √ N ≫ 1 that implies N δ N ≫ √ N ≫ 1/δ N ≫ t N .
The first part of the proposition is thus proved with A = 4B. The result for time T δN is obtained, once again, by using the second assertion of Lemma 5.1.

The supercritical regime

This section deals with the supercritical regime λ > µ. As the next proposition shows, the unstability of the system is straightforward in this case. Theorem 6.1 establishes an almost sure result describing the long term behavior, and Theorem 6.2 presents a surprising phenomenon. Proposition 6.1. When λ > µ the process X is not ergodic.

Proof. Just remark, using Proposition 4.1, that if x ∈ AE n is the initial state:

L(t) ≥ |x| + N λ (t) -N µ (t).
Hence for any initial state, L(t) almost surely goes to +∞ as t tends to +∞.

The following theorem gives an almost sure description of the divergence of X(t) for t large. Among other arguments, the proof makes use for the first time of the estimate provided by Proposition 3.2, and uses the representation of X given by (4). Theorem 6.1. Assume λ > µ. Then, for any initial state x ∈ AE n , the following convergence holds almost surely:

lim t→+∞ X x (t) t = (λ -µ)π.
Remark 6.1. This theorem has a double meaning: it tells almost sure convergence both of χ(t) to π and of L(t)/t to λµ as t → +∞.

Proof. Assume the theorem is true when µ = 0. Then, using the notations of Theorem 4.1, t -1 (X x λ,0 (t) -X 0 µ,0 (t)) converges a.s. to (λµ)π and the componentwise inequality X x λ,µ ≥ X x λ,0 -X 0 µ,0 derived from Theorem 4.1, implies that each X x i (t) tends to infinity almost surely as t goes to infinity.

As a consequence, since |Z(t)| can increase only when some X i (t) is zero, lim t→+∞ |Z(t)| is finite with probability 1, thus lim t→+∞ Z(t)/t = 0 almost surely, so that, almost surely:

lim t→+∞ X x (t) t = lim t→+∞ X x λ,0 (t) -X 0 µ,0 (t) t = (λ -µ)π,
which is the stated result.

The theorem must now be proved in the case where µ = 0. In this case with no deaths, using representation (4), the process X x splits into two (independent) processes: X x = Y x + X 0 , where Y x is associated to a "closed" system with |x| particles moving independently, and X 0 has no initial particles, birth rate λ and death rates 0. Then t -1 Y x (t) obviously tends to zero almost surely as t tends to infinity, and all is left to show is that t -1 X 0 (t) converges almost surely to λπ.

So, dropping for simplicity the superscript 0, consider the process X with initial state 0, birth rate λ and death rates 0. Since L(t)/t = N λ (t)/t converges a.s. to λ as t tends to infinity, the problem is equivalent to proving that χ(t) converges almost surely to π, i.e., by Lemma 2.1 that:

∀ε > 0, È(∃T < +∞ : ∀t ≥ T, H(t) ≤ ε) = 1.
This will be done using Borel-Cantelli lemma and showing that:

∀ε > 0, +∞ k=1 È(∃t ∈ [σ k , σ k+1 [ : H(t) > ε) < +∞,
where σ k denotes as in Equation ( 4) of Section 4 the kth jump time of the birth process N λ .

Writing, for any fixed ε:

(7) È (∃t ∈ [σ k , σ k+1 [: H(t) > ε) ≤ È H(σ k ) > ε 2 + È H(σ k ) ≤ ε 2 and ∃t ∈]σ k , σ k+1 [: H(t) > ε ,
we will show that both series associated to both right hand side terms converge for ε sufficiently small (which is enough by monotonicity of the left hand side of ( 7)).

Let us begin with the second term. By definition of σ k , χ(t) = X(t)/k for any t ∈ [σ k , σ k+1 [. Moreover, σ k is a stopping time for the Markov process (X(t), t ≥ 0), because it is the first time when L(t) = k. Hence the strong Markov property yields

È 0 H(σ k ) ≤ ε 2 and ∃t ∈]σ k , σ k+1 [: H(t) > ε ≤ max x∈AE n :|x|=k and H(x/|x|,π)≤ε/2 È x (T ε H < σ 1 ) .
Clearly, the last event only depends on σ 1 and on the movements of the |x| initial particles, so that by independence of these variable and processes, one obtains, for

any x ∈ AE n : È x (T ε H < σ 1 ) = x e -λ T ε H ≤ x e -(λ∧θ) T ε H ,
where T ε H is the first time the entropy associated to the initial particles is larger than ε. Then, using Proposition 3.2 in the case of a closed system with δ = ε/4, α = (λ/θ) ∧ 1 and ℓ = k gives:

È x (T ε H < σ 1 ) ≤ C ε/4 [(λ/θ) ∧ 1)] -n e -εk/4 ,
for any x ∈ AE n such that |x| = k and H(x/|x|, π) ≤ ε/2. The second term in [START_REF] Dai | On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models[END_REF] is thus summable over k for ε small enough. Now it must be shown that the first term È(H(σ k ) > ε/2) in the right hand side of ( 7) is summable as well for ε small enough. Due to Lemma 2.1 it is enough to show that, for small ε and any i ∈ {1, . . . , n},

+∞ k=1 È X i (σ k ) k -π i > ε < +∞. ( 8
)
The idea for proving [START_REF] Dupuis | Lyapounov functions for semimartingale reflecting Brownian motions[END_REF] is close to the law of large numbers arguments of Section 5, except that here spaced births result in the presence of recent particles (as seen from σ k ) that are not yet close to stationarity in their movement. It then has to be proved that old particles dominate the network at time σ k for large k. Here, the law of large numbers is not accurate enough, and is replaced by Chernoff's inequality, that we recall in Lemma 6.1.

Lemma 6.1. (Chernoff 's inequality) Let Z h , 1 ≤ h ≤ k, be k independent random variables such that |Z h | ≤ 1 and (Z h ) = 0 for 1 ≤ h ≤ k.
The following bound holds for any η ∈ [0, 2σ], where

σ 2 = Îar k h=1 Z h : È k h=1 Z h ≥ ησ ≤ 2 exp -η 2 /4 .
In the present case with no initial particles nor death process, X(σ k ) simply writes:

X i (σ k ) = k h=1 ½ {ξ h (σ k -σ h )=i} , 1 ≤ i ≤ n,
Let us first assume that the Markov processes ξ h , h ≥ 1, are stationary, i.e., λ i /λ = π i for all i ∈ {1, . . . , n}. Then

X i (σ k ) k -π i = 1 k k h=1 Z (i) k,h with Z (i) k,h = ½ {ξ h (σ k -σ h )=i} -π i , 1 ≤ i ≤ n.
Since ξ h , h ≥ 1, are stationary, for each fixed i ∈ {1, . . . , n} and k ≥ 1, the k variables

Z (i) k,h , 1 ≤ h ≤ k, are i.i.d. centered random variables, bounded by 1 in modulus. Notice that independence of Z (i) k,1 , . . . , Z (i)
k,k results from independence of the processes ξ h , h ≥ 1, and N λ , and is only true in the stationary case.

We can thus apply Chernoff's inequality, which gives, for each fixed k and i:

È X i (σ k ) k -π i > ε = È k h=1 Z (i) k,h > kε ≤ 2e -ε 2 k 4v i , if ε ≤ 2v i , where v i = π i (1 -π i ) is the common variance of the variables Z (i)
k,h . Property ( 8) is then proved (for small ε, hence for any ε by monotonicity) in the case of stationary movements.

We now get back to the general case, where ξ h , h ≥ 1, are independent copies of a Markov process with generator Q and initial distribution n 1 (λ i /λ) δ i . Associate to each ξ h a stationary process ξ ′ h with the same generator, such that ((ξ h , ξ ′ h ), h ≥ 1) is a sequence of independent processes in {1, . . . , n} 2 , and, for h ≥ 1, ξ h , ξ ′ h are coupled in the classical following way: ξ h and ξ ′ h are independent until the first time T h when they meet, and after that stay equal for ever. Recall that the "coupling times" T h , h ≥ 1, are integrable. Moreover assume the (ξ k , ξ ′ k ), k ≥ 1, independent from N λ .

Define the process (X ′ (t), t ≥ 0) on AE n analogously to X, with the same N λ , but with ξ ′ h in place of ξ h (h ≥ 1):

X ′ i (t) = +∞ h=1 ½ {ξ ′ h (t-σ h )=i, σ h ≤t} , 1 ≤ i ≤ n and t ≥ 0.
Then, for each i ∈ {1, . . . , n}

X i (σ k ) -X ′ i (σ k ) k = 1 k k h=1 ½ {ξ h (σ k -σ h )=i} -½ {ξ ′ h (σ k -σ h )=i} ≤ 1 k k h=1 ½ {T h >σ k -σ h } .
The last sum is exactly the number of customers at the kth arrival time in an M/G/∞ queue with no customer at time 0, arrival process N λ , and services given by the i.i.d. integrable variables T h , h ≥ 1.

It is well known (see [START_REF] Robert | Stochastic Networks and Queues[END_REF], Section 7.2) that this M/G/∞ queue has stationary distribution given by the Poisson distribution with parameter λ (T 1 ), and that, in its stationary regime, the queue as seen by any newcoming customer has this same Poisson distribution as at any deterministic time. It follows that the stationary queue at time σ k , for any k ≥ 1, is distributed as 1 + Y , where Y is some Poisson variable with parameter λ (T 1 ). Since the stationary queue dominates the initially empty one, at any time t ≥ 0 (by its residual number of initial customers), one gets, for any i and any positive ε:

+∞ k=1 È X i (σ k ) -X ′ i (σ k ) k > ε ≤ È(1 + Y > kǫ).
Since Y is integrable, the last sum is finite and ( 8) is then true for X since it is for X ′ , by the above proof for the stationary case.

Along the preceding proof, we used σ 1 , in the particular case µ = 0, as an asymptotic lower bound (as the initial state grows to infinity) for the exit time of χ(t) from some neighborhood of π. This is a very crude underestimation, as the following result shows that this exit time is actually infinite with high probability. Theorem 6.2. Assume λ > µ, and fix δ and ε such that 0 < δ < ε < ε 0 , where ε 0 is given by Lemma 2.2. Consider a sequence (x N , N ≥ 1) with lim N →+∞ |x N |/N = 1 and H(x N /|x N |, π) ≤ δ. Then:

lim N →+∞ È xN (T ε H = +∞) = 1. Proof. By definition of T ε H , È xN (T ε H < +∞) = È xN (∃t ≥ 0 : H(t) ≥ ε)
, and so we need to study the behavior of H(t) for all time t ≥ 0. The idea of the proof is twofold: First, the estimate given by Proposition 3.2 is precise enough to show that T ε H is much larger than N , say T ε H ≥ N 2 . After this time, the initial particles are negligible, and Theorem 6.1 then gives a control on the rest of the trajectory by reducing the problem to the case where the system starts empty. So we use the following decomposition:

È xN (T ε H < +∞) ≤ È xN T ε H ≤ N 2 + È xN ∃t ≥ N 2 : H(t) ≥ ε .
For the first term, Markov's inequality gives

È xN T ε H ≤ N 2 ≤ e xN e -T ε H /N 2 . ( 9
)
Let δ ′ < εδ: by choice of ε and δ, and since H(x N /|x N |, π) ≤ δ, Proposition 3.2 shows that there exists a constant C δ ′ such that by choosing α = 1/(θN 2 ), for any N large enough and any ℓ N ,

xN e -T ε H /N 2 ; L(T ε H ) ≥ ℓ N ≤ C δ ′ e δ|xN |+2n log N -(ε-δ ′ )ℓN .
The choice of ℓ N requires some care: as N grows, it must be both of order |x N | and smaller than L(T ε H ) with high probability. Since

|x N | ∼ N , write |x N | = N + u N with u N = o(N ), and choose ℓ N = N - √ N v N with v N = |u N | ∨ 1. With this choice, ℓ N ∼ N and ℓ N -|x N | → -∞. The first relation implies, since ε-δ ′ -δ > 0, lim N →+∞ e δ|xN |+2n log N -(ε-δ ′ )ℓN = 0. Moreover, since T ε H ≤ T 0 because ε < ε 0 , Proposition 4.1 implies that L(T ε H ) = L(0) + N λ (T ε H ) -N µ (T ε H ), hence È xN (L(T ε H ) ≤ ℓ N ) = È xN (|x N | + N λ (T ε H ) -N µ (T ε H ) ≤ ℓ N ) ≤ È inf t≥0 (N λ (t) -N µ (t)) ≤ ℓ N -|x N |
where the last bound vanishes because λ > µ, and so inf t≥0 (N λ (t) -N µ (t)) is finite with probability one, whereas ℓ N -|x N | goes to -∞. It results that È xN T ε H ≤ N 2 goes to 0 thanks to [START_REF] Fricker | On the rates of convergence of Erlang's model[END_REF] and to the following inequality:

xN e -T ε H /N 2 ≤ xN e -T ε H /N 2 ; L(T ε H ) ≥ ℓ N + È xN (L(T ε H ) ≤ ℓ N )
, and it has been shown that each term goes to 0.

All is left to prove now is that lim N →+∞ È xN ∃t ≥ N 2 : H(t) ≥ ε = 0, or, by Lemma 5.1, that È xN ∃t ≥ N 2 : χ(t) -π ≥ ε vanishes. After time N 2 , the initial particles are negligible since a number of new particles of the order of N 2 have arrived. So the behavior of the system will be similar to that of a system starting empty, to which we can apply Theorem 6.1 (since in this case the initial state is fixed).

To formalize this argument, a coupling between the processes X x and X 0 , for any x ∈ AE n , is required: Lemma 6.2. For any x, y ∈ AE n with x ≥ y componentwise, it is possible to couple the two processes X x and X y in such a way that for any t ≥ 0, L x (t) -L y (t) ≤ |x| -|y| and the inequality X x (t) ≥ X y (t) holds componentwise.

The proof of this lemma is postponed at the end of the current proof. Let X 0 be the process starting empty coupled with X xN , and let

L 0 = |X 0 |, L xN = |X xN |, χ 0 = X 0 /L 0 and χ xN = X xN /L xN
be the corresponding quantities. The triangular inequality gives [START_REF] Grossglauser | Mobility increases the capacity of ad-hoc wireless networks[END_REF]

È(∃t ≥ N 2 : χ xN (t) -π ≥ ε) ≤ È(∃t ≥ N 2 : χ xN (t) -χ 0 (t) ≥ ε/2) + È(∃t ≥ N 2 : χ 0 (t) -π ≥ ε/2).
Theorem 6.1 states that χ 0 (t) converges to π almost surely, which shows that the last term goes to 0. For the first term, write for each i = 1, . . . , n,

χ xN i (t) -χ 0 i (t) = X xN i (t) L xN (t) - X 0 i (t) L 0 (t) = X xN i (t) -X 0 i (t) L 0 (t) -X 0 i (t)∆ xN (t) L 0 (t) ∆ xN (t) + L 0 (t)
,

where ∆ xN (t) = L xN (t) -L 0 (t). Lemma 6.2 implies that |X xN i (t) -X 0 i (t)| ≤ ∆ xN (t) ≤ |x N |, hence, since the function z → z/(z + a) is decreasing for any a ≥ 0, |χ xN i (t) -χ 0 i (t)| ≤ 2∆ xN (t) ∆ xN (t) + L 0 (t) ≤ 2|x N | |x N | + L 0 (t) = 2 1 + L 0 (t)/|x N | .
This yields in turn, using t ≥ N 2 for the second inequality,

È(∃t ≥ N 2 : χ xN (t) -χ 0 (t) ≥ ε/2) ≤ È ∃t ≥ N 2 : 2 1 + L 0 (t)/|x N | ≥ ε/2 ≤ È inf t≥N 2 1 + L 0 (t)/t • N 2 /|x N | ≤ 4/
ε , Theorem 6.1 shows that L 0 (t)/t → λµ almost surely as t → +∞, and N 2 /|x N | goes to infinity as N goes to infinity by choice of x N . Hence almost surely, lim

N →+∞ inf t≥N 2 1 + L 0 (t)/t • N 2 /|x N | = +∞,
and the theorem is proved.

We now fill in the gap in this proof by proving Lemma 6.2.

Proof of Lemma 6.2. The coupling is given by representation (5) of Section 5 by using the same Poisson processes for X x and X y . It is easy to check that the inequalities X x i (t) ≥ X y i (t) true at t = 0 are preserved at each jump of any of the Poisson processes involved, and that |X x | -|X y | is decreasing over time.

The previous results make it possible to establish the fluid regime of the system by studying the rescaled process X N defined by

X N (t) = X(N t) N , t ≥ 0. ( 11
)
In the following, L N denotes the rescaled number of particles, i.e., L N (t) = L(N t)/N , and χ N = X N /L N is the corresponding proportions. Note that any fluid limit is discontinuous at 0 + (so that strictly speaking, X does not have any fluid limit), because Corollary 5.1 will show that the fluid limit is at π at time 0 + , and Theorem 6.2 will imply that it stays forever proportional to π. Corollary 6.1. Assume λ > µ, and let x : [0, +∞[ → Ê n be defined by

x(t) = 1 + (λ -µ)t π.
Then, for any sequence (x N , N ≥ 1) with |x N | = N , any s, t such that 0 < s < t and any ε > 0:

lim N →+∞ È xN sup s≤u≤t X N (u) -x(u) ≥ ε = 0.
Proof. Since the size of the initial state goes to infinity, the remark following Corollary 5.1 shows that for any δ > 0, the event {T δ ≤ t δ } occurs with high probability. Since T δ is a stopping time, the strong Markov property makes it possible to use X T δ as a new initial point, which is as close to equilibrium as desired. Since moreover the total number of customers did not significantly evolve in this time interval, this initial point will satisfy the hypotheses of Theorem 6.2, which makes it possible to conclude.

Denote ∆ N (s, t) the distance of interest:

∆ N (s, t) = sup s≤u≤t X N (u) -x(u) . (12)
First, the following decomposition makes it possible to consider all further convergences on the set {T δ ≤ t δ }:

È xN (∆ N (s, t) ≥ ε) ≤ È xN (∆ N (s, t) ≥ ε, T δ ≤ t δ ) + È xN (T δ > t δ ),
and the last term goes to 0 by the remark following Corollary 5.1. The strong Markov property used with the stopping time T δ then shows that

È xN (∆ N (s, t) ≥ ε, T δ ≤ t δ ) ≤ xN È X(T δ ) (∆ N (0, t) ≥ ε) . Now, we isolate the event of interest { L(T δ ) -|x N | ≤ √ N } by writing: xN È X(T δ ) (∆ N (0, t) ≥ ε) ; L(T δ ) -|x N | ≤ √ N ≤ max y∈AE n : |y|-|xN | ≤ √ N and y/|y|-π ≤δ È y (∆ N (0, t) ≥ ε) ,
therefore, if we note y N the value that realizes this maximum (the set over which the maximum is considered is finite),

xN È X(T δ ) (∆ N (0, t) ≥ ε) ≤ È xN L(T δ ) -|x N | ≥ √ N + È yN (∆ N (0, t) ≥ ε) .
The following inequality holds for any time u ≥ 0 and any initial state:

|L(u) -L(0)| ≤ N λ (u) + N µ (u) def = N λ+µ (u),
and yields

È xN L(T δ ) -|x N | ≥ √ N ≤ È xN N λ+µ (T δ ) ≥ √ N, T δ ≤ t δ +È xN (T δ > t δ ) ≤ È N λ+µ (t δ ) ≥ √ N + È xN (T δ > t δ ) .
This last sum vanishes, so that all is left to prove is that as N → +∞,

È yN (∆ N (0, t) ≥ ε) = È yN sup 0≤u≤t X N (u) -x(u) ≥ ε → 0.
Note that the initial state y N is now such that |y N |/N goes to 1 (because

|x N | = N and |y N | -|x N | ≤ √ N )
, and H(y N /|y N |, π) is as small as needed to apply Theorem 6.2, since y N /|y N |π ≤ δ and δ > 0 is arbitrary small.

The triangular inequality and the definition of x give for any 0

≤ u ≤ t X N (u) -x(u) ≤ X N (u) -L N (u)π + L N (u) -(1 + (λ -µ)u) π ≤ χ N (u) -π sup 0≤u≤t L N (u) + π sup 0≤u≤t L N (u) -(1 + (λ -µ)u) ,
and so

(13) È yN (∆ N (0, t) ≥ ε) ≤ È yN sup 0≤u≤t χ N (u) -π ≥ ε/ 2 sup 0≤u≤t L N (u) + È yN sup 0≤u≤t L N (u) -(1 + (λ -µ)u) ≥ ε/(2 π ) .
Under È yN , a trivial upper bound for L N (u) for 0 ≤ u ≤ t is given by

L N (u) ≤ 1 N (|y N | + N λ (N t)) def = A N (t),
therefore for any constant C > 0,

È yN sup 0≤u≤t χ N (u) -π ≥ ε/ 2 sup 0≤u≤t L N (u) ≤ È yN sup 0≤u≤t χ N (u) -π ≥ ε/ (2C) + È(A N (t) ≥ C).
For any t ≥ 0, A N (t) converges almost surely to 1 + λt as N goes to infinity, therefore È(A N (t) ≥ C) goes to 0 for C = 2(1 + λt). The other term vanishes as well. Indeed,

È yN sup 0≤u≤t χ N (u) -π ≥ ε/ (2C) = È yN T ε/(2C) ≤ N t ,
and by Lemma 2.1, there exists some

ε ′ > 0 such that T ε/(2C) ≥ T ε ′ H , hence È yN T ε/(2C) ≤ N t ≤ È yN T ε ′ H ≤ N t ≤ È yN T ε ′ H < +∞ .
One can moreover assume ε ′ < ε 0 without loss of generality. Observe that so far, δ is arbitrary: it can be chosen small enough, say δ ≤ δ 0 so that using Lemma 2.1, H(y N /|y N |, π) ≤ ε ′ /2, and y N thus satisfies the hypotheses of Theorem 6.2, which shows that È yN (T ε ′ H < +∞), and hence the first term in the upper bound of (13), vanishes in the limit N → +∞.

The second term of ( 13) is easier to deal with. We reduce the problem to the event {T 0 = +∞} by using the following upper bound:

(14) È yN sup 0≤u≤t L(u) -(1 + (λ -µ)u) ≥ ε/(2 π ) ≤ È yN (T 0 < +∞) + È yN sup 0≤u≤t L(u) -(1 + (λ -µ)u) ≥ ε/(2 π ), T 0 = +∞ .
The first term È yN (T 0 < +∞) in the right hand side of (14) goes to 0 since, by Lemma 2.2, È yN (T 0 < +∞) ≤ È yN (T ε ′ H < +∞) which has just been proved to vanish as N → +∞.

Because L(u) = L(0) + N λ (u) -N µ (u) for all u ≥ 0 on {T 0 = +∞}, we get the following upper bound for the second term:

È sup 0≤u≤t 1 N (|y N | + N λ (N u) -N µ (N u)) -(1 + (λ -µ)u) ≥ ε/(2 π ) ,
and this term goes to 0 thanks to Doob's inequality. The proof is complete.

Stability of the subcritical regime

In this section we consider the subcritical regime λ < µ that is, the case when the input rate is smaller than the maximal output rate. As in the previous section, the key ingredients are the short and long term "homogenization" property and the M/M/1-like behavior of the total number of customers. The next lemma will be useful for establishing the fluid behavior of the system. It gives a control on the stopping time T ε H , or equivalently T ε : with high probability, T ε H is larger than the time needed for a stable M/M/1 queue to empty. Lemma 7.1. Assume λ < µ. Fix some a > 0 and let (x N , N ≥ 1) be any sequence in AE n such that

lim N →+∞ |x N | N = a and lim N →+∞ H(x N /|x N |, π) = 0.
Then, for any t < a/(µλ) and any ε < ε 0 , where ε 0 is given by Lemma 2.2,

lim N →+∞ È xN (T ε H ≤ N t) = 0.
Proof. Denote H N = H(x N /|x N |, π), and let (ℓ N , N ≥ 1) be a sequence of integers such that N ≫ ℓ N ≫ N H N and ℓ N ≫ log N (such a sequence clearly exists, e.g.,

ℓ N = N √ H N ∨ (log N ) 2 ). Proposition 3.2 with α = 1/N 2 and δ = ε/2 gives xN e -θT ε H /N 2 ; L(T ε H ) ≥ ℓ N ≤ C ε/2 e 2n log N +|xN |HN -εℓN /2 , ( 15
)
where the last bound goes to 0 by choice of ℓ N . Let now τ N be defined by τ N = inf{t ≥ 0 : L(t) ≤ ℓ N }. Since ℓ N is an integer and L has jumps ±1, we have L(τ N ) = ℓ N , and consequently, for any t > 0, ( 16)

xN e -θT ε H /N 2 ; L(T ε H ) ≥ ℓ N ≥ xN e -θT ε H /N 2 ; T ε H ≤ τ N ≥ e -θt/N È xN (T ε H ≤ τ N ∧ N t)
Inequalities ( 15) and ( 16) together imply that È xN (T ε H ≤ τ N ∧ N t) goes to 0 as N goes to infinity. Since

È xN (T ε H ≤ N t) ≤ È xN (T ε H ≤ τ N ∧ N t) + È xN (τ N < N t) , all is left to prove is that È xN (τ N < N t) goes to 0 if t < a/(µ -λ). Using the lower bound L(t) ≥ L(0) + N λ (t) -N µ (t) from Proposition 4.1 and the fact that |x N | ≥ (µ -λ)N t + ℓ N for N large enough if t < a/(µ -λ), we get for such a t È xN (τ N < N t) ≤ È xN (∃s ∈ [0, N t] : L(0) + N λ (s) -N µ (s) ≤ ℓ N ) ≤ È xN sup 0≤s≤N t (N µ (s) -N λ (s) -(µ -λ)s) ≥ |x N | -(µ -λ)N t -ℓ N ≤ È xN sup 0≤s≤N t (N µ (s) -N λ (s) -(µ -λ)s) 2 ≥ (|x N | -(µ -λ)N t -ℓ N ) 2 .
Since (N µ (s) -N λ (s) -(µλ)s, s ≥ 0) is a martingale, Doob's inequality yields that the last term is in turn upper bounded by

ÎarN λ (N t) + ÎarN µ (N t) (|x N | -(µ -λ)N t -ℓ N ) 2 ∼ (λ + µ)N t (a -(µ -λ)t) 2 N 2 → 0.
The fluid behavior can now be established. Recall that the rescaled process X N is defined by X N (t) = X(N t)/N for any t ≥ 0. In what follows, for u ∈ Ê, u + denotes max(u, 0). Proposition 7.1. Let x : [0, +∞[ → Ê n be defined by

x(t) = 1 + (λ -µ)t + π.
Then for all 0 < s < t and all ε > 0:

lim

N →+∞ max x∈AE n :|x|=N È x sup s≤u≤t X N (u) -x(u) ≥ ε = 0.
Proof. Lemma 7.1 makes it possible to study the system for t < 1/(µλ). An additional coupling argument, involving larger initial states, is then required to show that fluid limits stay at 0 after that time. For this technical reason, initial states of size equivalent to aN for some a > 0 will be considered, and the following more general result will be established: For a > 0, let x a : [0, +∞[ → Ê n be defined by

x a (t) = a + (λ -µ)t + π.
It will be proved that for any a > 0, any s, t with 0 < s < t and all ε > 0:

lim

N →+∞ max x∈AE n :x=⌊aN ⌋ È x sup s≤u≤t X N (u) -x a (u) ≥ ε = 0,
where the notations of the previous section are used. First assume t < t a = a/(µλ), and set ∆ N (s, t) = sup s≤u≤t X N (u)x a (u) : the first steps of the proof are similar to the underloaded regime, namely using the strong Markov property to replace the arbitrary initial state by some initial state with low entropy. More precisely, let δ N and t N be as in Proposition 5.2: for any

x ∈ AE n with |x| = N , one has È x (∆ N (s, t) ≥ ε) ≤ È x (∆ N (s, t) ≥ ε, T δN ≤ N s) + È x (T δN > N s).
Since t N /N goes to 0, Proposition 5.2 gives that the last term È x (T δN > N s) goes to 0 uniformly in x ∈ AE n with |x| = N . As for the first term, we write

È x (∆ N (s, t) ≥ ε, T δN ≤ N s) ≤ x È X(T δ N ) (∆ N (0, t) ≥ ε) ≤ È yN (∆ N (0, t) ≥ ε) + È x L(T δN ) -L(0) ≥ √ N , where y N ∈ AE * is such that È yN (∆ N (0, t) ≥ ε) = max y∈AE n : |y|-⌊aN ⌋ ≤ √ N and y/|y|-π ≤δN È y (∆ N (0, t) ≥ ε) .
Because T δN ≤ t N with high probability, and because t N / √ N → 0, one can show similarly as in Section 6 that as N goes to infinity, max

x∈AE n :|x|=N È x L(T δN ) -L(0) ≥ √ N → 0.
Along the same lines as in the overloaded case, one gets, by introducing the term L N (u)π that for any C > 0

(17) È yN (∆ N (0, t) ≥ ε) ≤ È yN sup 0≤u≤t χ N (u) -π ≥ ε/ (2C) +È yN sup 0≤u≤t L N (u) ≥ C +È yN sup 0≤u≤t L N (u) -(a + (λ -µ)u) ≥ ε/(2 π ) .
Note that since t < t a , x a (u) = (a + (λµ)u)π for 0 ≤ u ≤ t. For C large enough, È yN sup 0≤u≤t L N (u) ≥ C goes to 0 as N goes to infinity. Moreover, Lemma 2.1

gives

È yN sup 0≤u≤t χ N (u) -π ≥ ε/ (2C) = È yN T ε/(2C) ≤ N t ≤ È yN T ε ′ H ≤ N t
for some ε ′ > 0 that can be assumed to satisfy ε ′ < ε 0 . Since the sequence (y N , N ≥ 1) satisfies the hypotheses of Lemma 7.1 and since t < t a , this last upper bound goes to 0. Moreover, since

È yN sup 0≤u≤t L N (u) -(a + (λ -µ)u) ≥ ε/(2 π ) ≤ È yN (T 0 ≤ N t) + È yN sup 0≤u≤t L N (u) -(a + (λ -µ)u) ≥ ε/(2 π ), T 0 > N t ,
we conclude, using Lemma 7.1 together with Lemma 2.2 for the first term and Doob's inequality for the second one, that

È yN sup 0≤u≤t L N (u) -(a + (λ -µ)u) ≥ ε/(2 π ) → 0.
The proof in the case 0 < s < t < t a is thus complete.

To conclude in the other cases, a monotonicity argument derived from Lemma 6.2 is used. Let 0 < s < t and t ≥ t a , and assume in a first step that t-s < ε/(2(µ-λ)). In addition, let b > (µλ)t be fixed, and let t b = b/(µλ) be the corresponding time. Note that t ≥ t a implies that b > a, so that for any x ∈ AE n with |x| = ⌊aN ⌋, there exists some y ∈ AE n such that y ≥ x componentwise and |y| = ⌊bN ⌋. For such x, y, Lemma 6.2 shows that X x and X y can be coupled in such a way that |X x (t)| ≤ |X y (t)| for any t ≥ 0. Hence for any u ≥ s, using the inequality v ≤ |v| ≤ n v for any v ∈ Ê n , one gets

X x N (u) -x a (u) ≤ X x N (u) + |x a (s)| ≤ X y N (u) + |x a (s)| ≤ n X y N (u) -x b (u) + |x b (s)| + |x a (s)|.

By definition

|x b (s)| + |x a (s)| = (µ -λ)(t b -s) + (µ -λ)(t a -s) + ≤ 2(µ -λ)(t b -s).
This yields in turn

È x sup s≤u≤t X N (u) -x a (u) ≥ ε ≤ È y sup s≤u≤t X N (u) -x b (u) ≥ ε ′ where ε ′ = ε -2(µ -λ)(t b -s) /n, and finally max x∈AE n :|x|=⌊aN ⌋ È x sup s≤u≤t X N (u) -x a (u) ≥ ε ≤ max y∈AE n :|y|=⌊bN ⌋ È y sup s≤u≤t X N (u) -x b (u) ≥ ε ′ .
Since it has been assumed that ts < ε/(2(µλ)), b > (µλ)t can be chosen small enough so that ε ′ > 0. Since t < t b , the first part of the proof implies that lim

N →+∞ max y∈AE n :|y|=⌊bN ⌋ È y sup s≤u≤t X N (u) -x b (u) ≥ ε ′ = 0.
This proves in particular that when 0 < s < t and ts < ε/(2(µλ)), then

max |x|=⌊aN ⌋ È x (∆ N (s, t) ≥ ε) → 0.
It is now left to extend this result to any s, t such that s < t, which is a consequence of the following decomposition: max

x∈AE n :|x|=⌊aN ⌋ È x (∆ N (s, t) ≥ ε) ≤ q j=1 max x∈AE n :|x|=⌊aN ⌋ È x (∆ N (s j-1 , s j ) ≥ ε)
where s 0 = s < s 1 < . . . < s q = t and s js j-1 < ε/(2(µλ)) for 1 ≤ j ≤ q. Indeed, it has just been shown that each term of this finite sum goes to 0.

We finally can infer the stability of the process X by using Corollary 9.8 of [START_REF] Robert | Stochastic Networks and Queues[END_REF]:

Proposition 7.2. When λ < µ, the Markov process X is ergodic.

Proof. According to Corollary 9.8 p. 259 of [START_REF] Robert | Stochastic Networks and Queues[END_REF], it is enough to show that for some deterministic time T > 0, lim

N →+∞ max x∈AE n :|x|=N x (L N (T )) = 0.
Recall that L N (T ) = L(N T )/N , and let ε > 0 be fixed: then, for x ∈ AE n with |x| = N :

x L N (T ) ≤ ε + x L N (T ); L N (T ) > ε ≤ ε + (1 + λT )È x L N (T ) > ε + 1 N x N λ (N T ) -λN T ; L N (T ) > ε .
where the second inequality comes from L N (T ) ≤ L N (0) + N λ (N T )/N . For any T ≥ 0, using Cauchy-Schwartz inequality, an upper bound on the last term is given by

1 N x N λ (N T ) -λN T ; L N (T ) > ε ≤ 1 N (|N λ (N T ) -λN T |) ≤ λT N ,
so that finally max

x∈AE n :|x|=N x L N (T ) ≤ ε + (1 + λT ) max x∈AE n :|x|=N È x L N (T ) > ε + λT N ,
and all is left to prove is that for some T > 0, max |x|=N È x L N (T ) > ε goes to 0 as N grows to infinity: this is a direct consequence of Proposition 7.1 with T = 1/(µλ) since x(T ) = 0. The proof is now complete.

The function ϕ 0 can then be defined on D(0) by

ϕ 0 (v) = 0 -∞ n i=1 µ i φ i (v, s) 1 + φ i (v, s) -λ i φ i (v, s) ds
and is continuous and bounded above on D(0).

(ii) The function ϕ given by (19) is well defined for (v, t) ∈ A and satisfies:

ϕ(v, t) = ϕ 0 (P -t v) (v, t) ∈ A.
ϕ is bounded above on A and continuous with respect to v ∈ D(t) for fixed t ∈ Ê.

Proof. (i) Notice that, for fixed v ∈ Ê n , the map s → φ(v, s) = e -sQ v is continuous on Ê (with values in Ê n ). Moreover, if v ∈ H, it has a fast decay as s tends to -∞ as a consequence of the exponential fast convergence of P t (i, •) to π (already used in Section 5): There exist some positive constants η and C 1 such that, for any s ≤ 0 max 1≤i,j≤n

|P -s (i, j) -π j | ≤ C 1 • e ηs . ( 22
)
This gives, for s ≤ 0 and v ∈ H,

φ(v, s) ≤ C 2 • e ηs v , (23)
where C 2 = nC 1 , which ensures the existence of the vectorial integral 0 -∞ φ(v, s)ds for any v ∈ H. This integral is continuous with respect to v in H since, for v ∈ H,

0 -∞ P -s vds = 0 -∞ (P -s -Π) vds = 0 -∞ (P -s -Π) ds v
where Π is the square matrix with all lines equal to π = (π 1 , . . . , π n ) and the last matricial integral has a coefficientwise meaning (and is well defined due to ( 22)). This shows the integral 0 -∞ φ(v, s)ds as a linear function of v ∈ H, thus proving its continuity with respect to v ∈ H. The boundedness of this function on D(0) follows since D(0) has compact closure in H.

For the second integral, Lemma A.1 and the condition v ∈ D(0) first ensure that ½ + φ(v, s) > 0 for s ≤ 0. The existence of this integral then again follows from the continuity of s → φ(v, s) and from the exponential decay in (23).

Let us now begin by proving that it is bounded above on D(0), writing

0 -∞ φ i (v, s) 1 + φ i (v, s) ds = -1 -∞ φ i (v, s) 1 + φ i (v, s) ds + 0 -1 φ i (v, s) 1 + φ i (v, s) ds,
and upperbounding each term. It is easy for the second one, since 1

+ φ i (v, s) > 0 implies that φ i (v, s)/(1 + φ i (v, s)) ≤ 1. In particular, 0 -1 φ i (v, s) 1 + φ i (v, s) ds ≤ 1.
The first term can be extended to v ∈ D(0) (again by Lemma A.1 and by the exponential decay in (23)) and can be shown to be bounded on D(0). Indeed, for v ∈ D(0) and s ≤ -1, 1 + φ i (v, s) is positive and tends to 1 as s tends to -∞ uniformly in v ∈ D(0) since, by (23), sup

v∈D(0) φ(v, s) ≤ C 2 • e ηs sup v∈D(0) v . (24)
Then 1 + φ i (v, s) is bounded below by some positive δ for (v, s) ∈ D(0)×] -∞, -1] (by (24), this is the case on D(0)×]-∞, -κ] for κ large enough, and D(0)×[-κ, -1] is compact), and the following bound holds for v ∈ D(0), using (24):

-1 -∞ φ i (v, s) 1 + φ i (v, s) ds ≤ C 2 δ • sup u∈D(0) u -1 -∞ e ηs ds = C 2 e -η δη sup u∈D(0)
u .

Let us now show the continuity of 0 -∞ φ i (v, s)/(1 + φ i (v, s))ds with respect to v ∈ D(0), using the continuity of φ i (v, s) for fixed s, together with Lebesgue's dominated convergence theorem. The difficulty is that φ i (v, s)/(1 + φ i (v, s)) is not clearly dominated uniformly in v ∈ D(0) by some integrable function of s on ]-∞, 0], since for s close to 0 and v close to the the portion of ∂D(0) where 1+v i = 0, the ratio φ i (v, s)/(1 + φ i (v, s)) goes to infinity and is not easily controlled.

It is however possible to show local domination, using (21) in the particular case t 0 = 0 and dominating the integrand on each D(t), t > 0. This will prove continuity on each D(t), t > 0, hence continuity on D(0) since the D(t), t > 0, are open subsets of D(0). The domination uses the same argument as in the last point:

if t > 0, then δ(t) = inf 1 + φ i (v, s), (v, s) ∈ D(t)×] -∞, 0]
is positive. Then, for any v ∈ D(t) and s ≤ 0,

φ i (v, s) 1 + φ i (v, s) ≤ C 2 δ(t) • e ηs sup u∈D(t)
u where the right hand side is integrable on ] -∞, 0], and hence provides the required domination.

(ii) We use the group structure of (P s , s ∈ Ê) to rewrite both integrals as:

t -∞ φ i (v, s)ds = 0 -∞ φ i (v, s + t)ds = 0 -∞ φ i (P -t v, s)ds and t -∞ φ i (v, s) 1 + φ i (v, s) ds = 0 -∞ φ i (v, s + t) 1 + φ i (v, s + t) ds = 0 -∞ φ i (P -t v, s) 1 + φ i (P -t v, s)
ds, which ensures their existence for P t v ∈ D(0), i.e., v ∈ D(t) or equivalently (v, t) ∈ A, and proves the connexion between ϕ and ϕ 0 , hence the stated properties of ϕ.

v ∈ D(0), ϕ(v, •) is clearly C 1 on the interval ] -∞, t v [, where t v = sup{t ≥ 0 : ½ + φ(v, t) > 0} > 0 (by continuity of φ(v, •) on Ê), and ∂ϕ(v, t)/∂t = n 1 [µ i φ i (v, t)/(1 + φ i (v, t)) -λ i φ i (v, t)] on this interval.
The following proposition constitutes the first step in defining a new spacetime harmonic function, obtained by integrating with respect to v ∈ D(t) the parametrized family of functions h v given by (18), with ϕ given by (19).

As D(t) ⊂ H and H is an n -1 dimensional subspace of Ê n which is isomorphic to Ê n-1 through the one to one linear mapping

H : Ê n-1 -→ H u -→ û = (u, -n-1 i=1 π i u i /π n )
, the new harmonic function will rather take the form of an integral over the following subset of Ê n-1 :

C(t) = H -1 (D(t)) = u ∈ Ê n-1 : û ∈ D(t) = u ∈ Ê n-1 : ½ + φ(û, t) > 0 .
Proposition A.1. For any locally Lebesgue-integrable f on Ê n-1 , the function g(t, x) given by the formula

g(t, x) = C(t) h û(t, x)f (u)du = C(t) e ϕ(û,t) • n i=1 (1 + φ i (û, t)) xi • f (u)du (25) is space-time harmonic in the domain [0, +∞[×AE * n . Proof. g is well-defined on [0, +∞[×AE * n . Indeed n 1 (1 + φ i (•, t))
xi is continuous on Ê n-1 for fixed t ≥ 0 and x ∈ AE * n , hence bounded on the bounded set C(t) (since C(t) corresponds to D(t) through H -1 ). By Lemma A.2, e ϕ(•,t) also is continuous and bounded on C(t) since ϕ(•, t) is continuous and bounded above on D(t). Then, since f is locally integrable, the product of these three functions is integrable on C(t).

We have to show that ∂g/∂t exists and satisfies ∂g(t, x)/∂t + Ω(g(t, •))(x) = 0. As a rough argument, one expects that ∂g ∂t

(t, x) = C(t) ∂h û ∂t (t, x) • f (u)du. ( 26
)
Indeed the additional derivation term resulting from the t-dependency of the domain C(t) is bound to vanish, since h û(t, x) is zero for u on the frontier of C(t) (recall that x ∈ AE * n ). Therefore, since Ω commutes with integration, ∂g ∂t

(t, x) + Ω(g(t, •))(x) = C(t) ∂h û ∂t (t, x) + Ω(h û(t, •))(x) • f (u)du = 0
by harmonicity of the functions h v , using Proposition 3.1 with V = [0, t v [. To make this rigorous, all is needed is to prove (26), by fixing some arbitrary

x ∈ AE * n and t 0 ≥ 0 and studying the ratio [g(t 0 + δ, x) -g(t 0 , x)]/δ as δ tends to zero. The monotonicity of the family of sets C(t) forces to distinguish the two cases δ > 0 and (for t 0 > 0) δ < 0. For the sake of shortness we will only present here the case δ > 0, the other side being similar: both cases make a repeated use of the mean-value theorem and of Lebesgue's dominated convergence theorem.

To simplify notations, define for u ∈ C(t), t ≥ 0 and

x ∈ AE * n , h(u, t, x) = h û(t, x) = e ϕ(û,t) n i=1 (1 + φ i (û, t)) xi .
Note that h inherits the derivability properties of ϕ with respect to t (the factor involving φ being C 1 on Ê):

for fixed u ∈ C(0) and x ∈ AE * n , h is C 1 on ] -∞, t û[.
Let x ∈ AE * n and t 0 ≥ 0 be fixed. For any positive δ, using the inclusion D(t 0 + δ) ⊂ D(t 0 ) one can write:

g(t 0 + δ, x) -g(t 0 , x) δ = C(t0+δ) h(u, t 0 + δ, x) -h(u, t 0 , x) δ f (u)du - C(t0)\C(t0+δ) h(u, t 0 , x) δ f (u)du.
Let first show that the first term tends to C(t0) ∂h ∂t (u, t 0 , x)f (u)du as δ tends to zero. Using the mean value theorem, since h(u, •, x) is C 1 on [0, t 0 + δ] for u ∈ C(t 0 + δ), this first term can be rewritten as

C(t0+δ) ∂h ∂t (u, t 0 + p(u)δ, x)f (u)du
for some p(u) ∈]0, 1[ depending on u, t 0 , x and δ.

As δ goes to zero, ∂h ∂t (u, t 0 + p(u)δ, x)f (u) tends to ∂h ∂t (u, t 0 , x)f (u) and the indicator function of C(t 0 +δ) tends to the indicator function of C(t 0 ) due to relation (21) which obviously extends to the sets C(t). The convergence of the first term will then result from Lebesgue's theorem by computing (we omit the variable (û, t) under φ):

∂h ∂t (u, t, x) = e ϕ(û,t) n i=1 (1 + φ i ) xi-1 j =i (1 + φ j ) xj µ i -λ i φ i (1 + φ i ) + x i ∂φ i ∂t ,
and then using the following domination: for 0 < δ < 1 and u ∈ Ê n-1 , ∂h ∂t

(u, t 0 + p(u)δ, x)f (u)½ C(t0+δ) ≤ k(t 0 , x) • |f (u)| • ½ C(t0) ,
where the right hand side is integrable on Ê n-1 , and k(t 0 , x) holds for:

sup

A e ϕ × sup D(t0)×[0,t0+1] n i=1 (1 + φ i ) xi-1 j =i (1 + φ j ) xj (µ i -λ i φ i (1 + φ i ) + x i ∂φ i ∂t ) .
The convergence of the first term is thus proved. We now prove that the second term vanishes as δ tends to 0. For any u ∈ C(t 0 )\C(t 0 +δ) there exists some index i (depending on u) such that 1+φ i (û, t 0 ) > 0 while 1 + φ i (û, t 0 + δ) ≤ 0, and this implies by the mean value theorem that 0 < 1 + φ i (û, t 0 ) ≤ -δ ∂φ i ∂t (û, t 0 + q(u)δ) for some q(u) ∈]0, 1[ depending on u, t 0 and δ. One can deduce the following upper bound, again assuming 0 < δ < 1:

C(t0)\C(t0+δ) h(u, t 0 , x) δ f (u)du ≤ k C(t0)\C(t0+δ) |f (u)|du,
where k is the following constant:

sup A e ϕ × max 1≤i≤n    sup D(t0)×[0,t0+1] ∂φ i ∂t × sup D(t0)×{t0} (1 + φ i ) xi-1 j =i (1 + φ j ) xj    .
The right hand side of the previous inequality converges to zero, again by Lebesgue's theorem, because f is integrable on the bounded set C(t 0 ), and the sets C(t 0 ) \ C(t 0 + δ) decrease to ∅ as δ decreases to zero, due to relation (21).

A.2. Change of variables. The last step is now a change of variable in the harmonic function given by the integral (25), for a suitable choice of f so as to separate the time and space variables.

It informally consists in choosing as new variables the quantities π i 1 + φ i (v, t)

(1 ≤ i ≤ n), changing the domain D(t) into P ≡ {v ∈ Ê n : v > 0 and n i v i = 1}. Formally, it will be slightly more complicated due to integration with respect to Lebesgue's measure on subdomains of Ê n-1 (the C(t)'s), which forces to a round trip from Ê n-1 through Ê n . So, to be correct, this change of variable will rather transform the domain C(t) into the following one:

S = u ∈ Ê n-1 : u > 0 and n-1 i=1 u i < 1 . ( 27
)
We need to introduce some additional notations. Denote by ∆ the diagonal n × n square matrix having π 1 , . . . , π n as its diagonal elements, by J the projection

J : Ê n -→ Ê n-1 (v 1 , . . . , v n ) -→ (v 1 , . . . , v n-1 )
,

and by K, the hyperplane of Ê n defined by

K = v ∈ Ê n : n i=1 v i = 1 .
K corresponds to Ê n-1 through the one to one affine transformation (analogous to H from Ê n-1 to H):

K : Ê n-1 -→ K u -→ ũ = (u, 1 -n-1 i=1 u i ) ,
Notice that the inverse mapping of K (resp. H) is given by the restriction of J to K (resp. H). The announced change of variable is given by the t-depending transformation Ψ t : Ê n-1 -→ Ê n-1 u -→ J∆(P -t Hu + ½) .

The next lemma shows that Ψ t can be considered for a change of variables:

Lemma A.3. For any t ≥ 0, Ψ t is a one to one affine transformation on Ê n-1 which inverse mapping is given by

Ψ -1 t (u) = JP t (∆ -1 Ku -½)
and which Jacobian is Jac(Ψ t ) = e θt n-1 i=1 π i . Moreover, Ψ t (C(t)) = S.

Proof. Since Ψ t is clearly an affine transformation in Ê n-1 , its Jacobian is the one of its linear part J∆P -t H. Now J∆ = ∆ ′ J, where ∆ ′ is the diagonal (n-1)×(n-1) square matrix having π 1 , . . . , π n-1 as its diagonal elements, so that Jac (J∆P -t H) = The second equality results from the facts that J restricted to H coincides with H -1 and that H is generated by the first n -1 eigenvectors of P -t , so that H is invariant under P -t , which restriction to H has Jacobian n-1 i=1 e -θit = n i=1 e -θit = Jac (P -t ) (= e θt ) since θ n = 0. In particular Jac(Ψ t ) = 0, so that Ψ t is invertible.

The formula for Ψ -1 easily results from the fact that ∆(• + ½) maps H onto K and that the inverse mapping of K is given by the restriction of J to K. Now using C(t) = u ∈ Ê n-1 : ½ + P -t Hu > 0 together with the facts that ∆ preserves the relation v > 0 and (again) that ∆(• + ½) maps H onto K, one gets that Ψ t (C(t)) is included in J({v ∈ K : v > 0}) = S. Equality results from a similar argument for Ψ -1 t (S) ⊂ C(t).

The transformation Ψ t hence corresponds to the two following diagrams:

H ⊂ Ê n K ⊂ Ê n H ⊂ Ê n K ⊂ Ê n C(t) ⊂ Ê n-1 S ⊂ Ê n-1 C(t) ⊂ Ê n-1 S ⊂ Ê n-1 H ∆(P-t•+½) J Ψt J K Pt(∆ -1 •-½) Ψ -1 t
All is left now is to choose for (25) a family of locally integrable functions in Ê n-1 which behave nicely with respect to the change of variable Ψ t . It will be given by the functions f α-1 for positive α's, where, for u ∈ Ê n-1 and v ∈ Ê n ,

f (u) = ψ(Hu) = ψ(û) and ψ(v) = n-1 i=1 |(ω -1 v) i |.
Here, for any v ∈ Ê n and 1 ≤ i ≤ n, v i denotes the ith coordinate of v, so that the (ω -1 v) i 's (1 ≤ i ≤ n -1) are the first n -1 coordinates of v in the base (ω 1 , . . . , ω n ) of eigenvectors of Q. As will become clear in (30), the next lemma establishes the property of ψ that makes it behave nicely with respect to the change of variables given by Ψ t , by isolating the dependency in time in a separate factor:

Lemma A.4. For any t ≥ 0 and v ∈ Ê n , ψ(P t v) = e -θt ψ(v).

Proof. This result stems from diagonalizing P t as ω -1 P t ω = e -tΘ , where Θ is the diagonal n×n square matrix having θ 1 , . . . , θ n as its diagonal elements. This readily gives ψ(P t v) = n-1 i=1 |(e -tΘ ω -1 v) i | = e -θt ψ(v).

The main technical point is to establish that f α-1 is locally integrable: the next lemma provides in addition a useful upper bound.

Lemma A.5. f α-1 is locally integrable on Ê n-1 for any α > 0. Moreover, for any compact set T ⊂ Ê n-1 ,

sup 0<α≤1 α n T f (u) α-1 du < +∞. ( 28
)
Proof. If α ≥ 1, f α-1 is continuous on Ê n-1 , hence locally integrable. So consider only the case when 0 < α < 1

If the matrix ω has real coefficients (it can be chosen such when the eigenvalues θ j of Q are real, which is in particular the case for a reversible Q), f α-1 is easily shown to be integrable on any compact set T of Ê n-1 by operating the change of variable:

Ê n-1 -→ Ê n-1 u -→ (ω -1 Hu) i 1≤i≤n-1 = Jω -1 Hu
which is linear and one to one, and transforms T f (u) α-1 du into the integral over some compact subset of Ê n-1 of the locally integrable function n-1 i=1 |u i | α-1 (up to the Jacobian constant factor). Then by considering A large enough so that Jω -1 H(T ) ⊂ [-A, A] n-1 and A ≥ 1, (28) is obtained from the fact that

[-A,A] n-1 n-1 i=1 |u i | α-1 du = (2A α ) n-1 α -(n-1) ≤ (2A) n-1 α -n .
This is not directly possible when ω has non real coefficients. In this case we can show that f α-1 is upper bounded by n-1 i=1 |(Lu) i | α-1 for some invertible (n -1) × (n -1) square matrix L with real coefficients. The change of variable u → Lu is then possible, showing (28) in this case similarly as before, which implies the local integrability of f α-1 for 0 < α < 1.

Since α < 1 this amounts to lower bounding f by All is left now is to prove the existence of some p ∈ [0, 1] such that pA + (1p)B is invertible. It is done through considering the degree n -1 polynomial with complex variable: det(A + zB), which is non zero at z = i (since det C = 0), hence not equal to the null polynomial. It then cannot be zero on the whole real interval [0, 1], which gives the result.

Proof of Theorem 3.1. The previous lemma shows that f α-1 is a suitable function to plug in (25): since ϕ(v, t) = ϕ 0 (P -t v) for (v, t) ∈ A, rewriting (25) and using the definition of f gives g(t, x) = C(t) e ϕ(û,t) n i=1

(1 + φ i (û, t)) xi f (u) α-1 du = C(t) e ϕ0(P-tHu) n i=1 (½ + P -t Hu) xi i ψ(P t P -t Hu) α-1 du.

Expressing P -t Hu through Ψ t u for u ∈ Ê n-1 , one gets, since K is the inverse of J restricted to K and ∆(P -t Hu + ½) ∈ K,

P -t Hu = ∆ -1 KΨ t u -½, u ∈ C(t), (29)
so that operating the change of variables given by Ψ t yields by Lemma A. (30)

Since ω n = ½, we have ψ(v -½) = ψ(v) for any v ∈ Ê n , hence ψ P t (∆ -1 ũ -½) = ψ P t ∆ -1 ũ = e -θt ψ(∆ -1 ũ), where the last equality comes from Lemma A.4. The following function g ′ , which only differs from g by a multiplicative factor, is thus again space-time harmonic: where we have defined G(v) = e ϕ0(∆ -1 v-½) , v ∈ P.

Hence defining F as

F (v) = ψ(∆ -1 v), v ∈ Ê n
yields exactly the local martingale of Theorem 3.1. The second expression ( 2) is easily obtained. All one needs to do to complete the proof of Theorem 3.1 is to check the announced properties of these two functions F and G.

First, G is continuous and bounded on P since, by Lemma A.2, ϕ 0 is continuous and bounded above on D(0) (if v ∈ P, then ∆ -1 v -½ ∈ H and ∆ -1 v > 0, so that ∆ -1 v -½ ∈ D(0)).

Moreover, F is clearly positive and continuous on Ê n , and thus bounded on the bounded subset P of Ê n , and so (3) is the only property left to be checked.

Relation (29) and the fact that ψ(• -½) = ψ(•), together with the definitions of where T = Ψ -1 0 (S). (3) then follows using Lemma A.5.

Proposition 5 . 2 .

 52 There exist two positive constants A and η such that, for any sequence of positive numbers (δ N , N ≥ 1) satisfying lim N →+∞ δ N = 0 and lim

n- 1 i=1

 1 |(Lu) i |.Call C the complex invertible (n -1) × (n -1) square matrix associated to the linear mapping Jω -1 H on Ê n-1 , so that f (u) = n-1 j=1 |(Cu) j |, and write C = A + iB where A and B are real square matrices. For any p ∈ [0, 1], u ∈ Ê n-1 and j ∈ {1, . . . , n -1} , the following inequalities hold:|(Cu) j | ≥ max{|(Au) j |, |(Bu) j |} ≥ |p(Au) j + (1p)(Bu) j | = (pA + (1p)B)u j .

3 g

 3 t (∆ -1 ũ -½) α-1 du.

g

  ′ (t, x) = e θt S -1 ũ) α-1 du,

FF

  and f , yield that F (ũ) = f (Ψ -1 0 u) according to the following steps:F (ũ) = ψ(∆ -1 Ku) = ψ(∆ -1 KΨ 0 (Ψ -1 0 u) -½) = ψ(HΨ -1 0 u) = f (Ψ -1 0 u).It follows by the change of variables induced by Ψ0 that, for α ≤ 1, S (ũ) α-1 du = S f (Ψ -1 0 u) α-1 du = Jac(Ψ 0 ) T f (u) α-1 du,

  The function ϕ is now legitimately defined by (19) for t ∈ Ê and v ∈ D(t). For fixed t ∈ Ê , ϕ(•, t) is continuous (hence measurable) with respect to v in

	D(t) and bounded above on this domain. Reversely, for fixed

Acknowledgement

We are grateful to Philippe Robert who pointed out this problem to us, and suggested substantial improvements both in the form and in the technical content of this paper.

Appendix A. Martingale construction

This appendix is devoted to proving Theorem 3.1, which states the existence of a fundamental family of local martingales. In Proposition A.1, we first establish the harmonicity of a special function g, which has an integral form. Then a change of variables leads to the local martingale introduced in Theorem 3.1.

A.1. An integral harmonic function. The starting point is the generator Ω of the Markov process X given, for any x ∈ AE n and any function f : Ê n → Ê, by:

In addition to the irreducibility of Q = (q ij ) 1≤i,j≤n , we will require that Q is diagonalizable in , i.e., that there exists a set (ω j , 1 ≤ j ≤ n) of eigenvectors of Q that generate Ê n . The complex square matrix ω = (ω i,j ) 1≤i,j≤n where ω j = (ω i,j ) 1≤i≤n is invertible.

We can assume without loss of generality that ω n = ½, denoting by ½ the vector in Ê n with all coordinates equal to 1, so that ω n is associated to the null eigenvalue; more generally, for 1 ≤ j ≤ n, θ j will denote the (possibly complex) eigenvalue associated to ω j . The negative trace of Q is then given by -θ = n 1 θ i with θ > 0.

In the sequel H will denote the hyperplane of Ê n defined by

For j = 1, . . . , n -1, ω j ∈ H since Qω j = θ j ω j for θ j = 0 implies (in a matricial form, where π is a row and ω j a column): πω j = (θ j ) -1 πQω j which is 0 since πQ = 0. These n -1 eigenvectors then generate H.

We recall some notations and results of Section 3. (P t , t ∈ Ê) denotes the Qgenerated Markov semi-group of linear operators in Ê n : P t = e tQ , extended to all real indices t into a group. Each P t has eigenvalues e θjt and eigenvectors ω j , j = 1, . . . , n. For any v ∈ Ê n and t ≥ 0, we define

is space-time harmonic with respect to Ω in the domain V × AE * n (see Proposi- tion 3.1).

The suitable domain of integration for constructing our martingale will be:

, where, for any u ∈ Ê n , u ≥ 0 (resp. u > 0) means that u i ≥ 0 (resp. u i > 0) for every i = 1, . . . , n.

For each t ∈ Ê, D(t) is an open subset of H. Moreover, it is clear from the definition of D(t) and from the invariance of H under the group of operators (P s , s ∈ Ê) that, for any v ∈ Ê n and any t ≥ 0, v ∈ D(t) ⇐⇒ P -t v ∈ D(0). So, for any t ∈ Ê, D(t) = P t (D(0)). Then, since D(0) = {v ∈ Ê n : n

Define the subset A of H × Ê by:

The first step is to show that the following choice of ϕ makes sense:

for (v, t) ∈ A. This is the object of the following two lemmas, which will also give some regularity properties of ϕ in view of Proposition A.1.

and

Proof. Let first remark that the irreducibility of Q implies that, for any r > 0 and (i, j) ∈ {1, . . . , n}, the probability P r (i, j) that a Markov process with generator Q initiated at i is in state j at time r is positive. Indeed, if i = i 0 , i 1 , . . . , i k = j is a path from i to j such that q i l-1 ,i l > 0 for l = 1, . . . , k, then there is a positive probability that the process has exactly followed this path by time r. This implies that P r u > 0 for any r > 0 and u ∈ Ê n such that u ≥ 0 and u = 0. Now let (v, t) satisfy the hypotheses in the lemma, then ½ + φ(v, t) = 0 since 0 = ½ + v = P t ½ + P -t v = P t ½ + φ(v, t) , and the previous property applied to u = ½ + φ(v, t) and r = ts for s < t gives,

The implication t > s =⇒ D(t) ⊂ D(s) follows, noticing that -½ / ∈ H.

To show (21) for t 0 ∈ Ê, note that D(t 0 ) contains the right hand side union by (20), and that the reverse holds since, for v ∈ D(t 0 ), the inequality ½+φ(v, t 0 ) > 0 extends to some neighborhood of t 0 .