Nicolas Champagnat
email: nicolas.champagnat@inria.fr

Denis Villemonais
email: denis.villemonais@univ-lorraine.fr

Lyapunov criteria for uniform convergence of conditional distributions of absorbed Markov processes

Keywords: stochastic Lotka-Volterra systems, multitype population dynamics, multidimensional birth and death process, multidimensional Feller diffusions, process absorbed on the boundary, quasi-stationary distribution, uniform exponential mixing property, Lyapunov function 2010 Mathematics Subject Classification. Primary: 60J27, 37A25, 60B10. Secondary: 92D25, 92D40

Introduction

We consider a Markov process (X t , t ≥ 0) evolving in a state space E ∪ ∂, where ∂ ∩ E = ∅ and ∂ is absorbing. A quasi-stationary distribution for X is a probability measure ν QSD on E such that

P ν QSD (X t ∈ • | t < τ ∂ ) = ν QSD , ∀t ≥ 0, P µ (X t ∈ • | t < τ ∂ ) -ν QSD T V ≤ Ce -γt µ(ϕ 1 ) µ(ϕ 2 ) , ∀t ≥ 0, (1.2)
for all initial distribution µ on E. In the cases considered below, the function ϕ 1 may be taken bounded, but ϕ 2 is usually not bounded away from zero close to the boundary of E, which leads to a non-uniform convergence result.

As may be expected, the stronger convergence result (1.1) requires a finer control of the behavior of the process near the boundary, uniformly in E. As a consequence, our Lyapunov criteria are more involved than those of [START_REF] Champagnat | General criteria for the study of quasi-stationarity[END_REF] and the techniques used here differ: in the present article, we use the control of the derivative of the continuous-time semi-group of the process to localize the conditioned process when it starts close to the boundary (see Proposition 2.3), while [START_REF] Champagnat | General criteria for the study of quasi-stationarity[END_REF] makes use of the time-discretisation of the semigroup for this purpose. Additional arguments are also required to control the behavior of the conditioned process close to infinity. Note however that, in the end, our approach relies on the discrete time criterion of [START_REF] Champagnat | Exponential convergence to quasistationary distribution and Q-process[END_REF] and it is tempting to think that one may use a combination of the present approach and of the discrete time criterion of [START_REF] Champagnat | General criteria for the study of quasi-stationarity[END_REF] in order to prove (1.2) with ϕ 2 = 1. Although this would lead to more complicated criteria than the one presented below, such an approach could also apply to processes that do not come down from infinity, such as Orstein-Uhlenbeck processes, with uniform convergence among initial distributions in bounded subsets. We leave this question for future research.

The uniform convergence (1.1) is also transferred to other properties of the process. Indeed, it provides uniformity in the time to the so-called mortality/extinction plateau (see [START_REF] Méléard | Quasi-stationary distributions and population processes[END_REF]), uniform convergence of the process conditioned to late survival to the so-called Q-process, uniform exponential ergodicity of the Q-process (see [START_REF] Champagnat | Uniform convergence to the Qprocess[END_REF]), and uniform convergence of x → e λ 0 t P x (t < τ ∂ ) to an eigenfunction η : E → (0, +∞) for the semigroup, for some positive constant λ 0 > 0, when t → +∞ (see [START_REF] Champagnat | Exponential convergence to quasistationary distribution and Q-process[END_REF]Theorem 2.5]).

One of the main tools of our proofs is [START_REF] Champagnat | Exponential convergence to quasistationary distribution and Q-process[END_REF], where we showed that the uniform exponential convergence of conditional distributions in total variation to a unique quasi-stationary distribution is equivalent to the following conditions: there exists a probability measure ν on E such that (A1) there exist t 0 , c 1 > 0 such that for all x ∈ E,

P x (X t 0 ∈ • | t 0 < τ ∂ ) ≥ c 1 ν(•);
(A2) there exists c 2 > 0 such that for all x ∈ E and t ≥ 0,

P ν (t < τ ∂ ) ≥ c 2 P x (t < τ ∂ ).
Although it has the merit of generality, this criterion appears to be hard to check in practice [START_REF] Champagnat | Uniform convergence to the Qprocess[END_REF][START_REF] Champagnat | Criteria for exponential convergence to quasi-stationary distributions and applications to multi-dimensional diffusions[END_REF][START_REF] Champagnat | Uniform convergence of conditional distributions for absorbed one-dimensional diffusions[END_REF][START_REF] Champagnat | Exponential convergence to quasistationary distribution for absorbed one-dimensional diffusions with killing[END_REF][START_REF] Chazottes | On time scales and quasistationary distributions for multitype birth-and-death processes[END_REF][START_REF] Horton | Stochastic Methods for the Neutron Transport Equation I: Linear Semigroup asymptotics[END_REF]. In particular, it lacks computational methods for verification. This is one of the purposes of the new criterion we present. It involves two bounded nonnegative functions V and ϕ such that V (x)/ϕ(x) → +∞ when x converges to the boundary of E or to ∞, satisfying

-Lϕ ≤ C 1 1 K
for some bounded subset K of E and

LV + C 2 V 1+ε ϕ ε ≤ C 3 ϕ
for some ε > 0 and some constants C 1 , C 2 , C 3 > 0, where L denotes (an extension of) the infinitesimal generator of the Markov process X.

We apply this criterion to Lotka-Volterra birth and death processes, and to competitive Lotka-Volterra Feller diffusion processes. The quasistationary behavior of (extensions of) these two models have received a lot of attention in the one-dimensional case [START_REF] Van Doorn | Quasi-stationary distributions and convergence to quasi-stationarity of birth-death processes[END_REF][START_REF] Steinsaltz | Quasistationary distributions for one-dimensional diffusions with killing[END_REF][START_REF] Kolb | Quasilimiting behavior for one-dimensional diffusions with killing[END_REF][START_REF] Martínez | Existence and uniqueness of a quasistationary distribution for markov processes with fast return from infinity[END_REF][START_REF] Cattiaux | Quasi-stationary distributions and diffusion models in population dynamics[END_REF][START_REF] Champagnat | Uniform convergence of conditional distributions for absorbed one-dimensional diffusions[END_REF][START_REF] Chazottes | Sharp asymptotics for the quasi-stationary distribution of birth-and-death processes[END_REF][START_REF] Hening | Quasistationary distributions for onedimensional diffusions with singular boundary points[END_REF]. We focus here on the multidimensional case, where the processes evolve on the state spaces E ∪ ∂ = Z d + for birth and death processes (with Z + = {0, 1, 2, . . .}) and E ∪ ∂ = R d + for diffusion processes, with d ≥ 2, and where absorption corresponds to the extinction of a single population. This means that ∂ = Z d + \ N d and E = N d (where N = {1, 2, . . .}) for multidimensional birth and death processes and ∂ = R d + \ (0, +∞) d and E = (0, +∞) d for multidimensional diffusions. Non-uniform exponential convergence to quasistationary distributions for such processes can be obtained using [START_REF] Champagnat | General criteria for the study of quasi-stationarity[END_REF], [START_REF] Velleret | Unique Quasi-Stationary Distribution, with a possibly stabilizing extinction[END_REF] or [START_REF] Ferré | More on the long time stability of Feynman-Kac semigroups[END_REF].

Remark 1. The case where absorption corresponds to the extinction of the whole population, i.e. ∂ = {(0, . . . , 0)}, can be handled combining the results of the present paper and those known in the one-dimensional case [START_REF] Champagnat | Uniform convergence to the Qprocess[END_REF][START_REF] Champagnat | Uniform convergence of conditional distributions for absorbed one-dimensional diffusions[END_REF] following the methods of [START_REF] Cattiaux | Competitive or weak cooperative stochastic Lotka-Volterra systems conditioned on non-extinction[END_REF]Thm. 1.1]. This case was also considered in [START_REF] Chazottes | On time scales and quasistationary distributions for multitype birth-and-death processes[END_REF].

A Lotka-Volterra birth and death process in dimension

d ≥ 2 is a Markov process (X t , t ≥ 0) on Z d + with transition rates q n,m from n = (n 1 , . . . , n d ) ∈ Z d + to m = n in Z d + given by q n,m =      n i (λ i + d j=1 γ ij n j ) if m = n + e i , for some i ∈ {1, . . . , d} n i (µ i + d j=1 c ij n j ) if m = n -e i ,
for some i ∈ {1, . . . , d} 0 otherwise, where e i = (0, . . . , 0, 1, 0, . . . , 0) where the 1 is at the i-th coordinate. Note that the set ∂ = Z d + \ N d is absorbing for the process. We make the usual convention that q n,n := -q n := -

m =n q n,m .
From the biological point of view, the constant λ i > 0 is the birth rate per individual of type i ∈ {1, . . . , d}, the constant µ i > 0 is the death rate per individual of type i, c ij ≥ 0 is the rate of death of an individual of type i from competition with an individual of type j, and γ ij ≥ 0 is the rate of birth of an individual of type i from cooperation with (or predation of) an individual of type j. In general, a Lotka-Volterra process could be explosive if some of the γ ij are positive, but the assumptions of the next theorem ensure that it is not the case and that the process is almost surely absorbed in finite time.

Theorem 1.1. Consider a competitive Lotka-Volterra birth and death process (X t , t ≥ 0) in Z d + as above. Assume that the matrix (c ij -γ ij ) 1≤i,j≤d defines a positive operator on R d + in the sense that, for all (x 1 , . . . ,

x d ) ∈ R d + \ {0}, ij x i (c ij -γ ij )x j > 0.
Then the process has a unique quasistationary distribution ν QSD and there exist constants C, γ > 0 such that, for all probability measures µ on E = N d ,

P µ (X t ∈ • | t < τ ∂ ) -ν QSD T V ≤ Ce -γt , ∀t ≥ 0.
An important difficulty here is the fact that the absorption rate (i.e. the rate of jump from a state in E to a state in ∂) is not bounded. Birth and death processes with bounded absorption rates are much easier to study, cf. e.g. [START_REF] Champagnat | Exponential convergence to quasistationary distribution and Q-process[END_REF]. The existence of a quasi-stationary distribution for this kind of multi-dimensional birth and death processes can also be obtained using the theory of R-positive matrices, as exposed in [START_REF] Ferrari | R-positivity, quasi-stationary distributions and ratio limit theorems for a class of probabilistic automata[END_REF], but without the uniform exponential convergence (1.1).

In Section 5, we consider general competitive Feller diffusions, which extend the classical example of Lotka-Volterra Feller diffusion process in dimension d ≥ 2, defined as the solution X t = (X 1 t , . . . , X d t ) to the stochastic differential equation

dX i t = γ i X i t dB i t + X i t   r i - d j=1 c ij X j t   dt, ∀i ∈ {1, . . . , d}, (1.3)
where (B 1 t , t ≥ 0), . . . , (B d t , t ≥ 0) are independent standard Brownian motions. The Brownian terms and the linear drift terms correspond to classical Feller diffusions, and the quadratic drift terms correspond to Lotka-Volterra interactions between coordinates of the process. The variances per individual γ i are positive numbers, and the growth rates per individual r i can be any real number, for all 1 ≤ i ≤ d. The parameters c ij are assumed nonnegative for all 1 ≤ i, j ≤ d, which corresponds to competitive Lotka-Volterra interaction. It is well known that, in this case, there is global strong existence and pathwise uniqueness for the SDE (1.3), and that it is almost surely absorbed in finite time in

∂ = R d + \ (0, +∞) d if c ii > 0 for all i ∈ {1, .
. . , d} (see [START_REF] Cattiaux | Competitive or weak cooperative stochastic Lotka-Volterra systems conditioned on non-extinction[END_REF] and Section 5). Theorem 1.2. Consider a competitive Lotka-Volterra Feller diffusion (X t , t ≥ 0) in R d + as above. Assume that c ii > 0 for all i ∈ {1, . . . , d}. Then the process has a unique quasi-stationary distribution ν QSD and there exist constants C, γ > 0 such that, for all probability measures µ on E = (0, ∞) d ,

P µ (X t ∈ • | t < τ ∂ ) -ν QSD T V ≤ Ce -γt , ∀t ≥ 0.
(1.4)

This results was previously known [START_REF] Cattiaux | Competitive or weak cooperative stochastic Lotka-Volterra systems conditioned on non-extinction[END_REF] when the process (after some transformations) is a Kolmogorov diffusion (i.e. of the form dY t = dW t -∇V (Y t )dt for some Brownian motion W and some C 2 function V ). In dimension 2, this holds if the constants c ij and γ ij satisfy c 12 γ 1 = c 21 γ 2 . Our result is valid in any dimension and has no restriction on the coefficients. One can also expect to extend our result to cooperative cases (e.g. with c 21 < 0 and c 12 < 0 as in [START_REF] Cattiaux | Competitive or weak cooperative stochastic Lotka-Volterra systems conditioned on non-extinction[END_REF]) by using our abstract Lyapunov criterion with functions combining those used to prove Theorems 1.1 and 1.2. Another motivations of our study comes from [START_REF] Bansaye | Approximation of stochastic processes by nonexpansive flows and coming down from infinity[END_REF], where the coming down from infinity of Lotka-Volterra Feller diffusions is studied. It appears that such processes may go extinct far from compact sets for very large initial conditions. Theorem 1.2 proves that this does not prevent the conditioned process to come back to compact sets fast.

Our general non-linear Lyapunov criterion, Theorem 2.4, is stated in Section 2 and proved in Section 3. Sections 4 and 5 are devoted to the study of (extensions of) competitive Lotka-Volterra birth and death processes and competitive Lotka-Volterra Feller diffusions and to the proofs of Theorems 1.1 and 1.2.

Since the publication of the first version of this preprint on Arxiv, the criteria presented here have been applied to other models, including diffusion models of deadlocks in distributed algorithms [START_REF] Champagnat | Probabilistic Nonasymptotic Analysis of Distributed Algorithms[END_REF] and stochastic reaction networks [START_REF] Hansen | Existence of a Unique Quasi-stationary Distribution for Stochastic Reaction Networks[END_REF], with a weakened condition for birth and death processes.

A general Lyapunov criterion for uniform exponential convergence of conditional distributions

Our general framework is inspired from [START_REF] Meyn | Stability of Markovian processes. III. Foster-Lyapunov criteria for continuous-time processes[END_REF].

Definitions and notations

We We assume that E ∩ ∂ = ∅, that ∂ is an absorbing set for the process and we introduce τ ∂ = inf{t ≥ 0, X t ∈ ∂}.

We assume that τ ∂ < ∞ a.s. and that the process is regularly absorbed, in the sense that

τ ∂ := lim n→+∞ T n , where T n := inf{t ≥ 0, X t ∈ O n } (2.1)
and that, for all x ∈ E and t ≥ 0, P x (t < τ ∂ ) > 0.

We also assume that, for any closed set C, the entry time in C defined by τ C = inf{t ≥ 0 : X t ∈ C}, are (F t ) t≥0 -stopping times. 1 In particular, since (E ∪ ∂) \ O n is closed, T n and thus τ ∂ are (F t ) t≥0 -stopping times.

We shall make use of the following weakened notion of generator for X, inspired from [START_REF] Meyn | Stability of Markovian processes. III. Foster-Lyapunov criteria for continuous-time processes[END_REF] and which extends the usual weak infinitesimal generator [START_REF] Dynkin | Markov processes. Vols. I, II[END_REF]. Definition 2.1. We say that a measurable function V : E ∪ ∂ → R belongs to the domain D(L) of the weakened generator L of X if there exists a measurable function W : E → R such that, for all n ∈ N, t ≥ 0 and x ∈ E,

E x t∧Tn 0 |W (X s )| ds < ∞ and E x V (X t∧Tn ) = V (x)+E x t∧Tn 0 W (X s )ds , (2.
2) and we define LV = W on E. We also define LV (x) = 0 for all x ∈ ∂.

Due to the local form of the above Dynkin formula, it is much easier to check that V belongs to D(L) than to the usual domain of the weak infinitesimal generator.

We also define the set of admissible functions to which our Lyapunov criterion applies. We will say that a measurable function on E or E ∪ ∂ is locally bounded if it is bounded on O n for all n ≥ 1. Definition 2.2. We say that a pair (V, ϕ) of functions V and ϕ measurable from E ∪ ∂ to R + is an admissible pair of functions if (i) V and ϕ are bounded, identically 0 on ∂, positive on E, and 1/V and 1/ϕ are locally bounded on E.

(ii) We have the convergences

lim n→+∞ inf x∈E\On V (x) ϕ(x) = +∞ (2.3) and lim n→+∞ V (X Tn ) = 0 a.s. (2.4)
(iii) V and ϕ belong to the domain of the weakened generator L of X, LV is bounded from above and Lϕ is bounded from below.

The main point of this definition of admissible functions is the following result, whose technical proof is postponed to Section 3.

Proposition 2.3. Assume (V, ϕ) is a pair of admissible functions. Then, for all x ∈ E and t ≥ 0, E x [LV (X s )] E x [ϕ(X s )] - E x [V (X s )] E x [ϕ(X s )] E x [Lϕ(X s )] E x [ϕ(X s )] ∈ L 1 ([0, t]) and E x [V (X t )] E x [ϕ(X t )] = V (x) ϕ(x) + t 0 E x [LV (X s )] E x [ϕ(X s )] - E x [V (X s )] E x [ϕ(X s )] E x [Lϕ(X s )] E x [ϕ(X s )]
ds.

(2.5)

A non-linear Lyapunov criterion

In the following assumption, we need a pair of functions, while usual drift conditions of Foster-Lyapunov criteria only use one (see for instance [START_REF] Meyn | Stability of Markovian processes. III. Foster-Lyapunov criteria for continuous-time processes[END_REF]). Roughly speaking, the function V is used to control return time in compact sets from neighborhood of the boundary, while the second one, ϕ, is used to control the absorption rate. One of the main difficulty when checking the following assumption, is that V needs also to be related to the absorption probability, via the inequality (2.

7).

Assumption 1. There exist a pair of admissible functions (V, ϕ) and constants

k 0 ∈ N, C 1 , C 2 , C 3 , ε > 0 such that -Lϕ ≤ C 1 1 O k 0 and LV + C 2 V 1+ε ϕ ε ≤ C 3 ϕ. (2.6)
and there exist constants r 0 , p 0 > 0 such that

P x (r 0 < τ ∂ ) ≤ p 0 V (x), ∀x ∈ E \ O k 0 . (2.7)
The main role of the first part in the above assumption is to bound the derivative computed in Proposition 2.3, which will allow us to show that the quantity Ex[V (Xt)]

Ex[ϕ(Xt)] is uniformly bounded in x ∈ E for t large enough. The second part of this assumption is needed to check that the boundedness of

Ex[V (Xt)]
Ex[ϕ(Xt)] implies that, conditionally on t < τ ∂ , X t ∈ O n with high probability for n large. This implies that the problem can be localized in this set O n , so that, in order to check Conditions (A1-A2), it is enough to assume the following local versions of (A1-A2), which are much easier to check.

Assumption 2. There exists a probability measure ν on E such that, for all n ≥ 1, there exist a n > 0 and θ n > 0 satisfying

P x (X θn ∈ •) ≥ a n ν, for all x ∈ O n .
In addition, for all n ≥ 0, there exists a constant D n such that, for all t ≥ 0,

sup x∈On P x (t < τ ∂ ) ≤ D n inf x∈On P x (t < τ ∂ ).
(

The Lyapunov criterion of Assumption 1 will be useful to check that the conditioned process comes back quickly in bounded subsets of E from any neighborhood of the boundary. However, it does not imply this property for initial distribution in a neighborhood of infinity. This is the purpose of the next assumption. Since it only concerns the unconditioned process, it may be proved using usual drift conditions or probabilistic arguments, as we illustrate in the two examples of Sections 4 and 5.

Assumption 3. For all λ > 0, there exists n ≥ 1 such that

sup x∈E E x (e λ(Sn∧τ ∂ ) ) < ∞.
(2.9)

where

S n = inf{t ≥ 0 : X t ∈ O n }.
It is well known [START_REF] Meyn | Stability of Markovian processes. III. Foster-Lyapunov criteria for continuous-time processes[END_REF] that this assumption is implied by the existence, for all λ > 0, of a bounded Lyapunov function

ψ λ : E ∪ {∂} → [1, +∞) such that Lψ λ (x) ≤ -λψ λ (x) + C1 On for some n ≥ 1. Indeed in this case, e λt ψ λ (X t ) - t 0 e λs [λψ λ (X s ) + Lψ λ (X s )] ds is a local martingale and e λ(t∧Sn∧τ ∂ ) ψ λ (X t∧Sn∧τ ∂ ) is a super-martingale in L ∞ . Fatou's lemma then implies that E x (e λ(Sn∧τ ∂ ) ) ≤ ψ λ (x).
Depending on the situations it might be simpler to check Assumption 3 directly using for instance coupling arguments as we do for example for Theorem 5.1 below, or to find a Lyapunov function.

We can now state our main general result. Its proof is given in Section 3.

Theorem 2.4. Assume that the process (X t , t ≥ 0) is regularly absorbed and that there exists a pair of admissible functions (V, ϕ) satisfying Assumption 1. Assume also that Assumptions 2 and 3 are satisfied. Then the process X admits a unique quasi-stationary distribution ν QSD and there exist constants C, γ > 0 such that for all probability measure µ on E,

P µ (X t ∈ • | t < τ ∂ ) -ν QSD T V ≤ Ce -γt , ∀t ≥ 0. (2.10)
3 Proof of the results of Section 2

We first give the proof of Proposition 2.3 in Subsection 3.1 and the proof of Theorem 2.4 in Subsection 3.2. The proofs of two technical lemmas are given in Subsections 3.3 and 3.4.

Proof of Proposition 2.3

In what follows, we use the classical definition of the integral of a signed function f with respect to a positive measure µ by µ(f

+ ) -µ(f -) ∈ [-∞, +∞]
(where f + and f -denote respectively the positive and negative parts of f ), which is well defined as soon as at least one of the two terms is finite. Classical results (as Lebesgue's theorem, Fatou's lemma and Fubini's theorem) still hold in this case. Using the Definition 2.1 of the weakened infinitesimal generator, we have for all n ≥ 1

E x V (X t∧Tn ) = V (x)+E x t∧Tn 0 LV (X s )ds = V (x)+E x t 0 LV (X s )1 s<Tn ds. (3.1) Note that E x V (X t∧Tn ) = E x (1 t<Tn V (X t )) + E x (1 Tn≤t V (X Tn )) .
Using (2.1), the Assumption (2.4) and that V (X Tn ) is uniformly bounded, Lebesgue's theorem implies that

lim n→+∞ E x V (X t∧Tn ) = E x (1 t<τ ∂ V (X t )) = E x (V (X t )). (3.2)
Now Fatou's lemma applied to the right-hand side of (3.1) (using that LV is bounded from above) gives

E x V (X t ) ≤ V (x) + E x t∧τ ∂ 0 LV (X s ) ds = V (x) + t 0 E x [LV (X s )] ds,
where we have used Fubini's theorem for the last inequality. Since V ≥ 0 and LV is bounded from above, we deduce that

E x LV (X s ) ∈ L 1 ([0, t]) and that V (X t ) ∈ L 1 (Ω)
. Therefore, we can actually apply Lebesgue's Theorem to the right-hand side of (3.1) and hence

E x V (X t ) = V (x) + t 0 E x [LV (X s )] ds.
The same argument applies to ϕ (note that (2.3) and (2.4) imply that lim ϕ(X Tn ) = 0 a.s.):

E x ϕ(X t ) = ϕ(x) + t 0 E x [Lϕ(X s )] ds. (3.3)
Therefore E x V (X t ) and E x ϕ(X t ) are continuous with respect to t and (cf. e.g. [2, Lem. VIII.2]), for all T > 0, t → (E x V (X t ), E x ϕ(X t )) belongs to the Sobolev space W 1,1 ([0, T ], R 2 ) (the set of functions from [0, T ] to R 2 in L 1 admitting a derivative in the sense of distributions in L 1 ).

In particular, since P x (t < τ ∂ ) > 0 and hence E x ϕ(X t ) > 0 for all t ∈ [0, T ], we deduce from the continuity of t → E x ϕ(X t ) that inf t∈[0,T ] E x ϕ(X t ) > 0. Therefore, we deduce from standard properties of W 1,1 functions [2, Cor. VIII.9 and Cor. VIII.10] that t → E x V (X t )/E x ϕ(X t ) also belongs to W 1,1 ([0, T ], R) and admits as derivative

t → E x LV (X t ) E x ϕ(X t ) - E x V (X t ) E x Lϕ(X t ) [E x ϕ(X t )] 2 ∈ L 1 ([0, T ]).
Hence we have proved (2.5).

Proof of Theorem 2.4

The proof is based on two lemmas. The first one combines Proposition 2.3 and Assumption (2.6) to give uniform (in x) controls on ExV (Xt) Exϕ(Xt) for t large enough. Its proof is given in Subsection 3.3. Lemma 3.1. There exists two positive constants A and B such that, for all x ∈ E and all s ≥ 0,

E x (LV (X s )) E x (ϕ(X s )) - E x (V (X s )) E x (ϕ(X s )) E x (Lϕ(X s )) E x (ϕ(X s )) ≤ A -B E x (V (X s )) E x (ϕ(X s )) 1+ε . (3.4)
In particular, there exists t 0 > 0 such that, for all x ∈ E and all t ≥ t 0 ,

E x V (X t ) E x ϕ(X t ) ≤ 2A B 1/(1+ε) + 2At 0 . (3.5)
The second lemma makes use of Assumption (2.7) to deduce from Lemma 3.1 the following inequality. Its proof is given in Subsection 3.4. Lemma 3.2. Enlarging k 0 in Assumption 1 if necessary, there exists D > 0 such that, for all t ≥ t 0 and all x ∈ E,

E x [V (X t )] ≤ D E x [V (X t )1 Xt∈O k 0 ]. (3.6)
We prove Theorem 2.4 by checking that the two conditions (A1) and (A2) in the introduction are satisfied (cf. [START_REF] Champagnat | Uniform convergence to the Qprocess[END_REF]).

Step 1: Proof of (A1). We first remark that there exists m 0 ≥ 0 such that ν(O m 0 ) > 0 (where ν and θ n below are from Assumption 2) and hence such that, for all n ≥ 1, all x ∈ O n and all k ≥ 1,

P x (X θn+kθm 0 ∈ •) ≥ a n ν(O m 0 ) inf y∈Om 0 P y (X kθm 0 ∈ •) ≥ a n a k m 0 ν(O m 0 ) k ν(•), (3.7)
where we used Markov's property and an induction procedure over k.

In particular, we can assume without loss of generality that θ k 0 ≥ r 0 (where r 0 is from Assumption 1 and k 0 satisfies Assumption 1 and Lemma 3.2). As a consequence, Assumption (2.7), Inequality (3.6) and Markov's property entail that, for all t ≥ t 0 (where t 0 is from Lemma 3.1),

P x (t + θ k 0 < τ ∂ ) ≤ P x (t + r 0 < τ ∂ ) ≤ D p 0 E x [V (X t )1 Xt∈O k 0 ] ≤ D p 0 sup O k 0 V P x (X t ∈ O k 0 ).
On the other hand,

P x (X t+θ k 0 ∈ •) ≥ P x (X t ∈ O k 0 ) inf y∈O k 0 P y (X θ k 0 ∈ •) ≥ P x (X t ∈ O k 0 ) a k 0 ν(•).
Setting t 0 = t 0 + θ k 0 , the two above equations imply that, for all x ∈ E,

P x (X t 0 ∈ • | t 0 < τ ∂ ) ≥ a k 0 Dp 0 sup O k 0 V ν(•),
and hence that Assumption (A1) holds true.

Step 2: Proof of (A2). Using (3.7), for all n ≥ m 0 , all x ∈ O n and all k ≥ 1, we obtain that, for all t ∈ [θ n + kθ m 0 , θ n + (k + 1)θ m 0 ),

P x (t + s < τ ∂ ) ≥ P x (X θn+(k+1)θm 0 ∈ O m 0 ) inf y∈Om 0 P y (s < τ ∂ ) ≥ a n a k+1 m 0 ν(O m 0 ) k+2 inf y∈On P y (s < τ ∂ ).
Setting λ := -ln(a m 0 ν(O m 0 ))/θ m 0 and using inequality (2.8) of Assumption 2, we deduce that, for all n ≥ 1 and all s, t ≥ 0,

inf x∈On P x (t + s < τ ∂ ) ≥ a n a m 0 ν(O m 0 ) 2 D n exp(-λt) sup x∈On P x (s < τ ∂ ). (3.8)
Now, we apply Assumption 3 for λ as defined above: there exists n ≥ m 0 such that

M := sup x∈E E x [exp(λ(S n-1 ∧ τ ∂ ))] < ∞. (3.9) Note that, since X t is càdlàg, X S n-1 ∈ O n-1 ⊂ O n on the event {S n-1 < ∞}.
Hence, using (3.9) and the strong Markov property at time S n-1 (which is a stopping time since it is the entry time in a closed set), for all x ∈ E,

P x (t < τ ∂ ) = P x (t < S n-1 ∧ τ ∂ ) + P x (S n-1 ≤ t < τ ∂ ) ≤ M e -λt + t 0 sup y∈On P y (t -s < τ ∂ )P x (S n-1 ∈ ds). Note that, if S n-1 < ∞, then S n-1 < τ ∂ and S n-1 = S n ∧ τ ∂ ). Thus, for all s ≤ t, P y (S n-1 ∈ ds) = P y (S n-1 ∧ τ ∂ ∈ ds, S n-1 < ∞) ≤ P y (S n-1 ∧ τ ∂ ∈ ds).
Hence, using (3.8) twice, we have for all x ∈ E

P x (t < τ ∂ ) ≤ M e -λt + t 0 sup y∈On P y (t -s < τ ∂ )P x (S n-1 ∧ τ ∂ ∈ ds) ≤ D n a n a m 0 ν(O m 0 ) 2 M inf y∈On P y (t < τ ∂ ) + inf y∈On P y (t < τ ∂ ) t 0 e λs P x (S n-1 ∧ τ ∂ ∈ ds) ≤ 2M D n a n a m 0 ν(O m 0 ) 2 inf y∈On P y (t < τ ∂ ) ≤ 2M D n a n a m 0 ν(O m 0 ) 2 ν(O n ) P ν (t < τ ∂ ). Since O n ⊃ O m 0 , we have ν(O n ) ≥ ν(O m 0 ) > 0,
so the last inequality implies (A2).

Proof of Lemma 3.1

Step 1: Proof of (3.4). Fix x ∈ E and s ≥ 0. On the one hand, it follows from (2.6) that

-E x (Lϕ(X s )) ≤ C 1 inf O k 0 ϕ E x (ϕ(X s )).
and hence

- E x (Lϕ(X s )) E x (ϕ(X s )) E x (V (X s )) ≤ C 1 inf O k 0 ϕ E x (V (X s )) (3.10)
On the other hand, we deduce from (2.6) that

E x (LV (X s )) ≤ C 3 E x (ϕ(X s )) -C 2 E x V (X s ) 1+ε ϕ(X s ) ε ≤ C 3 E x (ϕ(X s )) - C 2 2 E x V (X s ) 1+ε ϕ(X s ) ε - C 2 2 E x (V (X s )) 1+ε E x (ϕ(X s )) ε . (3.11)
where we used Hölder's inequality to deduce that

E x (V (X s )) 1+ε ≤ E x V (X s ) 1+ε ϕ(X s ) ε E x (ϕ(X s )) ε .
Now, because of Assumption (2.3), there exists m large enough such that, for all

y ∈ E \ O m , C 2 V ε (y) 2ϕ ε (y) ≥ C 1 inf O k 0 ϕ .
Therefore, for such a value of m,

C 2 2 E x V (X s ) 1+ε ϕ(X s ) ε = C 2 2 E x V (X s ) 1+ε ϕ(X s ) ε 1 Xs∈Om + C 2 2 E x V (X s ) 1+ε ϕ(X s ) ε 1 Xs∈E\Om ≥ C 1 inf O k 0 ϕ E x V (X s )1 Xs∈E\Om ≥ C 1 inf O k 0 ϕ E x V (X s ) - C 1 sup Om V inf O k 0 ϕ inf Om ϕ E x ϕ(X s ).
Finally, we obtain from the last inequality, (3.10) and (3.11) that there exists two positive constants A, B > 0 such that

E x (LV (X s )) E x (ϕ(X s )) - E x (V (X s )) E x (ϕ(X s )) E x (Lϕ(X s )) E x (ϕ(X s )) ≤ A -B E x (V (X s )) E x (ϕ(X s )) 1+ε
Step 2: Proof of (3.5).

We define a = (2A/B) 1/(1+ε) and t 0 = 4 εBa ε . Propositions 2.3 and (3.4) imply that, for all t ≥ 0 and all x ∈ E,

E x V (X t ) E x ϕ(X t ) ≤ V (x) ϕ(x) + At -B t 0 E x V (X s ) E x ϕ(X s ) 1+ε ds. (3.12)
Since ε > 0, this implies that, for all x ∈ E, there exists u x ∈ [0, t 0 ] such that ExV (Xu x ) Exϕ(Xu x ) < a for any x ∈ E. We prove this by contradiction: assume on the contrary that for all s ∈ [0, t 0 ], ExV (Xs) Exϕ(Xs) ≥ a. Then, for all t ∈ [0, t 0 ],

E x V (X t ) E x ϕ(X t ) ≤ V (x) ϕ(x) - B 2 t 0 E x V (X s ) E x ϕ(X s ) 1+ε ds.
Integrating this differential inequality up to time t 0 entails

E x V (X t 0 ) E x ϕ(X t 0 ) ≤ ϕ(x) V (x) ε + εBt 0 2 -1/ε ≤ 2 εBt 0 1/ε = a 2 ,
which gives a contradiction. Hence, using Proposition 2.3 and (3.4) again, we deduce that, for all t ∈ [t 0 , 2t 0 ] and all x ∈ E,

E x (V (X t )) E x (ϕ(X t )) ≤ E x V (X ux ) E x ϕ(X ux ) + A(t -u x ) -B t ux E x V (X s ) E x ϕ(X s ) 1+ε ds ≤ a + A(t -u x ) ≤ a + A 2 t 0 .
Using the same argument repetitively between time kt 0 (instead of 0) and (k + 2)t 0 (instead of 2t 0 ) gives the result for all time t ≥ t 0 .

3.4 Proof of Lemma 3.2

Set a = 2A B 1/(1+ε) + 3At 0 . Equation (2.3) implies that, enlarging k 0 in Assumption 1 if necessary, inf y∈E\O k 0 V (y) ϕ(y) ≥ 2a . Lemma 3.1 implies that, for all t ≥ t 0 , a > E x V (X t ) E x ϕ(X t ) ≥ E x [V (X t )1 Xt∈E\O k 0 ] + E x [V (X t )1 Xt∈O k 0 ] sup y∈E\O k 0 ϕ(y) V (y) E x [V (X t )1 Xt∈E\O k 0 ] + sup y∈E ϕ(y) V (y) E x [V (X t )1 Xt∈O k 0 ] ≥ E x [V (X t )1 Xt∈E\O k 0 ] + E x [V (X t )1 Xt∈O k 0 ] 1 2a E x [V (X t )1 Xt∈E\O k 0 ] + sup y∈E ϕ(y) V (y) E x [V (X t )1 Xt∈O k 0 ] . Therefore, a sup y∈E ϕ(y) V (y) -1 E x [V (X t )1 Xt∈O k 0 ] ≥ 1 2 E x [V (X t )1 Xt∈E\O k 0 ]. Since a > E x V (X t )/E x ϕ(X t ) ≥ 1/ sup y∈E (ϕ(y)/V (y))
, we deduce that there exists a constant D > 0 such that

E x [V (X t )] ≤ D E x [V (X t )1 Xt∈O k 0 ].
4 Application to multidimensional birth and death processes absorbed when one of the coordinates hits 0

We consider general multitype birth and death processes in continuous time, taking values in Z d + for some d ≥ 2. Let (X t , t ≥ 0) be a Markov process on Z d + with transition rates from n = (n 1 , . . . , n d ) to n + e j with rate n j b j (n), n -e j with rate n j d j (n) for all 1 ≤ j ≤ d, with e j = (0, . . . , 0, 1, 0, . . . , 0), where the nonzero coordinate is the j-th one, b(n

) = (b 1 (n), . . . , b d (n)) and d(n) = (d 1 (n), . . . , d d (n))
are functions from Z d + to (0, +∞) d . This model represents a density-dependent population dynamics with d types of individuals (say d species), where b i (n) (resp. d i (n)) represents the reproduction rate (resp. death rate) per individuals of species i when the population is in state n.

Note that the forms of the birth and death rates imply that, once a coordinate X j t of the process hits 0, it remains equal to 0. This corresponds to the extinction of the population of type j. Hence, the set ∂ := Z d + \ N d is absorbing for the process X.

We define for all k ≥ 1

d(k) = sup n∈N d , |n|=k |n| d i=1 1 n i =1 d i (n),
and

d(k) = inf n∈N d , |n|=k d i=1 n i [1 n i =1 d i (n) -b i (n)] ,
where |n| := n 1 + . . . + n d . We shall assume Assumption 4. There exists η > 0 small enough such that, for all k ∈ N large enough,

d(k) ≥ η d(k), (4.1
)

and d(k) k 1+η ----→ k→+∞ +∞. (4.2)
Note that, since the set O n is finite for all n, it is standard to check that any function f : Z d + → R is in the domain of the weakened infinitesimal generator of X and, for all n ∈ N d ,

Lf (n) = d j=1 [f (n + e j ) -f (n)]n j b j (n) + d j=1 [f (n -e j ) -f (n)]n j d j (n).
Under Assumption (4.2), setting W (n) = |n|, we have

LW (n) W (n) 1+η = - d j=1 n j (d j (n) -b j (n)) W (n) 1+η ≤ - d(|n|) |n| 1+η → -∞.
This classically entails that sup

n∈N d E n (|X 1 |) < +∞. ( 4.3)
(The argument is very similar to the one used for Lemma 3.1.) In particular, the process is non-explosive and τ ∂ is finite almost surely. Therefore, the process X is regularly absorbed, as defined in Section 2.1. We can now state the main result of the section.

Theorem 4.1. Under Assumption 4, the multi-dimensional competitive birth and death process (X t , t ≥ 0) absorbed when one of its coordinates hits 0 admits a unique quasi-stationary distribution ν QSD and there exist constants C, γ > 0 such that, for all probability measure µ on N d ,

P µ (X t ∈ • | t < τ ∂ ) -ν QSD T V ≤ Ce -γt , ∀t ≥ 0.
As will appear in the proof below, to check our conditions, it is sufficient to take functions V and ϕ of the form f (|n|)1 N d (n) for some f : N → R + . More precisely, the first part of Condition (2.6) can be checked for ϕ(n) = f (|n|)1 N d (n) with decreasing f and the second part for V (n) = g(|n|)1 N d (n) with increasing g, to take advantage of the drift of the birth and death process towards 0 for large |n|. However, let us emphasize that, although the

choice ϕ(n) = 1 N d (i.e. f ≡ 1) is natural, it cannot satisfy the first part of Condition (2.6), since in this case -Lϕ(n) = d i=1 1 n i =1 d i (n) (the ab- sorption rate) is unbounded. The direct study of E(V (X t ) | t < τ ∂ ) = E[V (X t )]/E[1 n∈N d (X t )]
is possible, but only allows to recover particular cases of Theorem 4.1 (cf. [START_REF] Champagnat | Population processes with unbounded extinction rate conditioned to non-extinction[END_REF]Section 4]). Our criterion is more flexible and better adapted to multidimensional birth and death models of interacting populations.

It is easy to check that Assumption 4 is satisfied in the general Lotka-Volterra birth and death process of the introduction. Indeed, we clearly have d(k) ≤ Ck 2 and

d(k) ≥ inf n∈N d , |n|=k d i=1 (d i (n) -b i (n)) - sup n∈N d , |n|=k n i=1 d i (n)1 n i =1 ≥ -Ck + inf n∈N d , |n|=k d i,j=1 n i (c ij -γ ij )n j for C = max i µ i + max i λ i + max i,j c ij .
Under the assumptions of Theorem 1.1, there exists C > 0 such that, for all n ∈ N d ,

d i,j=1 n i (c ij -γ ij )n j ≥ C |n| 2 .
This entails Assumption 4. and that Assumption 3 is also satisfied. Hence we only have to find a pair of admissible functions (V, ϕ) satisfying Assumption 1. This pair of functions is given for all n ∈ Z d + by

V (n) = |n| k=1 1 k α if n ∈ N d , 0 if n ∈ ∂ and ϕ(n) = +∞ k=|n|+1 1 k β if n ∈ N d , 0 if n ∈ ∂,
for appropriate choices of α, β > 1. Note that the two functions are bounded, nonnegative and positive on N d . Note also that, since

O n = {n ∈ N d , |n| ≤ n + d} (taking o = (1, . . . , 1
)), so Conditions (i-ii) of Definition 2.2 are clearly satisfied (in this discrete state space case, the condition (2.4) is trivial since, almost surely, T n = τ ∂ for all n large enough). Note also that, since inf n∈N d V (n) > 0, Condition (2.7) is also obviously satisfied.

Hence, we only have to check (2.6) since this of course implies that V and ϕ satisfy Point (iii) of Definition 2.2. So we compute

Lϕ(n) = - d i=1 n i b i (n) (1 + |n|) β + d i=1 n i 1 n i =1 d i (n) |n| β - d i=1 1 n i =1 d i (n) +∞ k=|n|+1 1 k β ≥ 1 |n| β d(|n|) - d(|n|) β -1 ,
where we used the fact that

+∞ k=x+1 1 k β ≤ +∞ x dy y β = 1 (β -1)x β-1 .
Hence it follows from Assumption (4.1) that there exists β > 1 large enough such that Lϕ(n) ≥ 0 for all |n| large enough. This entails the first inequality in (2.6).

We fix such a value of β. Using that sup

n∈N d V (n) = +∞ k=1 1 k α ≤ 1 + ∞ 1 dx x α = α α -1 and ϕ(n) ≥ ∞ |n|+1 dx x β = (1 + |n|) 1-β β -1 ≥ |n| 1-β 2(β -1)
for |n| large enough, we compute for such n 1) ,

LV (n) + V 1+ε (n) ϕ ε (n) ≤ d i=1 n i b i (n) (|n| + 1) α - d i=1 n i d i (n)1 n i =1 |n| α + C|n| ε(β-1) ≤ - d(|n|) |n| α + C|n| ε(β-
where C = [α/(α -1)] 1+ε [2(β -1)] ε . Choosing α = 1 + η/2 and ε = η/[2(β -1)], Assumption (4.2) implies that LV (n) + V 1+ε (n) ϕ ε (n) ≤ 0 for n ∈ O m
with m large enough. Since inf n∈Om ϕ(n) > 0, we have the second inequality in (2.6).

5 Application to multidimensional Feller diffusions absorbed when one of the coordinates hits 0

We consider a general multitype Feller diffusion (X t , t ≥ 0) in R d + , solution to the stochastic differential equation

dX i t = γ i X i t dB i t + X i t r i (X t )dt, 1 ≤ i ≤ d, (5.1)
where (B i t , t ≥ 0) are independent standard Brownian motions, γ i are positive constants and r i are measurable maps from R d + to R. From the biological point of view, r i (x) represents the growth rate per individual of species i in a population of size vector x ∈ R d + . We shall make the following assumption. Assumption 5. Assume that, for all i ∈ {1, . . . , d}, r i is locally Hölder on R d + and that there exist a > 0 and 0 < η < 1 such that

r i (x) ≤ a η -x η i , (5.2)
and there exist constants B a > a, C a > 0 and D a > 0 such that

d i=1 1 x i ≥Ba r i (x) ≤ C a d i=1 1 x i ≤a r i (x) + D a , ∀x ∈ R d + . (5.3)
This assumption implies in particular the non-explosion, strong existence and pathwise uniqueness for (5.1). Indeed, since r i is locally Hölder, standard arguments entail the strong existence and pathwise uniqueness for (5.1) up to the explosion time. Now, Assumption (5.2) and standard comparison results for one-dimensional diffusion processes (see e.g. Theorem 1.1 in [24, Chapter VI]) entail that each coordinate of the process can be upper bounded by the solution of the one-dimensional Feller diffusion

d Xi t = γ i Xi t dB i t + Xi t a η -Xi t η dt, 1 ≤ i ≤ d, (5.4)
with initial value Xi 0 = X i 0 . Since Xi is a diffusion on R + for which +∞ is an entrance boundary and 0 an exit boundary, we deduce that each coordinate is non-explosive and hence that the unique solution to (5.1) is non-explosive. Moreover, the subset ∂ = R d + \ (0, +∞) d is an absorbing boundary for the diffusion process (5.1), so the process X t is regularly absorbed in the sense of Section 2.2.

Strong existence and pathwise uniqueness imply well-posedness of the martingale problem, hence the strong Markov property hold on the canonical space with respect to the natural filtration (see e.g. [START_REF] Rogers | Diffusions, Markov processes, and martingales[END_REF]). Since the paths of X are continuous, the hitting times of closed subsets of R d + are stopping times for this filtration. In addition, it follows from Itô's formula and the local boundedness of the coefficients of the SDE that any measurable function f : R d + → R twice continuously differentiable on (0, +∞) belongs to the domain of the weakened generator of X and

Lf (x) = d i=1 γ i x i 2 ∂ 2 f ∂x 2 i (x) + d i=1 x i r i (x) ∂f ∂x i (x), ∀x ∈ (0, +∞) d .
We can now state the main result of the section.

Theorem 5.1. Under Assumption 5, the multi-dimensional Feller diffusion process (X t , t ≥ 0) absorbed when one of its coordinates hits 0 admits a unique quasi-stationary distribution ν QSD and there exist constants C, γ > 0 such that, for all probability measure µ on N d ,

P µ (X t ∈ • | t < τ ∂ ) -ν QSD T V ≤ Ce -γt , ∀t ≥ 0.
It is straightforward to check that Assumption 5 is satisfied in the competitive Lotka-Volterra model (1.3), where r i (x) = r i -d i=1 c ij x j with c ij ≥ 0 and c ii > 0 for all 1 ≤ i, j ≤ d. In particular, (5.3) holds because

d i=1 1 x i ≥Ba r i (x) ≤ dr - d i=1 1 x i ≥Ba c ii x i ≤ dr + c dB a - d i=1 x i ≤ dr + cdB a - c dc d i=1 1 x i ≤a d j=1 c ij x j ≤ dr + cdB a + c dc d i=1 1 x i ≤a r i (x),
where r = max i r i , c = max i,j c ij and c = min i c ii . Hence Theorem 1.2 is an immediate corollary of Theorem 5.1. Assumption 5 allows for other biologically relevant models. For instance, one can consider ecosystems where the competition among individuals only acts when the population size reaches a level K > 0, which leads for instance to the SDE

dX i t = γ i X i t dB i t + X i t   r - d j=1 c ij (X j t -K) +   dt, X i 0 > 0,
where c ij are non-negative constants and c ii > 0 for all i, j ∈ {1, . . . , d}.

Note also that a similar approach (i.e. using Theorem 2.4 with Lyapunov functions of the form d i=1 h(x i )) can also be used to handle diffusion processes evolving in bounded boxes.

Before giving the proof of Theorem 5.1, let us give some intuition about the choice of functions V and ϕ. The behavior of the process when one of the coordinates is close to 0 is similar to the behavior of a one-dimensional diffusion absorbed at 0 started close to 0. This suggests to look for Lyapunov functions of the form V (x) = d i=1 f (x i ) and ϕ(x) = d i=1 g(x i ) where the functions f and g satisfy our criterion for one-dimensional diffusions like (5.4), say dY t = 2Y t dB t + Y t (r -Y η t )dt, with generator Af (x) = xf (x) + x(r -x η )f (x). In the one dimensional case, Conditions (2.6) are restrictive only close to 0 and close to +∞. When x → 0, assuming f (x) = x α and g(x) = x β when x is close to 0, we obtain

Af (x) ∼ α(α -1)x α-1 and Ag(x) ∼ β(β -1)x β-1 .
In particular, to satisfy the first part of (2.6) close to 0, we need β > 1, and to satisfy the second part of (2.6), we need that α(α -1)x α-1 + x α-ε(β-α) ≤ x α in the neighborhood of 0. This holds true if 0 < α < 1 and ε(β -α) < 1. Similarly, assuming f (x) = a -x -γ and g(x) = x -δ close to +∞, with a, γ, δ > 0, we obtain Af (x) ∼ -γx γ+η and Ag(x) ∼ δx η-δ .

For such functions f and g close to +∞, the first part of (2.6) is always satisfied and the second part of (2.6) requires

-γx η-γ + a 1+ε x δε ≤ x -δ , when x → +∞. This holds true if η -γ > δε.
This gives the intuition to check our criterion in dimension 12 . The multi-dimensional case of Theorem 5.1 requires a more careful study, since we need to consider cases where some of the coordinates of the process are close to 0 or +∞, and the others belong to some compact set.

Proof of Theorem 5.1. Up to a linear scaling of the coordinates, we can assume without loss of generality that γ i = 2 for all 1 ≤ i ≤ d, so we will only consider this case from now on. Note that Assumption 5 is not modified by the rescaling (up to appropriate changes of the constants a, B a , C a and D a ).

We divide the proof into five steps, respectively devoted to the construction of a function ϕ satisfying the first inequality in (2.6), of a function V satisfying the second inequality in (2.6), to the proof of (2.7), to the proof of a local Harnack inequality (needed to check Assumption 2), and the proofs of Assumption 2 and of Assumption 3.

Step 1: construction of a function ϕ satisfying the first inequality in (2.6).

Recall the definition of the constants a > 0 and B a > a from Assumption 5. We use the following lemma, whose proof is left to the reader (see Figure 1 for a typical graph of h β ). Lemma 5.2. There exists M > 0 such that, for all β ≥ M , there exists a function h β : R + → R + twice continuously differentiable on (0, +∞) such that

h β (x) = 4x 2 /a 2 if x ∈ [0, a/2], B β a (2x) -β if x ≥ B a , h β (x) ≥ 1 for all x ∈ [a/2, a],
ϕ(x) = d i=1 h β (x i ), ∀x ∈ R d + .
We have

Lϕ(x) ϕ(x) = d i=1 x i h β (x i )r i (x) + x i h β (x) h β (x i ) .
Now, it follows from the properties of h β and Assumptions 5 that, for all x ∈ R + and all 1 ≤ i ≤ d, where we used in the last inequality the fact that r i (x) -a η ≤ 0 for all x. Using once again this property, we deduce that, for some constant B independent of β ≥ M ,

x i h β (x i )r i (x) + x i h β (x) h β (x i ) ≥            0 if x i ≥ a, -βr i (x) if x i ≥ B a , 2r i (x) + 2 x i if x i ≤ a/2, aM (r i (x) -a η ) -a 1+η M -aM if a/2 ≤ x i ≤ a,
x i h β (x i )r i (x) + x i h β (x) h β (x i ) ≥      0 if x i ≥ a, -βr i (x) if x i ≥ B a , (2 ∨ aM )r i (x) + 2 x i -B if x i ≤ a.
(5.5)

Hence, for all x ∈ R d + ,

Lϕ(x) ϕ(x) ≥ -β d i=1 1 x i ≥Ba r i (x) + d i=1 1 x i ≤a (2 ∨ aM )r i (x) + 2 x i -dB.
This and Assumption (5.3) imply that

Lϕ(x) ϕ(x) ≥ - d i=1 1 x i ≥Ba r i (x) + 2 d i=1 1 x i ≤a 1 x i -dB -(2 ∨ aM )D a ≥ d i=1 x η i + 2 x i -B ,
for some constant B , where we used Assumption (5.2) in the last inequality. Hence, there exist n ≥ 1 and a constant C > 0 such that

Lϕ(x) ≥ -C1 x∈On , since O n = {x ∈ [ 1 n+1 , +∞) d , x i ≤ n + 1} (we equip R d + with the L 1 distance)
. This ends the proof that ϕ satisfies the first inequality in (2.6).

Step 2: construction of a function V satisfying (2.6) and verification that (V, ϕ) is a pair of admissible functions.

For V , we define

V (x) = d i=1 g(x i ), ∀x ∈ R d + ,
where the function g : R + → R + is twice continuously differentiable on (0, +∞), increasing concave and such that

g(x) = x γ if x ≤ 1 δ -x -η/2 if x ≥ 2,
for some constants γ < 1 and δ > 0 and where η is defined in Assumption (5.2). Since g (1) = γ and g (2) = η2 -2-η/2 , it is possible to find δ > 0 such that such a function g exists as soon as η2 -2-η/2 < γ. Hence, we shall assume that γ belongs to the non-empty interval (η2 -2-η/2 , 1). We have

LV (x) V (x) = d i=1 x i g (x i )r i (x) + x i g (x i ) g(x i )
and

x i g (x i )r i (x) + x i g (x i ) g(x i ) ≤                γr i (x) - γ(1 -γ) x i if x i ≤ 1, 2a η sup 1≤x≤2 g (x) if 1 ≤ x i ≤ 2, ηr i (x)x -η/2 i 2(δ -x -η/2 i ) if x i ≥ 2.
We deduce from Assumptions (5.2) that there exist constants B , B > 0 such that

x i g (x i )r i (x) + x i g (x) g(x i ) ≤ B -      γ(1-γ) x i if x i ≤ 1, 0 if 1 ≤ x i ≤ 2, B x η/2 i if x i ≥ 2.
(5.6)

Thus, since h β (x i ) ≥ D β x 2 i ∧ x -β i for some constant D β > 0 and since g(x i ) ≤ δ, LV (x) V (x) + V (x) ε ϕ(x) ε ≤ B d -γ(1 -γ) d i=1 1 x i ≤1 x i -B d i=1 1 x i ≥2 x η/2 i + δ D β dε d i=1 x εβ i ∨ x -2ε i ≤ B d + γ(1 -γ) + B 2 η/2 -γ(1 -γ) inf i x i -1 -B sup i x i η/2 + δ D β dε sup i x i βdε + inf i x i -2dε
.

Therefore, choosing ε > 0 such that d(1 + α)ε < 1 and βdε < η/2, LV (x) + V (x) 1+ε /ϕ(x) ε ≤ 0 for all x ∈ R d + such that inf i x i is small enough or sup i x i is big enough. Since LV is bounded from above by (5.6) and since V and ϕ are positive continuous on any compact subset of (0, +∞) d , we have proved Condition (2.6).

We can now check that (V, ϕ) is a pair of admissible functions. First, V and ϕ are both bounded, positive on (0, +∞) and vanishing on ∂. They both belong to the domain of the weakened infinitesimal generator of X. Since the function g/h β is positive continuous on (0, +∞) and

g(x) h β (x) = x γ-2 if x ≤ 1 ∧ a/2, (δ -x -η/2 )(2x) β /B β a if x ≥ B a ∨ 2,
we deduce that (2.3) holds true. Condition (2.4) is also clear since X Tn → X τ ∂ almost surely. Finally, since LV is bounded from above and Lϕ is bounded from below, we have proved that (V, ϕ) is a pair of admissible functions.

Step 3: proof of (2.7).

Using the upper bound X i t ≤ Xi t for all t ≥ 0 and 1 ≤ i ≤ d, where Xi is solution to the SDE (5.4), and noting that the processes ( Xi ) 1≤i≤d are independent, we have for all x ∈ R d + and all t 2 > 0,

P x (t 2 < τ ∂ ) ≤ d i=1 P x i ( Xi t 2 > 0).
Now, there exist constants D and D such that

P x i ( Xi t 2 > 0) ≤ (Dx i ) ∧ 1 ≤ D g(x i
) for all x i > 0.

(5.7)

To prove this, we can consider a scale function s of the diffusion Xi such that s(0) = 0 and s(x) > 0 for x > 0. Using the expression of the scale function and the speed measure (see e.g. [32, V.52]), one easily checks that s(x i ) ∼ αx i when x i → 0 for some α = 0 and that Proposition 4.9 of [START_REF] Champagnat | Uniform convergence of conditional distributions for absorbed one-dimensional diffusions[END_REF] is satisfied, so that P x i ( Xi t 2 > 0) ≤ M s(x i ) for some M > 0. Since s(x i ) ∼ αx i when x i → 0, (5.7) is proved and hence (2.7) holds true.

Step 4: Harnack inequality for u. Consider a bounded nonnegative measurable function f and define the application u :

(t, x) ∈ R + × (0, +∞) d → E x (f (X t )1 t<τ ∂ ).
Our aim is to prove that, for all m ≥ 1, there exist two constants N m > 0 and δ m > 0, which do not depend on f , such that u(δ 2 m , x) ≤ N m u(2δ 2 m , y), for all x, y ∈ O m such that |x -y| ≤ δ m /2. (5.8)

We fix m ≥ 1 and we will omit the indices m for the constants δ and N for the rest of Step 4. Let K be a compact set with C ∞ boundary such that O m ⊂ K ⊂ (0, +∞) d and such that d(O m , ∂K) > 0. We set δ = d(O m , ∂K)/3 and τ = inf{t ≥ 0 : X t ∈ ∂K}. Let x and y be fixed in K such that |x -y| ≤ δ/2. We define µ x and µ y as the joint law of (δ 2 -τ ∧ δ 2 , X τ ∧δ 2 ) starting from X 0 = x and (2δ 2 -τ ∧ (2δ 2 ), X τ ∧(2δ 2 ) ) starting from X 0 = y, respectively. It follows from Lusin's theorem (see e.g. [START_REF] Dudley | Real analysis and probability[END_REF]Thm. 7.5.2]) that there exists a sequence (h n ) n≥1 of bounded C ∞ functions from ([0, ∞[×∂K) ∪ ({0} × K) to R + such that (h n ) n≥1 converges bounded pointwisely toward u, (µ x + µ y )-almost everywhere. For all n ≥ 1, we let u n : [0, +∞[×K → R be the solution to the linear parabolic equation

     ∂ t u n = d i=1 x i ∂ 2 u n ∂x 2 i + x i r i (x) ∂u n ∂x i , ∀(t, x) ∈ (0, ∞) × int(K), u n (t, x) = h n (t, x), ∀(t, x) ∈ ([0, ∞[×∂K) ∪ ({0} × K).
By [START_REF] Lunardi | Analytic semigroups and optimal regularity in parabolic problems[END_REF]Thm 5.1.15], for all n ≥ 1, u n is of regularity C 1,2 . In particular, applying Itô's formula to s → u n (δ 2 -s, X s ) at time τ ∧ δ 2 and taking the expectation, one deduces that,

u n (δ 2 , x) = E x u n (δ 2 -τ ∧ δ 2 , X τ ∧δ 2 ) = µ x (h n )
By Lebesgue's theorem, the last quantity converges when n → +∞ to

µ x (u) = E x 1 τ ≤δ 2 u(δ 2 -τ, X τ ) + E x (1 τ >δ 2 u(0, X δ 2 )) = E x 1 τ ≤δ 2 E Xτ (f (X δ 2 -τ )1 δ 2 -τ <τ ∂ ) + E x (1 τ >δ 2 f (X δ 2 )) = E x (f (X δ 2 )1 δ 2 <τ ∂ ) = u(δ 2 , x),
where we used the strong Markov property at time τ . Similarly, u n (2δ 2 , y) converges to u(2δ 2 , y).

Using the Harnack inequality provided by [26, Theorem 1.1] (with θ = 2 and R = δ), we deduce that there exists a constant N > 0 which does not depend on f , x, y ∈ K such that |x -y| ≤ δ/2 nor on n such that u n (δ 2 , x) ≤ N u n (2δ 2 , y).

Hence, we deduce that u(δ 2 , x) ≤ N u(2δ 2 , y), for all x, y ∈ K such that |x -y| ≤ δ/2

(5.9) and (5.8) is proved.

Step 5 : proof that Assumptions 2 and 3 are satisfied. Fix x 1 ∈ O 1 and let ν denote the conditional law P x 1 (X δ 2 1 ∈ • | δ 2 1 < τ ∂ ). Then the Harnack inequality (5.8) entails that, for all x ∈ O 1 such that |x -x 1 | ≤ δ 1 /2 and all measurable nonnegative bounded f on (0, +∞) d , As a consequence, the second part of Assumption 2 is satisfied. Assumption 3 is a direct consequence of the domination by solutions to (5.4), since these solutions come down from infinity and hit 0 in finite time almost surely (cf. e.g. [START_REF] Cattiaux | Quasi-stationary distributions and diffusion models in population dynamics[END_REF]).

E x f (X 2δ 2 1 )1 2δ 2 1 <τ ∂ ≥ 1 N 1 E x 1 f (X δ 2
Finally, we deduce from Steps 1, 2, 3 and 5 that all the assumptions of Theorem 2.4 are satisfied. This concludes the proof of Theorem 5.1.

Proof of Theorem 4 . 1 .

 41 Using (4.3) and copying the arguments of [13, Sec. 4.1.1 and Thm. 4.1], one deduces that Assumption 2 is satisfied with ν = δ (1,...,1)

  h β is nonincreasing and convex on [a, +∞), M := sup β≥M sup x∈[a/2,a] |h β (x)| < +∞ and M := sup β≥M sup x∈[a/2,a] |h β (x)| < +∞. We set β = M + (2 ∨ aM )/C a + 1 and

Figure 1 :

 1 Figure 1: A typical graph of h β .

  1 )1 δ 2 1 <τ ∂ . Now, let m ≥ 1. Since O m is bounded, connected and at a positive distance of ∂, P x (X 1 ∈ O 1 ∩ B(x 1 , δ 1 /2)) is uniformly bounded from below in O m by a positive constant M m . Therefore, Markov's property implies that, for all x ∈ O m , This is the first part of Assumption 2.The second part of Assumption 2 is also a consequence of (5.8). Indeed, for any fixed m and for all t ≥ 2δ 2 m , this equation applied to f (x) = P x (t -2δ 2 m < τ ∂ ) and the Markov property entail thatP x (t -δ 2 m < τ ∂ ) ≤ N m P y (t < τ ∂ ), for all x, y ∈ O m such that |x -y| ≤ δ m /2.Since s → P x (s < τ ∂ ) is non-increasing, we deduce thatP x (t < τ ∂ ) ≤ N m P y (t < τ ∂ ), for all x, y ∈ O m such that |x -y| ≤ δ m /2.Since O m has a finite diameter and is connected, we deduce that there exists N m such that, for all t ≥ 2δ 2 m ,P x (t < τ ∂ ) ≤ N m P y (t < τ ∂ ),for all x, y ∈ O m . Now, for t ≤ 2δ 2 m , we simply use the fact that x → P x (2δ 2 m < τ ∂ ) is uniformly bounded from below on O m by a constant 1/N m > 0. In particular, P x (t < τ ∂ ) ≤ 1 ≤ N m P y (2δ 2 m < τ ∂ ) ≤ N m P y (t < τ ∂ ), for all x, y ∈ O m .

	This means that
	P x (X 2δ 2 1 ∈ •) ≥	P x 1 (δ 2 1 < τ ∂ ) N 1	ν.
	P x (X 1+2δ 2 1 ∈ •) ≥	P x 1 (δ 2 1 < τ ∂ ) M n N 1	ν.

One can easily adapt our proofs to cases where entry times in other sets (e.g. open) are strong Markov times for the process.

Note that more efficient criteria exist for one-dimensional diffusions (see[START_REF] Champagnat | Uniform convergence of conditional distributions for absorbed one-dimensional diffusions[END_REF]). The interest of our criterion comes from the fact that it applies to multi-dimensional processes.


Emilie Lerigoleur

Sabrina Bosque

Nicolas Maestripieri

Emilie Gil

Mehdi Saqalli

Des cartes librement accessibles pour visualiser le paysage pétrolier en Amazonie

Localiser convenablement les infrastructures pétrolières et les déversements accidentels liés à l'exploitation pétrolière permet de montrer l'ampleur spatiale des menaces (ou « aléas ») auxquelles les populations locales et l'environnement sont exposées.

Conclusion

La cartographie interactive offre un support visuel de discussion autour de la problématique pétrolière de cette vaste région et une potentielle source valide d'informations accessibles à l'attention de différents publics, qu'il s'agisse des chercheurs, des partenaires institutionnels, de la population locale ou d'autres acteurs publics.

L

  'un des défis du programme MONOIL a consisté à collecter, analyser et compiler des données géographiques (existantes et nouvellement collectées) d'origines variées, afin de délivrer aux publicscommunautés, organisations gouvernementales, chercheurs…-des éléments objectifs sur le sujet, base documentaire fiable, facile d'accès, actualisée et validée par le regard croisé de scientifiques experts du domaine. Notre zone d'étude couvre les provinces de Napo, Sucumbíos et Orellana sur près de 41 000 km², elle s'étend de la frontière péruvienne à l'Est jusqu'au piémont de la Cordillère des Andes à l'Ouest. Le challenge fut de centraliser toutes les informations spatiales d'intérêt pour la compréhension de tous les facteurs impliqués dans les contaminations pétrolières sur ce vaste territoire. Centraliser des données géographiques hétérogènes et éparses dans une base de données commune La construction d'une base de données commune est une étape essentielle dans un projet multidisciplinaire et pluri-partenaires. Sur le terrain, les chercheurs ont collecté des données géographiques auprès de divers organismes dont les principaux sont : le MAE-PRAS (Programa de Reparación Ambiental y Social del Ministerio del Ambiente) pour l'inventaire des infrastructures pétrolières et des événements de contamination pétrolière, le SENPLADES (Secretaría Nacional de Planificación y Desarrollo) coordinateur du SNI (Sistema Nacional de Información) pour les données socio-économiques et administratives notamment, l'IGM (Instituto Geográfico Militar), l'Université Andina Simon Bolivar et enfin les municipalités et les juntes paroissiales. Cet inventaire a révélé la richesse des données disponibles, mais aussi leur hétérogénéité et de nombreuses redondances et lacunes, même si le SNI est en train de centraliser et d'harmoniser l'information disponible. La base de données ainsi constituée stocke et met à disposition non seulement les 145 cartes thématiques recensées, mais aussi les cartes de données spatiales produites dans le cadre du projet MONOIL comme par exemple la carte exprimant les différents niveaux de perception des contaminations pétrolières par la population interviewée. Un travail de regroupement et d'homogénéisation des données spatiales a permis d'aboutir à la production de 29 cartes de synthèse. Par exemple, les 9 couches de routes et sentiers, venant de différentes sources, souvent partiellement redondantes ou mal positionnées, ont été rassemblées dans une carte unique. Ce travail n'occulte en rien la provenance des sources d'information utilisées puisque la traçabilité des fournisseurs de données a été respectée. De plus, une série de traitements spatiaux a permis la réalisation de couches de relief, de pente, de pédologie, d'utilisation du sol, de sources de contamination hydrique ou aérienne, etc. Ce travail préalable de centralisation et de production de couches a permis notamment de générer des cartes « interactives ». Des cartes interactives à disposition de tous, acteurs publics, société civile et chercheurs Qu'est-ce qu'une carte interactive ? C'est une carte diffusée via le réseau Internet qui traite un sujet donné, ici les impacts pétroliers. On peut y naviguer, zoomer, voir même interroger ou éditer directement la carte. Pour les acteurs publics comme pour les chercheurs travaillant sur ce territoire, ce type de cartes offre un outil visuel comme support de discussions sans avoir recours à l'utilisation d'un logiciel SIG (Système d'Information Géographique). Pour les chercheurs, il donne accès à certains résultats de recherche du projet MONOIL. Quant aux populations locales ayant accès à Internet (et une connexion avec un débit suffisamment rapide), elles découvrent leur territoire sous un autre point de vue, celui du chercheur. Plusieurs technologies existent : c'est la solution Lizmap (http://www.3liz.com/lizmap.html) qui a été choisie pour publier facilement sur Internet des cartes préalablement créées avec un logiciel SIG libre QGIS (https://www.qgis.org). En quelques clics, la carte se retrouve diffusée sur Internet, avec un large choix de fonds de carte (Google, MapQuest, OpenStreetMap) et la possibilité de cocher/décocher les types de données, de réaliser des zooms, etc. (figure 23). Actuellement, cinq cartes thématiques distinctes sont diffusées sur le site web du laboratoire GEODE (onglet MONOIL) respectivement sur les contaminations pétrolières passées, les inondations, l'organisation sociale des populations locales avec la qualité de l'eau et leurs différents usages, les occupations du sol et enfin la perception des contaminations issues des activités pétrolières (figure 24). Cette dernière reprend notamment les résultats du travail de cartographie des perceptions par la méthode du "zonage à Dires d'acteurs" (Saqalli et al. 2009, Maestripieri et al. 2016) (voir p.205 de cet ouvrage).


Betty Fabre
email: betty.fabre@orange.com

Tanguy Urvoy
email: tanguy.urvoy@orange.com

Jonathan Chevelu
email: jonathan.chevelu@irisa.fr

Damien Lolive
email: damien.lolive@irisa.fr

Neural-Driven Multi-criteria Tree Search for Paraphrase Generation

A good paraphrase is semantically similar to the original sentence but it must be also well formed, and syntactically different to ensure diversity. To deal with this tradeoff, we propose to cast the paraphrase generation task as a multi-objectives search problem on the lattice of text transformations. We use BERT and GPT2 to measure respectively the semantic distance and the correctness of the candidates. We study two search algorithms: Monte-Carlo Tree Search For Paraphrase Generation (MCPG) and Pareto Tree Search (PTS) that we use to explore the huge sets of candidates generated by applying the PPDB-2.0 edition rules. We evaluate this approach on 5 datasets and show that it performs reasonably well and that it outperforms a state-of-the-art edition-based text generation method.

Introduction

The generation of paraphrase, i.e. the transformation of a sentence into a well-formed but lexically different one while preserving its original meaning, is a fundamental task of NLP. Its ability to provide diversity and coverage finds applications in several domains like question answering [START_REF] Harabagiu | Methods for Using Textual Entailment in Open-Domain Question Answering[END_REF], machine-translation [START_REF] Callison-Burch | Improved Statistical Machine Translation Using Paraphrases[END_REF], dialog systems [START_REF] Zhao | DocChat: An Information Retrieval Approach for Chatbot Engines Using Unstructured Documents[END_REF], privacy [START_REF] Gröndahl | Effective writing style imitation via combinatorial paraphrasing[END_REF] or more recently adversarial learning [START_REF] Iyyer | Adversarial Example Generation with Syntactically Controlled Paraphrase Networks[END_REF]. The formal definition of paraphrase may vary according to the targeted application and the tolerance we set along several axes including:

1. the semantic distance from the source that we want to minimize; 2. the quality of the syntax that we want to keep high; 3. the lexical distance from the source that we want to maximize to ensure diversity.

Automatically generating paraphrases that are semantically accurate, diverse, and well-formed remains a challenging problem, and with the lack of large and high-quality aligned paraphrase corpora, it is difficult to train generic supervised models on this task.

On the other hand, assessing the quality of a given sentence as a paraphrase has become a much more tractable task. Indeed, the availability of contextual embeddings networks trained on huge corpora have led to the development of high-quality semantic distances [START_REF] Devlin | BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding[END_REF][START_REF] Cer | Universal Sentence Encoder for English[END_REF][START_REF] Witteveen | Paraphrasing with Large Language Models[END_REF][START_REF] Zhang | BERTScore: Evaluating Text Generation with BERT[END_REF]. Regarding the quality of the syntax, the perplexity of a large-scale language model like GPT2 [START_REF] Radford | Language Models are Unsupervised Multitask Learners[END_REF] is an excellent ranking criterion as well. For the lexical distance we use a simple Levenshtein edition distance. Leveraging on these three metrics, we cast the paraphrase generation task as a multi-criteria search problem. In this experiment we use PPDB 2.0 [START_REF] Pavlick | PPDB 2.0: Better paraphrase ranking, fine-grained entailment relations, word embeddings, and style classification[END_REF], a large-scale database of rewriting rules derived from bilingual 1st Workshop on Learning Meets Combinatorial Algorithms @ NeurIPS 2020, Vancouver, Canada. corpora, to potentially generate billions of 'naive' candidate paraphrases by edition from the source sentence.

To sort efficiently the good candidates from the others, we experiment two algorithms. The first one, called MCPG for Monte-Carlo Paraphrase Generation, is a variant of the Monte-Carlo Tree Search algorithm (MCTS) [START_REF] Kocsis | Bandit Based Monte-carlo Planning[END_REF][START_REF] Gelly | Combining Online and Offline Knowledge in UCT[END_REF][START_REF] Chevelu | Introduction of a new paraphrase generation tool based on Monte-Carlo sampling[END_REF]. This algorithm is famous for its successes on mastering the -highly combinatorial -game of Go [START_REF] Gelly | Combining Online and Offline Knowledge in UCT[END_REF][START_REF] Silver | Mastering the game of Go with deep neural networks and tree search[END_REF]. The second one is a novel search algorithm that we call Pareto Tree Search (PTS). In contrast to MCTS which is a single-criterion search algorithm, we designed to retrieve an approximation of the whole Pareto optimal set. This allows for more flexibility on paraphrase generation where the balance between semantic distance, lexical distance, and syntax quality is hard to tune a priori.

Paraphrase Generation Lattice

We model the paraphrase generation as a sequence of editions and transformations from a source sentence into its paraphrase. In this work, we only consider local transformations, i.e. replacement of certain words or phrases by others, but the method we propose should work with more sophisticated transformations schemes as well.

Source sentence :

he is speaking on june 14 .

PPDB rule

Edited sentence is → is found he is found speaking on june 14 . is speaking → 's talking he 's talking on june 14 . speaking → speak now he is speak now on june 14 . 14 → 14th he is speaking on june 14th .

Table 1: PPDB rules samples applied to a source sentence

The Paraphrase Database (PPDB) [START_REF] Ganitkevitch | PPDB: The Paraphrase Database[END_REF][START_REF] Pavlick | PPDB 2.0: Better paraphrase ranking, fine-grained entailment relations, word embeddings, and style classification[END_REF] is a large collection of paraphrase edition rules that was automatically constructed from various bilingual corpora using a pivoting alignment method [START_REF] Callison-Burch | Syntactic Constraints on Paraphrases Extracted from Parallel Corpora[END_REF]. The PPDB database is divided into increasingly large and decreasingly accurate subsets 1 We used the XL subset, and we removed the rules labeled as "Independent". This left us with a set of 5.5 million rewriting rules. We give some examples of these rules on Table 1. By iteratively applying the rules from a source sentence like the one on Table 1, we obtain a vast lattice of candidate paraphrases. Some of these candidates like "he's talking on june 14" are well formed, but many like "he is speak now on june 14" are syntactically broken. The number of rules that apply, depends on the size of the source sentence and the words it contains. For instance on the MSRPARAPHRASE dataset (see section 4), the sentences are quite long and the median number of PPDB-XL rules that apply is around 450. After two steps of rewriting, the median number of candidates is around 10 5 and by iterative rewriting, we quickly reach a number of paraphrase candidates that is greater than 10 8 .

3 Searching Algorithms Searching for good paraphrases in the large lattice of candidates generated by PPDB is a costly task. The two algorithms that we propose are described as pseudocode on Tables 2 and3. They share a similar structure: the outer loop explores the lattice at different depths, while the inner loop explores the candidates at each depth. Both algorithms are anytime: they return the best solutions found so far when the time or space budget is depleted.

MCPG: Monte-Carlo Tree Search for Paraphrase Generation Following the idea of [START_REF] Chevelu | Introduction of a new paraphrase generation tool based on Monte-Carlo sampling[END_REF], we used Monte-Carlo Tree Search (MCTS) to explore the PPDB lattice. The three key ingredients of MCTS are: the use of a bandit policy at each node of a search-tree to select the most promising paths, the use of randomized roll-outs to estimate the quality of these paths, and the back-propagation of rewards along the paths to update the bandit. We opted here for the EXP3 [START_REF] Auer | The Nonstochastic Multiarmed Bandit Problem[END_REF] randomized bandit policy which proved to be robuster than UCB [START_REF] Auer | Finite-time Analysis of the Multiarmed Bandit Problem[END_REF]. candidates Dominated candidates

Figure 1: Cloud of candidates generated from a sample of the MSRPARAPHRASE. The optima of any positive combination of BERT score, Levenshtein distance, and GPT2 perplexity belong to the Pareto front (orange dots). We plotted the projections of MCPG combined score with dashed isolines. The BERT score and Levenshtein distance being clearly anti-correlated, the balance between these two criteria is difficult to tune.

The MCTS algorithm being not designed for multi-objective problems, we had to combine semantic similarity BERT S , syntax correctness GPT2 and surface diversity Lev S into a single criterion.

The simplest option was a linear scalarization but after some quantitative analysis of the scores distributions like in 1, we realized that it was easy for the search algorithm to maximize the score by just applying a lot of editions to the source sentence. To overcome this, we replaced the Lev S term by Lev S • BERT S which led us to the polynomial form α

• BERT S + β • Lev S • BERT S -γ • GPT2.
After a few experiments on train sets, we tuned empirically the weights to α = 3, β = 0.5 and γ = 0.025 in order to obtain a balanced policy. PTS: Pareto Tree Search in the paraphrase lattice The MCTS algorithm is powerful but we observed two drawbacks for paraphrase generation. First, it was designed for combinatorial problems like Go where the evaluation is only possible on the leaves of the search tree. This is not the case for paraphrase generation where our neural models can cheaply evaluate any rewriting step and where rewriting from good candidates is more likely to provide good paraphrases than rewriting from bad ones. Secondly, because it was designed for single criterion search it requires to set the balance between semantic similarity, lexical distance and syntax quality definitively before any paraphrase search begins. This is not very flexible and it becomes painful when we want to generate sets of candidates.

By plotting the distributions of the scores as on Figure 1, we noticed that most of the candidates were dominated in the Pareto sense: it was possible to eliminate most of the bad candidates without any hyper-parameter tuning. We hence adapted MCPG in order to explore the paraphrase lattice and recover an approximation of the Pareto front, postponing the balance between the criteria as a quick post-optimization stage. This flexibility is also useful for specific tasks like adversarial learning [START_REF] Iyyer | Adversarial Example Generation with Syntactically Controlled Paraphrase Networks[END_REF] where a valid paraphrase is selected in post-optimization according to its ability to deceive a given text classification model.

Experiments

Datasets and metrics To evaluate the paraphrase generation models, we rely on machine translation metrics that compare the generated paraphrase to one or several references [START_REF]Handbook of Natural Language Processing and Machine Translation: DARPA Global Autonomous Language Exploitation[END_REF].

We report the surface metric BLEU [START_REF] Clark | Better Hypothesis Testing for Statistical Machine Translation: Controlling for Optimizer Instability[END_REF] and the semantic metric BERT [START_REF] Zhang | BERTScore: Evaluating Text Generation with BERT[END_REF] : the average BERT score of the generated sentence with respect to the ground truth sentences2 .

Corpus

Size Len PPDB@1 PPDB@3 Table 4: Datasets statistics. 'Size' is the number of instances. 'Len' is the median number of words per sentence. The 'PPDB@x' columns give the median number of candidates that PPDB-XL generates from one sentence respectively at one and three rewriting steps.

On Table 4 we give a summary of the datasets we used. On one hand we have large datasets like MSCOCO or OPUSPAR-CUS (OPUSPAR.) that are noisy and very specific. On the other hand we have MSR-PARAPHRASE (MSRPARA.), a high-quality but small human-labeled dataset.

Baseline Constrained Sentence Generation by Metropolis-Hastings Sampling (CGMH) [START_REF] Miao | CGMH: Constrained Sentence Generation by Metropolis-Hastings Sampling[END_REF] is an approach that uses Metropolis-Hastings sampling [START_REF] Metropolis | Equation of State Calculations by Fast Computing Machines[END_REF] for constrained sentence generation. Starting from the source sentence, the CGMH model samples a sequence of sentences by using local editions: word replacement, deletion, and insertion. For paraphrase generation, CGMH constraints the sentence generation using a matching function that combines a measure of semantic similarity and a measure of English fluency. This model is therefore directly comparable with the MCPG and PTS approaches.

Results On Table 5 we report the evaluation of the CGMH, MCPG and PTS models on the five datasets of aligned paraphrases pairs. MCPG and PTS models outperform the CGMH baseline model on all corpora except on the MSCOCO dataset where the results are mixed. The low PTS upper-bound on MSCOCO and OPUSPAR-CUS indicates that PPDB-XL vocabulary does not match well with these datasets.

Discussion

We experimented two search-based approaches for paraphrase generation. These approaches are pragmatic and flexible. When compared against CGMH, another search-based and weakly-supervised method, our algorithms proved to be faster and more efficient. The use of local transformations however lead our models to produce paraphrases that are a bit too conservative, especially when starting from short sentences. For future work, we plan to refine the scoring with deep reinforcement learning techniques and enrich the rules with more sophisticated patterns like phrases permutations. We also plan to hybridize the search method with supervised seq2seq models [START_REF] Vaswani | Attention Is All You Need[END_REF] by data-augmentation, or through a planning-then-realization scheme like in [START_REF] Moryossef | Step-by-Step: Separating Planning from Realization in Neural Data-to-Text Generation[END_REF] and [START_REF] Fu | Paraphrase Generation with Latent Bag of Words[END_REF].

Table 2 :

 2 Monte-Carlo Tree Search (MCPG) algorithm

	leaves)
	Backward node rewards along paths
	MAB.UPDATES POLICY(node rewards)
	end while
	layer best ← ARGMAX(scored)
	candidates ← candidates ∪ REWRITE(layer best)
	depth ← depth + 1
	end while
	return ARGMAX(all scored nodes)
	end function

function MCPG(input sentence) candidates ← REWRITE(input sentence) depth ← 1 while time/space < budget do while time/space < layer-budget do nodes ← MAB.SELECTS FROM(candidates) paths ← ROLLOUT FROM(nodes) scored ← scored ∪ NN.SCORE(paths.

Table 3 :

 3 Pareto Tree Search (PTS)

Table 5 :

 5 Experiments summary. Higher values are better, best in bold. The PTS policy maximizes the MCPG criterion among the Pareto candidates.

	The PTS random policy picks a random candidate
	in the Pareto set. The PTS upper-bound (upper-b.)
	policy is "cheating" by taking a candidate that max-
	imizes individual BLEU against the target. These
	two former policies are given to assess the "quality"
	of the generated set of candidates.

PPDB is available on http://paraphrase.org

This usage of BERT score against reference/ground-truth must not be confused with the BERT score against source sentence (BERTS) that we use in the MCPG score.