Arnaud Guillin

Ald Éric Joulin

MEASURE CONCENTRATION THROUGH NON-LIPSCHITZ OBSERVABLES AND FUNCTIONAL INEQUALITIES

Keywords: 2000 Mathematics Subject Classification. 46E35, 60E15, 60J27, 60J60, 60K35 Concentration, invariant measure, reversible Markov process, Lyapunov condition, functional inequality, carré du champ, diffusion process, jump process

Non-Gaussian concentration estimates are obtained for invariant probability measures of reversible Markov processes. We show that the functional inequalities approach combined with a suitable Lyapunov condition allows us to circumvent the classical Lipschitz assumption of the observables. Our method is general and covers diffusions as well as pure-jump Markov processes on unbounded spaces.

Introduction

In the last few decades, the concentration of measure phenomenon has attracted a lot of attention. Given a metric probability space (X , d, µ) and a sufficiently large class of functions defined on this space (we call them observables), the concentration of measure occurs when, observed through these functions, the space seems to be actually smaller than it is. In other words, there exists a nondecreasing continuous function α : [0, ∞) → [0, ∞), null at the origin and tending to infinity at infinity, such that for a given (symmetric) class C of observables f : X → R, µ {x ∈ X : f (x) -X f dµ > r} ≤ e -α(r) , r ≥ 0.

The concentration is said to be Gaussian when α is quadratic-like. In connection with isoperimetry theory, the class C is usually taken to be the space of Lipschitz functions on (X , d, µ), say Lip(X ). A good review on the subject is the monograph [START_REF] Ledoux | The concentration of measure phenomenon[END_REF] where the interested reader will find a clear introduction to the topic. One may mention also the recent progress in the area through mass transportation techniques, see the recent survey [START_REF] Gozlan | Transport inequalities. A survey. Markov Process[END_REF].

In this paper, we emphasize a dynamical point of view of concentration of measure. Given the invariant measure µ of an ergodic continuous-time Markov process (X t ) t≥0 with carré du champ operator Γ (see below for the definition), we provide concentration properties of µ through observables which depend on the dynamics. As it is sometimes the case in previous studies, see for instance [START_REF] Ledoux | Concentration of measure and logarithmic Sobolev inequalities[END_REF] for a state of the art, our starting point is to assume that the pair (µ, Γ) satisfies a convenient functional inequality such as Poincaré or the entropic inequality. Such inequalities, which are verified by a wide variety of examples, are closely related to the longtime behaviour of the process. In particular, this approach allows to unify both continuous and discrete space settings even if, in essence, these two objects are rather different from each other. In the diffusion framework, the main ingredient to establish Gaussian concentration through functional inequalities is based on the chain rule derivation formula satisfied by the operator Γ. In the context of Markov jump processes, although this property is not verified -here Γ becomes a finite difference operator -this difficulty can be circumvented by using reversibility and Gaussian concentration properties are still available in this discrete situation. In both cases the carré du champ refers to a natural distance related to the dynamics and, within this notion of distance, the Lipschitz observables under which concentration estimates are obtained are the ones with a bounded carré du champ, that is to say the space Lip Γ (X ) of functions f such that Γ(f, f ) is µ-essentially bounded. Then a natural question arises: which type of measure concentration can we obtain beyond the space Lip Γ (X ) ? In particular in discrete space settings, such a study basically makes sense on an unbounded state space X . Using the notion of Ricci curvature for Markov chains (a definition also available in continuoustime), a first result of this kind was given by Ollivier in [START_REF] Ollivier | Ricci curvature of Markov chains on metric spaces[END_REF], in which he obtains concentration bounds involving a mixed Gaussian-exponential regime, i.e. α(r) is quadratic/linear for small/large r. In our language, he requires that the carré du champ Γ(f, f ) belongs to the space Lip(X ). Despite this interesting and new result, which is sufficiently robust to be extended to additive functionals, see e.g. [START_REF] Joulin | A new Poisson-type deviation inequality for Markov jump processes with positive Wasserstein curvature[END_REF] and [START_REF] Joulin | Curvature, concentration, and error estimates for Markov chain Monte Carlo[END_REF], it seems to the authors that there is no satisfactory treatment yet to this question and we hope to give (the beginning of) an answer to this problem with the present article.

Our idea is to use a Lyapunov condition on the observables. This kind of criteria have been successfully used for proving various types of functional inequalities, cf. [START_REF] Barthe | Poincaré inequalities for log-concave probability measures: a Lyapunov function approach[END_REF][START_REF] Cattiaux | A note on Talagrand transportation inequality and logarithmic Sobolev inequality[END_REF][START_REF] Cattiaux | Some remarks on weighted logarithmic Sobolev inequality[END_REF][START_REF] Guillin | Transportation inequalities for Markov processes[END_REF] and for concentration estimates of additive functionals, see for instance [START_REF] Cattiaux | Deviation bounds for additive functionals of Markov process[END_REF][START_REF] Gao | Bernstein type's concentration inequalities for symmetric Markov processes[END_REF][START_REF] Chafaï | Intertwining and commutation relations for birth-death processes[END_REF]. Namely we will consider the class L V (a, b) of observables f such that

Γ(f, f ) ≤ -a LV V + b,
where a, b are two positive constants and V is a convenient test function. When a vanishes the class L V (a, b) reduces to the space Lip Γ (X ) and the classical concentration results apply [START_REF] Ledoux | Concentration of measure and logarithmic Sobolev inequalities[END_REF]. In particular, the behaviour of the carré du champ Γ(f, f ) depends now on the growth of the term -LV /V , which has no reason to be bounded. Of course there is a price to pay for such an improvement and it resides in the concentration property of the measure µ, which is no longer Gaussian but only of Gaussian-exponential type under this class of observables.

To fix the ideas, let us consider a simple example on the set N := {0, 1, 2, . . .} endowed with the classical distance between integers. Denote µ p the geometric distribution on N of parameter p ∈ (0, 1), i.e. µ p ({x}) := (1p)p x , x ∈ N. Then there exist infinitely many dynamics on N admitting µ p as their reversible invariant measure, and among them let us consider the Markov process with carré du champ

Γ (n) (f, f )(x) := 1 2 p(x + 1) n (f (x + 1) -f (x)) 2 + x n 1 {x =0} (f (x -1) -f (x)) 2 ,
where x ∈ N and n ∈ N is some fixed parameter. On the one hand we can prove that for every n ∈ N the dynamics (µ p , Γ (n) ) satisfies a Poincaré inequality and adapting then to the discrete case the method introduced by Aida and Stroock in [START_REF] Aida | Moment estimates derived from Poincaré and logarithmic Sobolev inequalities[END_REF] entails a mixed Gaussian-exponential regime for the measure µ p , under observables f ∈ Lip Γ (n) (N). Actually, these observables correspond to:

-functions belonging to the space Lip(N) in the case n = 0. Such an estimate is sharp, cf. for instance [START_REF] Houdré | Remarks on deviation inequalities for functions of infinitely divisible random vectors[END_REF][START_REF] Joulin | Functional inequalities for discrete gradients and applications to the geometric distribution[END_REF];

-functions of order √ x in the case n = 1. According to the previous line, the measure µ p should concentrate at least like a Gaussian through these observables; -functions of order log(x) in the case n = 2. Under these observables, α(r) should behave like e -e r for large r;

-bounded functions in the case n ≥ 3. On the other hand Ollivier's method cleverly applies, but only in the case n = 1. Hence one observes that these two methods does not lead to sharp results as soon as n ≥ 2. Actually, thanks to the Lyapunov approach, the Gaussian-exponential concentration results we give in this paper apply for observables f with carré du champ Γ (n) (f, f )(x) of order x n , i.e. of the expected order of magnitude.

The paper is organized as follows. In section 2, we recall some basic material on Markov processes and functional inequalities. Two types of processes are considered in our study: diffusions and pure-jump Markov processes. Next we state in section 3 our main results of the paper, theorems 3.6 and 3.11, in which some mixed Gaussian-exponential concentration properties of µ are obtained through observables satisfying the Lyapunov condition defined above and under a convenient functional inequality assumption satisfied by the dynamics (µ, Γ). As a result, such new concentration inequalities extend the classical estimates obtained when the observables belong to the space Lip Γ (X ), corresponding to the case where a vanishes. Finally, section 4 is devoted to numerous examples in continuous and discrete settings. First we investigate the diffusion case of Kolmogorov processes whose invariant measure has density proportional to e -U , where U is some nice potential on R d , and for which we derive a concentration result when U is considered as an observable, in the spirit of the recent progress made by Bobkov and Madiman in [START_REF] Bobkov | Concentration of the information in data with log-concave distributions[END_REF]. Dealing with jump processes, the case of birth-death processes is addressed in detail. When we apply our concentration estimates to observables in Lip(N) equipped with the classical distance between integers, we are able to consider processes whose generator is unbounded, like the basic example investigated above. Finally, we focus our attention on an unbounded interacting particle system, namely the Glauber dynamics associated to a Gibbs measure defined with respect to a Poisson reference measure.

Preliminaries

2.1. Functional inequalities. Throughout the paper, (X , d) is a Polish space endowed with the corresponding Borel σ-field B and Lip(X ) is the space of Lipschitz functions on X with finite Lipschitz seminorm with respect to d, i.e.

f Lip := sup x =y |f (x) -f (y)| d(x, y) < ∞.
On a filtered probability space (Ω, F , (F t ) t≥0 , P), let {(X t ) t≥0 , (P x ) x∈X } be an X -valued càdlàg ergodic Markov process with reversible invariant measure (or stationary distribution) µ and symmetric semigroup (P t ) t≥0 on L 2 (µ). In the sequel we denote L p (µ

) := L p (X , B, µ) for p ∈ [1, ∞].
Denote L the self-adjoint generator acting on its dense domain D 2 (L) consisting of functions f ∈ L 2 (µ) such that t -1 (P t f -f ) admits a limit in L 2 (µ) as t → 0. One of the main protagonists of the present paper is the carré du champ Γ, which is a bilinear symmetric operator on

D 2 (L) × D 2 (L) defined by Γ(f, g) := 1 2 (L(f g) -f Lg -gLf ) .
As mentioned in the introduction, there is a natural pseudo-distance associated to the operator Γ which can be defined as

d Γ (x, y) := sup |f (x) -f (y)| : Γ(f, f ) L ∞ (µ) ≤ 1 , x, y ∈ X .
Although this distance can be infinite, it is well-defined in the situations of interest and carries a lot of information about the structure of the underlying process. In the sequel, we denote Lip Γ (X ) the space of Lipschitz functions with respect to d Γ .

The associated Dirichlet form acts on D(E µ ) × D(E µ ) as

E µ (f, g) = X Γ(f, g) dµ,
where D(E µ ) is the subspace of all functions f ∈ D 2 (L) such that E µ (f, f ) is well-defined. In particular, the Donsker-Varadhan information of any probability measure ν on X with respect to the invariant measure µ is defined as

I(ν|µ) := E µ √ f , √ f if dν = f dµ, √ f ∈ D(E µ ); ∞ otherwise.
A key point in our analysis is that the functional ν → I(ν|µ) is nothing but the rate function governing the Large Deviation Principle in large time of the empirical measure of (X t ) t≥0 . However in the non-reversible case, it is given by a contraction form of the Donsker-Varadhan entropy which is different from the Donsker-Varadhan information, so that our study will not extend to the nonsymmetric case, unfortunately. Now let us introduce the functional inequalities we will focus on in the paper. Given an integrable function f ∈ L 1 (µ), we denote µ(f ) := X f dµ. Let I be an open interval of R and for a convex function φ : I → R we define the φ-entropy of a function f :

X → I with φ(f ) ∈ L 1 (µ) as Ent φ µ (f ) := µ (φ(f )) -φ (µ(f )) . The dynamics (µ, Γ) satisfies a φ-entropy inequality with constant C φ > 0 if for any I-valued function f ∈ D(E µ ) such that φ ′ (f ) ∈ D(E µ ), C φ Ent φ µ (f ) ≤ 1 2 E µ (f, φ ′ (f )).
See for instance [START_REF] Chafaï | Entropies, convexity, and functional inequalities[END_REF] for a careful investigation of the properties of φ-entropies. The latter inequality is satisfied if and only if the following entropy dissipation of the semigroup holds: for any

I-valued function f such that φ(f ) ∈ L 1 (µ), Ent φ µ (P t f ) ≤ e -2C φ t Ent φ µ (f ), t ≥ 0.
In this paper we will consider three cases:

(i) the Poincaré inequality: φ(u) = u 2 with I = R and the φ-entropy inequality rewrites as

λ Var µ (f ) ≤ E µ (f, f ) , ( 2.1
) where the variance of f under µ is given by

Var µ (f ) := µ(f 2 ) -µ(f ) 2 .
The optimal constant λ 1 (say) is nothing but the spectral gap in L 2 (µ) of the operator -L, i.e. its smallest non-zero eigenvalue. Estimating λ 1 allows us to obtain the optimal rate of convergence of the semigroup in L 2 (µ).

(ii) the entropic inequality: φ(u) = u log u with I = (0, ∞) and the φ-entropy inequality is given by

ρ Ent µ (f ) ≤ E µ (f, log f ) , (2.
2) where the entropy under µ of the smooth positive function f is defined by

Ent µ (f ) := µ(f log f ) -µ(f ) log µ(f ).
We have skipped in the inequality the constant 1/2 for convenience in future computations. Once again, the best constant ρ 0 in (2.2) gives the optimal exponential decay of the entropy along the semigroup.

(iii) the Beckner-type inequality: φ(u) = u p with p ∈ (1, 2] and I = (0, ∞). We have in this case

α p (µ(f p ) -µ(f ) p ) ≤ p 2 E µ f, f p-1 . (2.3)
Estimating α p gives the optimal rate of convergence of the semigroup in L p (µ).

The entropic and Beckner-type inequalities are stronger than the Poincaré inequality (apply these inequalities to the function 1 + εf and take the limit as ε → 0). Moreover it reduces to the Poincaré inequality (2.1) if p = 2, whereas dividing both sides by p -1 and taking the limit as p → 1 we obtain the entropic inequality (2.2).

In this paper we will mainly consider two general classes of reversible Markov processes: diffusions and pure jump Markov processes to which we turn now.

Diffusion processes.

A diffusion process on the Euclidean space X = R d corresponds to a path continuous Markov process on R d whose generator L is a second order differential operator: for any sufficiently smooth function f : R d → R,

Lf (x) = d i,j=1 a i,j (x) ∂ 2 f ∂x i ∂x j (x) + d i=1 b i (x) ∂f ∂x i (x), x ∈ R d .
Here a := σσ * is a measurable and locally bounded function from R d to the space of d × d symmetric positive definite matrices with smooth entries, σ * being the transpose of the matrix σ, and the measurable drift b : R d → R d is also assumed to be smooth. In this case the carré du champ is given by

Γ(f, g) = d i,j=1 a i,j ∂f ∂x i ∂f ∂x j = < σ * ∇f, σ * ∇g >,
where < •, • > stands for the Euclidean scalar product in R d and ∇ is the usual gradient operator. In particular when σ is the identity matrix, the spaces Lip(R d ) and Lip Γ (R d ) might be identified.

In contrast to the jump case introduced below, Γ is a differentiation, i.e. for all any smooth enough functions (f k ) 1≤k≤n , f : R d → R and any C 1 function φ : R n → R,

Γ(φ(f 1 , . . . , f n ), f ) = n i=1 ∂φ ∂x i (f 1 , . . . , f n ) Γ(f i , f ). (2.4)
Due to this chain rule derivation formula, the entropic inequality (2.2) rewrites in the diffusion case as the famous log-Sobolev inequality

ρ Ent µ (f 2 ) ≤ 4 E µ (f, f ), (2.5)
which is the original inequality (up to the extra factor 4) derived by Gross in [START_REF] Gross | Logarithmic Sobolev inequalities[END_REF] to study hypercontractivity of the underlying semigroup. When we will consider diffusion processes in the sequel, we will use the terminology "log-Sobolev inequality" instead of "entropic inequality". On the other hand, letting p = 2/q for q ∈ [1, 2) and f = g q , the Beckner-type inequality (2.3) rewrites as the so-called standard Beckner inequality:

α 2/q µ(g 2 ) -µ(g q ) 2/q ≤ (2 -q) E µ (g, g). (2.6)
Such an inequality was introduced by Beckner in [START_REF] Beckner | A generalized Poincaré inequality for Gaussian measures[END_REF] for the Gaussian measure. In particular, the limiting case q → 2 recovers the classical log-Sobolev inequality.

Note however that the inequality (2.6) is weaker than the log-Sobolev inequality, cf. [START_REF] Latala | Between Sobolev and Poincaré[END_REF].

Markov jump processes.

Dealing with a pure-jump Markov process, the generator L is given for any function f ∈ D 2 (L) by

Lf (x) = X (f (y) -f (x)) Q x (dy), x ∈ X ,
where the transition kernel x → Q x is a measurable mapping from X to the set of Radon measures on X endowed with the corresponding Borel σ-field. We assume that it satisfies the following stability assumption:

X Q x (dy) < ∞, x ∈ X , ( 2.7)
which entails that the process is piecewise constant. Here, reversibility means that the following detailed balance condition is satisfied:

Q x (dy) µ(dx) = Q y (dx) µ(dy). (2.8)
The carré du champ operator Γ admits an explicit expression given for any f, g

∈ D 2 (L) by Γ(f, g)(x) = 1 2 X (f (y) -f (x)) (g(y) -g(x)) Q x (dy),
and we have

Γ(f, f )(x) = 1 2 X (f (y) -f (x)) 2 Q x (dy).
In particular, the spaces Lip(X ) and Lip Γ (X ) have no reason to coincide since the kernel of the generator may be unbounded, i.e.

sup x∈X X Q x (dy) = ∞.
(2.9)

Finally the Dirichlet form rewrites for any f, g ∈ D(E µ ) as

E µ (f, g) = 1 2 X X (f (y) -f (x)) (g(y) -g(x)) Q x (dy)µ(dx) = f (x)>f (y) (f (y) -f (x)) (g(y) -g(x)) Q x (dy)µ(dx),
where in the last line the reversibility is used. In our jump framework, the entropic inequality (2.2) corresponds to one of the so-called modified log-Sobolev inequalities introduced by Bobkov and Ledoux in [START_REF] Bobkov | On modified logarithmic Sobolev inequalities for Bernoulli and Poisson measures[END_REF]. However, due to the lack of chain rule for discrete gradients, this inequality is different from the discrete version of the log-Sobolev inequality (2.5), and the same remark holds between the Beckner-type inequality (2.3) and the standard Beckner inequality (2.6). We refer to [START_REF] Diaconis | Logarithmic Sobolev inequalities for finite Markov chains[END_REF][START_REF] Bobkov | On modified logarithmic Sobolev inequalities for Bernoulli and Poisson measures[END_REF][START_REF] Bobkov | Modified logarithmic Sobolev inequalities in discrete settings[END_REF] for historical and tutorial references on these discrete functional inequalities, together with a hierarchy of the various modified log-Sobolev inequalities.

Main results

As announced, we obtain concentration properties of the invariant measure µ through observables which are not required to belong to the spaces Lip(X ) nor Lip Γ (X ), but which satisfy a Lyapunov condition. In order to state this condition properly, let us introduce first the extended domain of the generator. Denote the probability measure P ν (•) := X P x (•) ν(dx) where ν is an arbitrary initial probability distribution. A continuous function f is said to belong to the extended domain D e (L) of the generator L if there exists some measurable function g : X → R such that for any t ≥ 0, t 0 |g(X s )| ds < ∞, P µ -a.s. and the process

M f t = f (X t ) -f (X 0 ) - t 0 g(X s ) ds, t ≥ 0,
is a local P µ -martingale. In this case we write f ∈ D e (L) and Lf = g. The first result on which our analysis is based is closely related to the theory of large deviations, see for instance [START_REF] Wu | Uniformly integrable operators and large deviations for Markov processes[END_REF].

Lemma 3.1. The Donsker-Varadhan information ν → I(ν|µ) is the rate function governing the Large Deviation Principle of the empirical measure of the reversible process (X t ) t≥0 . In other words,

I(ν|µ) = sup 0<V ∈D e(L ) X - LV V dν. ( 3.1)
Remark 3.2. Actually, we will only need the following inequality, available for any positive test function V ∈ D e (L):

X - LV V dν ≤ I(ν|µ).
For instance in the diffusion case, we can prove it as follows: assume that ν has density f 2 with respect to µ (trivial otherwise). Then by the chain rule formula satisfied by the carré du champ,

X - LV V dν = X Γ V, f 2 V dµ = X 2f V Γ(V, f ) - f 2 V 2 Γ(V, V ) dµ ≤ X 2f V Γ(V, V ) Γ(f, f ) - f 2 V 2 Γ(V, V ) dµ ≤ X Γ (f, f ) dµ = I(ν|µ),
where we used Cauchy-Schwarz' inequality to obtain the first inequality, and also the elementary bound 2xy ≤ x 2 + y 2 , x, y ∈ R, to get the final result.

Now we are able to state the Lyapunov condition we will focus on along this paper. Before stating our first main result, let us provide a key lemma. In the remainder of this paper, we only give the proofs in the jump case since the diffusion framework requires no additional difficulties and is even simpler, according to the chain rule derivation formula (2.4) satisfied by the carré du champ.

Γ(f, f ) ≤ -a LV V + b. ( 3
Lemma 3.5. Let f belong to the class L V (a, b). Given λ ∈ (0, 2/ √ a)
, let µ λ be the probability measure with density f λ := e λf /Z λ with respect to µ, where Z λ is the appropriate normalization constant. We assume that √ f λ ∈ D(E µ ). Then

I(µ λ |µ) ≤ λ 2 b 4 -λ 2 a , 0 < λ < 2 √ a .
Proof. Since f ∈ L V (a, b), we have for any λ ∈ (0, 2/ √ a):

I(µ λ |µ) = 1 Z λ f (x)>f (y) e λf (x)/2 -e λf (y)/2 2 Q x (dy)µ(dx) = f (x)>f (y) 1 -e -λ(f (x)-f (y))/2 2 f λ (x) Q x (dy)µ(dx) ≤ λ 2 4 X Γ(f, f ) dµ λ ≤ λ 2 4 X -a LV V + b dµ λ ≤ λ 2 4 (aI(µ λ |µ) + b) ,
where in the last line we used lemma 3.1. Finally rearranging the terms allows us to obtain the desired inequality.

We turn now to our first main and new result which exhibits a non-Gaussian concentration estimate through observables belonging to the class L V (a, b). Due to the approach we will use, the numerical constants in the estimates below have no reason to be sharp. Theorem 3.6. Assume that the pair (µ, Γ) satisfies the entropic inequality (2.2) with optimal constant ρ 0 . Let f ∈ L V (a, b) and let

r max := 8b 3ρ 0 √ a
be the size of the Gaussian window. Then the invariant measure µ has the following concentration property: for any 0 ≤ r ≤ r max , the deviation is of Gaussian-type:

µ ({x ∈ X : f (x) -µ(f ) > r}) ≤ e -3ρ 0 r 2 16b , (3.3)
and for any r ≥ r max , the decay is exponential:

µ ({x ∈ X : f (x) -µ(f ) > r}) ≤ e -r 2 √ a , ( 3.4)
Remark 3.7. In the sequel, a concentration property such as (3.3)-(3.4) will be called Gaussian-exponential concentration.

Proof. Denote L λ := λ -1 log Z λ , where Z λ := X e λf dµ, with λ ∈ (0, 1/ √ a), and let µ λ be the absolutely continuous probability measure with density f λ := e λf /Z λ with respect to µ. Using a standard approximation procedure one may assume that the observable

f ∈ L V (a, b) is bounded so that √ f λ ∈ D(E µ ).
The following proof is a modification of the famous Herbst method popularized by Ledoux. Using the entropic inequality (2.2),

d dλ L λ = 1 λ 2 Z λ Ent µ (e λf ) ≤ 1 ρ 0 λ 2 Z λ E µ λf, e λf = 1 ρ 0 λ f (x)>f (y) (f (x) -f (y)) 1 -e -λ(f (x)-f (y)) f λ (x) Q x (dy)µ(dx) ≤ 1 ρ 0 X X Γ(f, f ) dµ λ ≤ 1 ρ 0 X -a LV V + b dµ λ ≤ 1 ρ 0 (aI(µ λ |µ) + b) ,
where we used that f ∈ L V (a, b) and then lemma 3.1 in the two last lines. Thus lemma 3.5 entails the inequality

d dλ L λ ≤ 4b 3ρ 0 , 0 < λ < 1 √ a ,
and therefore the following log-Laplace estimate is available for any 0

< λ < 1 √ a : log X e λf dµ ≤ λµ(f ) + 4bλ 2 3ρ 0 . (3.5)
Finally using Chebyshev's inequality and optimizing in λ ∈ (0, 1/ √ a) yields the tail estimates (3.3) and (3.4). The proof of theorem 3.6 is thus complete. Remark 3.8. Two deviation regimes appear, Gaussian and exponential, with continuous transition from one to the other. In contrast to the classical Herbst method where the observables belong to Lip Γ (X ), i.e. a = 0 in the Lyapunov condition (3.2), our assumption allows us to go beyond this Lipschitz property. However the price to pay is to have a finite Gaussian window, i.e. r max < ∞. Remark 3.9. By the Central Limit Theorem, the order of magnitude is correct in the Gaussian regime. Since the entropic inequality entails a Poincaré inequality, we have ρ 0 ≤ λ 1 and thus for any observable f ∈ L V (a, b), we get Var µ (f ) ≤ b/ρ 0 . Therefore, if µ = ν ⊗d is a product measure and f (x) = d k=1 φ(x k ), x := (x 1 , . . . , x d ) ∈ X , then we obtain the following inequality, which is sharp for large d:

µ x ∈ X : f (x) -µ(f ) > r √ d ≤ e -3ρ 0 r 2 16 b , 0 ≤ r ≤ 8 b√ d 3ρ 0 √ a .
Here the important point is that the positive parameter b depends on φ but is independent of d.

Remark 3.10. The method is sufficiently robust to get, for large deviation level r, other regimes than exponential under particular observables. For example, assume that we consider f ∈ L V (a, b) such that Γ(f, f ) ≪ -aLV /V + b but that there exists two functions φ, ψ : (0, ∞) → (0, ∞) such that for all ε > 0,

Γ(f, f ) ≤ φ(ε) -a LV V + b + ψ(ε).
Then plugging this estimate in the previous proofs of lemma 3.5 and theorem 3.6, one has for all ε > 0,

I(µ λ |µ) ≤ λ 2 4 (aφ(ε)I(µ λ |µ) + bφ(ε) + ψ(ε)) .
Optimizing in ε > 0 enables to get for some function Φ : [0, ∞) → [0, ∞] and all λ > 0, I(µ λ |µ) ≤ Φ(λ), leading then to super-exponential regime for large r. We will illustrate this on an example in section 4.

Inspired by Otto-Villani's method, cf. [START_REF] Otto | Generalization of an inequality by Talagrand and links with the logarithmic Sobolev inequality[END_REF][START_REF] Sammer | Aspects of mass transportation in discrete concentration inequalities[END_REF] where the links between log-Sobolev and transportation inequalities are studied on continuous and finite state spaces respectively, let us recover theorem 3.6 by using a semigroup proof. Once again we focus our attention on the jump case. Let h be a smooth density with respect to µ. Given t > 0, denote ν t the probability measure with density P t h with respect to µ. We assume that the Donsker-Varadhan information I(ν t |µ) is well-defined, i.e. √ P t h ∈ D(E µ ). Using Cauchy-Schwarz's inequality and then reversibility,

E µ (P t h, f ) = 1 2 X X (P t h(x) -P t h(y)) (f (x) -f (y)) Q x (dy)µ(dx) ≤ I(ν t |µ) 1 2 X X P t h(x) + P t h(y) 2 (f (x) -f (y)) 2 Q x (dy)µ(dx) ≤ 2 I(ν t |µ) X Γ(f, f ) dν t ≤ 2 I(ν t |µ) X -a LV V + b dν t ≤ 2 I(ν t |µ) aI(ν t |µ) + b,
where in the two last lines we used that f ∈ L V (a, b) and then lemma 3.1. Using now the elementary inequality 2(ab) 2 ≤ (a 2b 2 ) log(a/b) available for any a, b > 0 and then the entropic inequality (2.2), we get

E µ (P t h, f ) ≤ E µ (P t h, log P t h)   √ a 2 + b E µ (P t h, log P t h)   ≤ E µ (P t h, log P t h)   √ a 2 + b ρ 0 Ent µ (P t h)   .
Integrating time between 0 and infinity entails the covariance inequality:

Cov µ (f, h) := µ(f h) -µ(f ) µ(h) = ∞ 0 E µ (P t h, f ) dt ≤ ∞ 0 E µ (P t h, log P t h)   √ a 2 + b ρ 0 Ent µ (P t h)   dt = √ a 2 Ent µ (h) + 2 b Ent µ (h) ρ 0 ,
which in turn yields the inequality

α (Cov µ (f, h)) ≤ Ent µ (h),
where α is the function

α(r) = ρ 0 r 2 4b + 2ρ 0 √ a r , r > 0.
Finally using theorem 3.2 in [START_REF] Gozlan | Transport inequalities. A survey. Markov Process[END_REF], we obtain the following concentration estimate through the observable f ∈ L V (a, b): r) , r ≥ 0.

µ ({x ∈ X : f (x) -µ(f ) > r}) ≤ e -α(
One deduces that, up to numerical constants, this result is similar to that emphasized in theorem 3.6 since for small deviation level, α(r) = O(ρ 0 r 2 /b) whereas α(r) = O(r/ √ a) for large r. As we have seen above, the entropic inequality (2.2) entails on the one hand a concentration property for the invariant measure µ through observables f ∈ L V (a, b). On the other hand and as announced in remark 3.4, the Poincaré inequality can be seen as a minimal assumption in our study. Hence one may wonder if the Beckner-type inequality (2.3), which interpolates between both, provides qualitative concentration estimates through observables in L V (a, b). Our second main result, theorem 3.11, goes in this way. However, although the estimates we provide below are somewhat similar to that of theorem 3.6 in regard of the mixed Gaussian-exponential behaviour, the price to pay is to lose the good order of magnitude for the Gaussian window since we obtain

r max = O( √ b) instead of O(b).
Theorem 3.11. Assume that there exists p ∈ (1, 2] such that the pair (µ, Γ) satisfies a Beckner-type inequality (2.3) and denote α p the optimal constant. Moreover, assume that the observable f ∈ L V (a, b) with the restriction α p ≤ 2b(p -1)/(3pa) and let r max := 32bp 27(p -1)α p be the size of the Gaussian window. Then the following tail estimates hold: for any 0 ≤ r ≤ r max ,

µ ({x ∈ X : f (x) -µ(f ) > r}) ≤ e -9αp r 2 32b , ( 3.6)
whereas for any r ≥ r max ,

µ ({x ∈ X : f (x) -µ(f ) > r}) ≤ e -r 3pαp 32b(p-1) . (3.7)
Proof. The proof is adapted from the method of Aida and Stroock introduced in [START_REF] Aida | Moment estimates derived from Poincaré and logarithmic Sobolev inequalities[END_REF]. Assume without loss of generality that f is centered and bounded and for any λ ∈ (0, λ 0 ), where

λ 0 := 3pα p 2b(p -1) ≤ 1 √ a ,
denote once again Z λ := X e λf dµ and µ λ the probability measure with density f λ := e λf /Z λ with respect to µ. We have by the Beckner-type inequality (2.3) applied to the function e λf /p ,

Z λ -Z p λ/p ≤ p 2α p E µ (e λf /p , e λ(1-1/p)f ) = p 2α p f (x)>f (y) e λf (x) 1 -e -λ(f (x)-f (y))/p 1 -e -λ(1-1/p)(f (x)-f (y)) Q x (dy)µ(dx) ≤ λ 2 (p -1)Z λ 2pα p X Γ(f, f ) dµ λ ≤ λ 2 (p -1)Z λ 2pα p X -a LV V + b dµ λ ≤ λ 2 (p -1)Z λ 2pα p (aI(µ λ |µ) + b) ≤ λ λ 0 2 Z λ ,
where we used that f ∈ L V (a, b) and lemmas 3.1-3.5 in the three last lines. Hence rearranging the terms above and iterating the procedure yields for every n ≥ 1,

Z λ ≤ n-1 k=0 λ 2 0 λ 2 0 -λ 2 /p 2k p k (Z λ/p n ) p n .
Since f is centered, the quantity Z p n λ/p n goes to 1 as n → ∞ and from the latter we obtain after taking logarithm,

log Z λ ≤ - ∞ k=0 p k log 1 - (λ/λ 0 ) 2 p 2k = ∞ k=0 p 2k+1 p 2k+1 -1 × (λ/λ 0 ) 2(k+1) k + 1 ≤ - p p -1 log   1 - λ λ 0 2   .
In the last inequality we used the trivial inequality p 2k+1 ≤ ( p p-1 ) (p 2k+1 -1) available for any integer k because p ∈ (1, 2]. We thus obtain for any 0

< λ ≤ λ 0 /2, Z λ ≤ 1 + λ 2 λ 2 0 -λ 2 p/(p-1) ≤ exp pλ 2 (p -1)(λ 2 0 -λ 2 ) ≤ exp 4pλ 2 3(p -1)λ 2 0 .
Finally using the exponential Chebyshev inequality entails the desired result.

Remark 3.12. The assumption relying α p to the parameters a and b is a technical detail but cannot be avoided. However it will be always satisfied as soon as b is taken sufficiently large (or a small enough). Remark 3.13. As already mentioned, the Beckner-type inequality is stronger than the Poincaré inequality, i.e. α p ≤ λ 1 . However, theorem 3.11 does not entail a better concentration estimate than that obtained under the Poincaré inequality, except maybe when focusing on the constants depending on p (this is clearly not our interest here). The reason is due to the approach emphasized above which is exactly the same for any p ∈ (1, 2], in contrast to theorem 3.6 where the Herbst method is used.

Examples

Diffusion processes.

Let us apply now theorems 3.6 and 3.11 to diffusion processes. Below, the function U is a smooth potential such that e -U is Lebesgue integrable, and denote µ the Boltzmann probability measure with density e -U /Z with respect to the Lebesgue measure, where Z is the normalization factor.

The first example of interest is the so-called Kolmogorov process with generator given for any C 2 function f : R d → R with bounded derivatives by

Lf = ∆f -< ∇U, ∇f > .
One easily checks that µ is reversible for this process and the carré du champ is Γ(f, f ) = ∇f 2 where • stands for the Euclidean norm in R d . Hence by Rademacher's theorem, the spaces Lip(X ) and Lip Γ (X ) coincide. Moreover the domain D(E µ ) of the Dirichlet form is H 1 (µ).

Ornstein-Uhlenbeck process and the standard Gaussian distribution.

Let us consider first the case of the Ornstein-Uhlenbeck process which has the standard Gaussian distribution as invariant measure. Here the potential is given by U(x) = x 2 /2. By the famous Gross theorem [START_REF] Gross | Logarithmic Sobolev inequalities[END_REF], the pair (µ, Γ) satisfies the log-Sobolev inequality, i.e. the entropic inequality with (optimal) constant ρ 0 = 2. Hence theorem 3.6 will apply for observables in L V (a, b) for some good test function V . For instance if f (x) = x 2 , then choose the positive test function V = e cU with c ∈ (0, 1), i.e. V is at the boundary of non-integrability. Then we have

- LV (x) V (x) = -cd + c(1 -c) x 2 .
Thus with the choice c = 1/2 we get f ∈ L V (a, b) with a = 16 and b = 8d and by theorem 3.6, for any 0 ≤ r ≤ 8d/3,

µ {x ∈ R d : x 2 > d + r} ≤ e -3r 2 64d ,
which is sharp up to a numerical constant since in this case Var µ (f ) = 2d. In the exponential regime we get for any r ≥ 8d/3,

µ {x ∈ R d : x 2 > d + r} ≤ e -r 8 .
Actually, such a behaviour is expected since under µ, the variable f (x) is χ 2 (d)distributed, i.e. distributed as a chi-squared random variable with d degrees of freedom.

Let us come back to the example announced in remark 3.10. As observed above, our concentration result is convenient as soon as f is close to realize the equality in the Lyapunov condition (3.2). However what happens for a function g such that ∇g ≪ ∇f at infinity ? For instance if f (x) = x 2 as above then how concentrates the invariant measure through the observable g(x) = x 3/2 ? Let us investigate this point in detail now. Assume that there exists an observable g satisfying for any ε > 0,

∇g 2 ≤ ε ∇f 2 + 1 ε ≤ -a ε LV V + b ε ,
where a ε := aε and b ε := bε + 1/ε. Using the argument given in the proof of lemma 3.5, we have for any λ > 0,

I(µ λ |µ) ≤ inf ε>0 λ 2 4 (a ε I(µ λ |µ) + b ε ) = λ 2 2 aI(µ λ |µ) + b,
where in the definition of I(µ λ |µ) we replaced f by g. Hence we obtain

I(µ λ |µ) ≤ λ 2 2 aλ 2 2 + √ b .
Now the same argument as in the proof of theorem 3.6 together with the latter inequality entail

d dλ L λ ≤ inf ε>0 1 ρ 0 (a ε I(µ λ |µ) + b ε ) = 2 ρ 0 aI(µ λ |µ) + b ≤ 2 ρ 0 aλ 2 2 + √ b ,
since x(x + y) + y 2 ≤ x + y for any x, y ≥ 0. Hence we get for any λ > 0, log

X e λg dµ ≤ λµ(g) + 2 ρ 0 aλ 4 6 + λ 2 √ b .
Finally, a bit more of analysis shows that the decay in the concentration estimate is of order e -cr 4/3 for large deviation level r, which is of the good order of magnitude when choosing for instance g(x) to be proportional to x 3/2 . Now take the observable f as a quadratic form on R d , i.e. there exists a positive definite symmetric matrix A = (a i,j ) i,j=1,...,d of size d such f (x) =< Ax, x >, x ∈ R d . Then in the Gaussian regime we should obtain the variance of f in the denominator,

Var µ (f ) = 2 d i,j=1 a 2 i,j .
However theorem 3.6 does not yield such a result, unfortunately. For instance using the same test function V as before would entail that f ∈ L V (a, b) with a = 16 A 2 op and b = 8d A 2 op , where A op is the (Euclidean) operator norm of the matrix A, i.e. its spectral radius. With this choice of parameters the inequality Var µ (f ) ≤ b/ρ 0 is too weak to provide a reasonable variance estimate since b behaves badly in terms of dimension. To circumvent this difficulty, we choose V = e cf with c = 1/(4 A op ), so that V is positive and still integrable with respect to the Gaussian measure µ. We thus obtain that f ∈ L V (a, b) with the same a as before, but now with the improved variance estimate b = 2ac trace(A) = 8 trace(A) A op , where trace(A) is the trace of the matrix A. Therefore applying theorem 3.6 entails a tail estimate whose behaviour has been improved with respect to the dimension. This example emphasizes the inherent importance of the choice of the function V in the condition L V (a, b). See also for instance [START_REF] Hanson | A bound on tail probabilities for quadratic forms in independent random variables[END_REF][START_REF] Latala | Estimates of moments and tails of Gaussian chaoses[END_REF] for some nice studies on the concentration properties of Gaussian-like quadratic forms and Gaussian chaoses. 4.1.2. Kolmogorov process and the Boltzmann invariant measure. This class is a natural generalization of the Ornstein-Uhlenbeck process. To begin, assume that the measure µ is spherically log-concave, i.e. there exists a C 2 function φ : R → R convex and non-decreasing such that U(x) = φ( x ) for any x ∈ R d . By a famous result of Bobkov [START_REF] Bobkov | Spectral gap and concentration for some spherically symmetric probability measures[END_REF], the dynamics (µ, Γ) satisfy (at least) a Poincaré inequality. Let us consider the potential U as an observable and also the positive test function V = e cU , which belongs to L 1 (µ) for any c ∈ (0, 1) since φ is convex. Assume that there exists r > 0 and

M = M(r) ∈ (0, 1 -c) such that ∆U(x) ∇U(x) 2 = (d -1) φ ′ ( x ) + x φ ′′ ( x ) x φ ′ ( x ) 2 ≤ M, x ≥ r.
Since we have

- LV (x) V (x) = -c ∆U(x) + c(1 -c) ∇U(x) 2 = -c(d -1) φ ′ ( x ) x -c φ ′′ ( x ) + c(1 -c) φ ′ ( x ) 2 ,
one deduces that U belongs to the class L V (a, b) with a = 1/c(1c -M), the parameter b = b(r) being chosen conveniently on B r , the centered ball of radius r in R d , i.e. b is the maximum between 3aλ 1 and

a LV V + ∇U 2 1 Br L ∞ (µ)
.

As a result, one can apply theorem 3.11 to obtain a Gaussian-exponential concentration estimate through the observable U. See also the recent work of Bobkov and Madiman [START_REF] Bobkov | Concentration of the information in data with log-concave distributions[END_REF] where a somewhat similar tail estimate is established via a different approach.

Actually, spherically log-concave probability measures include the case of a potential U such that U(x) = x β with β ≥ 1. Since the case β = 2 has already been considered, three different situations arise:

(i) the case β = 1, for which only the Poincaré inequality is satisfied.

(ii) the case β ∈ (1, 2): the standard Beckner inequality holds, cf. [START_REF] Latala | Between Sobolev and Poincaré[END_REF].

(iii) the case β > 2: using Wang's criterion [START_REF] Wang | Logarithmic Sobolev inequalities on noncompact Riemannian manifolds[END_REF], the log-Sobolev inequality is then verified.

In these three cases, one may choose the following parameters: One may also extend the result to the non symmetrically invariant case, when for example a logarithmic Sobolev inequality holds. Let us assume for example that the potential U is such that its Hessian matrix, denoted Hess U, is lower bounded and that the following Lyapunov condition holds:

c := 1 2 , M := 1
LV (x) ≤ -c 1 x 2 + c 2 V (x), x ∈ R d ,
where c 1 , c 2 > 0 and V is a C 2 positive test function. Then a logarithmic Sobolev inequality holds, cf. [START_REF] Cattiaux | A note on Talagrand transportation inequality and logarithmic Sobolev inequality[END_REF], and one can apply theorem 3.6 for observables f such that the norm of ∇f (x) is at most x at infinity, since in this case f ∈ L V (a, b) with a = 1/c 1 and b = c 2 /c 1 . For instance, the Lyapunov condition above will be verified if at least one of the two conditions below is satisfied: there exist α ∈ (0, 1) and β > 0 such that for sufficiently large x,

(1 -α) ∇U(x) 2 -∆U(x) ≥ β x 2 or < x, ∇U(x) > ≥ β x 2 .
4.1.3. Log-Sobolev inequality for modified dynamics. Our last example concerns the case where a log-Sobolev inequality holds for a slightly modified dynamics, but with the same Boltzmann invariant measure. In a sense, it corresponds to a modified (or weighted) log-Sobolev inequality. Consider the process with the following generator:

L σ 2 f := σ 2 ∆f + < ∇(σ 2 ) -σ 2 ∇U, ∇f >,
where σ is some measurable and locally bounded function from R d to R. Once again the measure µ is reversible for this process, but the notable difference relies on the weight σ 2 in the carré du champ, i.e. Γ σ 2 (f, f ) := σ 2 ∇f 2 , so that a Lipschitz function f may have an unbounded carré du champ Γ σ 2 (f, f ), in contrast to the Kolmogorov example studied above. In particular, the domain of the Dirichlet form is a weighted H 1 space, i.e.

D(E

µ ) := f ∈ L 2 (µ) : R d σ 2 ∇f 2 dµ < ∞ .
We will focus mainly here on the simple case U(x) := x α for 1 < α < 2, so that the standard Beckner inequality (thus the Poincaré inequality) holds for the classical dynamics (µ, Γ), but not a log-Sobolev inequality. On the one hand, according to a result of Latala and Oleszkiewicz [START_REF] Latala | Between Sobolev and Poincaré[END_REF], the measure µ concentrate like e -r α for large deviation level r through Lipschitz observables. On the other hand, the following weighted log-Sobolev inequality holds:

Ent µ (f 2 ) ≤ C R d 1 + x 2-α ∇f (x) 2 µ(dx),
where C > 0 is some constant depending on dimension d, cf. [START_REF] Cattiaux | Some remarks on weighted logarithmic Sobolev inequality[END_REF]. Letting the weight function σ(x) 2 := 1 + x 2-α , one observes that this weighted inequality rewrites as the log-Sobolev inequality for the new dynamics (µ, Γ σ 2 ). Choosing the positive test function V (x) = e c x α , which belongs to L 1 (µ) for any c ∈ (0, 1), we have for any x outside a neighborhood of 0,

- L σ 2 V (x) V (x) = -cα(d + α -2) (1 + x 2-α ) x α-2 + α 2 c(1 -c)(1 + x 2-α ) x 2(α-1) -cα(2 -α),
which behaves like α 2 c(1c) x α at infinity. Hence using the same reasoning as in the case of the Kolmogorov process above, one deduces that observables f having a gradient ∇f (x) controlled by x α-1 for large x satisfy theorem 3.6 (the observable f (x) = x α belongs to this class, as expected according to [START_REF] Latala | Between Sobolev and Poincaré[END_REF]). We point out that our results might be made more precise by following the approach provided in remark 3.10. To that aim, one has to consider the functional inequality I µ (a) involved in Latala and Oleszkiewicz's work [START_REF] Latala | Between Sobolev and Poincaré[END_REF], which is more general than the standard Beckner inequality emphasized above.

In fact using the modified dynamics (µ, Γ σ 2 ), one can even consider interesting cases for which even the Poincaré inequality does not hold for the original dynamics (µ, Γ). For instance consider the generalized Cauchy measure µ with density proportional to (1 + x 2 ) -β , where the condition β > d/2 holds to ensure integrability at infinity. Such a measure satisfies both a weighted Poincaré inequality:

Var µ (f ) ≤ C R d 1 + x 2 ∇f (x) 2 µ(dx), (4.1)
with the slight restriction β ≥ d, cf. [START_REF] Bobkov | Weighted Poincaré-type inequalities for Cauchy and other convex measures[END_REF], and also a weighted log-Sobolev inequality according to [START_REF] Cattiaux | Some remarks on weighted logarithmic Sobolev inequality[END_REF]:

Ent µ (f 2 ) ≤ C R d 1 + x 2 log e + x 2 ∇f (x) 2 µ(dx), (4.2)
without further restriction on β. Here C and C are some positive constants depending on β and d. Letting the weights

σ 1 (x) 2 := 1 + x 2 and σ 2 (x) 2 := 1 + x 2 log e + x 2 ,
then the weighted inequalities (4.1) and (4.2) rewrite as the Poincaré and the log-Sobolev inequality for the dynamics (µ, Γ σ 2 1 ) and (µ, Γ σ 2 2 ), respectively. Now let V (x) = x k for some 0 < k < 2βd, so that the positive test function V lies in L 1 (µ). Then we have for any x outside a neighborhood of 0,

- L σ 2 1 V (x) V (x) = -k(d + k -2) 1 + x 2 x 2 + 2k(β -1),
and also

- L σ 2 2 V (x) V (x) = -k(d + k -2) 1 + x 2 x 2 log e + x 2 - 2k (1 + x 2 ) e + x 2 +2k(β -1) log e + x 2 .
The first quantity is constant at infinity whereas the second one is of order k(2βdk) log (e + x 2 ) for large x . Then we obtain by theorems 3.6 and 3.11 an exponential concentration estimate for large deviation level r through observables f having their gradient ∇f (x) dominated in both cases by 1/ x for large x.

Hence the previous example shows that weighted Poincaré and log-Sobolev inequalities (of course with a different weight) can lead to somewhat similar concentration estimates. Note that the function f (x) = log ( x ) belongs to this class of observables, leading to the well-known heavy tail phenomenon satisfied by Cauchy-type measures, cf. [START_REF] Bobkov | Weighted Poincaré-type inequalities for Cauchy and other convex measures[END_REF]. Finally, we mention that one can take profit of remark 3.10 to get intermediate concentration regime for observables not saturating the Lyapunov condition.

4.2. Birth-death processes. Let us begin the study of jump processes by considering a simple but however non trivial example, namely birth-death processes.

Here (X t ) t≥0 is a Markov process on the state space N := {0, 1, 2, . . .} endowed with the classical metric d(x, y) = |x -y|, x, y ∈ N. The transition probabilities are given by

P x (X t = y) =        λ x t + o(t) if y = x + 1, ν x t + o(t) if y = x -1, 1 -(λ x + ν x )t + o(t) if y = x,
where lim t→0 t -1 o(t) = 0. The transition rates λ and ν are respectively called the birth and death rates and satisfy to λ > 0 on N and ν > 0 on N * := {1, 2, . . .} and ν 0 = 0, so that the process is irreducible. Although we assume that the stability condition (2.7), which rewrites as

λ x + ν x < ∞, x ∈ N,
is satisfied, the generator might be unbounded in the sense of (2.9), i.e.

sup x∈N λ x + ν x = ∞.
The process is positive recurrent and non-explosive when the rates satisfy to

∞ x=1 λ 0 λ 1 • • • λ x-1 ν 1 ν 2 • • • ν x < ∞ and ∞ x=1 1 λ x + ν x λ x λ x-1 + • • • + ν x • • • ν 1 λ x • • • λ 1 λ 0 = ∞,
respectively. In this case the detailed balance condition (2.8) rewrites as

λ x µ({x}) = ν x+1 µ({x + 1}), x ∈ N,
where µ is the unique stationary distribution of the process given by µ({x}) = µ({0})

x y=1 λ y-1 ν y , x ∈ N, (4.3)
µ({0}) being the normalization constant. In the situations of interest, the death rate ν has to be bigger than λ to ensure such criteria. For any function f : N → R, the generator L of the process is given by

Lf (x) = λ x (f (x + 1) -f (x)) + ν x (f (x -1) -f (x)) , x ∈ N,
and the carré du champ is

Γ(f, f )(x) = 1 2 λ x (f (x + 1) -f (x)) 2 + ν x (f (x -1) -f (x)) 2 , x ∈ N.
In particular, the Dirichlet form is given by

E µ (f, g) := x∈N λ x (f (x + 1) -f (x)) (g(x + 1) -g(x)) µ({x}),
where f, g belong to the space D(E µ ) of functions u : N → R such that E µ (u, u) is finite.

On the one hand Joulin [START_REF] Joulin | Poisson-type deviation inequalities for curved continuous-time Markov chains[END_REF] gives, under some convenient ergodic assumptions, concentration estimates of Poisson-type through observables belonging to the space Lip(N). In particular, his proof requires the inclusion Lip(N) ⊂ Lip Γ (N), enforcing the rates λ and ν to be bounded. On the other hand, when we apply Ollivier's result [START_REF] Ollivier | Ricci curvature of Markov chains on metric spaces[END_REF] to birth-death processes, his Gaussian-exponential concentration property is available for observables f ∈ Lip(N) such that Γ(f, f ) ∈ Lip(N). It induces that λ, ν ∈ Lip(N), extending Joulin's result from bounded to (at most) linear rates. As announced in the introduction through the study of a specific example, theorems 3.6 and 3.11 entail Gaussian-exponential concentration estimates beyond these cases since the carré du champ Γ(f, f ) is allowed to have a growth comparable to that of ν.

First let us provide some basic conditions which ensure an entropic or Poincaré inequality. The following necessary (but not sufficient) condition is due to Caputo, DaiPra and Posta [START_REF] Caputo | Convex entropy decay via the Bochner-Bakry-Émery approach[END_REF] and has been recently recovered by Chafaï and Joulin [START_REF] Chafaï | Intertwining and commutation relations for birth-death processes[END_REF] by using a semigroup approach: if λ is non-increasing and ν is non-decreasing and there exists α > 0 such that

inf x∈N λ x -λ x+1 + ν x+1 -ν x ≥ α, ( 4.4)
then the entropic inequality (2.2) is satisfied with constant α, or equivalently ρ 0 ≥ α. Such an assumption exhibits very asymmetric rates. More precisely, it enforces the rates λ and ν to be bounded and super-linear, respectively, excluding some interesting cases which can be however considered for the Poincaré inequality. Indeed, Miclo [START_REF] Miclo | An example of application of discrete Hardy' s inequalities. Markov Process[END_REF] states that the spectral gap λ 1 is positive if and only if

δ := sup x≥1 x-1 k=0 1 λ k µ({k}) l≥x µ({l}) < ∞, (4.5)
and in this case we have 1/δ ≥ λ 1 ≥ 1/4δ, i.e. λ 1 is of order 1/δ. In particular, in contrast to the entropic inequality, one may find examples satisfying the Poincaré inequality with an unbounded birth rate λ. Now assume that the positive test function V (x) := κ x is in L 1 (µ) for some constant κ > 1 depending on λ, ν. Then an observable f belongs to L V (a, b) if and only if

Γ(f, f ) ≤ a(κ -1) κ (ν -κ λ) + b,
showing that on a large scale the behaviour of Γ(f, f ) is controlled by the growth of the death rate ν. To compare with the results of Joulin and Ollivier mentioned previously, assume that the observable f ∈ Lip(N). Then two extreme situations may appear when the death rate ν is unbounded: (i) a small birth rate λ, i.e. λ is bounded. In this case one may choose the following parameters to ensure that f ∈ L V (a, b):

a := κ 2(κ -1) and b := (1 + κ) λ L ∞ (µ) 2 .
(ii) a birth rate λ of the order of ν. Let x 0 ∈ N * and assume that λ x ≤ cν x for all x ≥ x 0 , where c ∈ (0, 1) is some parameter. Then in order to get f ∈ L V (a, b), one can choose for κ ∈ (1, 1/c),

a := κ(1 + c) 2(1 -cκ)(κ -1)
,

and b := λ + ν 2 + a LV V 1 [0,x 0 ] L ∞ (µ) = 1 + κ 2(1 -cκ) (λ -cν) 1 [0,x 0 ] L ∞ (µ) .
For instance the choice of κ := 1/ √ c entails the integrability of V and then we obtain

a = 1 + √ c 2(1 - √ c) and b = 1 + √ c 2 √ c(1 - √ c) (λ -cν) 1 [0,x 0 ] L ∞ (µ) .
Of course b has also to be at least 3aλ 1 if only the Poincaré inequality is satisfied. In both cases (i) and (ii) there exist plenty of examples satisfying Poincaré inequality and thus theorem 3.11, whereas only the case (i) may satisfy the entropic inequality and so theorem 3.6. In particular, the example emphasized in the introduction is a prototype of such a situation. Indeed denote µ p the geometric distribution on N of parameter p ∈ (0, 1), i.e. µ p ({x}) := (1p)p x , x ∈ N, and let us consider the carré du champ

Γ (n) (f, f )(x) := 1 2 p(x + 1) n (f (x + 1) -f (x)) 2 + x n 1 {x =0} (f (x -1) -f (x)) 2 ,
where x ∈ N and n ∈ N is some fixed parameter. The measure µ p is reversible with respect to these dynamics and by comparing the underlying Dirichlet form with that given in the case n = 0 (for which λ ≥ (1p) 2 /4). Hence for sufficiently large integer x 0 one can pick c = (1 + p) 2 /4 ∈ (0, 1), κ = 2/(1 + p) and for some integer x 1 ∈ (0, x 0 ),

a = 3 + p 2(1 -p) and b = max 3 + p 4(1 -p) 2 4p(x 1 + 1) n -(1 + p) 2 x n 1 , 3aλ (n) 1
.

To achieve the birth-death example, let us focus our attention on a model which mimics the diffusion case, namely ultra log-concave distributions on N, see for instance [START_REF] Johnson | Log-concavity and the maximum entropy property of the Poisson distribution[END_REF][START_REF] Caputo | Convex entropy decay via the Bochner-Bakry-Émery approach[END_REF]. We say that a probability measure µ on N is ultra log-concave (resp. log-concave) if it satisfies for any x ∈ N * ,

x µ({x}) 2 ≥ (x+1) µ({x+1}) µ({x-1}) (resp. µ({x}) 2 ≥ µ({x+1}) µ({x-1})).
For instance the Poisson distribution is ultra log concave whereas the geometric measure is only log-concave. Assume that the measure µ has density e -U /Z with respect to the counting measure on N, where U is some nice function and Z is the normalization constant. Denote ∆U the discrete Laplacian of the potential U, i.e.

∆U(x) :=

U(x + 1) -2U(x) + U(x -1), x ∈ N * .
Then µ is ultra log-concave (resp. log-concave) if and only if ∆U(x) ≥ log(1+1/x) for any integer x ∈ N * (resp. ∆U is non-negative). From a dynamical point of view, measure µ is the stationary distribution of the birth-death process with rates

λ x = 1 and ν x = e U (x)-U (x-1) 1 {x =0} , x ∈ N.
Then under the ultra log-concavity assumption, we have for any integer x ≥ 2,

λ x -λ x+1 + ν x+1 -ν x = e ∆U (x) -1 e x-1 k=1 ∆U (k)+U (1)-U (0) ≥ x-1 k=1 1 + 1 k e U (1)-U (0) x = e U (1)-U (0) = ν 1 ,
so that (4.4) is satisfied with α = ν 1 (the cases x ∈ {0, 1} being straightforward).

Thus the entropic inequality holds with constant ρ 0 ≥ ν 1 . In particular, the superlinearity of the death rate ν entails that the potential U has a growth at infinity at least x log(x), showing that the tail behaviour of µ can be compared to that of a Poisson distribution. Finally, note that the log-concavity assumption only is not sufficient to ensure an entropic inequality since one obtains in this case e U (k)-U (l) < ∞.

4.3.

Glauber dynamics for unbounded particles. We consider the situation where X is the unbounded configuration space N Λ , where Λ is a bounded subset of Z d . For each site x ∈ Λ, denote η x the number of particles located at x. Given a bounded function λ : Z d → [0, ∞), let π be the Poisson measure on N Λ with parameter λ, that is to say

π({η}) = x∈Λ e -λ(x) λ(x) ηx η x ! , η ∈ N Λ .
We equip N Λ with the total variation distance which counts the number of different particles. In other words, if η and η are two configurations in N Λ , then the total variation distance is given by d(η, η) :

= x∈Λ |η x -ηx |.
Our definition is a straightforward generalization of the classical notion of total variation distance between probability measures, since it coincides with the usual definition when the configurations are normalized by their total masses. For any f : N Λ → R, the discrete gradient operators are defined by Then the Gibbs measure µ at inverse temperature β > 0 is the probability measure on N Λ given by

µ({η}) = 1 Z e -β H(η) π({η}),
where Z is the normalization constant. As observed below, our study is based on the configuration space N Λ since our model exhibits free boundary condition, that is to say Λ is, in some sense, disconnected from the lattice Z d . However the aforementioned model might be extended outside Λ by introducing an appropriate boundary condition. Now, let us introduce the Glauber dynamics associated to the Gibbs measure above, which can be seen as a spatial birth-death process, cf. [START_REF] Preston | Spatial birth-and-death processes[END_REF]. If η is the configuration of the system at time t, then a particle appears or disappears at site x ∈ Λ with rates λ(x) e -βD +

x H(η) dt and dt, respectively. In particular, the case H = 0 corresponds to the non-interacting case. The generator L is thus of birth-death type and defined for any function f : N Λ → R by

L(η) := x∈Λ c -(η, x) D - x f (η) + c + (η, x) D + x f (η) , η ∈ N Λ ,
where the rates of the dynamics c + and c -are given by c + (η, x) = λ(x) e -βD + x H(η) = λ(x) e -β y∈Λ φ(x-y) ηy ; c -(η, x) = η x .

In particular, the stability condition (2.7) is clearly satisfied since Λ is finite and moreover, according to the detailed balance condition (2.8) which in our context rewrites as c ± (η, x) µ({η}) = c ∓ (η ± δ x , x) µ({η ± δ x }), η x > 0, (η, x) ∈ N Λ × Λ, the Gibbs measure µ is reversible for these dynamics. Finally, the carré du champ of an observable f is given by

Γ(f, f )(η) = 1 2 x∈Λ c -(η, x) |D - x f (η)| 2 + c + (η, x) |D + x f (η)| 2 , η ∈ N Λ .
Recently, the problem of finding the speed of convergence to equilibrium of this model has been addressed in several articles, cf. for instance [START_REF] Bertini | The spectral gap for a Glauber-type dynamics in a continuous gas[END_REF] or [START_REF] Wu | Estimate of spectral gap for continuous gas[END_REF] for a spectral method (i.e. related to Poincaré inequality) in the continuum R d , and also [START_REF] Dai Pra | Entropy inequalities for unbounded spin systems[END_REF] for an approach through the entropic inequality. In all these papers, the objective is to find constants which are independent of Λ and of the boundary condition. In a recent work [19], Dai Pra and Posta established the entropic inequality with constant ρ 0 ≥ 1λ ∞ ε(β), under the following Dobrushin-type uniqueness condition:

ε(β) := x∈Z d 1 -e -βφ(x) < 1 λ ∞ . ( 4.6)
Here • ∞ denotes the supremum norm of a bounded function on Z d . Note that assumption (4.6) will be verified as soon as β is small enough, i.e. the temperature of the system is sufficiently high. Therefore, if we choose for some κ > In particular if λ is assumed to be summable on Z d , then b no longer depends on the box Λ.

Definition 3 . 3 .

 33 Let a, b be two positive constants and let V ∈ D e (L) be a positive test function. A function f ∈ D 2 (L) belongs to the class L V (a, b) if the following inequality is satisfied µa.s.:

4

 4 , a := 8 and r := 4 1/β d + β -2 β 1/β , provided the restriction d + β -2 > 0 holds. Finally, if β > 2 then the parameter b can be easily chosen, in contrast to the case β ∈ [1, 2) for which U is not C 2 at 0. Therefore, to obtain a convenient constant b in this non-smooth situation, one can choose a test function V = e c Ũ where Ũ is C 2 on R d and U = Ũ outside the ball B r . Then the proof above remains valid with Ũ instead of U and an easy perturbation argument entails the standard Beckner inequality (or the Poincaré inequality in the case β = 1) for the Boltzmann probability measure defined with respect to the potential Ũ .

) 1 ≥ ( 1 - √ p) 2 (

 112 2 , cf.[START_REF] Chen | Estimation of spectral gap for Markov chains[END_REF][START_REF] Joulin | Functional inequalities for discrete gradients and applications to the geometric distribution[END_REF]), the dynamics (µ p , Γ (n) ) satisfies a Poincaré inequality with optimal constant λ (nMiclo's result (4.5) would only entail λ (n) 1

  inf x∈N λ xλ x+1 + ν x+1ν x ≥ 0.However, as in the diffusion case, one may find examples of log-concave distributions on N satisfying the Poincaré inequality by using Miclo's condition (4.5), which simply rewrites as sup x∈N * 0≤k≤x-1<l

  D + x f (η) := f (η + δ x )f (η), D - x f (η) := f (ηδ x )f (η), η ∈ N Λ, where δ x is the Dirac mass at point x ∈ Λ and by convention D -x f (∅) := 0. Note that by[START_REF] Decreusefond | Upper bounds on Rubinstein distances on configuration spaces and applications[END_REF], a given function f belongs to the space Lip(N Λ ) if and only if sup(η,x)∈N Λ ×Λ |D + x f (η)| < ∞. Now let φ : Z d → [0, ∞)be an even function, null at the origin and summable on Z d , i.e. satisfying x∈Z d φ(x) < ∞. We define the Hamiltonian H : N Λ → R + as H(η) := 1 2 x,y∈Λ φ(xy) η x η y .

  1 the test function V (η) := κ x∈Λ ηx which is in L 1 (µ), then an observable f belongs to the class L V (a, b) if and only ifΓ(f, f )(η) ≤ a(κ -1) κ x∈Λ η xκ λ(x) e -βD + x H(η) + b, η ∈ N Λ ,as in the context of birth-death processes above. Thus the Gaussian-exponential concentration estimate of theorem 3.6 applies under these observables. Finally, we have D + x H(η) ≥ 0 because φ is non-negative and if f ∈ Lip(N Λ ) then one may choose

  The Poincaré inequality can be seen as a minimal assumption in our study of concentration by means of the Lyapunov condition (3.2). Indeed, if there exists a function f ∈ D 2 (L) such that Γ(f, f ) is lower bounded by a positive constant at infinity, and this the case in the main examples of interest (except in the Cauchy-like case appearing in section 4), then the Poincaré inequality is

	.2)
	Remark 3.4.

satisfied, cf.

[START_REF] Cattiaux | Poincaré inequalities and hitting times[END_REF]

. Moreover, integrating with respect to µ entails that f ∈ D(E µ ) and by Poincaré inequality we have Var µ (f ) ≤ b/λ 1 . In other words the constant b/λ 1 can be interpreted in the sequel as a variance term of the observable f .

Acknowledgments. The authors are grateful to Paolo Dai Pra and G. Posta for useful discussions about the statistical mechanics part. They thank also the ANR Project EVOL for financial support.


Aline Roumy

Vincent Roca

Bessem Sayadi

Memory Consumption Analysis for the GOE and PET Unequal Erasure Protection Schemes

. These two solutions have the main benefit of being compatible with existing standardized Application Layer FEC (AL-FEC) schemes, which is a major practical benefit.

. However additional key differences become apparent when considering such a practical metric as the peak memory consumption. Thanks to a modeling of the packet storage behavior at the receiver side, and by considering two major parameters, namely the channel loss probability and the permutation type, we show that the PET scheme is equivalent to the average uniformly permuted GOE scheme. We also show that, when no permutation is used, GOE allows to further reduce the peak memory with respect to PET.

I. INTRODUCTION

Unequal Erasure Protection (UEP) is an attractive approach to protect data flows that contain information of different priority levels. The various solutions that have been proposed can be classified into three families. The first one consists of specific, UEP-aware FEC codes, that map the information dependency within the code structure. It enables to design a specific solution, valid for a specific data flow, as in [START_REF] Bouabdallah | Dependency-aware unequal erasure protection codes[END_REF]. However, because this is a specific solution, its practical interest is also narrowed.

In this work, we focus on two additional solution families. One family implements UEP thanks to a dedicated packetization scheme, as it is the case with Priority Encoding Transmission (PET) [START_REF] Albanese | Priority encoding transmission[END_REF], while the other family uses a dedicated signaling scheme, as is the case with the Generalized Object Encoding (GOE) [START_REF] Roca | The Generalized Object Encoding (GOE) Approach for the Forward Erasure Correction (FEC) Protection of Objects and its Application to Reed-Solomon Codes over GF(2x)[END_REF]. These two solutions have the main benefit of being compatible with existing standardized Application Layer FEC (AL-FEC) schemes, which is a major practical benefit.

The PET scheme is an elegant solution. However this is also a complex scheme. It features many constraints that make its use in practical systems difficult as we have shown in [START_REF] Roumy | Unequal Erasure Protection and Object Bundle Protection with the Generalized Object Encoding Approach[END_REF]. On the opposite GOE is based on a simple solution that consists in encoding each priority class with an appropriate code rate. From a practical point of view, GOE defines an UEP-aware signaling mechanism that creates a mapping between the original object, composed of several priority classes, and the so-called "Generalized Objects" (GO) that correspond to each priority class. FEC encoding is performed independently for each GO. We have demonstrated in [START_REF] Roumy | Unequal Erasure Protection and Object Bundle Protection with the Generalized Object Encoding Approach[END_REF] that GOE provides the same UEP protection as PET, while being simple to understand, implement and use in practical systems.

The goal of this paper is to focus on one key practical aspect, namely the peak memory requirements during the decoding process (receiver), a topic that was missing in our previous work [START_REF] Roumy | Unequal Erasure Protection and Object Bundle Protection with the Generalized Object Encoding Approach[END_REF]. This metric can be of high importance for UEP deployments on lightweight terminals (e.g. smartphones), with limited processing and storage capabilities. Thanks to a careful analytical modeling of PET and GOE, we show in particular that GOE without permutation largely outperforms PET from this point of view.

In Section II we shall present the two implementations of the UEP scheme, namely PET and GOE. We shall compare the coding metrics of the two schemes (number of coded packets, coding rate, amount of uncoded and coded data, ...). This gives a basis for comparing the peak memory usage at the decoder for both schemes. Then, Section III analyzes the memory requirements of the PET scheme as a function of time. This allows to derive the peak memory usage as a function of the erasure probability. In Section III we use different criteria to analyze the memory requirements of the GOE scheme. In fact, we derive the peak memory usage as a function of the erasure probability and as a function of the interleaver.

II. TWO UNEQUAL ERASURE PROTECTION SCHEMES

Let us first introduce some notations. We consider an input object that needs to be unequally protected. Without loss of generality, we use the term "original object" to denote this input object and "object" (or "Generalized Object" in case of GOE) to denote each data chunk of a given priority in the "original object". Each object is therefore FEC encoded as appropriate and independently from other objects with both PET and GOE. The input parameters are:

• m, the original object length, in bytes; • d, the number of objects;

• α i , i = 1, ..., d, the length in bytes of the object of index i; • ρ i , i = 1, ..., d, the desired coding rate for the object of index i. • l, the target packet length in bytes. This size is usually determined by the maximum transmission unit size on the path between the source and the receiver(s), minus the protocol header sizes;

A. PET Principles

Goal: PET provides UEP in such a way that each packet is interchangeable in order to provide a deterministic erasure recovery behavior.

Detailed procedure: The number n P ET of packets and the number and size of symbols for each object need to be determined prior to FEC encoding. This is achieved as follows (Fig. 1):

• Determine the total number of packets: In [START_REF] Albanese | Priority encoding transmission[END_REF], due to roundoff errors, this number is given by:

n P ET = g l -d = d i=1 α i ρ i (l -d) (1)
In this formula g stands for the girth, or more precisely the sum of all the encoded object lengths when the target coding rate of each object, ρ i , is strictly respected: g = d i=1 αi ρi .

• Determine the number of source symbols in object i, β i :

β i = n P ET ρ i (2)
• Determine the size of symbols in object i:

s i = α i β i .
Note that the last symbol of an object, when shorter, is zero padded.

• FEC encode each of the d objects, thereby producing n P ET encoding symbols. For object i, the n P ET encoding symbols of index 1 to β i are source symbols whereas the remaining n P ET -β i are repair symbols. • Build packet j, j = 1, .., n P ET by concatenating the j th encoding symbol of each of the d objects. It can be verified that the sum of the d symbol sizes is less or equal to l, the target packet size.

B. GOE Principles

Goal: GOE provides UEP in a simple and flexible way while considering such practical aspects as minimizing the number of data copies, the number of FEC encodings, the maximum memory requirements or the number of packets to process. Detailed procedure: GOE works as follows (Fig. 1):

• Segment each object i into k i source symbols of length l bytes each (except the last one which may be shorter). We have: k i = α i l • FEC encode each object into n i encoding symbols according to the associated target coding rate:

n i = k i ρ i (3)
Unlike PET, here each encoding symbol (source or repair) corresponds to a packet. • It follows that the total number of packets sent is:

n GOE = d i=1 n i = d i=1 αi l ρ i (4)
• Choose a packet interleaving scheme: Several schemes are possible that have major practical impacts. One of them consists in a uniform interleaving (random packet transmission order), in order to make the transmission robust in front of long erasure bursts. On the opposite packets can be sent in sequence (no interleaving), in decreasing object priority order, which offers limited robustness in front of erasure bursts but is most beneficial in terms of decoding delay and memory requirements.

C. Preliminary comparison of the PET and GOE schemes

The output of both UEP schemes is a set of n P ET or n GOE packets ready to be sent to the receivers (usually n P ET = n GOE ). These packets contain one (GOE) or several (PET) encoding symbols (i.e. source or repair symbols) generated after a FEC encoding of the associated object.

However, even if the number of packets are not strictly equal they are equivalent as stated in the following lemma.

Lemma 1. For the PET and GOE schemes, we have the following equivalences and ordering:

n P ET ≈ n GOE (5)
ρ i ≈ β i n P ET ≈ k i n i (6)
β i s i ≈ k i l (7) n P ET s i ≈ n i l (8) β 1 β 2 ... β d (9) Proof:
(5) to (8) follow from the definition of the parameters (see Section II-A and II-B) by taking out all rounding operators, and since d l. (9) follows from the definition (2) and from the ordering of the object in decreasing priority order (or equivalently increasing coding rate).

In order to illustrate the analytical results, we consider the same parameters as those used in the original PET paper [START_REF] Albanese | Priority encoding transmission[END_REF] (Table I). By construction, packets are all inter-changeable with PET. Therefore the channel loss fraction, p e , is the only "degree of freedom" to consider in the analysis (packet interleaving has no sense, unlike GOE). Two cases of interest are studied:

A. PET with no erasure

The number of symbols to be stored increases with the number of packets received. But once enough symbols have been received (i.e. β i for object i), the decoding is successful and the received symbols can be deleted. Therefore, the memory usage across the packet reception for object i is:

t.s i .1 1 t βi ( 10
)
where t is the current number of received packets, which varies from 1 to n P ET and where 1 1 t βi = 1 if 1 t β i and 0 otherwise (echelon function). Thus, the peak memory which is defined as the maximum over the sum of the memory usage for each object can be expressed as:

peak mem no erasure P ET = max t∈[1,n P ET ] d i=1 t.s i .1 1 t βi = max 1 j d   β j d i=j s i   (11)
From (10) the peak memory for object i is reached when t = β i . When considering all objects, the global peak can be searched over all local maxima that corresponds to a maximum of the per object peak memory. Moreover, the β i are ordered (9). Therefore, when object j can be decoded, which occurs when β j packets have been received, the objects that have not yet been decoded are: object j + 1 to d, and their symbols must be kept. A local maximum, when object j can be decoded, is thus β j d i=j s i . This explains the last equality in (11). Figure 2 symbols are available for decoding to take place. The black curve is the total memory requirement over the time, and the peak is reached after receiving 335 packets.

B. PET with erasures

If erasures occur, only (1 -p e )n P ET packets are received and some of the objects may not be decoded. The memory usage curve is therefore truncated. For instance figure 3 illustrates this behavior when p e = 0.45. The memory usage for object i can be expressed as:

t.s i .1 1 t min(βi,(1-pe)n P ET ) . (12)
and the peak memory is:

peak mem P ET = max t∈[1,n P ET ] d i=1 t.s i 1 1 t min(βi,(1-pe)n P ET ) (13) = max   max 1 j τ   β j d i=j s i   , (1 -p e )n P ET d i=τ +1 s i  
where τ s.t. β τ (1 -p e )n P ET < β τ +1 . In other words, we have received a number of packets such that all classes up to index τ have been decoded, but not classes of index τ + 1 and above.

Figure 4 shows the peak memory as a function of the channel loss fraction p e . We observe a first step at low p e , which corresponds to the maximum of the memory consumption shown in Figure 2 and expressed in the closed formula (11). If the erasure probability increases, this peak may not exist anymore (as shown in Figure 3) and a second step occurs at the second maximal value of all peaks (13). Depending on the relative values of the peaks and of their positions, there might be up to d steps. In our example, there are only 2. Finally, when p e gets larger, no decoding will be performed successfully and no memory is freed. Therefore, the peak memory equals the total number of symbols received, which decreases linearly with p e .

IV. PEAK MEMORY ANALYSIS FOR GOE

The GOE scheme is more flexible than PET. Here two "degrees of freedom" are considered: the channel loss fraction and the packet permutation (interleaving). Five cases of interest are studied:

A. GOE with no erasure and no permutation At the receiver, packets are kept in memory as long as the object they belong to has not been decoded. Once decoded, all the packets of this object are immediately deleted. Since k i packets are sufficient to decode object i, the memory consumption for this object after receiving t packets (1 t n i ) is:

t.l.1 1 t ki (14)
The peak memory for object i occurs when t = k i : max

1 t ni t.l.1 1 t ki = k i l. (15)
Let us first assume that no erasure occurs and that no permutation has been used. Objects are received in their index increasing order and objects are processed in sequence. Therefore the memory usage is the time concatenation of the functions given in (14) and is shown in Figure 5. The peak memory is then given by the maximum of each per object peak memory: peak mem no erasure no perm GOE = l max

1 i d k i (16)

B. GOE with erasures and no permutation

If erasures occur, n i (1-p e ) packets for object i are received. If this is greater than k i , then the memory is freed when k i packets are received. Otherwise, when the reception of object i + 1 starts, the receiver knows that no more packets for object i will be received and it can free the memory. The peak memory is then given by: peak mem no perm GOE = l max

1 i d min k i , n i (1 -p e ) ( 17
)
where the maximum is computed over all the per object peak memories.

Theorem 1 (PET vs. GOE no permutation). The peak memory for PET is much larger than the peak memory of the GOE scheme with no permutation.

Proof: From the equivalence of the amount of useful data (7), we have β j d i=j s i ≈ lk j + β j d i=j+1 s i lk j . Moreover, from the equivalence of the amount of encoded data (8)

n P ET d i=τ +1 s i ≈ d i=τ +1 n i l n i l.
Finally, comparing (13) and ( 17), we get that the peak memory for PET is much larger than the peak memory of GOE without any permutation.

Figure 6 shows the peak memory difference between the GOE (no permutation) and the PET schemes.

C. GOE with a uniform permutation

Theorem 1 shows that GOE without permutation allows to save memory with respect to the PET scheme. However, GOE without permutation is not robust to burst of erasures. Therefore, we study the case of GOE under a uniform permutation in order to increase the robustness to bursts.

When a uniform permutation distribution is used, the peak memory consumption occurs when each object can almost be decoded (i.e. k j -1 packets received for object j) except one object that can be decoded. Therefore, the peak memory (without erasures) is:

peak mem no erasure unif perm GOE = l   d j=1 k j -d + 1   (18)
If erasures occur, the same memory peak as (18) can be achieved unless not enough packets have been received. Therefore, the peak memory under erasure becomes:

peak mem unif perm GOE = l. min   d j=1 k j -d + 1, n GOE (1 -p e )   (19)
Theorem 2 (PET vs. GOE uniform permutation). The peak memory for GOE with a uniform permutation is larger than the peak memory of the PET scheme, unless the erasure probability is so large that no object can be decoded, in which case the peak memories are equal.

Proof: Let us first compare the peak memory without erasure and let us compare each term to be maximized in (11) and (18). ∀j, 1 j d, we have

β j d i=j s i = min j i d β i d i=j s i d i=j β i s i d i=1 β i s i ≈ l. d i=1 k i ,
where the first equality follows from the ordering (9) and the last one from [START_REF] Roumy | Unequal Erasure Protection and Object Bundle Protection with the Generalized Object Encoding Approach[END_REF]. Thus, by neglecting d in (19), we get that peak mem no erasure P ET peak mem no erasure unif perm GOE . Moreover, since the number of packets are equivalent, see (5), we have n P ET (1 -p e ) ≈ n GOE (1 -p e ). Therefore, comparing (13) and ( 19), we get that if the erasure probability is so large that no object can be decoded, then the peak memories are equal. This is illustrated in Figure 6.

D. GOE with no erasure but an average permutation

In order to further investigate the GOE scheme, we analyze the peak memory of an average permutation, which is typical of the permutation behavior. This average permutation results from the average decoding delay that has been studied in detail in [START_REF] Roumy | Unequal Erasure Protection and Object Bundle Protection with the Generalized Object Encoding Approach[END_REF]. For the sake of completeness, we recall that the mean decoding delay (under GOE) can be efficiently approximated by: Moreover, this upper bound (20) is exact for low value of p e , i.e. p e → 0. Therefore, when there is no erasure, the average decoding delay is:

dec delay GOE min n GOE , n GOE n i k i 1 -p e min (n GOE , dec delay ∞ GOE ) (20)
dec delay no erasure GOE (object i) = k i n i n GOE . (21)
Definition 1 (The average permutation). The average permutation is a permutation such that, for each object, the decoding delay occurs at exactly the average decoding delay (21).

First, the objects are sent in a decreasing priority order (i.e. high priority first or low coding rate k i /n i first). As a consequence, they are also ordered according to their increasing average decoding delay, see (21). Before object 1 is decoded, the memory usage increases by l for each packet received. It reaches a peak when object 1 is decoded, which value is dec delay GOE (object 1) and decreases by k 1 l, the memory used for object 1 being freed. Due to the permutation, packets from object 1 continue to be received, but discarded. Then, the memory further increases by an amount of l if the received packet does not belong to object 1. Therefore the slope is now l(1 -n1 n GOE ). By repeating this procedure, we obtain that the peak values are:

l(1 - j-1 i=1 n i n GOE ) k j n j n GOE = l( d i=j n i ) k j n j .
It follows that the peak memory under GOE is given by peak mem no erasure avg perm GOE = max

1 j d l( d i=j n i ) k j n j (22)
From ( 6), we have kj nj ≈ βj n P ET and from (8), we have l.n i ≈ n P ET s i . Therefore, comparing (11) and (22) we conclude that, up to round-off errors, the peak memory of PET and GOE with an average permutation and without erasures are equal.

E. GOE with erasures and an average permutation

If erasures occur, we observe the same behavior as for PET. More precisely, the peak memory is given by:

peak mem avg perm GOE = max   max 1 j τ l( d i=j n i ) k j n j , (1 -p e )l d i=τ +1 n i   ( 23
)
where τ is such that: dec delay GOE (τ ) (1 -p e )n GOE <dec delay GOE (τ + 1).

Theorem 3 (PET vs. GOE average permutation). The peak memory with PET and GOE with an average permutation are equal.

Proof: Let us compare (23) to (13). The equivalence of the first term (i.e. when there is no erasure) has been shown in the previous section. The second term of this formula is equivalent to that of (13). Indeed, the l d i=τ +1 n i is the total number of bytes after FEC encoding of the classes that will not be decoded with GOE, and this value is equivalent to n P ET d i=τ +1 s i , see (8), which is the same for PET. Finally, the τ of both formulas are equivalent since both techniques have the same recovery capabilities [START_REF] Roumy | Unequal Erasure Protection and Object Bundle Protection with the Generalized Object Encoding Approach[END_REF]. This proves that the peak memory with PET and GOE with an average permutation are equal.

Moreover, we conjecture that:

Conjecture 1 (Average peak memory vs. peak memory of the average permutation). The average peak memory for GOE with a uniform permutation is smaller than the peak memory of the average permutation.

Example 1. Consider two objects of the same length and priority. Therefore the two objects have the same average decoding delay. The memory usage (under the average permutation) is maximum when the number of received packets equals the k1 n1 n GOE delay. Thus the peak memory is 2k 1 l.

As for the peak memory average over all permutations, the two peaks (one for each object) will occur at the same time. And when they occur at two different times, the maximum is always smaller than 2k 1 l. Therefore, on average, the peak memory 2k 1 l = the peak memory obtained with the average permutation.

Claim 1 (PET vs. GOE average permutation). The average peak memory of GOE with a uniform permutation is smaller than the peak memory of PET.

Proof: This is a consequence of Theorem 3 and Claim 1. Figure 8 shows the span of the peak memory for the GOE scheme with a uniform permutation. We observe that, as stated in Claim 1, the mean of the peak memory is smaller than the peak memory of the PET scheme. Note also that it is only slightly smaller.

V. CONCLUSIONS

This work has compared two techniques capable of providing an unequal erasure protection service, namely PET and GOE. We have recently demonstrated that the protection performance of both approaches are equivalent [START_REF] Roumy | Unequal Erasure Protection and Object Bundle Protection with the Generalized Object Encoding Approach[END_REF]. However key differences become apparent when considering such practical metrics as the peak memory consumption during decoding. We have shown that GOE without any permutation offers the smallest peak memory but with a limited burst erasure resiliency. In order to increase the burst erasure resiliency, we considered GOE with a uniform permutation and showed that the peak memory of PET is smaller than the one for GOE (uniform distribution), unless no object can be decoded in which case they are equal. However, we showed that PET corresponds to the average behavior of the GOE uniformly permuted scheme.

In future works, we will analyze alternative permutations (for instance a ∆-permutation [START_REF] Roumy | Unequal Erasure Protection and Object Bundle Protection with the Generalized Object Encoding Approach[END_REF]). Being somewhere between these two extrema, such a permutation is likely to achieve a good trade off between burst erasure resiliency and peak memory consumption (among other practical considerations).

1 Fig. 1 .

 11 Fig. 1. PET vs GOE principles.

4 ←Fig. 2 .

 42 Fig. 2. PET memory usage as a function of the number of received packets, without erasure.

Fig. 3 .Fig. 4 .

 34 Fig. 3. PET memory usage as a function of the number of received packets, with pe = 0.45.

Fig. 5 .Fig. 6 .

 56 Fig. 5. GOE memory usage as a function of the number of received packets, with no erasure and no permutation.

Fig. 7 .

 7 Fig.7. GOE memory usage as a function of the number of received packets, with no erasure but an average permutation.

Fig. 8 .

 8 Fig. 8. Peak memory usage (average and 99% confidence intervals below and above the average) as a function of the channel loss fraction pe.

TABLE I PARAMETERS

 I FOR THE UEP PROBLEM, FROM[START_REF] Albanese | Priority encoding transmission[END_REF]. ALL SIZES IN BYTES.

	Input parameters
	m, original object length	100KB
	d, number of objects (priorities)	5
	α i , length of object i	[10KB, 10KB, 20KB, 30KB, 30KB]
	ρ i , target coding rate for object i	[0.5, 0.6, 0.65, 0.8, 0.95]
	l, target packet length	250 B
	Output parameters with PET
	β i , number of source symbols	[279, 335, 363, 447, 531]
	s i , symbol size of object i	[36 B, 30 B, 56 B, 68 B, 57 B]
	actual packet size	247 B
	number of encoded symbols	558
	actual coding rate	[0.5, 0.6, 0.651, 0.801, 0.952]
	n P ET , total number of packets	558
	Output parameters with GOE
	k i , number of source symbols	[40, 40, 80, 120, 120]
	symbol size (=l)	250 B
	n i , number of encoded symbols	[80, 67, 124, 150, 127]
	actual packet size	250 B
	actual coding rate	[0.5, 0.597, 0.645, 0.8, 0.945]
	n GOE , total number of packets	548
	III. PEAK MEMORY ANALYSIS FOR PET

VI. ACKNOWLEDGMENTS

This work was supported by the ANR-09-VERS-019-02 grant (ARSSO project) and by the INRIA -Alcatel Lucent Bell Labs joint laboratory. The authors would also like to thank the members of the ARSSO project for their comments that help improve the manuscript.