Daniele Frigioni
email: daniele.frigioni@univaq.itsebastian.stiller@tu-berlin.de

Sebastian Stiller

Daniel Cremers

Marc Langheinrich

Dorothea Wagner

Alexey Stratonnikov

Ralf Borndörfer

Daniel Delling

Laura Galli

Spyros Kontogiannis

Gabor Maroti

Frédéric Meunier

Marc Pfetsch

Robert Shorten

Alberto Marchetti

Rolf Möhring

Solving a Freight Railcar Flow Problem Arising in Russia

Preface

Transportation networks give rise to very complex and large-scale network optimization problems requiring innovative solution techniques and ideas from mathematical optimization, theoretical computer science, and operations research. Since 2000, the series of Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) workshops brings together researchers and practitioners who are interested in all aspects of algorithmic methods and models for transportation optimization and provides a forum for the exchange and dissemination of new ideas and techniques. The scope of ATMOS comprises all modes of transportation.

The 13th ATMOS workshop (ATMOS'13) was held in connection with ALGO'13, by INRIA and Campus SophiaTech, in Sophia Antipolis, France, on September 5, 2013. Topics of interest for ATMOS'13 were all optimization problems for passenger and freight transport, including, but not limited to, Demand Forecasting, Models for User Behavior, Design of Pricing Systems, Infrastructure Planning, Multi-modal Transport Optimization, Mobile Applications for Transport, Congestion Modeling and Reduction, Line Planning, Timetable Generation, Routing and Platform Assignment, Vehicle Scheduling, Route Planning, Crew and Duty Scheduling, Rostering, Delay Management, Routing in Road Networks, Traffic Guidance. Of particular interest were papers applying and advancing the following techniques: graph and network algorithms, combinatorial optimization, mathematical programming, approximation algorithms, methods for the integration of planning stages, stochastic and robust optimization, online and real-time algorithms, algorithmic game theory, heuristics for real-world instances, simulation tools.

In response to the call for papers we received 26 submissions, all of which were reviewed by at least three referees. The submissions were judged on originality, technical quality, and relevance to the topics of the workshop. Based on the reviews, the program committee selected the 12 papers which appear in this volume. Together, they quite impressively demonstrate the range of applicability of algorithmic optimization to transportation problems in a wide sense. In addition, Tobias Harks kindly agreed to complement the program with an invited talk entitled Modeling and Optimizing Traffic Networks.

We would like to thank the members of the Steering Committee of ATMOS for giving us the opportunity to serve as Program Chairs of ATMOS'13, all the authors who submitted papers, Tobias Harks for accepting our invitation to present an invited talk, the members of the Program Committee and all the additional reviewers for their valuable work in selecting the papers appearing in this volume, and the local organizers for hosting the workshop as part of ALGO'13. We also acknowledge the use of the EasyChair system for the great help in managing the submission and review processes, and Schloss Dagstuhl for publishing the proceedings of ATMOS'13 in its OASIcs series.

Finally, we are pleased to announce that this year, for the first time

  , ATMOS PC awards a Best Paper Award. The Best Paper of ATMOS 2013 is A Configuration Model for the Line Planning Problem by Ralf Borndörfer, Heide Hoppmann, and Marika Karbstein. Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'13). Editors: Daniele Frigioni, Sebastian Stiller OpenAccess Series in Informatics Schloss Dagstuhl -Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

	September, 2013
	Daniele Frigioni
	Sebastian Stiller

13th

List of Additional Reviewers

Gianlorenzo D'Angelo, Andrea D'Ariano, Mattia D'Emidio, Julian Dibbelt, Pavlos Efraimidis, Dimitris Fotakis, Loukas Georgiadis, Jan Marecek, Martin Mevissen, Alfredo Navarra, Alexander Richter, Arieh Schlote, Karsten Weihe, Jia Wuan Yu, Christos Zaroliagis.

Local Organizing Committee

Frédéric Cazals, Agnès Cortell (event manager), David Coudert, Olivier Devillers, Joanna Moulierac, Monique Teillaud (chair).


Valère Bitseki Penda

Hacène Djellout
email: hacene.djellout@math.univ-bpclermont.fr

Laure Dumaz
email: laure.dumaz@ens.fr

Florence Merlevède
email: florence.merlevede@univ-mlv.fr

S Valère

Bitseki Penda
email: valere.bitsekipenda@math.univ-bpclermont.fr

Frédéric Proïa
email: frederic.proia@inria.fr

Moderate deviations of functional of Markov Processes

Introduction

This paper groups the contributions of the speakers of the session dedicated to moderate deviations of functional of Markov processes organized during the Journées MAS, which took place in Clermont-Ferrand in August 2012.

The principle of moderate deviations (PDM, in short) is a subject of classic study of the probability theory. Indeed, in the study of the limit theorems of a probability or statistical model, the PDM is one of main questions that we look, after the laws of large numbers, the central limit theorem (CLT, in short) and the law of the iterated logarithm.

The MDP can be seen as an intermediate behavior between the CLT and large deviations principle (LDP, in short). Usually, the MDP exhibit a simpler rate function (quadratic) inherited from the approximated Gaussian process, and holds for a larger class of dependent random variables than the LDP.

The LDP and MDP of sums of random variables is now a wide and fastly growing branch of probability theory. It was created initially in the framework of the theory of sums of independent identically distributed random variables and then extended to a wide class of random processes, i.e., random functions in one variable, with some general conditions of weak dependence traditional for the theory of random processes.

We refer to Dembo and Zeitouni [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF], for an exposition of the general theory of large deviations and limit ourself below to the statement of some important facts and definitions which are useful for our needs.

It is best to think of a specific example to clarify the idea Example 0.1. (Cramér-Chernoff's Theorem) Let X 1 , X 2 , ... a sequence of i.i.d. centered real valued random variables. Define S n = n i=1 X i . Notice that L(t) := n -1 log E(e tSn ) = log E(e tX1 ) .

Whence, by the Gärtner-Ellis theorem, for all Borelians A,

-inf t∈A o I(t) ≤ lim inf n 1 n log P S n n ∈ A ≤ lim sup n 1 n log P S n n ∈ A ≤ -inf t∈ Ā I(t) ,
where I is the Fenchel-Legendre dual of L given by I(x) = sup t>0 (txlog E(e tX1 )).

Remark 0.2. The LDP is not distribution free, it holds for a small class of dependent sequences (see Bryc-Dembo [START_REF] Bryc | Large deviations and strong mixing[END_REF]), it requires the existence of moment generating function and, it is restricted to stationarity.

Example 0.3. (Heuristic for the MDP). Consider again (X i ) i≥1 a sequence of i.i.d. centered real valued random variables. Take a n → 0 and na n → ∞ (instead of a n = n -1 where I(x) = x 2 /(2σ 2 ). In the i.i.d. setting, we refer to Arcones [START_REF] Arcones | The large deviation principle for stochastic processes I[END_REF][START_REF] Arcones | The large deviation principle for stochastic processes II[END_REF], and to Eichelsbacher-Löwe [START_REF] Eichelsbacher | Moderate deviations for i.i.d. random variables[END_REF](see Theorem 2.14 in section 2) for necessary and sufficient conditions for the MDP to hold. Remark 0.4. MDP is distribution free, it holds for a larger class of dependent sequences, it does not require the existence of the moment generating function, it is non restricted to stationarity.

Before presenting the plan of our paper, let us now give the precise definition of a MDP: let (a n ) n≥0 be a positive sequence such that a n -→ n→∞ 0, and

na n -→ n→∞ ∞. (1)
Definition 0.5. A family of random variables {Z n , n > 0} with values in a topological space X equipped with σ-field B satisfies the MDP with speed a n satisfying (1) and good rate function I(•) if the level sets {x, I(x) ≤ α} are compact for all α < ∞, and for all Γ ∈ B inf

t∈Γ o I(t) ≤ lim inf n→∞ a n log P( √ a n Z n ∈ Γ) ≤ lim sup n→∞ a n log P( √ a n Z n ∈ Γ) ≤ -inf t∈ Γ I(t) ,
where Γ o (resp. Γ) denotes the interior (resp. closure) of Γ in X .

The paper is organized as follows. In Section 1, we state the MDP for weakly dependent random variables with applications to functions of mixing sequences, Markov chains, and functions of linear process. Section 2 is devoted to the MDP for the Durbin-Watson statistic related to the first-order autoregressive process. Section 3 is dedicated to the MDP for bufircating Markov chains and application to the bifurcating autoregressive process. Section 4 is very different from subjects approached on the previous sections. It concerns essentially the large deviations of the true self-repelling motion.

Moderate deviations for weakly dependent sequences

In this section, we are interested in the MDP and its functional form for a class of weakly dependent sequences. Examples that can be treated this way include some classes of Markov chains, iterated Lipschitz models and functions of linear processes with absolutely regular innovations.

Concerning the traditional LDP, it is known from the paper by Bryc and Dembo [START_REF] Bryc | Large deviations and strong mixing[END_REF] that it is not satisfied by many classes of weakly dependent random variables. This is the reason why it is convenient to look at MDP.

We shall use the new developed Bernstein-type inequalities to obtain sharp moderate deviation asymptotic results for some classes of dependent random variables.

Given X 1 , X 2 , ... a sequence of centered real valued random variables, our aim is to give dependence conditions to get the MDP for the partial sum and the normalized partial sum processes

S n = n i=1 X i or W n (•) =    [nt] i=1 X i , t ∈ [0, 1]    suitably normalized (W n is an element of D[0, 1]
, the space of functions on [0, 1] with left-hand limits and continuous from the right, equipped with the Skorohod topology).

MDP under projective conditions

What projective conditions can we expect ? Let us recall two results about the functional form of the CLT for stationary sequences. With this aim, it is convenient to define a stationary sequence (X i ) i∈Z as follows. Let θ : Ω → Ω be a bijective bimeasurable transformation preserving P on (Ω, A). For any i ∈ Z, let X i = X 0 • θ i where X 0 is a real-valued random variable defined on (Ω, A). For a subfield F 0 satisfying F 0 ⊆ θ -1 (F 0 ), let F i = θ -i (F 0 ). Denote also by I the θ-invariant sigma field.

Theorem 1.1. [Maxwell-Woodroofe [START_REF] Maxwell | Central limit theorems for additive functionals of Markov chains[END_REF]. Peligrad-Utev [START_REF] Peligrad | A new maximal inequality and invariance principle for stationary sequences[END_REF]]. Assume that X 0 is F 0 -measurable, in L 2 and that

n>0 n -3/2 E(S n |F 0 ) 2 < ∞ . Then {n -1/2 W n (t), t ∈ [0, 1]} converges in distribution in D[0, 1] to √ ηW
where W is a standard Brownian motion independent of I and η is a I-measurable nonnegative r.v. such that E(η) = σ 2 and

lim n→∞ E(S 2 n |I) n = η in L 1 . Theorem 1.2.
[Heyde [START_REF] Heyde | On the central limit theorem for stationary processes[END_REF]. Dedecker-Merlevède-Volnỳ [START_REF] Dedecker | On the weak invariance principle for non-adapted sequences under projective criteria[END_REF]]. Assume that

X 0 is F 0 -measurable, in L 2 and such that E(X 0 |F -∞ ) = 0 a.s. Assume that n≥0 P 0 (X n ) 2 < ∞ where P 0 (X n ) = E(X n |F 0 ) -E(X n |F -1 ) . Then {n -1/2 W n (t), t ∈ [0, 1]} converges in distribution in D[0, 1] to √ ηW where W is a standard Brownian motion independent of I and η = k∈Z E(X 0 X k |I) .
Remark 1.3. The theorems have different ranges of applicability. Both of them are satisfied under

k>0 k -1/2 E(X k |F 0 ) 2 < ∞. (2)
Let

φ(k) = sup t∈R E(1 X k ≤t |F 0 ) -E(1 X k ≤t ) ∞ . If X 0 ∈ L p for p ≥ 2, then (2) holds under k>0 k -1/2 (φ(k)) (p-1)/p < ∞.
Proof. The proofs are based on approximation by a stationary martingale in L 2 .

Starting from the so called coboundary decomposition (X k = d k + Z k -Z k+1 ) and using the MDP for martingale (see Puhalskii [START_REF] Puhalskii | Large deviations of semimartingales via convergence of the predictable characteristics[END_REF]), Gao [START_REF] Gao | Moderate deviations for martingales and mixing random processes[END_REF] and Djellout [START_REF] Djellout | Moderate deviations for Martingale Differences and applications to α-mixing sequences[END_REF] obtained the MDP for ϕ-mixing sequences with summable mixing rate.

In the context of Markov process, starting from the Poisson equation, Delyon-Juditsky-Lipster [START_REF] Delyon | Moderate deviation principle for ergodic Markov chain. Lipschitz summands[END_REF] proved the MDP for n -1/2 n k=1 H(Y k ) where H is a Lipshitz function and

Y k = F (Y n-1 , ε n ) where |F (x, z) -F (y, t)| ≤ κ|x -y| + L|z -t| with κ < 1 and (ε n ) an i.i.d. sequence of r.v. independent of Y 0 such that E(e δ|ε0| ) < ∞.
Usually, in dealing with dependent random variables, to brake the dependence, a standard procedure is to divide first the variables in blocks. This technique introduces a new parameter. The second step is then to approximate these blocks either by martingale differences, either by independent blocks using coupling results. Proposition 1.4. [A modification of Puhalskii's result [START_REF] Puhalskii | Large deviations of semimartingales via convergence of the predictable characteristics[END_REF]]. Let {d (m) j,n } 1≤j≤kn,m be a martingale difference sequence adapted to

F (m) j,n . Define Z (m) n (t) = n -1/2 [kn,mt] i=1 d (m)
i,n . Let (a n ) be a sequence of positive numbers satisfying [START_REF] Arcones | The large deviation principle for stochastic processes I[END_REF]. Assume that for all m ≥ 1 sup

1≤j≤kn,m d (m) j,n ∞ = o( √ na n ) as n → ∞
and that for all δ > 0, there exists σ 2 ≥ 0 such that

lim m→∞ lim sup n→∞ a n log P   1 n kn,m j=1 E((d (m) j,n ) 2 |F (m) (j-1),n ) -σ 2 ≥ δ   = -∞ .
Let {ζ n (t) , t ∈ [0, 1]} be a D[0, 1]-valued process such that for all δ > 0,

lim m→∞ lim sup n→∞ a n log P √ a n sup t∈[0,1] |ζ n (t) -Z (m) n (t)| ≥ δ = -∞ .
Then, the processes ζ n (.) satisfy the MDP with rate function I σ (•) given by

I σ (h) = 1 2σ 2 1 0 (h ′ (u)) 2 du (3)
if simultaneously σ > 0, h(0) = 0 and h is absolutely continuous, and I σ (h) = ∞ otherwise.

Theorem 1.5. [Dedecker-Merlevède-Peligrad-Utev [START_REF] Dedecker | Moderate deviations for stationary sequences of bounded random variables[END_REF]]. Assume that X 0 ∞ < ∞ and that X 0 is F 0 -measurable. In addition, assume that

∞ n=1 n -3/2 E(S n |F 0 ) ∞ < ∞ ,
and that there exists σ 2 ≥ 0 with lim

n→∞ n -1 E(S 2 n |F 0 ) -σ 2 ∞ = 0 .
Then, for all positive sequences (a n ) satisfying (1), the normalized partial sums processes n -1/2 W n (.) satisfy the MDP with the good rate function I σ (•) given in (3).

Remark 1.6. The conditions hold under

∞ n=1 n -1/2 E(X n |F 0 ) ∞ < ∞ , and lim n→∞ E(X i X j |F -n ) -E(X i X j ) ∞ = 0 forall i, j ≥ 1.
In this case

σ 2 = k∈Z E(X 0 X k ). Remark 1.7. Let φ 2 (n) = sup i>j≥n sup (s,t)∈R 2 E(1 Xi≤s 1 Xj ≤t |F 0 ) -E(1 Xi≤s 1 Xj ≤t ) ∞ .
The above conditions are satisfied if

k>0 k -1/2 φ 2 (k) < ∞ .
This improves the condition imposed by Gao [START_REF] Gao | Moderate deviations for martingales and mixing random processes[END_REF].

Proof. The proof of Theorem 1.5 is based on an approximation by a stationary martingale plus an Hoeffding-type inequality.

Let m be an integer and

k = k n,m = [n/m]. Let X i,m = im j=(i-1)m+1 X j , M (m) k = k i=1 (X i,m -E(X i,m |F (i-1)m ) := [n/m] i=1 D i,m and
M (m) k (t) := M (m) [kt] .
We first notice that lim sup

n→∞ 1 n [n/m] j=1 (E(D 2 j,m |F (j-1)m ) -σ 2 ∞ ≤ E(S m |F 0 ) 2 ∞ m + m -1 E(S 2 m |F 0 ) -σ 2 ∞ ,
and

sup t∈[0,1] |S [nt] -M (m) k (t)| ≤ o( √ na n ) + max 1≤j≤[n/m] | j i=1 E(X i,m |F (i-1)m )| .
To handle the last term in the right-hand side of the above inequality, we apply the Hoeffding-type inequality of Peligrad-Utev-Wu [START_REF] Peligrad | A maximal Lp-inequality for stationary sequences and its applications[END_REF]. This gives

a n log P a n n max 1≤j≤[n/m] | j i=1 E(X i,m |F (i-1)m )| ≥ δ ≤ a n log(4 √ e) - δ 2 m 2( E(S m |F 0 ) ∞ + 80 ∞ j=1 j -3/2 E(S jm |F 0 ) ∞ ) 2 .

Applications

Contracting Markov chain

Let (Y n ) n≥0 be a stationary Markov chain of bounded random variables with invariant measure µ and transition kernel K. Denote by • ∞,µ the essential supremum norm with respect to µ. Let Λ 1 be the set of 1-Lipschitz functions. Assume that there exist C > 0 and ρ ∈]0, 1[ such that sup

g∈Λ1 K n (g) -µ(g) ∞,µ ≤ Cρ n , (4)
for any f, g ∈ Λ 1 and any m ≥ 0 lim

n→∞ K n (f K m (g)) -µ(f K m (g)) ∞,µ = 0. ( 5
)
Let L be the class of functions

f from R to R such that |f (x) -f (y)| ≤ c(|x -y|),
for some concave and non decreasing function c satisfying

1 0 c(t) t | log t| dt < ∞ .
Assume that the stationary Markov chain (Y n ) n≥0 satisfies ( 4) and ( 5). If f belongs to L, then the MDP holds for {n

-1/2 [nt] k=1 (f (Y k ) -µ(f )), t ∈ [0, 1]} with σ 2 = σ 2 (f ) = µ((f -µ(f )) 2 ) + 2 n>0 µ(K n (f ) • (f -µ(f ))) .

Linear process

When we deal with functions of a linear process for instance, the next theorem can be more adapted.

Theorem 1.8. [Dedecker-Merlevède-Peligrad-Utev [8]]. Assume that X 0 ∞ < ∞, that X 0 is F 0 -measurable and that E(X 0 |F -∞ ) = 0 a.s. In addition, assume that n≥0 P 0 (X n ) ∞ < ∞ ,
and that for all j ≥ 0,

lim n→∞ n -1 n i=1 E(X i X i+j |F 0 ) -E(X 0 X j ) ∞ = 0 .
Then, for all positive sequences (a n ) satisfying (1), the normalized partial sums processes n -1/2 W n (.) satisfy the MDP with the good rate function I σ (•) given in [START_REF] Bercu | A sharp analysis on the asymptotic behavior of the Durbin-Watson statistic for the first-order autoregressive process[END_REF] where

σ 2 = k∈Z E(X 0 X k ).
Remark 1.9. This can be extended to linear processes Y k = j≥0 a j X k-j with (X i ) satisfying the conditions of the above theorem and (a k ) in ℓ 2 . The rate function is then eventually inherited from a fractional Brownian motion (see Merlevède-Peligrad [START_REF] Merlevède | Moderate deviations for linear processes generated by martingale-like random variables[END_REF]) and the normalizing sequence is Var(

n k=1 Y k ). 1.2.3. Functions of linear processes Let (c i ) i≥0 in ℓ 1 , {ε i } i∈Z a sequence of i.i.d. bounded r.v.'s and X k = f i≥0 c i ε k-i -E f i≥0 c i ε k-i Let δ(ε 0 ) = 2 inf{ ε 0 -x ∞ , x ∈ R}, and w f (h) = sup |t|≤h,x∈R |f (x + t) -f (x)| . • If n≥1 n -1/2 w f δ(ε 0 ) k≥n |c k | < ∞ the conditions of Theorem 1.5 hold. • If n≥0 w f δ(ε 0 )|c n | < ∞, the conditions of Theorem 1.8 hold. • Bernoulli Shifts: c i = 2 -i-1 and ε 0 is such that P (ε 0 = 1) = P (ε 0 = 0) = 1/2.
Then the MDP holds as soon as

1 0 w f (t) t | log t| dt < ∞ .

MDP for strong mixing sequences

The previous theorems do not allow to consider strong mixing sequences and unbounded random variables.

Let us consider α-mixing sequences; i.e.

α(n) = sup p∈Z α(F p , G n+p ) → 0 n → ∞ ,
where

F p = σ(X j , j ≤ p), G n+p = σ(X j , j ≥ n + p) and α(A, B) = sup A∈A,B∈B |P(A ∩ B) -P(A)P(B)| .
Assume that for all n ≥ 1,

α(n) ≤ exp(-cn γ1
) where γ 1 > 0 and c > 0, and the following tail condition:

there exist b ∈]0, ∞[, γ 2 ∈]0, +∞] such that sup i>0 P(|X i | > t) ≤ exp(1 -(t/b) γ2
) for all t > 0.

In the next theorem, we present a Bernstein-type inequality Theorem 1.10. [Merlevède-Peligrad-Rio [START_REF] Merlevède | A Bernstein type inequality and moderate deviations for weakly dependent sequences[END_REF]]. Assume that γ < 1 where

1 γ = 1 γ 1 + 1 γ 2 .
Then there exists η > 0 such that for n ≥ 4 and λ ≥ C(log n

) η P sup k∈[1,n] |S k | ≥ λ ≤ exp(-λ 2 /(C 1 + C 1 nV )) + (n + 1) exp(-λ γ /C 2 ),
where for

ϕ M (x) = (x ∧ M ) ∨ (-M ), V = sup M ≥1 sup i>0 Var(ϕ M (X i )) + 2 j>i |Cov(ϕ M (X i ), ϕ M (X j ))| .
Remark 1.11. Heuristically the inequality can be useful to study a n log P

√ a n √ n S n > t) provided a n n γ/(2-γ) → ∞.
Theorem 1.12. [Merlevède,Peligrad-Rio [START_REF] Merlevède | A Bernstein type inequality and moderate deviations for weakly dependent sequences[END_REF]]. Assume that α(n) ≤ exp(-cn γ1 ) and

sup i>0 P(|X i | > t) ≤ exp(1 -(t/b) γ2 ) ,
and γ < 1 where

1 γ = 1 γ1 + 1 γ2 . Let σ 2 n = VarS n and assume that lim inf n→∞ σ 2 n n > 0.
Then, for all positive sequence (a n ) such that

a n → 0 and a n n γ/(2-γ) → ∞ {σ -1 n S n } satisfies the MDP with I(t) = t 2 /2.
Remark 1.13. If (X i ) is a second order stationary sequence, under the mixing and tail conditions lim n→∞ σ 2 n n = σ 2 > 0 as soon as σ 2 n → ∞. Proof. We give some hints for the proof of Theorem 1.12. The Bernstein type inequality allows to consider the r.v's truncated at a level T n . Let

I(n, j) = {(j -1)(p n + q n ) + 1, . . . , (j -1)(p n + q n ) + p n } J(n, j) = {(j -1)(p n + q n ) + p n + 1, . . . , j(p n + q n )} let S ′ (K) = i∈K X ′ i and m n = [n/(p n + q n )] S ′ n = mn j=1 S ′ (I(n, j)) + mn j=1 S ′ (J(n, j)) + R n .
The idea is to consider discrete Cantor type sets. We construct a set

K (ℓn) I(n,j) = 2 ℓn i=1 I ℓn,i (p n , j) ,
where the I ℓn,i (p n , j) are disjoint sets of consecutive integers, each of same cardinal such that

p n 2 ℓn (1 + ε n ) ≤ CardI ℓn,i (p n , j) ≤ p n 2 ℓn .
We have the following

I(n,j) / a n σ 2 n → t 2 2 as n → ∞.
This can be done by decorrelation step by step on the Cantor set that implies

a n mn j=1 log E exp tS ′ K (ℓn) I(n,j) / a n σ 2 n - mn j=1 2 ℓn i=1 log E exp tS ′ I ℓn,i (p n , j) / a n σ 2 n → 0 as n → ∞ .
Remark 1.14. On the mixing-coefficients. The α-mixing coefficients are not needed in their full generality. We need mixing-coefficients allowing coupling and decorrelation of blocks of random variables. We can use of the τ -mixing coefficients as introduced by Dedecker and Prieur [START_REF] Dedecker | Coupling for τ -dependent sequences and applications[END_REF]. These coefficients are easily computable in a lot of situations as for instance iterated Lipschitz models or functions of linear processes generated by absolutely regular innovations.

1.4. Applications

Application to Markov chains

Let (Y j ) j≥0 be an E-valued, irreducible ergodic and stationary Markov chain with a transition probability P having a unique invariant probability measure π. Assume that the chain has an atom: there exists A ∈ E with π(A) > 0 and ν a probability measure such that P (x, .) = ν(.) for all x ∈ A. Assume that there exists δ > 0 and γ 1 ∈]0, 1] such that for τ = inf{n ≥ 0; Y n ∈ A}:

E ν (exp(δτ γ1 )) < ∞.
Djellout and Guillin [START_REF] Djellout | Moderate deviations for Markov chains with atom[END_REF]: for each bounded function f from E to R with π(f ) = 0, the MDP holds for n -1/2 n i=1 f (Y i ) with a n such that a n → 0 and a n n γ1/(2-γ1) → ∞. Applying our MDP result we obtain: Suppose that π(f ) = 0 and there exist b ∈]0, ∞[ and γ 2 ∈]0, ∞] such that

π(|f | > t) ≤ exp(1 -(t/b) γ2 ) for any t > 0 .
If 1/γ 1 + 1/γ 2 > 1 then the MDP holds with speed (a n ) satisfying a n → 0 and a n n γ/(2-γ) → ∞.

Autoregressive Lipschitz model

For δ in [0, 1[ and C in ]0, 1], let L(C, δ) be the class of 1-Lipschitz functions f which satisfy

f (0) = 0 and |f ′ (t)| ≤ 1 -C(1 + |t|) -δ almost everywhere.
Let (ε i ) i∈Z be a sequence of i.i.d. real-valued random variables. For η ∈]0, 1], let ARL(C, δ, η) be the class of Markov chains on R defined by

Y n = f (Y n-1 ) + ε n with f ∈ L(C, δ) and E(exp(λ|ε 0 | η )) < ∞ for a λ > 0. Let g be a 1-Lipschitz function such that |g(x)| ≤ c(1 + |x| ζ ) for ζ in [0, 1]. If δ + ζ > 0, then (g(Y i ) - E(g(Y i )) ) i∈Z satisfies the MDP with γ 2 = η(1 -δ)/ζ and γ 1 = η(1 -δ)(η(1 -δ) + δ) -1 .

Moderate deviations for the Durbin-Watson statistic related to the first-order autoregressive process

The purpose of this section is to investigate MDP for the Durbin-Watson statistic associated with the stable first-order autoregressive process where the driven noise is also given by a first-order autoregressive process. We first establish a MDP for both the least squares estimator of the unknown parameter of the autoregressive process as well as for the serial correlation estimator associated with the driven noise. It enables us to provide a MDP for the Durbin-Watson statistic in the easy case where the driven noise is normally distributed and in the more general case where the driven noise satisfies a less restrictive Chen-Ledoux type condition.

We start by introducing some notations and definitions, see [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF]. In the whole paper, for any matrix M , M ′ and M stand for the transpose and the euclidean norm of M , respectively. Let (b n ) be a sequence of increasing positive numbers such that

b n -→ ∞, b n √ n -→ 0. ( 6
)
Remark 2.1. The condition (6) corresponds to (1) with a n = 1/b 2 n .

Definition 2.2. We say that Z n converges (b 2 n )-superexponentially fast in probability to some random variable Z if, for all δ > 0, lim sup Let us introduce the autoregressive process of order 1 with autocorrelated driven noise that we shall consider. For all n ≥ 1,

X n = θX n-1 + ε n ε n = ρε n-1 + V n (7)
where X 0 and ε 0 are square-integrable, (

V n ) is i.i.d. with E[V 2 1 ] = σ 2 and E[V 4 1 ] = τ 4 .
The stability of the process is insured by |θ| < 1 and |ρ| < 1. We introduce the least squares estimates

θ n = n k=1 X k X k-1 n k=1 X 2 k-1 , ρ n = n k=1 ε k ε k-1 n k=1 ε 2 k-1 , D n = n k=1 ( ε k -ε k-1 ) 2 n k=0 ε 2 k ,
where the least squares residuals are given at stage n, for all 1 ≤ k ≤ n, by

ε k = X k -θ n X k-1 .
Our objectives is to establish an MDP for these estimates under the restrictive case where (V n ) is gaussian and under the more general hypothesis that (V n ) satisfies a Chen-Ledoux type condition.

Before going further, let us recall here a useful theorem to establish MDP for gaussian martingales, used intensively in the next section.

Theorem 2.4. [Worms [START_REF] Worms | Moderate deviations of some dependent variables. I. Martingales[END_REF][START_REF] Worms | Moderate deviations for stable Markov chains and regression models[END_REF]]. Let (Y n ) be an adapted sequence with values in R p , and (V n ) a gaussian noise with variance σ 2 > 0. We suppose that (Y n ) satisfies, for some invertible square matrix C of order p, the exponential convergence, for any δ > 0,

lim n→∞ 1 b 2 n log P 1 n n-1 k=0 Y k Y ′ k -C > δ = -∞.
Then, the sequence n -1/2 M n n≥1 satisfies an MDP on R p of speed 1/b 2 n and rate function

I(x) = 1 2σ 2 x ′ C -1 x,
where (M n ) is the martingale given by

M n = n k=1 Y k-1 V k .
We also introduce a similar result related to nongaussian martingales which will be useful in the last section.

Theorem 2.5. [Puhalskii [START_REF] Puhalskii | Large deviations of semimartingales via convergence of the predictable characteristics[END_REF]]. Let (m n j ) 1≤j≤n be a triangular array of martingale differences with values in R d , with respect to the filtration (F n ) n≥1 . Let (b n ) be a sequence of real numbers satisfying [START_REF] Bryc | Large deviations and strong mixing[END_REF]. Suppose that there exists a symmetric positive-semidefinite matrix Q such that

1 n n k=1 E m n k (m n k ) ′ F k-1 superexp -→ b 2 n Q.
Suppose that there exists a constant c > 0 such that, for each

1 ≤ k ≤ n, m n k ≤ c √ n b n a.s.
Suppose also that, for all a > 0, we have the exponential Lindeberg's condition

1 n n k=1 E m n k 2 I m n k ≥a √ n bn F k-1 superexp -→ b 2 n 0.
Then, the sequence n -1/2 n k=1 m n k n≥1 satisfies an MDP on R d with speed 1/b 2 n and good rate function

Λ * (v) = sup λ∈R d λ ′ v - 1 2 λ ′ Qλ . In particular, if Q is invertible Λ * (v) = 1 2 v ′ Q -1 v.

Results on the Durbin-Watson testing procedure

In [START_REF] Bercu | A sharp analysis on the asymptotic behavior of the Durbin-Watson statistic for the first-order autoregressive process[END_REF], the following almost sure convergences are established for our estimates,

lim n→∞ θ n = θ * a.s. lim n→∞ ρ n = ρ * a.s. lim n→∞ D n = D * a.s.
where θ * = (1 + θρ) -1 (θ + ρ), ρ * = θρ θ * and D * = 2(1ρ * ). The objective of [START_REF] Bercu | A sharp analysis on the asymptotic behavior of the Durbin-Watson statistic for the first-order autoregressive process[END_REF] was in particular to establish a statistical procedure for testing H 0 : "ρ = 0" against H 1 : "ρ = 0" and we shall recall the associated result in the sequel. To summarize, assume that θ = 0 and θ * = 0. Then, under the null H 0 ,

n 4 θ 2 n D n -2 2 L -→ n→∞ χ 2 1 .
In addition, under the alternative H 1 ,

lim n→∞ n 4 θ 2 n D n -2 2
= +∞ a.s.

On Figure 1 below, the empirical frequencies with which H 0 is rejected for a large simulation study is represented for different values of ρ, in comparison with other usual procedures for testing serial correlation (Durbin's h-test HT, Breusch-Godfrey BG, Ljung-Box LB and Box-Pierce BP). Figure 1 shows that the aforesaid procedure outperforms all tests on small-size samples, and that it is equally powerful than the BG and HT procedures on large samples.

Moderate deviations when (V n ) gaussian

In this section, we need to introduce the following hypothesis.

(H1) The driven noise (V n is i.i.d. with a gaussian distribution,

E[V 1 ] = 0 and E[V 2 1 ] = σ 2 . ( H2
) There exists t > 0 such that E exp(tε 2 0 ) < ∞ and E exp(tX 2 0 ) < ∞.

Moderate deviations for θ n

Theorem 2.6. [Bercu-Proïa [START_REF] Bercu | A sharp analysis on the asymptotic behavior of the Durbin-Watson statistic for the first-order autoregressive process[END_REF]]. Assume that E[V 4 1 ] < ∞. Then, we have the asymptotic normality

√ n θ n -θ * L -→ n→∞ N (0, σ 2 θ )
where

σ 2 θ = (1 -θ 2 )(1 -θρ)(1 -ρ 2 ) (1 + θρ) 3 .
Theorem 2.7. [Bitseki Penda-Djellout-Proïa [START_REF] Penda | Moderate deviations for the Durbin-Watson statistic related to the first-order autoregressive process[END_REF]]. Assume that the hypothesis (H1), (H2) are satisfied. Then, the sequence

√ n θ n -θ * n≥1
satisfies an MDP on R with speed 1/b 2 n and good rate function

I θ (x) = x 2 2σ 2 θ .
Proof. To get an outline of the proof, consider the decomposition

√ n b n θ n -θ * = √ n b n σ 2 1 + θρ M n M n + n S n-1 1 1 + θρ R n b n √ n where M n = n k=1 X k-1 V k is a martingale, S n = n k=0 X 2
k and R n is a residual. We prove that the first term satisfies an MDP by Theorem 2.4, and that the second term is exponentially negligible. Then, we establish the exponential equivalence

√ n b n θ n -θ * superexp ∼ b 2 n 1 ℓ(1 + θρ) M n b n
√ n where ℓ is the almost sure limit of S n /n. We conclude by using the contraction principle. The whole proof may be found in [START_REF] Penda | Moderate deviations for the Durbin-Watson statistic related to the first-order autoregressive process[END_REF].

Moderate deviations for ρ n

Theorem 2.8. [Bercu-Proïa [START_REF] Bercu | A sharp analysis on the asymptotic behavior of the Durbin-Watson statistic for the first-order autoregressive process[END_REF]]. Assume that E[V 4 1 ] < ∞. Then, we have the joint asymptotic normality

√ n θ n -θ * ρ n -ρ * L -→ n→∞ N (0, Γ)
where

Γ = σ 2 θ θρσ 2 θ θρσ 2 θ σ 2 ρ and σ 2 ρ = (1 -θρ) (1 + θρ) 3 (θ + ρ) 2 (1 + θρ) 2 + (θρ) 2 (1 -θ 2 )(1 -ρ 2 ) .
Theorem 2.9. [Bitseki Penda-Djellout-Proïa [START_REF] Penda | Moderate deviations for the Durbin-Watson statistic related to the first-order autoregressive process[END_REF]]. Assume that the hypothesis (H1), (H2) are satisfied. Then, as soon as θ = -ρ, the sequence

√ n θ n -θ * ρ n -ρ * n≥1
satisfies an MDP on R 2 with speed 1/b 2 n and good rate function

K(x) = 1 2 x ′ Γ -1 x.
Proof. To get an outline of the proof, consider the decomposition

√ n b n θ n -θ * ρ n -ρ * = 1 b n √ n A n Z n + √ n b n 1 1 + θρ R 1,n R 2,n
where

A n = A (1,1) n 0 A (2,1) n A (2,2) n , Z n = M n N n ,
and where

M n = n k=1 X k-1 V k and N n = n k=2 X k-2 V k are martingales,
A n is a square matrix, explicitly given, converging almost surely and exponentially to A, and R 1,n and R 2,n are residuals. We prove that the first term satisfies an MDP by Theorem 2.4, and that the second term is exponentially negligible. Then, we establish the exponential equivalence

√ n b n θ n -θ * ρ n -ρ * superexp ∼ b 2 n 1 b n √ n AZ n .
We conclude by using the contraction principle. The whole proof may be found in [START_REF] Penda | Moderate deviations for the Durbin-Watson statistic related to the first-order autoregressive process[END_REF].

Moderate deviations for D n

Theorem 2.10. [Bercu-Proïa [START_REF] Bercu | A sharp analysis on the asymptotic behavior of the Durbin-Watson statistic for the first-order autoregressive process[END_REF]]. Assume that E[V 4 1 ] < ∞. Then, we have the asymptotic normality

√ n D n -D * L -→ n→∞ N (0, σ 2 D )
where σ 2 D = 4σ 2 ρ . Theorem 2.11. [Bitseki Penda-Djellout-Proïa [START_REF] Penda | Moderate deviations for the Durbin-Watson statistic related to the first-order autoregressive process[END_REF]]. Assume that the hypothesis (H1), (H2) are satisfied. Then, the sequence

√ n D n -D * n≥1
satisfies an MDP on R with speed 1/b 2 n and good rate function

I D (x) = x 2 2σ 2 D .
Proof. The result immediately follows from the exponential equivalence

√ n b n D n -D * superexp ∼ b 2 n -2 √ n b n ρ n -ρ * .
The whole proof may be found in [START_REF] Penda | Moderate deviations for the Durbin-Watson statistic related to the first-order autoregressive process[END_REF].

Moderate deviations when (V n ) satisfies a Chen-Ledoux type condition

In this section, we need to introduce the following hypothesis.

(H3) The Chen-Ledoux type condition. For a > 0, lim sup

n→∞ 1 b 2 n log n P |V 1 | a > b n √ n = -∞.
(H4) The initial values satisfy

|ε 0 | a b n √ n superexp -→ b 2 n 0 and |X 0 | a b n √ n superexp -→ b 2 n 0.
Depending on the result we are currently proving, we need to assume that a = 2 or a = 4.

Remark 2.12. For b n = n α and 0 < α < 1/2, the Chen-Ledoux condition for a = 2 is satisfied if there exists t > 0 and 0 < β < 1 such that

E exp(tV 2β 1 ) < ∞. The condition is also satisfied for b n = n α if |V 1 | a b n √ n superexp -→ b 2 n 0.
Theorem 2.13. [Bitseki Penda-Djellout-Proïa [START_REF] Penda | Moderate deviations for the Durbin-Watson statistic related to the first-order autoregressive process[END_REF]]. Assume that the hypothesis (H3), (H4) are satisfied. Then, the MDP established in Theorems 2.7, 2.9 and 2.11 still hold.

Proof. We need to use Theorem 2.5 of Puhalskii [START_REF] Puhalskii | Large deviations of semimartingales via convergence of the predictable characteristics[END_REF] for nongaussian martingales to establish a related MDP, together with a result of Eichelsbacher and Löwe [START_REF] Eichelsbacher | Moderate deviations for i.i.d. random variables[END_REF] related to i.i.d. random variables for which we have no information on the log-Laplace transform, that we state below.

Theorem 2.14. [Eichelsbacher-Löwe [START_REF] Eichelsbacher | Moderate deviations for i.i.d. random variables[END_REF]]. The following results are equivalent.

(1) The i.i.d. real-valued random variables

(Y k ) satisfy E[Y 1 ] < ∞ and lim sup n→∞ 1 b 2 n log n P |Y 1 | > b n √ n = -∞.
(

) The sequence n -1/2 n k=1 Y k -E[Y k ] n≥1 2
satisfies an MDP with speed 1/b 2 n and good rate function I(x) > 0 for all x = 0, and lim

x→-∞ I(x) = lim x→+∞ I(x) = +∞.
Let us just give a sketch of the strategy used to prove our result. We first establish an MDP for our estimates without any gaussianity assumption on the driven noise. To summarize, it is possible to truncate all sequences beyond an unbounded limit, that is, for r, R > 0,

X (r) k = X k I |X k |≤ r √ n bn , V (R) k = V k I {|V k |≤ R} -E V k I {|V k |≤ R} , M (r,R) n = n k=1 X (r) k-1 V (R) k .
Then, by Theorem 2.5 applied to the nongaussian martingale (M (r,R) n

), we establish an MDP on the truncated decomposition. The rate function is given by

I R (x) = x 2 2ℓE (V (R) 1 ) 2 .
Finally, we show that the remaining part of the sequences are exponentially negligible. For all r > 0 and δ > 0, lim sup

R→∞ lim sup n→∞ 1 b 2 n log P 1 b n √ n M n -M (r,R) n > δ = -∞.
The whole and technical proof may be found in [START_REF] Penda | Moderate deviations for the Durbin-Watson statistic related to the first-order autoregressive process[END_REF].

Moderate deviation principle for Bifurcating Markov Chains

The objective of this section is to give deviation inequalities and MDP for Bifurcating Markov Chains (BMC, in short). The results will be obtained under hypothesis of geometric ergodicity or uniform geometric ergodicity of an embedded Markov chain. As statistical applications, we provide deviation inequalities (for either the gaussian setting or the bounded setting), for least square estimators of the parameters of a first order bifurcating autoregressive process.

BMC's model

Bifurcating Markov chains (BMC) are an adaptation of Markov chains to the data of a regular binary tree. They are appropriate for example in the modeling of cell lineage data when each cell in one generation gives birth to two offspring in the next one. Recently, they have received a great deal of attention because of the experiments of biologists on aging of Escherichia Coli (E. Coli in short). E. Coli is a rod-shaped bacterium which reproduces by dividing in the middle, thus producing two cells, one which already existed and that we call old pole progeny cell, and the other which is new and that we call new pole progeny cell. One question of interest is to know if the new pole progeny cells grow at the same rate that the old pole progeny cells. The answer to this question was one of the main motivation of the introduction of BMC by Guyon [START_REF] Guyon | Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging[END_REF]. Let us now formally introduce the BMC.

G r = 2 r , 2 r + 1, • • • , 2 r+1 -1 (resp. T r = 1, 2, • • • , 2 r+1 -1 )
the r-th generation (resp. the first r + 1 generations of the population). Then, the cardinality

|G r | of G r (resp. |T r | of T r ) is |G r | = 2 r (resp. |T r | = 2 r+1 -1).
The generation of a given individual n is G rn with r n = ⌊log 2 n⌋, where ⌊x⌋ denotes the integer part of the real number x.

Let (S, S) be a metric space endowed with its Borel σ-field. We call T-transition probability any mapping P : S × S 2 → [0, 1] such that • P (., A) is measurable for all A ∈ S 2 ,

• P (x, .) is a probability measure on (S 2 , S 2 ) for all x ∈ S.

For a T-transition probability P on S × S 2 , we denote by P 0 , P 1 and Q respectively the first and the second marginal of P , and the mean of P 0 and P 1 , that is P 0 (x, B) = P (x, B × S), P 1 (x, B) = P (x, S × B) for all x ∈ S and B ∈ S and Q = P 0 + P 1 2 .

For p ≥ 1, we denote by B(S p ) (resp. B b (S p )), the set of all S p -measurable (resp. S p -measurable and bounded) mappings f : S p → R. For f ∈ B(S 3 ), when it is defined, we denote by P f ∈ B(S) the function

x → P f (x) = S 2
f (x, y, z)P (x, dydz).

Then, let (X n , n ∈ T) be a family of S-valued random variables defined on a filtered probability space (Ω, F, (F r ) r≥0 , P). Let ν be a probability on (S, S) and P be a T-transition probability. Definition 3.1. We say that (X n , n ∈ T) is a (F r )-bifurcating Markov chain with initial distribution ν and T-transition probability P if (a) X n is F rn -measurable for all n ∈ T, (b) L(X 1 ) = ν, (c) for all r ∈ N and for all family

(f n , n ∈ G r ) ⊆ B b (S 3 ) E n∈Gr f n (X n , X 2n , X 2n+1 ) F r = n∈Gr P f n (X n ).
Remark 3.2. A typical example of bifurcating Markov chain is given by the (stable) first order bifurcating autoregressive process (BAR(1), in short) defined as follows:

L(X 1 ) = ν, and ∀n ≥ 1,

   X 2n = α 0 X n + β 0 + ε 2n X 2n+1 = α 1 X n + β 1 + ε 2n+1 ,
where ν is a distribution probability on R, α 0 , α 1 ∈ (-1, 1); β 0 , β 1 ∈ R and (ε 2n , ε 2n+1 ), n ≥ 1 forms a sequence of centered i.i.d. bivariate random variables with covariance matrix

Γ = σ 2 1 ρ ρ 1 , σ 2 > 0, ρ ∈ (-1, 1).
One can think of a cell of E. Coli "n", that reproduces by dividing into two, thus producing two individuals: one, denoted by 2n + 1, the old pole progeny cell, and the other, denoted by 2n, the new pole progeny cell. For a cell "n", X n denote some quantitative value (growth rate, weight...). An issue in this model is for example whether the values associated to new pole progeny and that associated to old pole progeny evolve in the same way. For this purpose, it is advisable to estimate the parameters θ = (α 0 , β 0 , α 1 , β 1 ), σ 2 and ρ and to test null hypothesis

H 0 = {(α 0 , β 0 ) = (α 1 , β 1 )} against its alternative H 1 = {(α 0 , β 0 ) = (α 1 , β 1 )}.
In order, for example, to study the statistics arising for BAR(1) process, we need to define some empirical means related to BMC (X n , n ∈ T). For all f ∈ B(S) (resp. B(S 3 )), we set

M Tr (f ) = i∈Tr f ( ∆ i ), with f ( ∆ i ) = f (X i ) if f ∈ B(S) f ( ∆ i ) = f (∆ i ) if f ∈ B(S 3 ) where ∆ i = (X i , X 2i , X 2i+1 ), Theorem 3.4.
[Bitseki Penda-Djellout-Guillin [START_REF] Penda | Deviation inequalities, Moderate deviations and some limit theorems for bifurcating Markov chains with application[END_REF]]. We assume that (A1) is fulfilled. Let f ∈ B S 3 such that P f and P f 2 exists and belong to F and (µ, P f ) = 0. Then for all δ > 0 and all r ∈ N P

M Tr (f ) > δ ≤                c ′ δ 2 1 2 r+1 if α 2 < 1 2 ; c ′ δ 2 r 1 2 r+1 if α 2 = 1 2 ; c ′ δ 2 α 2(r+1) if α 2 > 1 2 ;
where the positive constant c ′ depends on f and α. Furthermore, if P f = 0, we have

P M Tr (f ) > δ ≤ c ′ δ 4 1 4 r+1 .
Ideas for the proofs. The proof of Theorems 3.3 and 3.4 is based on two points: Markov inequality and control of fourth order moment (Theorems 3.3) and second order moment (Theorems 3.4) of M Tr (f ). These controls are done using explicit calculations (via successive conditioning) of fourth and second order moments of M Gr (f ) (where Remark 3.5. Notice that the dichotomy around the value α 2 = 1 2 naturally appears in the calculus. Let (H n ) n≥1 be the filtration defined by H 0 = σ(X 1 ) and H n = σ ∆ Π(i) , Π(i + 1), 1 ≤ i ≤ n where ∆ Π(i) = (X Π(i) , X 2Π(i) , X 2Π(i)+1 ) and Π is an application which allows to create a random order on the population T which preserves the genealogical order (we refer to [START_REF] Penda | Deviation inequalities, Moderate deviations and some limit theorems for bifurcating Markov chains with application[END_REF][START_REF] Guyon | Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging[END_REF] for more details on this application). Then, we have the following result on MDP.

M Gr (f ) = 1 |Gr| i∈Gr f (X i )), hypothesis (
n √ n -→ +∞, b n √ n log n -→ 0.
Let f ∈ B S 3 such that P f = 0, P f 2 and P f 4 exist and belong to F . Assume also that lim sup

n→∞ n b 2 n log n ess sup 1≤k≤c -1 (bn+1) P f ∆ Π(k) > b n H k-1 = -∞ where c -1 (b n+1 ) := inf k ∈ N : k b k ≥ b n+1 .
Then for all δ > 0, we have

lim r→∞ |T r | b 2 |Tr| log P 1 b |Tr| |M |Tr| (f )| > δ = - δ 2 2(µ, P f 2 )
.

Ideas for the proof. The proof of Theorem 3.6 is based on deviation inequalities (8) and the MDP for the martingale.

Now, under the stronger assumption (A2), we have the following more sharp estimations.

Proposition 3.12. [Bitseki Penda-Djellout-Guillin [START_REF] Penda | Deviation inequalities, Moderate deviations and some limit theorems for bifurcating Markov chains with application[END_REF]]. We have

P θr -θ > δ ≤                                    c 2 exp c ′′ γ q δ 1-p/2 exp -c ′ γ 2q δ 2-p |T r | , ∀r ∈ N, if α < 1 2 ; c 2 exp c ′ γ q δ 1-p/2 (r + 1) -c ′ γ 2q δ 2-p |T r | , ∀r ∈ N, if α = 1 2 ; c 2 exp -c ′ γ 2q δ 2-p |T r | , ∀r > r 0 , if 1 2 < α < √ 2 2 ; c 2 exp -c ′ γ q δ 2-p |Tr| r+1 , ∀r > r 0 , if α = √ 2 2 ; c 2 exp -c ′ γ 2q δ 2-p 1 α 2(r+1) , ∀r > r 0 , if α > √ 2 2 ;
where c 2 is a positive constant, c ′ and c ′′ depend on α, and c.

Large deviations of the "true" self-repelling motion

In this section, we explain some features related to large deviations of a self-interacting one-dimensional process called the "true" self-repelling motion (TSRM), defined by Bálint Tóth and Wendelin Werner in [START_REF] Tóth | The true self-repelling motion[END_REF] which were established in [START_REF] Dumaz | Large deviations and path properties of the true self-repelling motion[END_REF]. Let us first very briefly recall the intuitive definition of this process and describe the motivations that lead to our study. The TSRM is a continuous real-valued process (X t , t ≥ 0) that is locally self-interacting with its past occupation-time. More precisely, for each positive time t, define its occupation-time measure µ t that assigns to each interval I ∈ R, the time spent in it by X before time t: µ t (I) = t 0 1 {Xs∈I} ds It turns out that for this particular process X, almost surely for each t, the measure µ t has a continuous density x → L t (x) with respect to the Lebesgue measure we will call local time by analogy with semi-martingales. Heuristically, the dynamics of X t is such that the TSRM is locally pushed in the direction of the negative "gradient" of its local time at its current position. Loosely formulated, one can write dX t = -∇ x L t (X t )dt (even if (X t , t ≥ 0) is a random process). For more details and comments on this description, we refer to [START_REF] Tóth | The true self-repelling motion[END_REF].

When a process admits a local time, we may assign a height to the process which simply represents the time spent on the current position. For our process, we will denote by H t this height i.e. H t := L t (X t ). Notice that in this way, one obtains a space-filling 1+1-dimensional curve (X t , H t ).

It turns out that this process is of a very different type than diffusions. For example (see again [START_REF] Tóth | The true self-repelling motion[END_REF]), its quadratic variation almost surely vanishes whereas its variation of power 3/2 is positive and finite. Similarly, it does not have the Brownian scaling property, it has instead a 2/3 scaling behavior i.e., for any positive λ, (X λt , t ≥ 0) has the same law as (λ 2/3 X t , t ≥ 0).

The construction of the process X t is based on a family of coalescing one-dimensional Brownian motions starting from all points in the plane. Such families had been constructed by Arratia and are now called "Brownian web". As a consequence, the estimates on the TSRM follow from results concerning this Brownian web.

The TSRM seems at present to be one of the few such "non-diffusive" continuous processes that probabilists can define. This gives us some motivation to study in more detail its behavior. There exists two main versions of the TSRM, a stationary one and a zero-initial conditions one (see [START_REF] Dumaz | Large deviations and path properties of the true self-repelling motion[END_REF]). For the sake of simplicity, we only state here the results of [START_REF] Dumaz | Large deviations and path properties of the true self-repelling motion[END_REF] about the stationary TSRM.

First, let us write both for the process (X t , t ≥ 0) itself as for the height process (H t , t ≥ 0) upper and lower bounds for the probability that their value at a given time is very large. More precisely, we have: where a ′ 1 is the first negative root of the derivative of the Airy function. Moreover, there exist c 1 , c ′ 1 , c 2 and c ′ 2 such that for all h > 0, exp(-c 1 h 3/2 ) ≤ P(H 1 > h) ≤ exp(-c ′ 1 h 3/2 ) exp(-c 2 h 3/2 ) ≤ P(H 1 < -h) ≤ exp(-c ′ 2 h 3/2 ).

This enables us to derive almost sure fluctuation results (of the type of the law of the iterated logarithm) for these two processes. Note that we need a 0 -1-law arguments to derive the result about the height process. Let us point out that the process X does not have independent increments, so that the standard proof of the LIL for Brownian motion can not be adapted directly for the lower bound.

  ,j) ) c . Using coupling arguments, we reduce the problem of studing the MDP for mn j=1 S * K (ℓn) I(n,j) where the random variables S * (K (ℓn) I(n,j) ) 1≤j≤mn are independent with the same distribution as the random variables S ′ (K (ℓn) I(n,j) ). We need to show that a n mn j=1 log E exp tS ′ K (ℓn)

n→∞ 1 b 2 nDefinition 2 . 3 .b 2 n

 2232 log P Z n -Z > δ = -∞,and we note Z n superexp We say that Y n and Z n are (b 2 n )-exponentially equivalent if Y n -Z n is negligible with respect to the large deviations, that is, for all δ > 0, lim supn→∞ 1 log P Y n -Z n > δ = -∞,and we note Y n

Figure 1 .

 1 Figure 1. Simulation study for n = 30 and n = 500 (p = 1, p = 3).

Figure 2 .

 2 Figure 2. The binary tree T

  A1) and hypothesis (i)-(vi) on F , and the relation M Tr (f ) = r q=0 |Gq| |Tr| M Gq (f ).

Theorem 3 . 6 .

 36 [Bitseki Penda-Djellout-Guillin [4]]. Let (b n ) be a sequence of increasing positive real numbers satisfying b

Proposition 4 . 1 ( 1 | 3 27 x 3 +

 4113 Dumaz). When x → ∞,P(X 1 ≥ x) ≤ exp -4|a ′ O(ln(x))

Proposition 4 . 2 (

 42 Dumaz). Almost surely, we have:lim sup t→0 t -2/3 (ln(ln(1/t))) -1/3 X t = 3/(2 2/3 |a ′ 1 |) lim sup t→+∞ t -2/3 (ln(ln(t))) -1/3 X t = 3/(2 2/3 |a ′ 1 |).And there exist two positive constants m and m ′ such that almost surely,lim sup t→0 t -1/3 (ln(ln(1/t))) -2/3 H t = m lim sup t→+∞ t -1/3 (ln(ln(t))) -2/3 H t = m ′ .

and

M Tr (f ) = |T r | -1 M Tr (f ).

Under suitable regularity assumptions, Guyon, J. [START_REF] Guyon | Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging[END_REF] proved laws of large numbers and CLT for empirical averages M Tr (f ). Our objectives in this section are:

• on the one hand, to specify the order of magnitude in this law of large numbers by given deviation inequalities for M Tr (f ), that is non asymptotic estimation of the form

where h, c and s will be specify later; • on the other hand to give MDP for

where the sequence (b n ) will be specify later.

We will work with the subspace F of B(S) which verifies

)) for all x ∈ S, and P (F ⊗ F ) ⊂ F , (iv) there exists a probability µ on (S, S) such that F ⊂ L 1 (µ) and lim

We introduce the following hypothesis (where µ is the probability measure given in above hypothesis (iv)):

(A1) Geometric ergodicity of Q: ∀f ∈ F such that (µ, f ) = 0, ∃g ∈ F such that ∀r ∈ N and ∀x ∈ S, |Q r f (x)| ≤ α r g(x) for some α ∈ (0, 1).

(A2) Uniform geometric ergodicity of Q: ∀f ∈ B b (S) such that (µ, f ) = 0, ∃c > 0 such that |Q r f (x)| ≤ cα r for some α ∈ (0, 1) and for all x ∈ S.

Main results

Theorem 3.3. [Bitseki Penda-Djellout-Guillin [START_REF] Penda | Deviation inequalities, Moderate deviations and some limit theorems for bifurcating Markov chains with application[END_REF]]. Let f ∈ F such that (µ, f ) = 0. We assume hypothesis (A1). Then for all r ∈ N

where the positive constant c ′ depends on α and f .

When f depends on the mother-daughters triangle (∆ i ), we have the following.

Then for all δ > 0 we have

where r 0 := log (δ/c 0 ) / log(α), and c 0 , c ′ and c ′′ are positive constants which depend on α, f ∞ and c. If f ∈ B b S 3 such that (µ, P f ) = 0 then we have the same conclusions for M Tr (f ).

Ideas for the proof. The proof is based on Chernoff inequality, successive conditioning and successive applications of Azuma-Bennet-Hoeffding using (A2).

Remark 3.8. Once again, notice that the dichotomy around α = 1 2 and α 2 = 1 2 in (9) naturally appears from the calculations. Theorem 3.9. [Bitseki Penda-Djellout-Guillin [START_REF] Penda | Deviation inequalities, Moderate deviations and some limit theorems for bifurcating Markov chains with application[END_REF]]. Let (b n ) be an increasing sequence of positive real numbers such that

) such that P f = 0. Then 2(µ,P f 2 ) .

Remark 3.10. The conditions (v2)-(v4) come from deviation inequalities [START_REF] Dedecker | Coupling for τ -dependent sequences and applications[END_REF].

Ideas for the proof. The proof is based on deviation inequalities (9) and MDP for bounded martingale.

Application

We consider the first order bifurcating autoregressive process (BAR(1)).

L(X 1 ) = ν, and ∀n ≥ 1,

where α 0 , α 1 ∈ (-1, 1); β 0 , β 1 ∈ R, ((ε 2n , ε 2n+1 )) n≥1 forms a sequence of i.i.d. bivariate random variables and ν a probability measure on R. This model is a typical example of bifurcating markovian dynamics and it has been the motivation for the rigorous mathematical study of BMC in [START_REF] Guyon | Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging[END_REF]. We assume that ν has finite moments of all orders. The least square estimator θr of θ = (α 0 , β 0 , α 1 , β 1 ) is given by, for η ∈ {0, 1}

The BAR [START_REF] Arcones | The large deviation principle for stochastic processes I[END_REF] processes are an adaptation of autoregressive processes, when the data have a binary tree structure. They were first introduced by Cowan and Staudte [START_REF] Guyon | Statistical study of cellular aging[END_REF] for cell lineage data where each individual in one generation gives rise to two offspring in the next generation.

In [START_REF] Guyon | Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging[END_REF], Guyon, after establishing the first results on the theory of BMC, proves laws of large numbers and CLT for the least-square estimators θr = (α r 0 , βr 0 , αr 1 , βr 1 ) of the 4-dimensional parameter θ = (α 0 , β 0 , α 1 , β 1 ). He also gives some statistical tests which allow to check if the model is symmetric or not (roughly α 0 = α 1 or not), and if the new pole and the old pole populations are even distinct in mean, which allows him to conclude a statistical evidence in aging in E. Coli.

The gaussian setting

First we consider that ((ε 2n , ε 2n+1 )) n≥1 forms a sequence of i.i.d. bivariate random variables with law N 2 (0, Γ) with

We take Let us define two continuous functions µ 1 : Θ → R and µ 2 : Θ×R * + → R by writing (µ, x) = µ 1 (θ) and (µ, x 2 ) = µ 2 (θ, σ 2 ), where θ = (α 0 , β 0 , α 1 , β 1 ) ∈ Θ = (-1, 1) × R × (-1, 1) × R, and µ is the stationary distribution of Q. Then, we have the following deviation inequalities. Proposition 3.11. [Bitseki Penda-Djellout-Guillin [START_REF] Penda | Deviation inequalities, Moderate deviations and some limit theorems for bifurcating Markov chains with application[END_REF]]. For all δ > 0, for all r ∈ N and for all γ < min c1b 1+δ , c1b

δ , where c 1 = c 1 (µ 1 ) > 0, we have

where c = c(α, µ 1 , µ 2 ) > 0, p = p(δ) ∈ {0, 2, 4} and q = q(δ) ∈ {0, 1}. √ δ where c 1 is a positive constant which depends on µ 1 , let r 0 := log γ q δ 1-p/2 /c 0 log α , where c 0 = c 0 (α, c, γ), p ∈ {0, 1, 3/2} and q ∈ {0, 1}. Then we have the following deviation inequalities.


Emmanuel Frénod

AN ATTEMPT AT CLASSIFYING HOMOGENIZATION-BASED NUMERICAL MATHODS

Keywords: 2000 Mathematics Subject Classification. Primary: 65L99, 65M99, 65N99 Homogenization-Based Numerical Mathods, Homogenization, Asymptotic Analysis, Asymptotic Expansion, Numerical Simulation

An Attempt at Classifying Homogenization-Based

Numerical Methods

1.

Introduction. A Homogenization-Based Numerical Method is a numerical method that incorporates in its conception concepts coming from Homogenization Theory. Doing this gives to the built method the capability to tackle efficiently heterogeneities or oscillations. This approach can be applied to problems occurring in a heterogeneous medium, that have oscillating boundary conditions or that are constrained to oscillate by an external action (for instance a magnetic field on a charged particle cloud). This topic is currently active. The goal of this special issue is to emphasis recent advances in this topic in a wide variety of application fields. This introductory paper introduces a classification of Homogenization-Based Numerical Methods, in which stand: Direct Homogenization-Based Numerical Methods; H-Measure-Based Numerical Methods; Two-Scale Numerical Methods and TSAPS: Two-Scale Asymptotic Preserving Schemes.

2. Direct Homogenization-Based Numerical Methods. The context of Direct Homogenization-Based Numerical Methods is depicted in the next diagram:

u ε solution to O ε u ε = 0 ε → 0 / / u solution to O u = 0 u∆z solution to O ∆z u ∆z = 0 ∆z → 0 O O ∆z → 0 O O ∆z → 0 O O ∆z → 0 O O (2.1)
It is when we face with an operator O ε that generates in solution u ε of equation O ε u ε = 0 oscillations or heterogeneities of characteristic size ε -which is small -and when it is known that, in some sense, for small ε, u ε (z) is close to u(z) for which is known a well-posed problem O u = 0. In this context, it is possible, in place of building a numerical approximation of operator O ε , to build a numerical operator O ∆z approximating O. Then solving O ∆z u ∆z gives a solution u ∆z (z) which is close to u and consequently to u ε (z), when ε is small. This approach permits to obtain an approximation of u ε (z) without resolving the oscillations the model to compute it contains.

In the case when a corrector result is known, i.e, if in association with u(z), a function u 1 (z), solution to well-posed equation O 1 u 1 = 0, is such that u ε (z) is close to u(z) + εu 1 (z) for small ε, it is possible build two numerical operators O ∆z and O 1 ∆z that are discretizations of O and O 1 . Using them, we can compute approximated solutions u ∆z (z) and u 1 ∆z (z) of u(z) and u 1 (z) and obtain a good approximation of u ε (z) computing u ∆z (z) + εu 1 ∆z (z). Such a method is called order-1 Direct Homogenization-Based Numerical Methods and is illutrated by the following diagram.

u ε solution to O ε u ε = 0 ε → 0 / / u, u1 solutions to O u = 0 O 1 u 1 = 0 u∆z, u∆z solution to O ∆z u ∆z = 0 O 1 ∆z u 1 ∆z = 0 ∆z → 0 O O ∆z → 0 O O ∆z → 0 O O ∆z → 0 O O (2.2)
The paper by Legoll & Minvielle [START_REF] Legoll | Variance reduction using antithetic variables for a nonlinear convex stochastic homogenization problem[END_REF], by Laptev [START_REF] Laptev | Discrete and Continuous Dynamical Systems -Serie S. Special Issue on Numerical Methods based on Homogenization and Two-Scale Convergence[END_REF], by Bernard, Frénod & Rousseau [START_REF] Bernard | Paralic confinement computations in coastal environment with interlocked areas[END_REF], and by Xu & Yue [START_REF] Xu | Discrete and Continuous Dynamical Systems -Serie S. Special Issue on Numerical Methods based on Homogenization and Two-Scale Convergence[END_REF] of this special issue may enter this framework 3. H-Measure-Based Numerical Methods. The context of those kind of methods is when the transition from a microscopic scale (of size ε) to a macroscopic one (of size 1) -with quantities of interest at the microscopic scale that are not the same as the quantities of interest at the macroscopic scale -needs to be described. This occurs for instance in the simulation of phenomena some parts of which call upon quantum description or in the simulation of turbulence. This context can be represented by the following diagram:

u ε solution to O ε u ε = 0 e ε = E(u ε ) ε → 0 / / e solution to M e = 0 u ε ∆z solution to M ε ∆z e ε ∆z = 0 ∆z → 0 O O ε → 0 / / u∆z solution to
M ∆z e ∆z = 0

∆z → 0 O O ∆z → 0 O O ∆z → 0 O O ∆z → 0 O O (3.1)
and explained as follows. The part in the top left of diagram (3.1) symbolizes a problem which is set at the microscopic level. This problem writes O ε u ε = 0 and generates oscillations in its solution u ε . Besides, the quantity that makes sense at the macroscopic level is e ε ; it is related to u ε by a non-linear relation e ε = E(u ε ) and it is, in some sense, close to e solution to M e = 0 (see the top right of the diagram) which represents the model at the macroscopic level.

Then, the goal of a H-Measure-Based Numerical Method consists in building a numerical operator M ε ∆z , giving a numerical solution e ε ∆z close to e ε , for any ε as soon as ∆z is small (see the bottom left of the diagram), which behaves as a numerical approximation of M when ε is small (see the bottom right of the diagram).

The paper by Tartar [START_REF] Tartar | Multi-scales h-measures. Discrete and Continuous Dynamical Systems -Serie S. Special Issue on Numerical Methods based on Homogenization and Two-Scale Convergence[END_REF] of this special issue lays the foundation of the theory for those kinds of methods.

4. Two-Scale Numerical Methods. The papers by Assyr, Bai & Vilmar [START_REF] Abdulle | Discrete and Continuous Dynamical Systems -Serie S. Special Issue on Numerical Methods based on Homogenization and Two-Scale Convergence[END_REF], Back & Frénod [START_REF] Back | Geometric two-scale convergence on manifold and applications to the Vlasov equation[END_REF], Faye, Frénod & Seck [START_REF] Faye | Two-scale numerical simulation of sand transport problems. Discrete and Continuous Dynamical Systems -Serie S. Special Issue on Numerical Methods based on Homogenization and Two-Scale Convergence[END_REF], Frénod, Hirtoaga & Sonnendrücker [START_REF] Frénod | An exponential integrator for a highly oscillatory Vlasov equation. Discrete and Continuous Dynamical Systems -Serie S. Special Issue on Numerical Methods based on Homogenization and Two-Scale Convergence[END_REF], Lutz [START_REF] Lutz | Application of Lie transform techniques for simulation of a charged particle beam. Discrete and Continuous Dynamical Systems -Serie S. Special Issue on Numerical Methods based on Homogenization and Two-Scale Convergence[END_REF] and Henning & Ohlberger [START_REF] Henning | Discrete and Continuous Dynamical Systems -Serie S. Special Issue on Numerical Methods based on Homogenization and Two-Scale Convergence[END_REF] of this special issue are related to this framework of Two-Scale Numerical Methods.

An order-0 Two-Scale Numerical Method may be explained using the following diagram:

u ε solution to O ε u ε = 0 ε → 0 / / ε → 0 , two-scale ) ) R R R R R R R R u solution to O u = 0 U solution to O U = 0 Z dζ 6 6 n n n n n n u∆z solution to O ∆z u ∆z = 0 ∆z → 0 O O U∆z solution to O ∆z U ∆z = 0 ∆z → 0 O O Num Z dζ 6 6 n n n n n n (4.1)
The context includes the one of Direct Homogenization-Based Numerical Methods and diagram (4.1) has to be regarded as a prism. Its deepest layer is nothing but diagram (2.1). Yet, if more is known about the asymptotic behavior of u ε , i.e. if it is known that u ε (z) is close to U (z, z ε ), with U (z, ζ) periodic in ζ, when ε is small (which can be translated as u ε (z) Two-Scale Converges to U (z, ζ)) and if it is known a well posed problem O U = 0 for U (see the middle of the diagram), that gives the equation for u (see the top right of the diagram) when integrated with respect to periodic variable ζ, it is possible to build a specific numerical method. This method consists in building a numerical approximation O ∆z of operator O. Using this operator can give a numerical solution U ∆z (see the bottom of the diagram) and U ∆z (z, z ε ) is an approximation of u ε (z) for small ε. To be consistent with the continuous level, a numerical integration of the O ∆z U ∆z = 0 needs to yield a numerical approximation of the equation for u (see the bottom right of the diagram).

When a little more is known concerning the asymptotic behavior of u ε when ε is small, i.e. if u ε is close to U (z, z ε ) + εU 1 (z, z ε ) with U 1 (z, ζ) also periodic in ζ and if a well-posed problem is known for U 1 , we can enrich diagram (4.1) and obtain the following diagram of order-1 Two-Scale Numerical Methods:

u ε solution to O ε u ε = 0 ε → 0 / / ε → 0 , two-scale ( ( Q Q Q Q Q Q Q Q Q Q u, u1 solutions to O u = 0 O 1 u 1 = 0 U , U 1 solutions to O U = 0 O 1 U 1 = 0 Z dζ 6 6 n n n n n n u∆z, u 1 ∆z solutions to O ∆z u ∆z = 0 O 1 ∆z u 1 ∆z = 0 ∆z → 0 O O U∆z, U 1 ∆z solutions to O ∆z U ∆z = 0 O 1 ∆z U 1 ∆z = 0 ∆z → 0 O O Num Z dζ 6 6 n n n n n n (4.2)
5. TSAPS: Two-Scale Asymptotic Preserving Schemes. To describe Two-Scale Asymptotic Preserving Schemes, it is first needed to describe what is an Asymptotic Preserving Scheme (or AP-Scheme in short).

u ε solution to O ε u ε = 0 ε → 0 / / u solution to O u = 0 u ε ∆z solution to O ε ∆z u ε ∆z = 0 ∆z → 0 O O ε → 0 / / u∆z solution to O ∆z u ∆z = 0 ∆z → 0 O O ∆z → 0 O O ∆z → 0 O O ∆z → 0 O O (5.1)
For this, we comment on diagram (5.1). The context is when we are face-to-face with an operator O ε which is approached, when ε is small, by another operator O which has not the same nature as O ε . An Asymptotic Preserving Scheme to approximate problem O ε u ε = 0 (see the top left of the diagram) is a numerical operator O ε ∆z that gives, when solving O ε ∆z u ε ∆z = 0 (see the bottom right of the diagram) a numerical solution u ε ∆z which is close to u, with an accuracy depending on step ∆z and not on ε. Besides, this operator needs to mimic the behavior of an numerical approximation (see the bottom right of the diagram) of limit problem O u = 0 (see the top right of the diagram) as ε is small. For an introduction to this kind of method the reader is referred to Jin [START_REF]Efficient asymptotic-preserving (ap) schemes for some multiscale kinetic equations[END_REF].

The explanation of TSAPS, will be based on the following diagram:

u ε solution to O ε u ε = 0 ε → 0 / / ε → 0 , two-scale + + W W W W W W W W W W W W W W W W W W W W W W W W W W u, u 1 solutions to O u = 0, O 1 u 1 = 0 U , U 1 solutions to O U = 0 O 1 U 1 = 0 Z dζ 6 6 m m m m m m m m m U ε solution to O ε U ε = 0 ζ = z ε >> > > > > > > > > > > > > > > > > > > ε → 0 7 7 o o o o o o o u ε ∆z solution to O ε ∆z u ε ∆z = 0 ∆z → 0 O O ε → 0 / / u ∆z , u 1 ∆z solutions to O ∆z u ∆z = 0, O 1 ∆z u 1 ∆z = 0 ∆z → 0 O O U ∆z , U 1 ∆z solutions to O ∆z U ∆z = 0 O 1 ∆z U 1 ∆z = 0 ∆z → 0 O O Num Z dζ 6 6 m m m m m m m m U ε ∆z solution to O ε ∆z U ε ∆z = 0 ζ = z ε >> > > > > > > > > > > > > > > > > > > ∆z → 0 O O ε → 0 7 7 o o o o o o (5.
2) This diagram has to be regarded as a prism with three layers. The deepest one is the diagram of the AP-schemes. At the top left of this layer is found the equation that generates in its solution oscillations of size ε. At the top right stands the limit problem, as ε is small. (This limit problem is assumed to be an order-1 problem, i.e. u ε ∼ u 0 + εu 1 for ε small and equations are known for u 0 and u 1 .) At the bottom left stands the AP-Scheme that approximate equation O ε u ε = 0 for any ε and that mimics an approximation of the limit problem when ε is small (see the bottom right of the layer). The middle layer is exactly the diagram of the order-1 Two-Scale Numerical Methods. The top layer is the new part. at the bottom, stands the TSAPS. This is a numerical method that gives a solution U ε ∆z which depends on two variables z and ζ. When taken in ζ = z/ε, U ε ∆z gives a numerical approximation of the solution to the problem given at the top right of the diagram, with an accuracy that only depends on the discretization step ∆z, and not on ε. Moreover, as ε is small, the TSAPS O ε ∆z needs to mimic the behavior of the order-1 Two-Scale Numerical Operator (the couple (O, O 1 )). To builtd a TSAPS, a reformulation of problem O ε u ε = 0 calling upon a Two-Scale Macro-Micro Decomposition (that reads O ε U ε = 0, see the middle of the diagram) is used. A first step towards TSAPS is led in Crouseilles, Frénod, Hirstoaga & Mouton [START_REF] Crouseilles | Two-Scale Macro-Micro decomposition of the Vlasov equation with a strong magnetic field[END_REF].

E-mail address: emmanuel.frenod@univ-ubs.fr