Thème NUM -Systèmes numériques Équipes-Projets CQFD

Keywords: Feynman-Kac measures, nonlinear filtering, interacting particle systems, historical and genealogical tree models, central limit theorems, Gaussian fields, propagations of chaos, trees and forests, combinatorial enumeration

We present a mean field particle theory for the numerical approximation of Feynman-Kac path integrals in the context of nonlinear filtering. We show that the conditional distribution of the signal paths given a series of noisy and partial observation data is approximated by the occupation measure of a genealogical tree model associated with mean field interacting particle model. The complete historical model converges to the McKean distribution of the paths of a nonlinear Markov chain dictated by the mean field interpretation model. We review the stability properties and the asymptotic analysis of these interacting processes, including fluctuation theorems and large deviation principles. We also present an original Laurent type and algebraic tree-based integral representations of particle block distributions. These sharp and non asymptotic propagations of chaos properties seem to be the first result of this type for mean field and interacting particle systems.

Une théorie champ moyen du filtrage non linéaire

Résumé : Nous exposons ici une théorie particulaire de type champ moyen pour la résolution numérique des intégrales de chemins de Feynman utilisées en filtrage non linéaire. Nous démontrons que les lois conditionnelles des trajectoires d'un signal bruité et partiellement observé peuvent être calculées à partir des mesures d'occupation d'arbres généalogiques associés à des systèmes de particules en interaction. Le processus historique caractérisant l'évolution ancestrale complète converge vers la mesure de McKean des trajectoires d'une chaîne de Markov non linéaire dictée par l'interprétation champ moyen du modèle de filtrage. Nous passons en revue les propriétés de stabilité et les résultats d'analyse asymptotique de ces processus en interaction, avec notamment des théorèmes de fluctuations et des principes de grandes déviations. Nous exposons aussi des développements faibles et non asymptotiques des distributions de blocs de particules en termes combinatoire de forêts et d'arbres de coalescences. Ces propriétés fines de propagations du chaos semblent être les premiers résultats de ce type pour des systèmes de particules en interaction de type champ moyen.

Mots-clés :

Mesures de Feynman-Kac, filtrage non linéaire, systèmes de particules en interaction, processus historique et modèles d'arbres généalogiques, théorèmes de la limite centrale, champs gaussiens, propriétés de propagations du chaos, combinatoire d'arbres et de forêt.

Introduction 1.A mean field theory of nonlinear filtering

The filtering problem consists in computing the conditional distributions of a state signal given a series of observations. The signal/observation pair sequence (X n , Y n ) n≥0 is defined as a Markov chain which takes values in some product of measurable spaces (E n ×F n ) n≥0 . We further assume that the initial distribution ν 0 and the Markov transitions P n of the pair process (X n , Y n ) have the form ν 0 (d(x 0 , y 0 )) = g 0 (x 0 , y 0 ) η 0 (dx 0 ) q 0 (dy 0 )

P n ((x n-1 , y n-1 ), d(x n , y n )) = M n (x n-1 , dx n ) g n (x n , y n ) q n (dy n ) (1.1)
where g n are strictly positive functions on (E n × F n ) and q n is a sequence of measures on F n . The initial distribution η 0 of the signal X n , the Markov transitions M n and the likelihood functions g n are assumed to be known.

The main advantage of this general and abstract set-up comes from the fact that it applies directly without further work to traditional real valued or multidimensional problems, as well as to smoothing and path estimation filtering models. For instance the signal X n = (X 0 , . . . , X n ) may represents the path from the origin up to time n of an auxiliary Markov chain X n taking values in some measurable state space (E n , E n ). A version of the conditional distributions η n of the signal states X n given their noisy observations Y p = y p up to time p < n is expressed in terms of a flow of Feynman-Kac measures associated with the distribution of the paths of the signal and weighted by the collection of likelihood potential functions.

To better connect the mean field particle approach to existing alternatives methods, it is convenient at this point to make a couple of remarks.

Firstly, using this functional representation it is tempting to approximate this measures using a crude Monte Carlo method based on independent simulations of the paths of the signal weighted by products of the likelihood functions from the origin up to time n. This strategy gives satisfactory results when the signal paths are sufficiently stable using a simple weight regularization to avoid their degeneracy with respect to the time parameter. We refer to [START_REF] Moral | A Uniform convergence theorem for the numerical solving of the non linear filtering problem[END_REF][START_REF] Moral | Non linear filtering using random particles[END_REF][START_REF] Del Moral | Non linear filtering using Monte Carlo particle methods[END_REF] for further details. Precise comparisons of the fluctuation variances associated with this Monte Carlo method and the mean feld particle models presented in the present article have been studied in [START_REF] Del Moral | Interacting particle filtering with discrete-time observations : asymptotic behaviour in the Gaussian case[END_REF].

Another commonly used strategy in Bayesian statistics and in stochastic engineering is the well-known Monte Carlo Markov chain method (abbreviate MCMC methods). The idea is to interpret the conditional distributions η n as the invariant measure of a suitably chosen Markov chain. This technique as to main drawbacks. The first one is that we need to run the underlying chain for very long times. This burning period is difficult to estimate, and it is often too long to tackle filtering problems with high frequency observation sequences such as those arising in radar processing. The second difficulty is that the conditional distributions η n vary with the time parameter and we need to chose at each time an appropriate MCMC algorithm.

In contrast to the two ideas discussed above, the mean field particle strategy presented in this article can be interpreted as a stochastic and adaptive grid approximation model. Loosely speaking, this particle technique consists in interpreting the weights likelihood as branching selection rates. No calibration of the convergence to equilibrium is needed, the conditional measures variations are automatically updated by the stochastic particle model. The first rigorous study in this field seems to be the article [START_REF] Moral | Non linear filtering: interacting particle solution[END_REF] published in 1996 on the applications of interacting particle methods to nonlinear estimation problems. This article provides the first convergence results for a series of heuristic genetic type schemes presented in the beginning of the 1990's in three independent chains of articles on nonlinear filtering [START_REF] Gordon | Novel approach to nonlinear/non-Gaussian Bayesian state estimation[END_REF][START_REF] Gordon | Bayesian state estimation for tracking and guidance using the bootstrap filter[END_REF], [START_REF] Kitagawa | Monte-Carlo filter and smoother for non-Gaussian nonlinear state space models[END_REF], and [START_REF] Carvalho | Optimal nonlinear filtering in GPS/INS integration[END_REF][START_REF] Kolokoltsov | Idempotent Analysis and Its Applications[END_REF][START_REF] Del Moral | Résolution particulaire et traitement non-linéaire du signal : application radar/sonar[END_REF][START_REF] Del Moral | Estimation et commande optimale non linéaire[END_REF]. In the end of the 1990's, three other independent works [START_REF] Crisan | A particle approximation of the solution of the Kushner-Stratonovitch equation[END_REF][START_REF] Crisan | Nonlinear filtering and measure valued processes[END_REF][START_REF] Crisan | A particle approximation of the solution of the Kushner-Stratonovitch equation[END_REF] proposed another class of particle branching variants for solving continuous-time filtering problems.

For a more thorough discussion on the origins and the analysis these models, we refer the reader to the research monograph of the first author [START_REF] Moral | Feynman-Kac formulae[END_REF]. The latter is dedicated to Feynman-Kac and Boltzmann-Gibbs measures with their genealogical and interacting particle system interpretations, as well as their applications in physics, in biology and in engineering sciences. Besides their important application in filtering, Feynman-Kac type particle models also arise in the spectral analysis of Schrdinger type operators, rare events estimation, as well as in macromolecular and directed polymers simulations. In this connection, we also mention that the mean field theory presented here applies without further work to study the analysis of a variety of heuristic like models introduced in stochastic engineering since the beginning of the 1950's, including genetic type algorithms, quantum and sequential Monte Carlo methods, pruned enrichment molecular simulations, bootstrap and particle filters, and many others. For a rather thorough discussion on these rather well known application areas, the interested reader is also recommended to consult the book [START_REF] Doucet | Sequential Monte Carlo Methods in Pratice[END_REF], and the references therein. These study can be completed with the more recent articles of the first author with A. Doucet and A. Jasra [START_REF] Del Moral | Sequential Monte Carlo for Bayesian Computation[END_REF][START_REF] Del Moral | Sequential Monte Carlo Samplers[END_REF] on sequential Monte Carlo techniques and their applications in Bayesian computation. We also mention that the continuous time version of the material presented in this review article can also be found in the series of articles of the first author with L. Miclo [START_REF] Del Moral | Strong Propagations of Chaos in Moran's type Particle interpretations of Feynman-Kac measures[END_REF][START_REF] Del Moral | Branching and interacting particle systems approximations of Feynman-Kac formulae with applications to nonlinear filtering[END_REF][START_REF] Del Moral | A Moran particle system approximation of Feynman-Kac formulae[END_REF][START_REF] Del Moral | Particle approximations of Lyapunov exponents connected to Schrödinger operators and Feynman-Kac semigroups[END_REF]. For instance, the first reference [START_REF] Del Moral | Branching and interacting particle systems approximations of Feynman-Kac formulae with applications to nonlinear filtering[END_REF] provides an original mean field particle interpretation of the robust nonlinear filtering equation.

This first key idea towards a mean field particle approach to nonlinear filtering is to recall that the flow of conditional measures η n satisfies a dynamical system in distribution space, often called the nonlinear filtering equations. As in physics and more particularly in fluid mechanics, the second step is to interpret these equations as the evolution of he laws of a nonlinear Markov process. More formally, this preliminary stage simply consists in expressing the nonlinear filtering equations in terms of a transport model associated with a collection of Markov kernels K n+1,ηn indexed by the time parameter n and the set of measures η n on the space E n ; that is, we have that

η n+1 = η n K n+1,ηn (1.2)
The mean field particle interpretation of this nonlinear measure valued model is an

E N n -valued Markov chain ξ (N ) n = ξ (N,i) n 1≤i≤N
, with elementary transitions

INRIA defined as P ξ (N ) n+1 ∈ d(x 1 , . . . , x N )|ξ (N ) n = N i=1 K n+1,η N n (ξ (N,i) n , dx i ) (1.3) with η N n := 1 N N j=1 δ ξ (N,j) n
The initial system ξ (N ) 0 consists of N independent and identically distributed random variables with common law η 0 . The state components of this Markov chain are called particles or sometimes walkers. The rationale behind this is that η N n+1 is the empirical measure associated with N independent variables with distributions K n+1,η N n (ξ

(N,i) n , .
), so as soon as η N n is a good approximation of η n then, in view of (1.3), η N n+1 should be a good approximation of η n+1 . This strategy is not restricted to nonlinear filtering models and it applies under appropriate regularity conditions to any kind of measure valued model of the form (1.2). In our context, the evolution of the particles is dictated by the well known pair prediction-updating transitions associated with the optimal filter equations. The prediction transition is associated with a mutation transition of the whole population of particles. During this stage, the particles explore the state space independently of one another, according to the same probability transitions as the signal. The filter updating stage is associated with a branching type selection transition. During this stage, each particle evaluates the relative likelihood value of its location. The ones with poor value are killed, while the ones with high potential duplicate.

Using this branching particle interpretation, we notice that the ancestral lines of each particle form a genealogical tree evolving as above by tracking back in time the whole ancestor line of current individuals. In other words, the genealogical tree model associated with the branching process described above is the mean field particle interpretation of the nonlinear filtering equation but in path space. Using this simple observation, we readily prove that the genealogical tree occupation measure converges, as the population size tends to infinity, to the conditional distribution of the paths the signal (X p ) 0≤p≤n given the observations delivered by the sensors up to time n. Another important mathematical object is the complete genealogical tree structure defined by the whole population model from the origin up to the current time horizon. The occupation measure of this ancestral tree keep tracks of the whole history of the particle and its convergence is technically more involved. We can prove that it converges, as the population size tends to infinity, to the McKean distribution of the paths of a nonhomogeneous Markov chain with transition probabilities K n+1,ηn , and starting with the initial distribution η 0 .

In the present article, we provide a synthetic review of the stability properties and the convergence analysis of these mean field interacting particle models going from the traditional law of large numbers to more sophisticated empirical process theorems, uniform estimates with respect to the time parameter, central limit theorems, Donsker type theorems, as well as large-deviation principles. We also analyze the increasing and strong propagation of chaos properties, including an original algebraic tree-based functional representations of particle block distributions, stripped of all analytical superstructure, and probabilistic irrelevancies. These Laurent type integral representations seems to be the first sharp and precise propagations of chaos estimates for this type of mean field particle models. We emphasized that most of the material presented in this review is taken from the book of the first author [START_REF] Moral | Feynman-Kac formulae[END_REF], and results from various collaboration with Donald Dawson, Jean Jacod, Michel Ledoux, Laurent Miclo, and Alice Guionnet. We refer to [START_REF] Moral | Feynman-Kac formulae[END_REF] for a detailed historical account with precise reference pointers. The sharp propagation of chaos expansions presented in the second part of this article are taken from the article [START_REF] Del Moral | Coalescent Tree Based Functional Representations for some Feynman-Kac Particle Models[END_REF]. The latter also discusses Hilbert series techniques for counting forests with prescribed numbers of vertices at each level, or with prescribed coalescence degrees, as well as new wreath products interpretations of vertex permutation groups. In this connection, we mention that forests and their combinatorics have also appeared recently in various fields such as in theoretical physics and gaussian matrix integral models [START_REF] Guionnet | Combinatorial aspects of matrix models[END_REF], renormalization theory in high-energy physics or Runge-Kutta methods, two fields where the structure and complexity of perturbative expansions has required the development of new tools [START_REF] Ch | Runge-Kutta methods and renormalization[END_REF][START_REF] Connes | Hopf algebras, renormalization and noncommutative geometry[END_REF].

The article is divided into four main parts, devoted respectively to the precise description of Feynman-Kac path integral models and their mean field particle interpretations, to the stability analysis of non linear semigroups, to the asymptotic analysis of mean field interacting processes, and to propagation of chaos properties.

Contents

Notation and conventions

For the convenience of the reader we have collected some of the main notation and conventions used in the article. We denote respectively by M(E), P(E), and B(E), the set of all finite signed measures on some measurable space (E, E), the convex subset of all probability measures, and the Banach space of all bounded and measurable functions f on E, equipped with the uniform norm f = sup x∈E |f (x)|. We also denote Osc 1 (E), the convex set of E-measurable functions f with oscillations less than one; that is,

osc(f ) = sup {|f (x) -f (y)| ; x, y ∈ E} ≤ 1 We let µ(f ) = µ(dx) f (x), be the Lebesgue integral of a function f ∈ B(E),
with respect to a measure µ ∈ M(E), and we equip the Banach space M(E) with the total variation norm

µ tv = sup f ∈Osc1(E) |µ(f )|. We recall that a integral operator Q from a measurable space E 1 into an auxiliary measurable space E 2 into itself, is an operator f → Q(f ) from B(E 2 ) into B(E 1 ) such that the functions Q(f )(x) = E2 Q(x 1 , dx 2 ) f (x 2 ) ∈ R are E 1 -measurable and bounded, for any f ∈ B(E 2 ). It also generates a dual operator µ → µQ from M(E 1 ) into M(E 2 ) defined by (µQ)(f ) := µ(Q(f )).
We denote by β(M

) := sup x,y∈E1 M (x, .) -M (y, .) tv ∈ [0, 1] the Dobrushin coefficient associated with a Markov transition M from E 1 into E 2 .
For further use in various places of this article we recall that β(M ) is the norm of both the operator µ → µM on the set of measures with null mass or the operator f → M (f ) on the set of functions f ∈ Osc 1 (E 1 ). Thus, we have that

∀f ∈ Osc 1 (E 1 ) osc(M (f )) ≤ β(M ) osc(M (f ))
For a proof of this rather well known inequality, we refer the reader to proposition 4.2.1 [START_REF] Moral | Feynman-Kac formulae[END_REF]. We also simplify the notation and we write for any f, g ∈ B(E 2 ) and

x ∈ E 1 Q[(f -Qf ) (g -Qg)](x) instead of Q[(f -Q(f )(x)) (g -Q(g)(x))](x) = Q(f g)(x) -Q(f )(x) Q(g)(x)
The q-tensor power Q ⊗q , with q ≥ 1, represents the bounded integral operator on E q 1 into E q 2 , defined for any F ∈ B(E q 2 ) by

Q ⊗q (F )(x 1 , . . . , x q ) = E q 2 Q(x 1 , dy 1 ) . . . Q(x q , dy q ) F (y 1 , . . . , y q )
For a pair of integral operators

Q 1 from E 1 into E 2 , and Q 2 from E 2 into E 3 , we denote by Q 1 Q 2 the composition integral operator from E 1 into E 3 defined for any f ∈ B(E 3 ) by (Q 1 Q 2 )(f ) := Q 1 (Q 2 (f )).
With respect to the N -particle model introduced in (1.2), as soon as there is no possible confusion we simplify notation and suppress the index (.) (N ) and write (ξ n , ξ i n ) instead of (ξ

(N ) n , ξ (N,i) n
). To clarify the presentation, we often suppose that all the random processes including the signal and the particle processes are defined on some common probability space, and we denote by E(.) and P(.) the integral expectation and the probability measure on this common probability space. Last but not least, we fix a series of observations Y n = y n , with n ≥ 0, and unless otherwise is stated all the results presented in this article are quenched in the sense that they depend of the observation sequence. The following classical conventions ( ∅ , ∅ ) = (0, 1) are also used.

Feynman-Kac and mean field particle models

This section is concerned with Feynman-Kac formulations of the filtering equations with their mean field particle interpretations. The functional representations of both the one-step predictor and the optimal filter are discussed in the first subsection. In the second subsection, we discuss some advantages of these abstract models in the analysis of smoothing and path space filtering problems including continuous time signal-observation models. The mean field interacting particle systems and the corresponding genealogical tree based models are described in the final subsection.

Description of the models

We let G n be the non homogeneous function on E n defined for any

x n ∈ E n by G n (x n ) = g n (x n , y n ).
(

Note that G n depends on the observation value y n at time n. To simplify the presentation, and avoid unnecessary technical discussion, we shall suppose that the likelihood functions are chosen so that there exists a sequence of strictly positive constants n (G) ∈ (0, 1] that may depend on the observation values y n and such that for any x n , x n ∈ E n we have that

G n (x n ) ≥ n (G) G n (x n ) > 0
The archetype of such nonlinear filtering model is the situation where Y n is a real valued observation sequence described by a dynamical equation

Y n = h n (X n ) + V n
where V n represents a sequence of centered gaussian random variables with

E(V 2 n ) := σ n > 0 and h n ∈ B(E n ).
In this situation, (1.1) and the above condition are clearly met with the Lebesgue measure q n on R and the likelihood potential function given by

G n (x n ) = exp - 1 2σ 2 n (y n -h n (x n )) 2
Notice that in this case we have

n (G) ≥ exp σ -2 n osc(h n ) (y n + h n )
In this notation, versions of the one step predictor η n ∈ P(E n ) and the optimal filter η n ∈ P(E n ) given for any

f n ∈ B(E n ) by η n (f n ) := E(f n (X n ) | Y p = y p , 0 ≤ p < n) INRIA and η n (f n ) := E(f n (X n ) | Y p = y p , 0 ≤ p ≤ n)
have the functional representations

η n (f n ) = γ n (f n )/γ n (1) and η n (f n ) = γ n (f n )/ γ n (1) (2.2)
with the Feynman-Kac measures γ n and γ n defined by the formulae

γ n (f n ) = E[f n (X n ) 0≤k<n G k (X k )] and γ n (f n ) = γ n (f n G n ) (2.3)
A simple change of measure shows that the optimal filter can also be rewritten in the following prediction type form :

η n (f n ) = E[f n ( X n ) 0≤k<n G k ( X k )]/E[ 0≤k<n G k ( X k )] (2.4)
In the above display, the signal X n is a Markov chain with initial distribution η 0 and the elementary transitions

M n (x n-1 , dx n ) = M n (x n-1 , dx n ) G n (x n ) M n (G n )(x n-1 ) and G n (x n ) = M n+1 (G n+1 )(x n )
(2.5) This simple observation shows that all the analysis on the one step predictor flow remains valid without further work to study the optimal filter. Another simple calculation shows that the unnormalized flow can be computed in terms of the normalized distributions. More precisely, we easily deduce the following multiplicative formulae :

γ n (f ) = η n (f ) n-1 p=0 η p (G p ) (2.6)

Path space and related filtering models

Firstly, it is important to notice that the abstract Feynman-Kac formulation presented in section 2.1 is particularly useful for describing Markov motions on path spaces. For instance, X n may represent the historical process

X n = (X 0 , . . . , X n ) ∈ E n = (E 0 × . . . × E n ) (2.7)
associated with an auxiliary Markov chain X n which takes values in some measurable state spaces E n . In this situation, we have that

η n = Law((X 0 , . . . , X n ) | Y p = y p , 0 ≤ p ≤ n)
As we shall see, this apparently innocent observation is essential for modelling and analyzing genealogical evolution processes. Another important state space enlargement allowed by our abstract formulation is the following. We let p n be an increasing sequence of integers such that p 0 = 0, and we consider the pair signal observation model (X n , Y n ) is given by

X n = (X q ) pn≤q<pn+1 ∈ E n := pn≤q<pn+1 E q RR n°0123456789 and Y n = (Y q ) pn≤q<pn+1 ∈ F n := pn≤q<pn+1 F q
We further assume that the auxiliary pair signal observation model (X n , Y n ) is defined as in (1.1) with a pair transition-likelihood function (M n , g n ). In this situation, if we choose in (2.

2) the multiplicative likelihood potential functions

G n (X n ) = pn≤q<pn+1 g q (x q , y q )
then we have that

η n = Law((X q ) 0≤q≤pn+1 | Y q = y q , 0 ≤ q < p n+1 ) (2.8)
As we shall see in the further development of section 2.3, one advantage of the mean field particle interpretation of this model comes from the fact that it only updates the sampled path predictions at the chosen times p n . The "optimal" choice of the updating times depend on the filtering problem. For instance, in radar processing we current observation measures a noisy distance to the target. Thus, the speed and acceleration components are observable only after a series of three observations. The traditional nonlinear filtering problem in continuous time is again defined in terms of a pair signal/observation Markov process (S t , Y t ) taking values R d+d . The signal S t is given by a time homogeneous Markov process with right continuous and left limited paths taking values in some Polish space E, and the observation process is an R d -valued process defined by

dY t = h t (S t ) dt + σ dV t
where V t is a d -vector standard Wiener process independent of the signal, and h t is a bounded measurable function from E into R d . The Kallianpur-Striebel formula (see for instance [START_REF] Kallianpur | Stochastic differential equations occurring in the estimation of continuous parameter stochastic processes[END_REF]) states that there exists a reference probability measure P 0 under which the signal and the observations are independent. In addition, for any measurable function f t on the space D([0, t], R d ) of R d -valued càdlàg paths from 0 to t, we have that

E(f t ((S s ) s≤t ) | Y t ) = E 0 (f t ((S s ) s≤t ) Z t (S, Y ) | Y t ) E 0 (Z t (S, Y ) | Y t ) (2.9)
where Y t = σ(Y s , s ≤ t) represents the sigma-field generated by the observation process and

log Z t (S, Y ) = t 0 H s (S s ) dY s - t 0 H s (S s )H s (S s ) ds
In the above definition (.) stands for the transposition operator. We let t n , n ≥ 0, be a given time mesh with t 0 = 0 and t n ≤ t n+1 . Also let X n be the sequence of random variables defined by

X n = S [tn,tn+1]
By construction, X n is a nonhomogeneous Markov chain taking values at each time n in the space

E n = D([t n , t n+1 ], R d ).
From previous considerations, the INRIA observation process Y t can be regarded as a random environment. Given the observation path, we define the "random" potential functions G n on

E n = (E 0 × . . . × E n )
by setting for any x n = (x 0 , . . . , x n ), with x p = (x p (s)) tp≤s≤tp+1 ∈ E p , and

0 ≤ p ≤ n G n (x n ) = G n (x n ) := exp tn+1 tn H s (x n (s)) dY s - tn tn H s (x n (s))H s (x n (s)) ds
By construction, we can check that the quenched Feynman-Kac path measures (2.2) associated with the pair (X n , G n ) coincide with the Kallianpur-Striebel representation and by (2.9) we prove that

η n = Law S [t0,t1] , . . . , S [tn,tn+1] | Y tn (2.10)
Next, we suppose that the observations are only delivered by the sensors at some fixed times t n , n ≥ 0, with t n ≤ t n+1 . To analyze this situation, we first notice that

(Y tn+1 -Y tn ) = tn+1 tn H s (S s ) ds + σ (V tn+1 -V tn )
and σ (V tn+1 -V tn ) are independent and random variables with Gaussian density q n . Arguing as before and using the same notation as there, we introduce the "random" potential functions G n defined by We end this section with a couple of remarks.

G n (x n ) = q n Y tn+1 -Y tn -
To compute the Feynman-Kac distributions (2.10) and (2.11), it is tempting to use directly the mean field particle approximation model introduced in (1.3). Unfortunately, in practice the signal semigroup and the above integrals are generally not known exactly and another level of approximation is therefore needed. As shown in [START_REF] Del Moral | The Monte-Carlo Method for filtering with discrete time observations[END_REF], the use of Euler approximation schemes introduces a deterministic bias in the fluctuation of the particle measures, but the resulting approximation models can be analyzed using the same perturbation analysis as the one we shall describe in section 4.1 (see also [START_REF] Crisan | Interacting particle systems approximations of the Kushner-Stratonovitch equation[END_REF][START_REF] Moral | Feynman-Kac formulae[END_REF], for a more thorough analysis of the discrete time schemes and genetic type particle approximations).

To solve the continuous time problem, another strategy is to use a fully continuous time particle approximation model of the robust equations. Loosely speaking, the geometric acceptance rates of the discrete generation particle models are replaced by exponential clocks with an appropriate stochastic intensity dictated by the log-likelihood potential functions. For an introduction to interacting particle interpretation of continuous time Feynman-Kac models we recommend the review article on genetic type models [START_REF] Del Moral | Asymptotic results for genetic algorithms with applications to nonlinear estimation[END_REF] as well as the series of articles [START_REF] Del Moral | Branching and interacting particle systems approximations of Feynman-Kac formulae with applications to nonlinear filtering[END_REF][START_REF] Del Moral | A Moran particle system approximation of Feynman-Kac formulae[END_REF][START_REF] Del Moral | Particle approximations of Lyapunov exponents connected to Schrödinger operators and Feynman-Kac semigroups[END_REF].

McKean interpretations

By the Markov property and the multiplicative structure of (2.2), it is easily checked that the flow of measures (η n ) n≥0 satisfies the following equation

η n+1 = Φ n (η n-1 ) := Ψ n (η n )M n+1
(2.12)

with the updating Bayes or the Boltzmann-Gibbs transformation Ψ n :

P(E n ) → P(E n ) defined by Ψ n (η n )(dx n ) := 1 η n (G n ) G n (x n ) η n (dx n ) (= η n (dx n )) .
The mean field particle approximation of the flow (2.12) depends on the choice of the McKean interpretation model. As we mentioned in the introduction, these stochastic models amount of choosing a suitably defined Markov chain X n with the prescribed evolution (2.12) of the laws of its states. More formally, these probabilistic interpretations consist of a chosen collection of Markov transitions K n+1,ηn , indexed by the time parameter n and the set of probability measures η ∈ P(E n ), and satisfying the compatibility condition

Φ n+1 (η) = ηK n+1,η (2.13)
The choice of these collections is not unique. We can choose, for instance the composition transition operator

K n+1,ηn = S n,ηn M n+1
with the updating Markov transition S n,ηn from E n into itself defined by the following formula

S n,ηn (x n , dy n ) = n (η n ) G n (x n ) δ xn (dy n ) + (1 -n (η n ) G n (x n )) Ψ n (η n )(dy n ) (2.

14)

In the above display, n (η n ) represents any possibly null constant that may depends on the current distribution η n , and such that n (η n ) G n ≤ 1. For instance, we can choose 1/ n (η n ) = η n -ess -sup G n . The corresponding nonlinear transport equation

η n+1 = η n K n+1,ηn
can be interpreted as the evolution of the laws η n of the states of a Markov chain X n whose elementary transitions K n+1,ηn depend on the law of the current state; that is, we have

P(X n+1 ∈ dx n+1 | X n = x n ) = K n+1,ηn (x n , dx n+1 ) with P • X -1 n = η n (2.
15) The law K n of the random path (X p ) 0≤p≤n is called the McKean measure associated with the Markov transitions (K n,η ) n≥0,η∈P(En) and the initial distribution η 0 . This measure on path space is explicitly defined by the following formula

K n (d(x 0 , . . . , x n )) = η 0 (dx 0 ) K 1,η0 (x 0 , dx 1 ) . . . K n,ηn-1 (x n-1 , dx n ) INRIA 2.

Mean field particle and genealogical tree based models

The N -particle model associated with a given collection of Markov transitions satisfying the compatibility condition (2.13) is the Markov chain introduced in (1.2). By the definition of the updating transitions (2.14), it appears that the mean field interacting particle model (1.2) is the combination of simple selection/mutation genetic transitions. The selection stage consists of N randomly evolving path-particles ξ i n-1

ξ i n-1 according to the update transition S n,η N n-1 (ξ i n-1 , .
). In other words, with probability n-1 (η N n-1 )G n-1 (ξ i n-1 ), we set ξ i n-1 = ξ i n-1 ; otherwise, the particle jumps to a new location, randomly drawn from the discrete distribution Ψ n-1 (η N n-1 ). During the mutation stage, each of the selected particles ξ i n-1 ξ i n evolves according to the Markov transition M n .

For any sufficiently regular transitions K n,ηn-1 satisfying the compatibility condition (2.13), we can prove that for any time horizon n

K N n := 1 N N i=1 δ (ξ i 0 ,...,ξ i n ) -→ N →∞ K n and η N n := 1 N N i=1 δ ξ i n -→ N →∞ η n
Mimicking formula (2.6), we also construct an unbiased estimate for the unnormalized model and we have that

γ N n (.) := η N n (.) n-1 p=0 η N p (G p ) -→ N →∞ γ n (.) = η n (.) n-1 p=0 η p (G p )
The convergence above can be understood in various ways. A variety of estimates going from the traditional L p -mean error bounds and exponential inequalities to fluctuation and large deviation theorems are provided in section 4 dedicated to the asymptotic behavior of these particle measures.

If we interpret the selection transition as a birth and death process, then arises the important notion of the ancestral line of a current individual. More precisely, when a particle ξ i n-1 -→ ξ i n evolves to a new location ξ i n , we can interpret ξ i n-1 as the parent of ξ i n . Looking backwards in time and recalling that the particle ξ i n-1 has selected a site ξ j n-1 in the configuration at time (n -1), we can interpret this site ξ j n-1 as the parent of ξ i n-1 and therefore as the ancestor

ξ i n-1,n at level (n -1) of ξ i n .
Running back in time we trace mentally the whole ancestral line of each current individual :

ξ i 0,n ←-ξ i 1,n ←-. . . ←-ξ i n-1,n ←-ξ i n,n = ξ i n
If we consider the historical process formulation (2.7) of a given signal model X n , then the mean field particle model associated with the Feynman-Kac measures on path spaces consists of N path particles evolving according to the same selection/mutation transitions. It is rather clear that the resulting path particle model can also be interpreted as the evolution of a genealogical tree model. This shows that the occupation measures of the corresponding N -genealogical tree model

η N n = 1 N N i=1 δ (ξ i 0,n ,ξ i 1,n ,...,ξ i n,n )
converge as N → ∞ to the Feynman-Kac path measures η n defined as in (2.2) with the pair of mathematical objects (X n , G n ) given by

X n = (X 0 , . . . , X n ) and G n (X n ) = g n (X n , y n )
From previous considerations, we already mention that the mathematical techniques developed to study the convergence of the particle measures η N N apply directly without further work to analyze the asymptotic behavior of this class of genealogical tree particle models. The occupation measures K N n of the complete genealogical tree (ξ i 0 , . . . , ξ i n ) 1≤i≤N keep track of the whole descendant history of the initial population individuals ξ 0 . The asymptotic analysis of these particle measures strongly depends on the choice of the McKean interpretation model and it requires more attention.

Last but not least, the mean filed particle methodology we have developed applies directly to solve the path-space filtering models we have presented in section 2.2. We leave the interested reader to write down the interacting particle systems in each situation. We also mention that the prediction formulation of the optimal filter described in (2.4) leads to a genetic type particle scheme with a pair mutation-selection transition associated with the pair transitionpotential function ( M n , G n ) given in (2.5). This strategy is based on observation depended explorations and the resulting stochastic grid is often more accurate than the one based on free mutations. Nevertheless, expect in some particular situations the sampling of a transition ξ i n-1 ξ i n according to the distribution M n ( ξ i n-1 , dx n ) is often difficult. One idea is to introduce an auxiliary empirical particle approximation

M N n ( ξ i n-1 , dx n ) := 1 N N j=1 δ ζ i,j
n of the Markov transition M n ( ξ i n-1 , dx n ), and based on sampling N -independent random transitions ξ i n-1 ζ i,j n , 1 ≤ k ≤ N with common distribution given by M n ( ξ i n-1 , dx n ). The second step is to replace the pair transition-potential function ( M n , G n ) given in (2.5) by their N -particle approximations ( M N n , G N n ) defined by

M N n ( ξ i n-1 , dx n ) := M N n ( ξ i n-1 , dx n ) G n (x n ) M N n (G n )( ξ i n-1 ) and G N n-1 ( ξ i n-1 ) := M N n (G n )( ξ i n-1
) These particle exploration models can be combined without further work with the path space enlargement techniques presented in (2.8). Roughly speaking, the corresponding path particle model is based on exploring the state space using the conditional transitions of signal sequences (X q ) pn-1≤q<pn (X q ) pn≤q<pn+1 based on (p n -p n-1 ) observations data (Y q ) pn≤q<pn+1 . The auxiliary N -particle approximation described above only provides a practical way of sampling these explorations on an auxiliarly pool of N sampled sequences.

These conditional exploration strategies have been originally developed in [START_REF] Moral | Measure valued processes and interacting particle systems. Application to non linear filtering problems[END_REF][START_REF] Del Moral | deviations for interacting particle systems. Applications to non linear filtering problems[END_REF]. We also refer the interested reader to chapter 11 of the book [START_REF] Moral | Feynman-Kac formulae[END_REF] for further stochastic particle recipes including a variety of branching type selection variants.

INRIA 3 Stability Analysis

This section is concerned with the regularity and the stability properties of the evolution semigroup of the measure valued process introduced in (2.12). This analysis is motivated by tow essential problems. From the signal processing perspective, the first one is to ensure that the underlying filtering problem is well posed, in the sense that it corrects automatically any erroneous initial data. This stability property is fundamental in most of the filtering problems encountered in practical situations where the initial distribution of the signal is unknown. The second motivation is well-known in the numerical analysis of dynamical systems. Indeed, it is generally useless to approximate an unstable and chaotic dynamical system that propagates any local perturbation. In our context, the mean field particle model can be interpreted as a stochastic perturbation of the nonlinear dynamical system (2.12). In this situation, the regularity properties of the evolution semigroup ensure that these local perturbations will not propagate. These ideas will be made clear in the forthcoming development of section 4.

Feynman-Kac evolution semigroups

We let Q p,n , with 0 ≤ p ≤ n, be the Feynman-Kac semi-group associated with the flow of unnormalized Feynman-Kac measures γ n = γ p Q p,n defined in (2.3). For p = n, we use the convention that Q n,n = Id, the identity operator. Using the Markov property, it is not difficult to check that Q p,n has the following functional representation

Q p,n (f n )(x p ) = E f n (X n ) p≤k<n G k (X k ) | X p = x p (3.1)
for any test function f n ∈ B(E n ), and any state x p ∈ E p . We denote by Φ p,n , 0 ≤ p ≤ n, the nonlinear semigroup associated with the normalized measures η n introduced in (2.2)

Φ p,n = Φ n • Φ n-1 • . . . • Φ p+1 (3.2)
As usual we use the convention Φ n,n = Id, for p = n. It is important to observe that this semigroup is alternatively defined by the formulae

Φ p,n (η p )(f n ) = η p (Q p,n (f n )) η p (Q p,n (1)) = η p (G p,n P p,n (f n )) η p (G p,n )
with the pair potential and Markov transition (G p,n , P p,n ) defined by

G p,n = Q p,n (1) and P p,n (f n ) = Q p,n (f n )/Q p,n (1)
The next two parameters P p,n (x p , .) -P p,n (y p , .) tv (3.3) measure respectively the relative oscillations of the potential functions G p,n and the contraction properties of the Markov transition P p,n . Various asymptotic estimates on particle models derived in the forthcoming sections will be expressed in terms of these parameters. For instance and for further use in several places in this article, we have the following Lipschitz regularity property.

Proposition 3.1 For any f n ∈ Osc 1 (E n ) we have |[Φ p,n (η p ) -Φ p,n (µ p )] (f n )| ≤ 2 r p,n β(P p,n ) [η p -µ p ] P µp p,n (f n ) (3.4)
for some function

P µp p,n (f n ) ∈ Osc 1 (E p )
that doesn't depends on the measure η p .

Proof:

We check this inequality using the key decomposition

[Φ p,n (η p ) -Φ p,n (µ p )] (f n ) = 1 η p (G µp p,n ) (η p -µ p )R µp p,n (f n ) with the function G µp p,n := G p,n /µ p (G p,n ) and the integral operator R µp p,n from B(E n ) into B(E p ) defined below : R µp p,n (f n )(x p ) := G µp p,n (x p ) × P p,n [f n -Φ p,n (µ p )(f n )] (x p )
Recalling that osc(P p,n (f n )) ≤ β(P p,n ) osc(f n ), one readily check that (3.4) is satisfied with the integral operator

P µp p,n from B(E n ) into B(E p ) defined P µp p,n (f n )(x p ) := 1 2 1 rp,n Gp,n(xp) inf Gp,n 1 β(P p,n ) [P p,n (f n )(x p ) -P p,n (f n )(y p )] G µp p,n (y p ) µ p (dy p )

Contraction properties

In this section, we present an abstract class of H-entropies like criteria. We also provide a brief introduction a brief introduction to the Lipschitz contraction properties of Markov integral operators. For a more detailed discussion on this subject, we refer the reader to chapter 4 of the book [START_REF] Moral | Feynman-Kac formulae[END_REF], and to a joint work of the first author with M. Ledoux and L. Miclo [START_REF] Del Moral | On contraction properties of Markov kernels[END_REF]. The contraction functional inequalities described in this section are extended to the nonlinear Feynman-Kac semigroup introduced in (3.2). Let h : R 2 + → R ∪ {∞} be a convex function satisfying for any a, x, y ∈ R + such that h(ax, ay) = ah(x, y), and h(1, 1) = 0. We associate with this homogeneous function the H-relative entropy on M + (E) defined symbolically as

H(µ, ν) = h (dµ, dν)
By homogeneity arguments, the above entropy is better defined in terms of any measure λ ∈ M(E) dominating µ and ν by the formula

H(µ, ν) = h dµ dλ , dν dλ dλ

INRIA

To illustrate this rather abstract definition, we provide hereafter a collection of classical h-relative entropies arising in the literature. Before to proceed, we first we come back to the definition of h-entropy, and we denote by h : R + → R {+∞} the convex function given for any x ∈ R + by h (x) = h(x, 1). By homogeneity arguments, we note that h is almost equivalent to h . More precisely, only the specification of the value h(1, 0) is missing. In most applications, the natural convention is h(1, 0) = ∞. The next lemma connects the h-relative entropy with the h -divergence in the sense of Csiszar [START_REF] Csiszár | Eine informationstheoretische Ungleichung und ihre Anwendung auf den Beweis der Ergodizität von Markoffschen Ketten[END_REF].

Lemma 3.2 ( [START_REF] Moral | Feynman-Kac formulae[END_REF]) Assume that h(1, 0) = +∞. Then, for any µ and ν ∈ M + (E), we have

H(µ, ν) = h dµ dν dν if µ ν, and H(µ, ν) = ∞ otherwise. (3.5)
As we promised above, let us present some traditional H-entropies commonly used probability theory. If we take h (t) = |t -1| p , p ≥ 1, we find the L pnorm given for any µ, ν ∈ P(E) by H(µ, ν) = 1 -dµ/dν p p,ν if µ ν, and ∞ otherwise.The case h (t) = t log(t) corresponds to the Boltzmann entropy or Shannon-Kullback information given by the formula H(µ, ν) = ln dµ dν dµ, if µ ν and ∞ otherwise. The Havrda-Charvat entropy of order p > 1 corresponds to the choice h (t) = 1 p-1 (t p -1); that is we have for any µ ν,

H(µ, ν) = 1 p-1 dµ dν p dν -1 .
The Hellinger and Kakutani-Hellinger integrals of order α ∈ (0, 1) correspond to the choice h (t) = t -t α , and with some obvious abusive notation we have H(µ, ν) = 1 -(dµ) α (dν) 1-α . In the special case α = 1/2, this relative entropy coincides with the Kakutani-Hellinger distance; and finally, the case h (t) = |t -1|/2 corresponds to the total variation distance. In the study of regularity properties of Φ p,n , the following notion will play a major role. Definition 3.3 Let (E, E) and (F, F) be a pair of measurable spaces. We consider an h-relative entropy criterion H on the sets P(E) and P(F ). The contraction or Lipschitz coefficient β H (Φ) ∈ R + ∪ {∞} of a mapping Φ : P(E) → P(F ) with respect to H is the best constant such that for any pair of measures µ, ν ∈ P(E) we have

H(Φ(µ), Φ(ν)) ≤ β H (Φ) H(µ, ν)
When H represents the total variation distance, we simplify notation and sometimes we write β(Φ) instead of β H (Φ).

When H is the total variation distance, the parameter β(Φ) coincides with the traditional notion of a Lipschitz constant of a mapping between two metric spaces. In [START_REF] Del Moral | On contraction properties of Markov kernels[END_REF], we prove the following regularity property. This functional inequality will be pivotal in the contraction analysis of Feynman-Kac semigroups developed in section 3.3. Theorem 3.4 For any pair of probability measures µ and ν ∈ P(E) and for any Markov kernel M from E into another measurable space F , we have the contraction estimate

H(µM, νM ) ≤ β(M ) H(µ, ν) (3.6)

Functional inequalities

The main objective of this section will be to estimate the contraction coefficients β H (Φ p,n ) of the nonlinear Feynman-Kac transformations Φ p,n in terms of the Dobrushin coefficient β(P p,n ) and the relative oscillations of the potential functions G p,n .

To describe precisely these functional inequalities precisely, it is convenient to introduce some additional notation. When H is the h -divergence associated with a differentiable h ∈ C 1 (R + ), we denote by ∆h the function on

R 2 + defined by ∆h(t, s) = h (t) -h (s) -∂h (s) (t -s) (≥ 0)
where ∂h (s) stands for the derivative of h at s ∈ R + . We further assume that the following growth condition is satisfied

∀(r, s, t) ∈ R 3 + we have ∆h(rt, s) ≤ a(r) ∆h(t, θ(r, s)) (3.7)
for some nondecreasing function a on R + and some mapping θ on R 2 + such that θ(r, R + ) = R + , for any r ∈ R + .

For instance, the Boltzmann entropy corresponds to the situation where h (t) = t log t. In this case, (3.7) is met with a(r) = r and θ(r, s) = s/r. For the Havrda-Charvat entropy of order α > 1, we have h (t) = (t α -1)/(α -1), and the growth condition (3.7) is now met with a(r) = r α and θ(r, s) = s/r. The Hellinger integrals of order α ∈ (0, 1) correspond to the choice h (t) = t -t α , and the growth condition is met with the same parameters. The L 2 -relative entropy corresponds to the case h (t) = (t -1) 2 , and we find that (3.7) is met with a(r) = r 2 , and again θ(r, s) = s/r.

The following theorem is s slightly weaker version of a theorem proved in [START_REF] Moral | Feynman-Kac formulae[END_REF].

Theorem 3.5 For any 0 ≤ p ≤ n and any pair of measures µ p , ν p ∈ P(E p ), we have the Lipschitz contraction inequality

Φ p,n (µ p ) -Φ p,n (ν p ) tv ≤ r p,n β(P p,n ) µ p -ν p tv (3.8)
In addition, if we set a H (r) := ra(r) then we have

β H (Φ p,n ) ≤ a H (r p,n ) β(P p,n ) and β(P p,n ) = sup µp,νp∈P(Ep) Φ p,n (µ p ) -Φ p,n (ν p ) tv (3.9)
Our next objective is to estimate the the contraction coefficient β H (Φ p,n ) in terms of the mixing type properties of the semigroup

M p,n (x p , dx n ) := M p+1 M p+2 . . . M n (x p , dx n )
associated with the Markov operators M n . We introduce the following regularity condition.

(M ) m There exists an integer m ≥ 1 and a sequence ( p (M )) p≥0 ∈ (0, 1) N such that ∀p ≥ 0 ∀(x p , x p ) ∈ E 2 p M p,p+m (x p , .) ≥ p (M ) M p,p+m (x p , .)

INRIA

It is well known that the above condition is satisfied for any aperiodic and irreducible Markov chains on finite spaces. Loosely speaking, for non compact spaces this condition is related to the tails of the transition distributions on the boundaries of the state space. For instance, let us suppose that E n = R and M n is the bi-Laplace transition given by

M n (x, dy) = c(n) 2 e -c(n) |y-An(x)| dy
for some c(n) > 0 and some drift function A n with bounded oscillations osc(A n ) < ∞. In this case, it is readily checked that condition (M ) m holds true for m = 1 with the parameter n-1 (M ) = exp (-c(n) osc(A n )).

Under the mixing type condition (M ) m we have for any n ≥ m ≥ 1, and

p ≥ 1 r p,p+n ≤ p (M ) -1 0≤k<m p+k (G) -1
and

β(P p,p+n ) ≤ n/m -1 k=0 1 - (m) p+km (G, M )
with the sequence of parameters

(m) p (G, M ) given by (m) p (G, M ) = 2 p (M ) p+1≤k<p+m k (G)
Several contraction inequalities can be deduced from these estimates (see for instance chapter 4 of the book [START_REF] Moral | Feynman-Kac formulae[END_REF]). To give a flavor of these results, we further assume that (M ) m is satisfied with m = 1, and we have (M ) = inf n n (M ) > 0.

In this case, we can check that r p,p+n ≤ ( (M ) p (G)) By (3.9) we conclude that

β H (Φ p,p+n ) ≤ a H (( (M ) p (G)) -1 ) 1 -(M ) 2 n
In addition, using the same line of reasoning we also prove the following potential free estimates

β H ( Φ p,p+n ) ≤ a H ( -1 (M )) 1 -2 (M ) n
Another strategy consists in combining the Markov contraction inequality (3.6) with some entropy inequalities obtained by Ocone in [START_REF] Ocone | Entropy inequalities and entropy dynamics in nonlinear filtering of diffusion processes[END_REF] (see also [START_REF] Clark | Relative entropy and error bounds for filtering of Markov processes[END_REF]). Using this strategy, we proved in [START_REF] Moral | Feynman-Kac formulae[END_REF] the following annealed contraction inequalities.

Theorem 3.6 Let η n and η n := Ψ n (η n ) be an auxiliary model defined with the same random equation as the pair η n and η n = Ψ n (η n ), but starting at some possibly different η 0 ∈ P(E 0 ). For any n ∈ N, and any η 0 we have

E(Ent( η n | η n )) ≤ E(Ent(η n | η n )) ≤ n p=1 β(M p ) Ent(η 0 | η 0 ) (3.10)
the mean field particle model.

η 0 → η 1 = Φ 1 (η 0 ) → η 2 = Φ 0,2 (η 0 ) → • • • → Φ 0,n (η 0 ) ⇓ η N 0 → Φ 1 (η N 0 ) → Φ 0,2 (η N 0 ) → • • • → Φ 0,n (η N 0 ) ⇓ η N 1 → Φ 2 (η N 1 ) → • • • → Φ 1,n (η N 1 ) ⇓ η N 2 → • • • → Φ 2,n (η N 2 ) ⇓ . . . η N n-1 → Φ n (η N n-1 ) ⇓ η N n
In the above display, the local perturbations W N n are represented by the implication sign "⇓". This picture yields the following pivotal formula

η N n -η n = n q=0 [Φ q,n (η N q ) -Φ q,n (Φ q (η N q-1 ))]
with the convention Φ 0 (η N -1 ) = η 0 for p = 0. Speaking somewhat loosely, a first order development of the semigroup Φ q,n around the measure Φ q (η N q-1 ) shows that the "small errors" induced by local perturbations do not propagate, as soon as the semigroup Φ p,n is sufficiently stable. Using the same line of arguments, the fluctuation analysis of the particle measures η N n around their limiting values η n results from a second order approximation of the semigroup Φ p,n . These two observations will be made clear in section 4.2 and section 4.3, devoted respectively to non asymptotic L p -mean error bounds and to central limit theorems.

Convergence of empirical processes

Using the Lipschitz regularity property (3.4) we obtain the following first order estimate :

Φ q,n (η N q ) -Φ q,n (Φ q (η N q-1 )) (f n ) ≤ 2 r q,n β(P q,n ) 1 √ N W N q P Φq(η N q-1 ) q,n (f n )
From these estimates and using the refined version of the Marcinkiewicz-Zygmund lemma presented in [START_REF] Moral | Feynman-Kac formulae[END_REF] (see lemma 7.3.3), we prove the following theorem. Theorem 4.1 ([11]) For any n ≥ 0, p ≥ 1, any tensor product function F n = (f 0 ⊗ . . . ⊗ f n ), with any functions f q ∈ Osc 1 (E q ) for all q ≤ n, we have

sup N ≥1 √ N E K N n -K n (F n ) p 1 p < ∞ and √ N E |[η N n -η n ](f n )| p 1 p ≤ c(n) d(p) 1/p (4.2)
with c(n) ≤ 2 n q=0 r q,n β(P q,n ), and the sequence of parameters d(p), with p ≥ 1, given by

d(2p) = (2p) p 2 -p and d(2p -1) = (2p -1) p p -1/2 2 -(p-1/2)
The L p mean error estimates in the right and side of (4.2) can be used to derive the following exponential estimate

∀ > 0 P(|η N n (f n ) -η n (f n )| > ) ≤ (1 + N/2) exp - N 2 2c(n) 2 (4.3)
We associate with a collection of measurable functions f : E → R, with f ≤ 1, the Zolotarev seminorm on P(E) defined by

µ -ν F = sup |µ(f ) -ν(f )|; f ∈ F ,
(see for instance [START_REF] Rachev | Probability Metrics and the Stability of Stochastic Models[END_REF]). To avoid some unnecessary technical measurability questions, we further suppose that F is separable in the sense that it contains a countable and dense subset. To measure the size of a given class F, one considers the covering numbers N ( , F, L p (µ)) defined as the minimal number of L p (µ)-balls of radius > 0 needed to cover F. By N ( , F), > 0, and by I(F) we denote the uniform covering numbers and entropy integral given by N ( , F) = sup N ( , F, L 2 (η)); η ∈ P(E) and

I(F) = 1 0 log (1 + N ( , F)) d
Various examples of classes of functions with finite covering and entropy integral are given in the book of Van der Vaart and Wellner [START_REF] Van Der Vaart | Weak Convergence and Empirical Processes with Applications to Statistics[END_REF]. The estimation of the quantities introduced above depends on several deep results on combinatorics that are not discussed here.

Let F n be a countable collection of functions f n with f n ≤ 1 and finite entropy I(F n ) < ∞. Suppose that the Markov transitions M n have the form M n (u, dv) = m n (u, v) p n (dv) for some measurable function m n on (E n-1 × E n ) and some p n ∈ P(E n ). Also assume that we have for some collection of mappings

θ n on E n sup u∈En-1 | log m n (u, v)| ≤ θ n (v) with p n (e 3θn ) < ∞ (4.4)
In this situation, we obtain the following fluctuation result.

Theorem 4.2 For any n ≥ 0 and p ≥ 1 we have

√ N E η N n -η n p Fn 1 p ≤ a [p/2]! [I(F n ) + c(n -1) r n-1,n p n (e 3θn )] (4.5)
with a collection of constants a < ∞ and c(n) ≤ n q=0 r q,n β(P q,n ).

INRIA in section 9.7 of the book [START_REF] Moral | Feynman-Kac formulae[END_REF]. We only examine the situation with a null acceptance rate n (µ) = 0, and we further suppose that condition (4.4) is satisfied with p n (e rθn ), for any r ≥ 1.

For any x = (x 0 , . . . , x n ) and z = (z 0 , . .

. , z n ) ∈ Ω n := (E 0 × . . . × E n ) we set a n (x, z) := b n (x, z) - Ωn K n (dx ) b n (x , z) and b n (x, z) := n k=1 c k (x, z)
In the above displayed formulae c k stands for the collection of functions on Ω 2 n given by

c k (x, z) := G k-1 (z k-1 ) m k (z k-1 , x k ) E k-1 G k-1 (u k-1 ) m k (u k-1 , x k ) η k-1 (du)
Under our assumptions,we can prove that the integral operator A n given by for any

F n ∈ L 2 (K n ) by A n (F n )(x) = Ωn a n (z, x) F n (z) K n (dz)
is a Hilbert-Schmidt operator on L 2 (K n ) and the operator (I -A n ) is invertible.

Extending the fluctuation analysis developed by T. Shiga and H. Tanaka in [START_REF] Shiga | Central limit theorem for a system of Markovian particles with mean field interaction[END_REF] to nonlinear mean field interaction models, we prove in [START_REF] Del Moral | A central limit theorem for nonlinear filtering using interacting particle systems[END_REF] the following central limit theorem.

n := √ N [K N n -K n ] converges as N → ∞ to a centered Gaussian field W n satisfying E (W n (F n )W (F n )) = (I -A n ) -1 (F n -K n (F n )), (I -A n ) -1 (F n -K n (F n )) L2(Kn)
for any F n , F n ∈ L 2 (K n ), in the sense of convergence of finite-dimensional distributions.

Large deviations principles

In this section, we introduce the reader to the large deviation analysis of mean field particle models associated with a given McKean interpretation of a measure valued equation. We start with the derivation of the large deviation principles (abbreviated LDP) combining Sanov's theorem with the Laplace-Varadhan integral lemma. This rather elementary result relies on an appropriate regularity condition on the McKean transitions under which the law of the N -particle model is absolutely continuous w.r.t. the law of N independent copies of the Markov chain associated with the McKean interpretation model.

We equip the space of all finite and signed measures M(E) on a Polish space (E, E) with the weak topology generated by the open open neighborhoods

V f, (µ) = {η ∈ P(E) : |η(f ) -µ(f )| < }
where f is a bounded continuous function on E, µ ∈ P(E), and ∈ (0, ∞). Using this topological framework, if we take E = E n and f = f n , then the

INRIA

To check this formula, we first notice that for any c ∈ [N ] [q] , there are (N -|c|) q-|c| × (q) |c| different ways to write c = ab ∈ q, N • [q] [q] . On the other hand, if a ∈ q, N , then we have that |b| = |c| and

(N ) |c| (q) |c| × (N -|c|) q-|c| ×(q) |c| (N )q = 1.
The partial derivative measures ∂ k Q n,q involved in the Laurent type expansions (5.5) are intimately related to the following measure-valued functional

∆ n,q : a ∈ A n,q → ∆ a n,q = η ⊗q 0 D a0 Q ⊗q 1 D a1 . . . Q ⊗q n D an ∈ M(E q n ) (5.8)
For instance, for q = 3 and n = 2 and the sequence of mappings a = (a 0 , a 1 , a 2 )

given below

1 2 0 0 `3 i 1 ) ) Y Y Y Y Y Y Y Y 2 Ñ Ñ Ó Ó Ó Ó Ó Ó Ó Ó 3
x x q q q q q q q q q q q q q q a 2 (i) 1 2

Ñ Ñ Ó Ó Ó Ó Ó Ó Ó Ó 3 a 1 (a 2 (i)) 1 2 3
a 0 a 1 (a 2 (i)) we have the formula ∆ a n,q (F ) = η 0 (dx 1 )η 0 (dx 2 )η 0 (dx 3 ) Q 1 (x 1 , dy 1 )Q 1 (x 1 , dy 2 )Q 1 (x 3 , dy 3 ) × Q 2 (y 1 , dz 2 )Q 2 (y 1 , dz 3 )Q 2 (y 2 , dz 1 )F (z 1 , z 3 , z 3 )

The first steps to these integral expansions are given by the following fundamental lemma.

Lemma 5.1 For any particle block size q ≤ N , any time horizon n ∈ N, and any F ∈ B(E q n ), we have

Q N n,q (F ) = 1 N q a∈[q] [q] (N ) |a| (q) |a| Q N n-1,q (Q ⊗q n D a F ) = 1 N q(n+1)
a∈An,q (N) |a| (q) |a| ∆ a n,q (F ) (5.9)

Proof:

We let A N q be an [q] [q] -valued random variable (independent of the particle model) with distribution 1 N q a∈[q] [q] (N ) |a| (q) |a| δ a . Indeed, combining the definition We let G q be the symmetric group of all permutations of [q]. The group G n+2 q acts naturally on sequences of maps a ∈ A q,n , and on jungles J(a) ∈ J q,n by permutation of the vertices at each level. More precisely, for all a ∈ A n,q and all s = (s 0 , ..., s n+1 ) ∈ G n+2 q by the pair of formulae s(a) := (s 0 a 0 s -1 1 , s 1 a 1 s -1 2 , ..., s n a n s -1 n+1 ) and sJ(a) := J(s(a)) (5.10)

Notice that if two sequences a and b ∈ A q,n differ only by the order of the vertices in J(a) and J(b), that is by the action of an element of G p , then the associated forests are identical: F (a) = F (b). Moreover, the converse is true: if F (a) = F (b), then J(a) and J(b) differ only by the ordering of the vertices, since they have the same underlying non planar graph. In this situation, a and b belong to the same orbit under the action of G p . In particular, the set of equivalence classes of jungles in J q,n under the action of the permutation groups G q,n is in bijection with the set of forests F q,n . We denote by B(t) the forest deduced from cutting the root of tree t; that is, removing its root vertex, and all its incoming edges. In the reverse angle, we denote by B -1 (f ) the tree deduced from the forest f by adding a common root to its rooted tree. The symmetry multiset S(t) of a tree t = B -1 (t m1 1 . . . t m k k ) associated with a forest written in normal form, is defined by S(t) := (m 1 , . . . , m k ). The symmetry multiset of a forest is given by S(t Combining the class formula with recursive multiplication principles with respect to the height parameter, one obtains the following closed formula.

Theorem 5.2 The number #(f ) of jungles in f ∈ F q,n , viewed as an equivalence class, is given by

#(f ) = (q!) n+2 / n i=-1 S(B i (f ))!
To get one step further, we notice that the measures ∆ a n,q have the invariance property ∆ b n,q (F ) = ∆ s(b) n,q (F ), for any symmetric function F ∈ B b (E q n ). Thus, we can define unambiguously ∆ f n,q (F ) = ∆ a n,q (F ), and |f | = |a|, for any choice a of a representative of some f ∈ F q,n in A q,n ∼ = J q,n .

The difference (p -l), of a pair of integer sequences p = (p k ) 0≤k≤n and l = (l k ) 0≤k≤n , is the sequence (p -l) := (p k -l k ) 0≤k≤n . When no confusions can arise, we write q, for the constant sequence (q) 0≤i≤n . For any multi index p = (p k ) 0≤k≤n ≤ q, we let F n,q (p) ⊂ F n,q be the subset of forets with at least p k leaves at each level k, with 0 ≤ k ≤ n. We also write for any pair of multi indexes p ≤ l where the s(l k , p k ) are Stirling numbers of the first kind. The next theorem is the main result of this section.

INRIA

Theorem 5.3 For any 1 ≤ q ≤ N , we have the polynomial expansion (5.5), with the collection of signed, and weak derivative measures ∂ k Q n,q given by the formula

∂ k Q n,q =
r<q:|r|=k f ∈Fn,q(r) s(|f |, qr) #(f ) (q) |f | ∆ f n,q

(5.11)

Let now B sym 0 (E q n ) be the set of symmetric functions F on E q n such that F (x 1 , . . . , x q-1 , x q ) γ n (dx q ) = 0

We write t k for the unique tree with a single coalescence at level k, and its two leaves at level (n + 1); and we write u k for the trivial tree of height k.

Corollary 5.4 For any even integer q ≤ N and any symmetric function F ∈ B sym 0 (E q n ), we have ∀k < q/2 ∂ k Q n,q (F ) = 0, ∂ q/2 Q n,q (F ) = r<q,|r|= q 2 q! 2 q/2 r! ∆ fr n,q F (5.12)

with the forest f r := t r0 0 u r0 0 ...t rn n u rn n associated with a multi index sequence r = (r k ) 0≤k≤n < q. For odd integers q ≤ N , the partial derivatives are the null measure on B sym 0 (E q n ), up to any order k ≤ q/2 .

H

  s (x n (s)) ds By construction, the quenched Feynman-Kac path measures (2.2) associated with the pair (X n , G n ) now have the following interpretation η n = Law S [t0,t1] , . . . , S [tn,tn+1] | Y t1 , . . . , Y tn (2.11)

r

  p,n = sup xp,yp∈Ep (G p,n (x p )/G p,n (y p )) and β(P p,n ) = sup xp,yp∈Ep

- 1 and

 1 β(P p,p+n ) ≤ 1 -(M ) 2 n

Theorem 4 . 5

 45 The random field W N

INRIA

Figure 2 :

 2 Figure2: a graphical representation of a planar forest f = t 1 t 3 t 2 t 3 t 3 t 1 . We let G q be the symmetric group of all permutations of [q]. The group G n+2

m1 1 .

 1 . . t m k k ) :=   S(t1), . . . , S(t 1 ) m1-terms , . . . , S(t k ), . . . , S(t k )

  |p| := (p 0 + ... + p n ) p! = n k=0 p k ! and s(l, p) = n k=0 s(l k , p k )

  Relative entropy estimates . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Polynomial tree-based expansions . . . . . . . . . . . . . . . . . . 28 5.3 Coalescent tree based representations . . . . . . . . . . . . . . . . 29

	1 Introduction	3
	1.1 A mean field theory of nonlinear filtering . . . . . . . . . . . . .	3
	1.2 Notation and conventions . . . . . . . . . . . . . . . . . . . . . .	7
	2 Feynman-Kac and mean field particle models	8
	2.1 Description of the models . . . . . . . . . . . . . . . . . . . . . .	8
	2.2 Path space and related filtering models . . . . . . . . . . . . . . .	9
	2.3 McKean interpretations . . . . . . . . . . . . . . . . . . . . . . . 12
	2.4 Mean field particle and genealogical tree based models . . . . . . 13
	3 Stability Analysis	15
	3.1 Feynman-Kac evolution semigroups . . . . . . . . . . . . . . . . . 15
	3.2 Contraction properties . . . . . . . . . . . . . . . . . . . . . . . . 16
	3.3 Functional inequalities . . . . . . . . . . . . . . . . . . . . . . . . 18
	4 Asymptotic analysis	20
	4.1 A stochastic perturbation model . . . . . . . . . . . . . . . . . . 20
	4.2 Convergence of empirical processes . . . . . . . . . . . . . . . . . 21
	4.3 Fluctuation analysis . . . . . . . . . . . . . . . . . . . . . . . . . 23
	4.4 Large deviations principles . . . . . . . . . . . . . . . . . . . . . . 24
	5 Propagations of chaos properties	27
	5.1 INRIA

RR n°0123456789

Asymptotic analysis

This section is concerned with the convergence analysis of the particle approximation measures introduced in section 2.4. In the first subsection, a stochastic perturbation methodology that allows to enter the stability of the limiting Feynman-Kac semigroup into the convergence analysis of the particle models. The convergence of empirical processes including exponential estimates and L pmean error bounds for the McKean particle measures K N n and their density profiles η N n are discussed in subsection 4.2. Central limit theorems and large deviation principles are presented respectively in subsection 4.3 and subsection 4.4.

A stochastic perturbation model

We provide in this section a brief introduction to the asymptotic analysis of the particle approximation models (1.3) as the size of the systems and/or the time horizon tends to infinity. Firstly, we observe that the local sampling errors are expressed in terms of the random fields W N n , given for any f n ∈ B(E n ) by the formula

Rewritten in a slightly different way, we have the stochastic perturbation formulae

with the centered random fields W N n with conditional variance functions given by

In section 4.3 we shall see that the random fields (W N n ) n≥0 behave asymptotically as a sequence of independent Gaussian and centered random fields (W n ) n≥0 with conditional variance functions given as in (4.1), by replacing the particle empirical measures η N n by their limiting values η n . These fluctuation covariance functions depend on the choice of the McKean interpretation model. To underline the role of the parameter n (η n ) given in (2.14), we observe that for any µ ∈ P(E n-1 ) we have that

This formula shows that the simple genetic particle model associated with a null parameter n (µ) = 0 is in this sense the less accurate. The following picture gives a sound basis to the main questions related to the convergence analysis of

INRIA

Fluctuation analysis

The fluctuation analysis of the particle measures η N n around their limiting values η n is essentially based on the asymptotic analysis of the local sampling errors W N n associated with the particle approximation sampling steps. The next central limit theorem for random fields is pivotal. Its complete proof can be found in [START_REF] Moral | Feynman-Kac formulae[END_REF] (see theorem 9.3.1 and corollary 9.3.1 on pages 295-298).

Theorem 4.3 For any fixed time horizon n ≥ 1, the sequence (W N p ) 1≤p≤n converges in law, as N tends to infinity, to a sequence of n independent, Gaussian and centered random fields (W p ) 1≤p≤n ; with, for any f p , g p ∈ B(E p ), and

Using the pair of decompositions

we readily deduce the following corollary :

Corollary 4.4 For any fixed time horizon n ≥ 1, the sequence of random fields

converges in law, as N tends to infinity, to a sequence of n independent, Gaussian and centered random fields W γ n and W η n ; with, for any

and

The random fields W N,γ n and W η,N n can also be regarded as empirical processes indexed by the collection of bounded measurable functions

is asymptotically tight (see for instance lemma 9.6.1 in [START_REF] Moral | Feynman-Kac formulae[END_REF]). In this situation, the random fields W N,γ n and W η,N n also converge in law in l ∞ (F n ) to the Gaussian processes W γ n and W η n . The fluctuation analysis of the random fields K N n around the McKean measure K n is technically much more involved. For completeness, we have chosen to present this result in a rather simple form. The complete proof can be found deviant event presented in (4.3) is equivalently expressed in terms of a basis neighborhood of the McKean measure

as soon as the function f n is continuous. One objective of the forthcoming analysis is to estimate the exact exponential deviation of the particle measures η N n and more generally K N n around there limiting values η n and K n . For instance, we would like is to compute the following quantities for any continuous bounded functions f n or F n on the state space E n or on the path space

and lim

To describe precisely this result we need to introduce another round of notation. We let P N n ∈ P(Ω N n ) be the distribution of the mean field Ninteracting particle model ξ i 0 , . . . ξ i n 1≤i≤N introduced in (1.3), and we denote by

the image distribution of the empirical measures K N n , with the empirical projection mapping π N n given by

We recall that the sequence P N n satisfies the LDP with the good rate function I n as soon as we find a mapping lower semicontinuous mapping

for any Borel subset A ⊂ P(Ω n ), where

•

A and A denote respectively the interior and the closure of the set A.

By a direct application of Sanov's theorem, under the tensor product measure

of the empirical measures K N n associated with N independent path particles with common distribution K n satisfy the LDP with a good rate function H n given by the Boltzmann relative entropy defined by

To get one step further, we suppose that condition (4.4) is satisfied with p n (e rθn ), for any r ≥ 1. In this condition, the measures P

RR n°0123456789

In the above display, the function V n is given for any probability measure µ ∈ P(Ω n ) by te following formula

with the mapping

and where µ p ∈ P(E p ) stands for the pth time marginal of µ with 0 ≤ p ≤ n. Under our assumptions, using an extended version of the Laplace-Varadhan integral lemma (see for instance lemma 10.4.1 in [START_REF] Moral | Feynman-Kac formulae[END_REF]) we prove the following theorem.

As we mentioned above, the large deviation analysis we have described is not restricted to mean field interpretations of the nonlinear filtering equations. A more general result for an abstract class of McKean kernels (K n,η ) n,η is provided in theorem 10.1.1 in [START_REF] Moral | Feynman-Kac formulae[END_REF].

Working a little harder, we can also derive a LDP for the τ -topology for the distribution of the particle density profiles (η N p ) 0≤p≤n associated with the

McKean transitions K n,η (x, .) := Φ n (η). For the convenience of the reader, we recall that the τ -topology on a set of probability measures is generated by the sets V f, (µ), with non necessarily continuous functions f ∈ B(E). The following theorem is taken from a joint work of the first author with D. Dawson [START_REF] Dawson | Large deviations for interacting processes in the strong topology[END_REF].

Theorem 4.7 Assume that for any n ≥ 1, there exists some reference measure λ n ∈ P(E n ) and some parameters ρ n > 0 such that ∀µ ∈ (P(E n-1 )

In this situation, the law of the flow of particle density profiles (η N p ) 0≤p≤n satisfies the LDP for the product τ -topology with the good rate function J n on n p=0 P(E p ) given by

In the context of Feynman-Kac models, it can be checked that the one-step mappings Φ n are τ -continuous and condition (4.8) is met as soon as for any x n-1 ∈ E n-1 we have

2 (y-an(x)) 2 dy, where a n is a bounded measurable drift function on R, then condition (4.8) is met with the reference measure given by λ n (dy) = p n (dy)/p n (R) and with p n (dy) = def.

1 √ 2π e -y 2 2 -|y| an dy and ρ n = e -an 2 /2 p n (R)

Propagations of chaos properties

The initial configuration of the N -particle mean field model (1.3) consists in N independent and identically distributed random variables. Their common law is dictated by the initial distribution of the underlying nonlinear equation (1.2). In this sense, the initial system is in "complete chaos" and the law of each particle perfectly fits the initial distribution.

During their time evolution the particles interact one another. The nature of the interactions depends on the McKean interpretation model. Nevertheless, in all interesting cases the independence property and the adequacy of the laws of the particles with the desired distributions are broken. The propagation of chaos properties of mean field particle models presented in this section can be seen as a way to measure these properties. In the first subsection, we estimate the relative entropy of the laws of the first q paths of a complete genealogical tree model with respect to the q-tensor product of the McKean measure. In the second part of this section, we present an original Laurent type and algebraic tree-based integral representations of particle block distributions. In contrast to the first entropy approach, this technique applies to any genetic type particle model without any regularity condition on the mutation transition.

Relative entropy estimates

In this section, we provide strong propagation estimates with respect to the relative entropy criterion for the interacting particle system associated with the McKean interpretation model defined in (1.3). We further assume that n (µ) does not depend on the measure µ, and the Markov transitions M n satisfy the regularity condition (4.4), with p n = η n . We let P N n be the distribution of the mean field N -interacting particle model ξ i 0 , . . . ξ i n 1≤i≤N . By the deviation analysis provided in section 4.4, we have that

We let P (N,q) n be the distribution of the first q path particles ξ i 0 , . . . ξ i n 1≤i≤q , with q ≤ N . Using an elegant lemma of Csiszar on the entropy of the first q-coordinates of an exchangeable measure (see [START_REF] Csiszar | Sanov property, generalized i-projection and a conditional limit theorem[END_REF], or lemma 8.5.1 in [START_REF] Moral | Feynman-Kac formulae[END_REF]), we find that

By the exchangeability property of the particle model, we also have that

Using the fact that Ent(µ|η) ≤ 1 -dµ/dη 2 2,η , and estimating the local Lipschitz continuity coefficient of the mappings µ → dKn,µ(u,.) dKn,η n-1 (u,.) (v) at µ = η n-1 , we prove the following theorem.

Theorem 5.1 For any q ≤ N and any time horizon n, we have the relative entropy estimate

Ent

r q,p β(P q,p )

and some universal finite constant c .

Polynomial tree-based expansions

This section is concerned with propagation of chaos properties of the mean field particle model associated with the null acceptance rate parameter n (µ) = 0. Without any regularity conditions on the Markov transitions M n it is more all less well known that we have the following strong propagation of chaos estimate

for some finite constant, which only depends on the time parameter n. The complete proof of this result can be founded in [START_REF] Moral | Feynman-Kac formulae[END_REF] (see for instance theorem 8.3.3 and theorem 8.3.4).

The main object of this section is to provide an explicit asymptotic functional expansion of the law of the first q particles at a given time n with respect to the precision parameter N . These expansions at any order extend the sharp but first order propagation of chaos estimates developed by the first author with A. Doucet, and G.W. Peters in a recent article [START_REF] Del Moral | Sharp Propagation of Chaos Estimates for Feynman-Kac Particle Models[END_REF].

Next, for any q ≤ N we consider the q-tensor product occupation measures, resp. the restricted q-tensor product occupation measures, on E q n defined by

In the above display, [N ] [q] , resp. q, N , stands for the set of all N q mappings, resp. all (N ) q := N !/(N -q)! one-to-one mappings, from the set [q] := {1, . . . , q} into [N ] := {1, . . . , N }. The unnormalized versions of these measures are simply defined by

problem is to obtain functional expansions, with respect to the precision parameter N , of the pair of particle block distributions defined for any F ∈ B(E q n ) by the formulae

In this Note, we design a coalescent tree-based representation of the unnormalized particle distributions Q N n,q with the following polynomial form

In the above display, ∂ k Q n,q stands for a sum of signed, and weak derivative measures, whose values can be explicitly described in terms of a class of forests with maximal coalescent degree k. These Laurent type expansions reflect the complete interaction structure of the particle model, the k-th order terms represent the 1/N k -contributions of mean field particle scenarios with an interaction degree k.

The analysis of the distributions P N n,q is a little more involved, combining judicious renormalization techniques on path spaces, with colored tree-based combinatorial expansions (cf. [START_REF] Del Moral | Coalescent Tree Based Functional Representations for some Feynman-Kac Particle Models[END_REF]).

∂ k+1 P N n,q tv < ∞

Coalescent tree based representations

Let A n,q be the set of (n + 1)-sequences a = (a p ) 0≤p≤n of mappings a p from [q] into itself. By |a|, we denote the cardinality of the set a([q]); and for a ∈ A n,q , we write |a| the integer sequence (|a i |) 0≤i≤n . For any pair of integers q ≤ N , we use the the multi index notation (q) |a| = 0≤k≤n (q) |a k | . For b ∈ [q] [q] and F ∈ B(E q n ), we define :

For any air of mappings a, b ∈ [q] [q] we have the composition formula D a D b = D ab . We notice that

F ) sym ) So we may assume in our forthcoming computations on q-tensor products occupation measures that F is in B sym (E q n ), the subset of B(E q n ) of symmetric functions. We also observe that

of the particle model with (5.7), we first find that

Integrating over the past, the end of the proof is straightforward.

Next, we turn our attention to a coalescent tree based formulation of the integral expansion (5.9). We start with recalling some more or less classical terminology on trees and forests. A tree (respectively a planar tree) is a (isomorphism class of) finite non-empty oriented connected (and respectively planar) graph t without loops such that any vertex of t has at most one outgoing edge. Paths are oriented from the vertices to the root. A forest f is a multiset of trees, that is a set of trees, with repetitions of the same tree allowed, or equivalently an element of the commutative monoid T on T , with the empty graph T 0 = ∅ as a unit.

Since the algebraic notation is the most convenient, we write f = t m1 1 ...t m k k , for the forest with the tree t i appearing with multiplicity m i , i ≤ k. When t i = t j for i = j, we say that f is written in normal form. A planar forest f is an ordered sequence of planar trees. Planar forests can be represented by noncommutative monomials (or words) on the set of planar trees. The sets of forests and planar forests with height (n + 1), and with q vertices at each level set are written F q,n and PF q,n .

A sequence a ∈ A q,n is naturally associated a forest F (a): the one with one vertex for each element of [q] n+2 , and a edge for each pair (i, a k (i)), i ∈ [q]. The sequence can also be represented graphically uniquely by a planar graph J(a), where however the edges between vertices at level k + 1 and k are allowed to cross. We call such a planar graph, where paths between vertices are entangled, a jungle. The set of such jungles is written J q,n . In a planar forest f , vertices at the same level k ≥ 0, are naturally ordered from left to right, and therefore in bijection with [q]. Planar forests f ∈ PF q,n of height (n + 1) are therefore canonically in bijection with sequences a of weakly increasing map from [q] into itself.

•


Impact of machine stiffness and heat treatments on crack propagation instabilities in an

INSTABILITY CRITERIA

Paris, Tada, Zahoor, Ernst, 1979Paris, Tada, Ernst, Zahoor, 1979Hutchinson, Paris, 1979Zahoor, Paris, 1981Zahoor, 1982 "cleavage" instability

Origin ?

Interaction between elastic energy and tearing modulus?

  Al-Mg-Si alloy Microstructural origin Before max load Typical for brittle fracture Fracture toughness tests "Pop-in" = local instability leading to rapid but limited crack propagation associated with a sudden decrease in load Little studied in the literature. 2 types : First pop-in type: "Cleavage" instability Mechanical origin After max load Typical for ductile fracture Fracture toughness tests "Pop-in" = local instability leading to rapid but limited crack propagation associated with a sudden decrease in load Little studied in the literature. 2 types : Second pop-in type: "Tearing" mechanism

  Impact of machine stiffness and heat treatments on crack propagation instabilities in anAl-Mg-Si alloy System Fracture toughness tests "Pop-in" = local instability leading to rapid but limited crack propagation associated with a sudden decrease in load Little studied in the literature. 2 types : nanoprecipitation increase in the size and density with the aging time Atom Probe Tomography: 22 nd European Conference on Fracture | 26-31. August, 2018 | 8 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy appearance after 12 and 16 h of aging time Decrease in tearing modulus Low strain hardening ability High strength  low tearing modulus  pop-in Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy No preferential localization of coarse particles  transgranular fracture Intergranular fracture only around the small grains stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloyConclusions :• Pop-ins studied are purely mechanical crack growth instabilities• Result from the interaction of the material behavior (favored by a decrease of tearing modulus) and imposed loading (favored by a high compliance of the total system)

nd European Conference on Fracture | 26-31. August, 2018 | 5 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy

nd European Conference on Fracture | 26-31. August, 2018 | 7 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy

nd European Conference on Fracture | 26-31. August, 2018 | 9 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy

nd European Conference on Fracture | 26-31. August, 2018 | 19 Impact of machine stiffness and heat treatments on crack propagation instabilities in an Al-Mg-Si alloy

Impact of machine stiffness and heat treatments on crack propagation instabilities in an