Large Deviations for Interacting Particle Systems. Applications to Non Linear Filtering

P. Del Moral^{∗}, A. Guionnet^{†}

Abstract

The non linear filtering problem consists in computing the conditional distributions of a Markov signal process given its noisy observations. The dynamical structure of such distributions can be modelled by a measure valued dynamical Markov process. Several random particle approximations were recently suggested to approximate recursively in time the so-called non linear filtering equations. We present an interacting particle system approach and we develop large deviations principles for the empirical measures of the particle systems. We end this paper extending the results to an interacting particle system approach which includes branchings.

\underline{Keywords :} Large deviations, Interacting random processes, Filtering, Stochastic approximation. \underline{code A.M.S :} 60F10, 60H10, 60G35, 93E11, 62L20.

1 Introduction

1.1 Background and motivations

The non linear filtering problem consists in computing the conditional distribution of a signal given its noisy observation. Roughly speaking, a basic model for non linear filtering problems is to assume that the signal is a time inhomogeneous Markov process X with observations Y described by

Y_{n} = h_{n}(X_{n}) + V_{n}  (1)

∗UMR C55830, CNRS, Bat.1R1, Univ. Paul Sabatier, 31062 Toulouse, delmoral@cict.fr.

†URA 743, CNRS, Bat. 425, Université de Paris Sud, 91405 Orsay, France, guionnet@stats.matups.fr

where h_{n} are some continuous functions and V_{n} a noise, which we will assume independent of the signal X_{n}.

It was proven in a general setting by Kunita [25] and Stettner [31] that the law of X_{n} given the observations (Y_{p}, p ≤ n) obeys the so-called non linear filtering equations. Basically, if η_{n} denotes the law of X_{n} given (Y_{p}, p ≤ n), these equations are of the form

η_{n} = ϕ(n, η_{n−1})  ∀n ≥ 1  η_{0} = η  (2)

where η is the law of the initial signal and ϕ(n, .) an application on the space of probability measures on the state space of the signal. ϕ(n, .) depends on the observations (Y_{p}, p ≤ n), on the laws of (V_{p}, p ≤ n) and on the transition probability kernels of the signal process ( see Lemma 3.1 for its complete description ).

The study of equations of type (2) is far from being straightforward. Such equations also occur in Statistical Physics and Biology (see [12],[35] and references therein). In these frameworks, the dynamical system (2) usually describes the time evolution of the density profiles of McKean-Vlasov stochastic processes with mean field drift functions. It was proposed by McKean and Vlasov to approximate the corresponding equations by mean field interacting particle systems. A crucial practical advantage of this situation is that the dynamical structure of the non linear stochastic process can be used in the design of an interacting particle system in which the mean field drift is replaced by a natural interaction function. Such models are called in Physics Masters equations and/or weakly interacting particle systems. They are now well understood (see [2], [11], [12],[21], [35], [36] and references therein). Under rather general assumptions, it was shown that the particle density profile (that is the random empirical measures of the particle systems) converges towards the solution of (2) as the number of particles is going to infinity. As a consequence, propagation of chaos occurs. To specify the rate of this convergence, large deviations properties and fluctuations were studied.

Among the most exciting developments in Non Linear Filtering Theory are those centered around the recently established connection with interacting and branching particle systems. In non linear filtering problems the dynamical system (2) describes the time evolution of the conditional distribution of the internal states in dynamical systems when partial observations are made. In contrast to the situation described above the conditional distributions cannot be viewed as the law of a finite dimensional stochastic process which incorporates a mean field drift. We therefore have to find a new strategy to define an interacting particle system which will approximate the desired distributions. In the last decade several different stochastic particle approximations were suggested to approximate the so-called non linear filtering equation. The evolution of this rapidly developing area of research may be seen quite directly through the following chain of papers [6],[8],[9],[10],[13], [15] and [20]. In [16] and [17], general particle systems which include branching and non linear interactions were described. The laws of the empirical measures of these systems were shown to converge weakly to the desired conditional distribution as the number of particles is growing.

Several practical problems which have been solved using these methods are given in [5], [6], [13], [14], signal processing and GPS/INS integration.

In the current work we develop large deviations for some of the particle approximations studied in [16] and [17] in which the interaction function only depends on the empirical measure of the system. Such results provide the exact speed of convergence of the algorithms we consider until a finite given time. The study of their long time behavior is a rather different subject which we will hopefully investigate in another paper.

1.2 Description of the model; Statement of some results

To describe precisely our model, let us introduce some notations. The signal X_{n} at time n will take its values into a Polish space E. E is endowed with a Borel σ-field B(E). We denote by M_{1}(E) the space of all probability measures on E furnished with the weak topology. We recall that the weak topology is generated by the bounded continuous functions. We will denote C_{b}(E) the space of these functions.

The particle system (Ω, F_{n}, (ξ_{n})_{n≥0}, P) under study will be a Markov process with state space E^{N}, where N ≥ 1 is the size of the system. The N-tuple of elements of E, i.e. the points of the set E^{N}, are called particle systems and will be mostly denoted by the letters x, z. Our dynamical system is then described by

P (ξ_{0} ∈ dx) = ∏_{p=1}^{N} η_{0}(dx^{p}) P (ξ_{n} ∈ dx/ ξ_{n−1} = z) = ∏_{p=1}^{N} ϕ (n, \frac{1}{N} ∑_{q=1}^{N} δ_{z^{q}} ) (dx^{p})

(3)

where dx =^{def} dx^{1} × … × dx^{N}. Our goal is to prove large deviation principles for the law of the empirical distribution of the N-particle system (3)

η^{N}(ξ_{[0,n]}) = \frac{1}{N} ∑_{i=1}^{N} δ_{(ξ_{0}^{i},...,ξ_{n}^{i})}  (4)

which is a random measure on the path space Σ_{n} = E^{n+1}. Our results will then basically be stated under the following form.

Theorem 1.1 If the functions (ϕ(n, .))_{n≥1} are ”good enough” then we have that

η^{N}(ξ_{[0,n]}) \overrightarrow{N → ∞} η_{[0,n]} =^{def} η_{0} ⊗ … ⊗ η_{n}  a.s.  (5)

In addition

1. The law (Q_{N}^{n})_{N≥1} of η^{N}(ξ_{[0,n]}) satisfies a large deviation principle (LDP) with rate function I_{n} which reads

(a) I_{n} : Σ_{n} → [0, ∞] has compact level sets, that is {I_{n} ≤ M} is a compact subset of Σ_{n}.

(b) For any closed set C ⊂ M_{1}(Σ_{n})

lim sup_{N→∞} \frac{1}{N} log Q_{N}^{n}(C) ≤ − inf_{C} I_{n}.  (6)

(c) For any open set A ⊂ M_{1}(Σ_{n})

lim inf_{N→∞} \frac{1}{N} log Q_{N}^{n}(A) ≥ − inf_{A} I_{n}.  (7)

2. I_{n} has a unique minimizer which is η_{[0,n]}.

The LDP precise the rate of the convergence (5). Let us give an explicit upper bound for this rate. To do so, let us introduce a metric d on M_{1}(Σ_{n}) compatible with the weak topology :

d(μ, ν) =^{def} ∑_{m≥1} 2^{−(m+1)} |μf_{m} − νf_{m}|  (8)

where (f_{m})_{m≥1} is a suitable sequence of uniformly continuous functions uniformly bounded by 1 (theorem 6.6 pp. 47, Parthasarathy [29]). We consider the function Φ_{n} : M_{1}(Σ_{n}) → M_{1}(Σ_{n}) so that

Φ_{n}(μ) = η_{0} ⊗ ϕ(1, T_{0}μ) ⊗ … ⊗ ϕ(n, T_{n−1}μ)  (9)

where T_{k}μ, 0 ≤ k ≤ n, is the k-marginal of μ. Clearly,

d(Φ_{n}(μ), μ) = 0 ⟺ μ = η_{[0,n]}.

We will see that, thanks to the large deviation results proved in section 2, under appropriate assumptions, for any ϵ > 0 there exists N(ϵ) ≥ 1 so that

∀N ≥ N(ϵ) P (d(η^{N}(ξ_{[0,n]}), Φ_{n} (η^{N}(ξ_{[0,n]}))) > ϵ) ≤ e^{− \frac{N ϵ^{2}}{4}} .

The crucial point is now to specify the assumptions needed on the ϕ(n, .)’s for such result to hold. Throughout this paper, we shall weaken these hypotheses as much as we can in order to include as many examples encountered in non linear filtering problems as possible.

The paper has the following structure:

We will derive in section 2 large deviation principles for the particle system (3) keeping in mind to weaken the assumptions on the functions ϕ(n, .)’s as much as we can in order to apply it to non linear filtering particle systems. In subsection 2.1, we consider the empirical measure on path space. In subsection 2.2, we considerably weaken the hypotheses needed in the latter and get large deviation principles for the time marginals.

The applications of the large deviation results obtained in section 2 to non linear filtering problems will be explored in section 3.

We end this paper with some generalizations of the former large deviation results to some random particle approximations which includes branchings and interactions.

2 LDP for Interacting Particle Systems

Our interest is in large deviation results for the laws of the empirical measures associated to our interacting particle systems (3). The study of the minimizers of the rate functions governing these large deviations will in turn provide convergence of the empirical trajectories towards η_{[0,n]} and an exponential speed for this convergence. A general formulation for studying such problems was given by Varadhan in [38] and by Azencott in [1]. More recent developments can be found in Deuschel-Stroock [19] and Dembo-Zeitouni [18].

Our developments will be mainly based on Laplace method, Gärtner-Ellis and Baldi theorem.

2.1 LDP for the Empirical Measures on the Path Space

In this section, we focus on the empirical trajectories η^{N}(ξ_{[0,n]}) ∈ M_{1}(Σ_{n}) defined by (4) until a given finite time n ∈ IN. With these notations, we can rewrite the law Q_{n}^{N} of η^{N}(ξ_{[0,n]}) for our particle system (3) as the probability so that, for any F ∈ C_{b}(M_{1}(Σ_{n})),

Q_{n}^{N}F = ∫_{Σ_{n}^{N}} F (η^{N}(x)) ϕ(n, T_{n−1}η^{N}(x))^{⊗N}(dx_{n}) … ϕ(1, T_{0}η^{N}(x))^{⊗N}(dx_{1}) η_{0}^{⊗N}(dx_{0})

where ϕ(k, μ)^{⊗N}, 1 ≤ k ≤ n, μ ∈ M_{1}(E), is the N-fold product of the measure ϕ(k, μ).

To prove large deviations for {Q_{n}^{N}, N ≥ 1} we will always assume that (A) : For any time n ≥ 1 there exists a probability of reference λ_{n} ∈ M_{1}(E) such that

∀μ ∈ M_{1}(E) ϕ(n, μ) ∼ λ_{n}.

This condition might seem difficult to check in general but in fact covers many typical examples of non linear filtering problems ( see section 3 ). It is obvious that the situation becomes considerably more involved when dispensing with this assumption. As we will see in section 2.2, it turns out that a continuity assumption on the functions ϕ(n,.) is sufficient to obtain an inductive LDP for the time marginals.

The main simplification due to assumption (A) is that each law Q_{n}^{N} is equivalent to the distribution R_{n}^{N} ∈ M_{1}(M_{1}(E)) given by

R_{n}^{N}F = ∫_{Σ_{n}^{N}} F (η^{N}(x)) λ_{0}^{⊗N}(dx_{0}) … λ_{n}^{⊗N}(dx_{n})

for any F ∈ C_{b}(M_{1}(Σ_{n})), with the convention λ_{0} = η_{0}. We notice that the latter formula can be written in the form

R_{n}^{N}F = ∫_{Σ_{n}^{N}} F (η^{N}(x)) R_{n}^{⊗N}(dx) with R_{n} = λ_{0} ⊗ … ⊗ λ_{n}

It is also easily seen that

\frac{dQ_{n}^{N}}{dR_{n}^{N}} = exp (NF_{n})  R_{n}^{N} − a.s.  (10)

where F_{n} : M_{1}(Σ_{n}) → IR is the function defined by

F_{n}(μ) = ∑_{k=1}^{n} ∫_{E} log \frac{dϕ(k, T_{k−1}μ)}{dλ_{k}} dT_{k}μ = ∫_{Σ_{n}} log \frac{dΦ_{n}(μ)}{dR_{n}} dμ  (11)

with the notation of (9). In a first stage for analysis it is reasonable to suppose that

(B) For any time n ≥ 1 the function (μ, ν) → ∫ log \frac{dϕ(n, ν)}{dλ_{n}} dμ is bounded continuous.

If I(μ|ν) denotes the relative entropy of μ with respect to ν, that is the function

I(μ|ν) = \{ \begin{matrix}∫ log \frac{dμ}{dν} dμ  if μ << ν \\ +∞  otherwise, \end{matrix} ,

Sanov’s theorem and Varadhan’s lemma yields

Theorem 2.1 Under (A) and (B), {Q_{n}^{N}, N ≥ 1} satisfies a LDP with good rate function

I_{n}(μ) = I(μ|Φ_{n}(μ)).

η_{[0,n]} is the unique minimizer of I_{n}.

Indeed, F_{n} is bounded continuous under (B) so that {Q_{n}^{N}, N ≥ 1} satisfies a LDP with good rate function I_{n} = I(.|R_{n}) − F_{n} according to Sanov’s theorem and Varadhan’s lemma ( see [19] for instance ). From the definition of I( |R_{n}) and F_{n}, it is obvious that I_{n} is also given by I_{n}(μ) = I(μ|Φ_{n}(μ)) from which it is easily seen that

I_{n}(μ) = 0 ⟺ μ = η_{[0,n]}.

At this point it is appropriate to address a deficiency in the preceding result. An approximatively equivalent condition of (B) is given by the two following assumptions

(C0) For any time n ≥ 1,

(x, ν) → log \frac{dϕ(n, ν)}{dλ_{n}}(x)

is uniformly continuous w.r.t. x and continuous w.r.t. ν.

(C) For any time n ≥ 1 there exists a non negative real number a_{n} so that

∀(x, ν) ∈ E × M_{1}(E) a_{n}^{−1} ≤ \frac{dϕ(n, ν)}{dλ_{n}}(x) ≤ a_{n}

A clear disadvantage of condition (C) is that it is in general not satisfied when E is not compact and in particular in many non linear filtering problems. Yet we are going to see that this condition can be relaxed considerably. The relevance of the foregoing results will be illustrated in section 3 when applied to non linear filtering problems. It is now convenient to introduce some additional notations. For any M > 0 we note ψ^{M} : IR → IR the cut-off function given by

ψ^{M}(x) = \{ \begin{matrix}x & if |x| ≤ M, \\ sign(x) M & if |x| > M, \end{matrix}

and F_{n}^{M} : M_{1}(Σ_{n}) → IR the function

F_{n}^{M}(μ) = ∑_{k=1}^{n} ∫_{E} ψ^{M} (log \frac{dϕ(k, T_{k−1}μ)}{dλ_{k}}) dT_{k}μ.

Under (C0) , F_{n}^{M} is bounded continuous ( beware here that this statement requires the uniform continuity ( and not only the continuity ) property of hypothesis (C0). Next conditions relax assumption (C). (C1) For any time n ≥ 0 and ϵ > 0 there exists a function L_{n;ϵ}, L_{n;ϵ}(M) goes to infinity when M goes to infinity, so that

R_{n}^{N} (e^{−NF_{n}}1I_{(|F_{n}−F_{n}^{M} |>ϵ)}) ≤ e^{−NL_{n,ϵ}(M)}.

(C2) For any time n ≥ 0 and for any A ∈ B(M_{1}(Σ_{n})) we have

lim_{M→∞} inf_{A} (I(.|R_{n}) − F_{n}^{M} ) = inf_{A} (I(.|R_{n}) − F_{n}) .

Let us describe the main result of this section

Theorem 2.2 Assume that the functions ϕ(n,.), n ≥ 1, satisfy conditions (A), (C0), (C1) and (C2). Then, for any n ≥ 0, {Q_{n}^{N} : N ≥ 1} satisfies a LDP with good rate function I_{n}.

The proof is based on the ideas of Azencott and Varadhan and amounts to replace the functions F_{n} ( which are a priori nor bounded nor continuous ) by the functions F_{n}^{M} to get the LDP up to a small error ϵ in the rate function by (C1) and then pass to the limit M → ∞ by (C2) to let finally ϵ ↓ 0. We leave the details to the reader.

Conditions (C1) and (C2) are hard to work with. In practice we will check the following more elegant conditions

(D1) For any time n ≥ 1, there exists constants c_{n} < ∞, α_{n} > 1 such that

R_{n}^{N} (e^{α_{n}NF_{n}}) ≤ e^{c_{n}N}  (12)

and, for every ϵ > 0 there exists a function L_{n,ϵ}, L_{n;ϵ}(M) goes to infinity when M goes to infinity, so that

R_{n}^{N} (|F_{n} − F_{n}^{M}| > ϵ) ≤ e^{−NL_{n,ϵ}(M)}.  (13)

(D2) For any time n ≥ 1, there exists constants δ_{n} > 0 C_{n} < ∞, D_{n} < ∞ and a function ϵ_{n}, ϵ_{n}(M) is going to zero when M is going to infinity, such that for any μ ∈ M_{1}(Σ_{n}) and M ∈ IR ∪ {∞}

I(μ|R_{n}) − F_{n}^{M}(μ) ≥ δ_{n} I(μ|R_{n}) − C_{n}
|F_{n}(μ) − F_{n}^{M}(μ)| ≤ ϵ_{n}(M) (I(μ|R_{n}) + D_{n})

Using Hölder’s inequality it can be checked directly that (D1) ⇒ (C1). On the other hand, for any A ∈ B(M_{1}(Σ_{n})) and any integer number L we have

inf_{A}{I(.|R_{n})−F_{n}^{M}} = inf {  inf_{A∩{I(.|R_{n})≤L}}{I(.|R_{n}) − F_{n}^{M}}; inf_{A∩{I(.|R_{n})≥L}}{I(.|R_{n}) − F_{n}^{M}}} .

(14)

Let us first assume that inf_{A} I_{n} < ∞. Then, the second assumption of (D2) yields

|  inf_{A∩{I(.|R_{n})≤L}}{I(.|R_{n}) − F_{n}^{M}} − inf_{A∩{I(.|R_{n})≤L}}{I(.|R_{n}) − F_{n}}| ≤ ϵ_{n}(M)(L + D_{n}). (15)

On the other hand, the first assumption shows that, uniformly in M,

inf_{A∩{I(.|R_{n})≥L}}{I(.|R_{n}) − F_{n}^{M}} ≥ δ_{n}L − C_{n}.

Thus, for L and M large enough, it is clear that (14) implies

inf_{A}{I(.|R_{n}) − F_{n}^{M}} = inf_{A∩{I(.|R_{n})≤L}}{I(.|R_{n}) − F_{n}^{M}},  inf_{A} I_{n} = inf_{A∩{I(.|R_{n})≤L}} I_{n}

and therefore

|inf_{A}{I(.|R_{n}) − F_{n}^{M}} − inf_{A}{I(.|R_{n}) − F_{n}}| ≤ ϵ_{n}(M)(L + D_{n}).

Also, if inf_{A} I_{n} = +∞, inf_{A∩{I(.|R_{n})≤L}} I_{n} = +∞ for any integer number L and therefore (15) gives, for any integer number L,

inf_{A}{I(.|R_{n}) − F_{n}^{M}} = inf_{A∩{I(.|R_{n})≥L}}{I(.|R_{n}) − F_{n}^{M}} ≥ δ_{n}L − C_{n}.

Letting L going to infinity implies

inf_{A}{I(.|R_{n}) − F_{n}^{M}} = +∞ = inf_{A} I_{n}

which completes the proof of (D2) ⇒ (C2). We end this section with an example of how the preceding theorem can be applied. This corollary will be one of the key tools used in most of the applications of our results to non linear filtering problems (cf section 3). It is quite remarkable that the weakening of condition (B) is compensated by an exponential moment condition.

Corollary 2.3 Suppose the functions ϕ(n,.), n ≥ 1, satisfy (A) and (C0) and that for any 1 ≤ k ≤ n, x ∈ E and μ ∈ M_{1}(E)

|log \frac{dϕ(k, μ)}{dλ_{k}}(x)| ≤ φ(x) + μ(ψ)  (16)

for some non negative and B(E)-measurable functions φ and ψ. In addition, assume that there exists constants α, β ∈]1, ∞] and ϵ > 0 such that \frac{1}{α} + \frac{1}{β} < 1 and for any 1 ≤ k ≤ n

∫ exp (αφ^{1+ϵ}) dλ_{k} ∨ ∫ exp (βψ^{1+ϵ}) dλ_{k} < ∞  (17)

Then, {Q_{n}^{N} : N ≥ 1} satisfies the LDP with good rate function I_{n}.

Proof: Recalling our discussion preceding the corollary we only have to check that (17) implies (D1) and (D2). For any n ≥ 1, choose and fix constants α, β > 1 and ϵ > 0 so that (17) is satisfied. Define p, q > 1 and δ > 1 by

\frac{1}{δ} = \frac{1}{α} + \frac{1}{β}  \frac{1}{p} = 1 − \frac{δ}{β}  \frac{1}{q} = 1 − \frac{1}{p}

Let us now state some useful bounds which are needed in the sequel. From (16) we find that for any μ ∈ M_{1}(Σ_{n}) and n ≥ 1

|F_{n}(μ)| ∨ |F_{n}^{M}(μ)| ≤ ∑_{k=0}^{n} T_{k}μ(ϕ + ψ)  (18)

and

|F_{n}(μ) − F_{n}^{M}(μ)| ≤ (\frac{2}{M} )^{ϵ} ∑_{k=0}^{n} T_{k}μ(ϕ^{1+ϵ} + ψ^{1+ϵ})  (19)

The last inequality is a clear consequence of Hölder’s inequality and the fact that (a + b)^{1+ϵ} ≤ 2^{ϵ}(a^{1+ϵ} + b^{1+ϵ}) for any a, b ≥ 0 and |ψ^{M}(x) − x| ≤ |x| 1_{|x|>M}. Let us now establish the moment condition (12). Using (18) we have

\frac{1}{N} log R_{n}^{N}(e^{δNF_{n}}) ≤ ∑_{k=0}^{n} log ∫ exp (δ(φ + ψ)) dλ_{k}

using Hölder’s inequality this shows that R_{n}^{N}(e^{δNF_{n}}) ≤ exp (NC_{n}) with

C_{n} = ∑_{k=0}^{n} log {∫ exp (αφ) dλ_{k} ∨ ∫ exp (βψ) dλ_{k}}

On the other hand we see from (19) that, for any positive δ,

R_{n}^{N}(|F_{n} − F_{n}^{M}| > δ) ≤ R_{n}^{N} (\{μ : ∑_{k=0}^{n} T_{k}μ(ϕ^{1+ϵ} + ψ^{1+ϵ}) > (\frac{M}{2} )^{ϵ} ϵ\})

≤ exp (−Nδ2^{−ϵ}M^{ϵ}) ( ∏_{k=0}^{n} ∫ exp (ϕ^{1+ϵ} + ψ^{1+ϵ})dλ_{k})^{N}

Again using Hölder’s inequality and recalling that α > p and β > q one concludes

\frac{1}{N} log R_{n}^{N}(|F_{n} − F_{n}^{M}| > δ) ≤ −L_{n,δ}(M)

with

L_{n,δ}(M) = δ2^{−ϵ}M^{ϵ} − ∑_{k=0}^{n} log (∫ exp (αφ^{1+ϵ}) dλ_{k} ∨ ∫ exp (βψ^{1+ϵ}) dλ_{k})

Now we proceed to the proof of (D2). Taking into consideration the inequality (18) we have for any μ ∈ M_{1}(Σ_{n}) and M < ∞

|F_{n}^{M}(μ)| ≤ μ(θ_{n})  with  θ_{n}(x_{0}, …, x_{n}) = ∑_{k=0}^{n} φ(x_{k}) + ψ(x_{k}).

Using the well known property of the relative entropy

I(μ|ν) = sup_{V ∈C_{b}(X)} (μ(V) − ν(e^{V}))  (20)

and the monotone convergence theorem it follows that

δ|F_{n}^{M}(μ)| ≤ I(μ|R_{n}) + log ∫ exp (δθ_{n}) dR_{n}.

Thus, we arrive at

I(μ|R_{n}) − F_{n}^{M}(μ) ≥ (1 − \frac{1}{δ}) I(μ|R_{n}) − \frac{1}{δ} ∑_{k=0}^{n} log ∫ exp (δ(φ + ψ))dλ_{k}.

Now, by a further use of Hölder’s inequality one gets

I(μ|R_{n}) − F_{n}^{M}(μ) ≥ (1 − \frac{1}{δ}) I(μ|R_{n}) − C

with

C = ∑_{k=0}^{n} log (∫ exp (αφ)dλ_{k} ∨ ∫ exp (βψ)dλ_{k}).

By a method similar to that used above one can also establish that for any μ ∈ M_{1}(Σ_{n})

|F_{n}(μ) − F_{n}^{M}(μ)| ≤ (\frac{2}{M} )^{ϵ} (I(μ|R_{n}) + D)

with

D = ∑_{k=0}^{n} log (∫ exp (αφ^{1+ϵ})dλ_{k} ∨ ∫ exp (βψ^{1+ϵ})dλ_{k}).

This ends the proof.

Before closing this section we examine how theorem 2.2 makes it possible to estimate in a simple way the probability of the events B_{n,ϵ} := {μ : d(μ, Φ_{n}(μ)) < ϵ}, ϵ > 0. Under (C0), μ → Φ_{n}(μ) is continuous so that B_{n,ϵ} is open for the weak topology. Recalling that d(μ, Φ_{n}(μ))) = 0 iff μ = η_{[0,n]}, we see that this event is an open neighborhood of η_{[0,n]}. If we denote ∥.∥_{T V} denotes the total variation norm then using the well known inequalities

d(μ, Φ_{n}(μ)) ≤ ∥μ − Φ_{n}(μ)∥_{T V} ≤ (2 I(μ|Φ_{n}(μ)))^{1/2}

and the large deviation upper bound one concludes that

lim sup_{N→∞} \frac{1}{N} log Q_{n}^{N}(\{μ : d(μ, Φ_{n}(μ)) ≥ ϵ\}) ≤ −\frac{ϵ^{2}}{2}

It follows that there exists N(ϵ) ≥ 1 such that for any N ≥ N(ϵ)

Q_{n}^{N} (\{μ : d(μ, Φ_{n} (μ)) < ϵ) ≥ 1 − exp −(\frac{N ϵ^{2}}{4} )

2.2 LDP for the Particles Density Profiles

The large deviations results presented in section 2.1 rely entirely on the existence of a family of reference distributions {λ_{n} : n ≥ 1} satisfying condition (A) and therefore does not apply to some filtering problems (see section 3). To remove this assumption we shall be dealing with the law P_{n}^{N}, n ≥ 0, N ≥ 1, of the particle density profiles

η^{N}(ξ_{n}) =^{def} \frac{1}{N} ∑_{i=1}^{N} δ_{ξ_{n}^{i}}.

We also can relax the continuity assumption (C0) into

(CW) : For any time n ≥ 1, ϕ(n, .) is continuous.

To insure an exponential tightness property we shall propose the following assumption which is motivated for its applications in non linear filtering problems. If, for any Markov transition M and any μ ∈ M_{1}(E) we denote μM the probability so that for any f ∈ C_{b}(E),

μMf = ∫ f(y)M(dy, x)μ(dx),

this hypothesis reads

(ET) : For any n ≥ 1, ϵ > 0 and for any Markov transition M on E, there exists a Markov kernel M̃ and 0 < δ ≤ ϵ such that

μM̃(A^{c}) < δ ⟹ ϕ(n, μ)M(A^{c}) < ϵ

for any μ ∈ M_{1}(E) and for any compact set A ⊂ E.

\underline{Remark} 2.4: Observe that condition (ET) holds if, for any n ≥ 1, there exists a Markov transition K_{n} on E and a non negative constant c(n) so that

ϕ(n, μ)(A^{c}) ≤ c(n) μK_{n}(A^{c})

for any compact set A ⊂ E.

Proposition 2.5 Assume that condition (ET) holds. Then, for any L > 0 and n ≥ 0 we can find a compact set K_{L} ⊂ M_{1}(E) so that

P (η^{N}(ξ_{n}) ∈ K_{L}^{c}) ≤ 4 e^{−N L}  (21)

Proof:

For every sequence of real numbers m = (m_{l})_{l≥1} satisfying lim_{l→∞} m_{l} = ∞ and m_{l} ≥ 1 and, every sequence of compact subsets A = (A_{l})_{l≥1} of E we shall denote C(A, m) the compact subset of M_{1}(E) given by

C(A, m) = ∩_{l≥1}G(A_{l}, m_{l})  G(A_{l}, m_{l}) = \{ν ∈ M_{1}(E) : ν(A_{l}^{c}) ≤ \frac{1}{m_{l}} \}  ∀l ≥ 1

We shall need a modification of Azencott and Stroock lemma (see for instance lemma 6.13 pp. 125 [34]).

Lemma 2.6 For any L < ∞ and for any sequence of real numbers m = (m_{l})_{l≥1} satisfying lim_{l→∞}m_{l} = ∞ and m_{l} ≥ 1, l ≥ 1, there exists a sequence of real numbers m̃ = (m̃_{l})_{l≥1} so that m̃_{l} ≥ m_{l} for any l ≥ 1, and

μM ∈ C(A, m̃) ⟹ μ^{⊗N} (\frac{1}{N} ∑_{i=1}^{N} δ_{x^{i}}M ∈ C(A, m)^{c}) ≤ 2 exp (−NL)

for any μ ∈ M_{1}(E), any Markov transition M on E, any sequence of compact sets A = (A_{l})_{l≥1} and any N ≥ 1.

Using this lemma we see that for any

• N ≥ 1,

• Markov kernel M on E,

• sequence of compact sets A = (A_{l})_{l≥1},

• sequence of real numbers m(0) = (m_{l}(0))_{l≥1} satisfying

lim_{l→∞} m_{l}(0) = ∞  and  m_{l}(0) ≥ 1  ∀l ≥ 1

we have

P (η^{N}(ξ_{n})M ∈ C(A, m(0))^{c})
≤ P (\{η^{N}(ξ_{n})M ∈ C(A, m(0))^{c}\} ∩ \{ϕ(n, η^{N}(ξ_{n−1}))M ∈ C(A, \overline{m}(0))\})
+P (ϕ(n, η^{N}(ξ_{n−1}))M ∈ C(A, \overline{m}(0))^{c})
≤ 2 e^{−N (n+1) L} + P (ϕ(n, η^{N}(ξ_{n−1}))M ∈ C(A, \overline{m}(0))^{c})

for any sequence of real numbers \overline{m}(0) = (\overline{m}_{l}(0))_{l≥1} chosen according to lemma 2.6. Hence, using (ET) there exists a sequence of real numbers m(1) = (m_{l}(1))_{l≥1} satisfying m_{l}(1) ≥ \overline{m}_{l}(0) for any l ≥ 1 and a Markov transition M_{!} so that

P (η^{N}(ξ_{n})M ∈ C(A, m(0))^{c}) ≤ 2 e^{−N (n+1) L} + P (η^{N}(ξ_{n−1})M_{1} ∈ C(A, m(1))^{c}) (22)

Using repeatedly (22) one concludes

P (η^{N}(ξ_{n}) ∈ C(A, m(0))^{c}) ≤ 2 ∑_{k=0}^{n−1} e^{−NL(n+1−k)} + P (η^{N}(ξ_{0})M_{n} ∈ C(A, m(n))^{c})

(23)

for some sequence of real numbers m(n) = (m_{l}(n))_{l≥1} and a Markov transition M_{n}. Since E is separable and complete η_{0}M_{1} … M_{n} is tight. Then, for any sequence or real numbers m̃ = (m̃_{l})_{l≥1} satisfying lim_{l→∞}m̃_{l} = ∞ one can choose the sequence of compact sets A = (A_{l})_{l≥1} so that

η_{0}M_{n} ∈ C(A, m̃)

Using lemma 2.6 it follows that

P (η^{N}(ξ_{0})M_{n} ∈ C(A, m(n))^{c}) ≤ 2 e^{−NL}

which, plugged in (23), gives a compact set K_{L} = C(A, m(0)) ⊂ M_{1}(E) such that

P (η^{N}(ξ_{n}) ∈ C(A, m(0))^{c}) ≤ 4 e^{−N L}.

We are now in position to state the main result of this section

Theorem 2.7 Assume that conditions (CW) and (ET) hold. Then, for any n ≥ 1, {P_{n}^{N} : N ≥ 1} obeys a large deviation principle with good rate function H_{n} given by

\{ \begin{matrix}H_{n}(μ) & = & inf_{ν}\{I (μ|ϕ(n, ν)) + H_{n−1}(ν)\}  n ≥ 1 \\ H_{0}(μ) & = & I(μ|η_{0}) \end{matrix}

In addition H_{n}(μ) = 0 iff μ = η_{n}, for any n ≥ 1.

Proof: Hereafter we shall denote for n ≥ 1, ν_{1}, ⋯, ν_{n} ∈ M_{1}(E)^{n}, ν̄_{n} = ν_{n} ⊗ ⋯ ⊗ ν_{1} and Ψ(n, ν̄_{n−1}) = ϕ(n, ν_{n−1}) ⊗ ⋯ ⊗ ϕ(1, ν_{1}) ⊗ η_{0} ∈ M_{1}(E^{n}).

Let us first show that H_{n} is a good rate function. Indeed, it is clearly non negative. Moreover, by induction one finds that

H_{n}(μ) = inf_{ν_{n−1},···ν_{1}∈M_{1}(E)^{n−1}}{I(μ ⊗ ν̄_{n−1}|Ψ(n, ν̄_{n−1}))}.

But, (μ, ν̄_{n−1}) → I(μ ⊗ ν̄_{n−1}|Ψ(n, ν̄_{n−1})) is a lower semi-continuous function since it can be obtained as a supremum of continuous functions by the formula

I(μ ⊗ ν̄_{n−1}|Φ(n, ν̄_{n−1})) = sup_{V ∈C_{b}(E^{n})}{∫ V dμ ⊗ ν̄_{n−1} − log ∫ e^{V} dΨ(n, ν̄_{n−1})}

where we have observed that the last term in the above supremum is continuous by assumption (CW). Hence, I is lower semi-continuous and since H_{n} is obtained by contraction over the last marginal, so is H_{n}. The fact that H_{n} has compact level sets with be a consequence of the exponential tightness assumed here and the proof of the weak large deviation principle below (see Dembo-Zeitouni, Lemma 1.2.18). Finally, it is clear that H_{n} admits η_{n} as a unique minimizer since I(μ ⊗ ν̄_{n−1}|Ψ(n, ν̄_{n−1})) vanishes only at η_{n} ⊗ ⋯ ⊗ η_{0}.

Let us now turn to the proof of the large deviation upper bound. We shall obtain in fact a LDUB for the process (η^{N}(ξ_{n}), ⋯, η^{N}(ξ_{0})) ∈ M_{1}(E)^{n+1} with rate function I_{n+1}(μ) = I(μ|Ψ(n + 1, μ̄_{n})). To this end we proceed by induction on the parameter n ≥ 0. Consider first the case n = 0. The particle system ξ_{0} = (ξ_{0}^{1}, …, ξ_{0}^{N}) consists of N i.i.d. variables with common law η_{0}. Thus Sanov’s theorem tells us that the family {P_{0}^{N} : N ≥ 1} obeys a LDUB with rate function H_{0}(μ) = I(μ|η_{0}). Assume that {P_{n−1}^{N} : N ≥ 1} obeys a LDUB with rate function I_{n−1} for some n ≥ 1.

To prove the result at time n, observe first that Proposition 2.5 insures that the law of (η^{N}(ξ_{n}), ⋯, η^{N}(ξ_{0})) is exponentially tight so that it is sufficient to prove the weak large deviation upper bound.

Applying Chebyshev’s inequality, we conclude that for any μ_{1}, ⋯, μ_{n−1} ∈ M_{1}(E)^{n}, any V ∈ C_{b}(E), any δ > 0,

P (1_{d(η^{N} (ξ_{j}),μ_{j})≤δ,1≤j≤n})
= P (1_{d(η^{N} (ξ_{j}),μ_{j})≤δ,1≤j≤n−1}ϕ(n, η^{N}(ξ_{n−1}))^{⊗N} (e^{N ∫ V dη^{N} (ξ_{n})−N ∫ V dη^{N} (ξ_{n})}))
≤ e^{−N ∫ V dμ_{n}+Nϵ(δ)}P (1_{d(η^{N} (ξ_{j}),μ_{j})≤δ,1≤j≤n−1}e^{N log ϕ(n,η^{N} (ξ_{n−1})(e^{V} )})  (24)

where ϵ(δ) is a function going to zero with δ.

Now, for any bounded continuous function V on E, any μ_{0}, ⋯, μ_{n−1} ∈ M_{1}(E),

lim sup_{δ→0} lim sup_{N→∞} \frac{1}{N} log P (1_{d(η^{N} (ξ_{j}),μ_{j})≤δ,1≤j≤n−1}e^{N ∫ V dη^{N} (ξ_{n})})

= lim sup_{δ→0} lim sup_{N→∞} \frac{1}{N} log P (1_{d(η^{N} (ξ_{j}),μ_{j})≤δ,1≤j≤n−1}e^{N log ϕ(n,η^{N} (ξ_{n−1}))(e^{V} )})
≤ − lim inf_{δ→0} inf{I_{n−1}(ν̄_{n−1}) − log ϕ(n, ν_{n−1})(e^{V}), d(ν_{j}, μ_{j}) ≤ δ, 1 ≤ j ≤ n − 1}
= −I_{n−1}(μ̄_{n−1}) − log ϕ(n, μ_{n−1})(e^{V})  (25)

where we have used in the last line our induction hypothesis and the fact that μ → log ϕ(n, μ)(e^{V}) is continuous to apply Laplace’s method. Taking the limit N going to infinity and then δ to zero, we find, thanks to our induction hypothesis, (24) and (25), that

lim sup_{δ→0} lim sup_{N→∞} \frac{1}{N} log P (1_{d(η^{N} (ξ_{j}),μ_{j})≤δ,1≤j≤n}) ≤ − ∫ V dμ_{n}+log ϕ(n, μ_{n−1})(e^{V})−I_{n−1}(μ̄_{n−1})

Taking the supremum over V and recalling that

I(μ_{n}|ϕ(n, μ_{n−1})) = sup_{V ∈C_{b}(E)}{∫ V dμ_{n} − log ϕ(n, μ_{n−1})(e^{V})}

gives the weak large deviation upper bound with rate function I_{n−1}(μ̄_{n−1}) + I(μ_{n}|ϕ(n, μ_{n−1})) = I_{n}(μ̄_{n}) .

We finally obtain the large deviation upper bound for the law of η^{N}(ξ_{n}) for n ∈ IN by the contraction principle.

Let us now turn to the lower bound. Again, we proceed by induction. At time n = 0, Sanov’s theorem shows that the law of η^{N}(ξ_{0}) satisfies a large deviation lower bound with rate function H_{0}(μ) = I(μ|η_{0}). Let us assume that the result is true at time n − 1, for some n ≥ 1. Let μ ∈ M_{1}(E) be given. We need to prove that for any δ > 0,

lim inf_{N→∞} \frac{1}{N} log P (d(η^{N}(ξ_{n}), μ) < δ) ≥ −H_{n}(μ).

We can of course restrict ourselves to μ such that H_{n}(μ) < ∞. Let ϵ > 0 be given and ν ∈ M_{1}(E) such that

H_{n}(μ) ≥ I(μ|ϕ(n, ν)) + H_{n−1}(ν) − ϵ.

A fortiori, since H_{n}(μ) < ∞ and H_{n−1}(ν) ≥ 0, I(μ|ϕ(n, ν)) ≤ H_{n}(μ) < ∞ so that μ is absolutely continuous with respect to ϕ(n, ν), dμ = e^{V} dϕ(n, ν) with a measurable function V such that ∫ e^{V} dϕ(n, ν) = 1.

Let us assume that V is bounded continuous. Then, for any δ′ > 0,

P (d(η^{N}(ξ_{n}), μ) < δ) ≥ P ({d(η^{N}(ξ_{n}), μ) < δ} ∩ {d(η^{N}(ξ_{n−1}), ν) < δ′})
= P (1_{{d(η^{N} (ξ_{n−1}),ν)<δ′}}ϕ(n, η^{N}(ξ_{n−1}))^{⊗N} (d(η^{N}(ξ_{n}), μ) < δ))
≥ e^{−N ∫ V dμ+N log ∫ e^{V} dϕ(n,ν)−Nη}

×P (1_{{d(η^{N} (ξ_{n−1}),ν)<δ′}}ϕ_{V} (n, η^{N}(ξ_{n−1}))^{⊗N} (d(η^{N}(ξ_{n}), μ) < δ)) (26)

where the last line is true for any η > 0 provided δ, δ′ are small enough (since we assumed V bounded continuous) and we have used the notation

dϕ_{V} (n, ν)(ξ) = \frac{e^{V (ξ)}dϕ(n, ν)(ξ)}{∫ e^{V} dϕ(n, ν)}.

Now, for any given ν, the law of large numbers asserts that η^{N}(ξ_{n}) converges towards ϕ_{V} (n, ν) almost surely under ϕ_{V} (n, ν)^{⊗N}. Since ν → ϕ(n, ν) is continuous, ϕ_{V} (n, ν′) goes to ϕ_{V} (n, ν) = μ as ν′ goes to ν. Hence, for any ν′ such that {d(ν′, ν) ≤ δ′} with δ′ small enough,

lim_{N→∞} ϕ_{V} (n, ν′)^{⊗N} (d(η^{N}(ξ_{n}), μ) < δ) = 1.

We deduce by bounded convergence theorem that for δ′ small enough,

lim_{N→∞} \frac{P (1_{\{d(η^{N} (ξ_{n−1}),ν)≤δ′\}}ϕ(n, η^{N}(ξ_{n−1}))^{⊗N} (d(η^{N}(ξ_{n}), μ) ≤ δ))}{P (d(η^{N}(ξ_{n−1}), ν) < δ′)} = 1

Now, by our induction hypothesis,

lim inf_{N→∞} \frac{1}{N} log P (d(η^{N}(ξ_{n−1}), ν) < δ′) ≥ −H_{n−1}(ν)

so that we obtain finally

lim inf_{N→∞} \frac{1}{N} log P (d(η^{N}(ξ_{n−1}), ν) ≤ δ′) ≥ −H_{n−1}(ν) − N ∫ V dμ + N log ∫ e^{V} dϕ(n, ν)
= −H_{n−1}(ν) − I(μ|ϕ(n, ν)) ≥ −H_{n}(μ) − ϵ.

To deal with the general case, we remark that in exercise 6.2.20 of Dembo-Zeitouni, it is shown that the continuous bounded away from zero and infinity densities are dense in the level sets of the relative entropy

E_{L} = {f ∈ L^{1}(ϕ(n, ν)), f ≥ 0 ϕ(n, ν)a.s., I(f.dμ|ϕ(n, ν)) = ∫ f log fdϕ(n, ν) ≤ L} for any L ∈ IR^{+}. Let μ_{p} = e^{V_{p}}dϕ(n, ν), with bounded continuous functions V_{p}, be a sequence in E_{H_{n}(μ)−H_{n−1}(ν)+ϵ} which converges to μ. For any δ > 0, for p large enough,

\{α ∈ M_{1}(E) : d(α, μ_{p}) < \frac{δ}{2}\} ⊂ \{α ∈ M_{1}(E) : d(α, μ) < δ\}

so that the previous result shows that

lim inf_{N→∞} \frac{1}{N} log P (\{d(η^{N}(ξ_{n−1}), ν) ≤ δ′\} ∩ \{d(η^{N}(ξ_{n}), μ) ≤ δ\})

≥ lim inf_{N→∞} \frac{1}{N} log P (\{d(η^{N}(ξ_{n−1}), ν) ≤ δ′\} ∩ \{d(η^{N}(ξ_{n}), μ_{p}) ≤ \frac{δ}{2}\})
≥ −H_{n−1}(ν) − I(μ_{p}|ϕ(n, ν))
≥ −H_{n}(μ) − ϵ

where we have used in the last line the fact that μ_{p} ∈ E_{H_{n}(μ)−H_{n−1}(ν)+ϵ}. We can now let ϵ going to zero to obtain the large deviation lower bound with rate H_{n} for the law of η^{N}(ξ_{n}).

3 Applications to Non Linear Filtering

3.1 Introduction

The basic model for the general Non Linear Filtering problem consists of a time inhomogeneous Markov process X and a non linear observation Y with observation noise V. Namely, let (X, Y) be the Markov process taking values in E × IR^{d}, d ≥ 1, and defined by the system:

F(X/Y)  \{ \begin{matrix}X = (X_{n})_{n≥0} \\ Y_{n} = h_{n} (X_{n}) + V_{n}  n ≥ 0 \end{matrix}  (27)

where E is a locally compact and separable metric space, h_{n} : E → IR^{d}, d ≥ 1, are bounded continuous functions and V_{n} are independent random variables with continuous and positive density g_{n} with respect to Lebesgue measure. The signal process X that we consider is assumed to be a non-inhomogeneous and E-valued Markov process with Feller transition probability kernel K_{n}, n ≥ 1, and initial probability measure ν, on E. We will assume the observation noise V and X are independent.

The classical filtering problem is concerned with estimating the distribution of X_{n} conditionally to the observations up to time n. Namely,

π_{n}(f) =^{def} E(f(X_{n})/Y_{0}, …, Y_{n})  (28)

for all f ∈ C_{b}(E). This problem has been extensively studied in the literature and, with the notable exception of the linear-Gaussian situation or wider classes of models (Bènes filters [3]) optimal filters have no finitely recursive solution (Chaleyat-Maurel/Michel [7]). Although Kalman filtering ([23],[26]) is a popular tool in handling estimation problems its optimality heavily depends on linearity. When used for non linear filtering (Extended Kalman Filter) its performance relies on and is limited by the linearizations performed on the concerned model. The interacting particle systems approach developed hereafter can be seen as a non linear filtering method which discards linearizations. More precisely these techniques use the non linear system model itself in order to solve the filtering problem. The problem of assessing the distributions (28) is of course related to that of recursively computing the conditional distributions π_{n}, n ≥ 0, which provides all statistical informations about the states variables X_{n} obtainable from the observations (Y_{0}, …, Y_{n}), n ≥ 0. For a detailed discussion of the filtering problem the reader is referred to the pioneering paper of Stratonovich [33] and to the more rigorous studies of Shiryaev [32] and Kallianpur-Striebel [24]. More recent developments can be found in Ocone [27] and Pardoux [28]. Some collateral readings such as Kunita [25], Stettner [31], Michel [7] will be helpful in appreciating the relevance of our approximations.

3.2 Formulation of the Non Linear Filtering Problem

Let us introduce the filtering model in such a way that the techniques of section 2 can be applied. To this end it is convenient to study the distribution of the state process X_{n} conditionally on the observation up to time (n − 1). Namely,

η_{n}f =^{def} E (f(X_{n})/Y_{0}, …, Y_{n−1}) ∀n ≥ 0 ∀f ∈ C_{b}(E)

with the convention η_{0} = ν. The following result shows that the dynamics structure of the conditional distributions η_{n}, n ≥ 0, can be viewed as a special case of (2).

Lemma 3.1 (Kunita [25],Stettner [31]) Given a fixed observation record Y=y, (η_{n})_{n≥0} is solution of the M_{1}(E)-valued dynamical system

η_{n+1} = ϕ_{n+1}(y_{n}, η_{n})  n ≥ 0  η_{0} = ν  (29)

where y_{n} ∈ IR^{d} is the current observation and ϕ_{n} is the continuous function given by

ϕ_{n+1}(y_{n}, η) = ψ_{n}(y_{n}, η)K_{n+1}  (30)

with

ψ_{n}(y_{n}, η)f =^{def} \frac{∫ f(x) \overline{g}_{n}(y_{n}, x) η(dx)}{∫ \overline{g}_{n}(y_{n}, z) η(dz)} ∀f ∈ C_{b}(E), η ∈ M_{1}(E)

The equation (29) is usually called the non linear filtering equation. Even if it looks innocent, it can rarely be solved analytically and its solving requires extensive calculations. To obtain a computionnally feasible solution some kind of approximation is needed.

We observe that the recursion (30) involves two separate mechanisms. Namely, the first one

μ(dx) ↦ \frac{\overline{g}_{n}(Y_{n}, x)}{∫ \overline{g}_{n}(Y_{n}, z) μ(dz)}μ(dx)

updates the distribution given the current observation. The second one

μ ↦ μK_{n}

does not depends on the current observation. It is usually called the prediction.

3.3 Interacting Particle Systems Approximations

Recalling the description (3), and using the fact that

ϕ_{n+1} (Y_{n}, \frac{1}{N} ∑_{i=1}^{N} δ_{z^{i}}) = (∑_{i=1}^{N} \frac{\overline{g}_{n}(Y_{n}, z^{i})}{∑_{j=1}^{N} \overline{g}_{n}(Y_{n}, z^{i})} δ_{z^{i}}) K_{n+1}  (31)

the N-particle system associated to (29) is defined by

P_{Y} (ξ_{n+1} ∈ dx/ ξ_{n} = z) = ∏_{j=1}^{N} ∑_{i=1}^{N} \frac{\overline{g}_{n}(Y_{n}, z^{i})}{∑_{j=1}^{N} \overline{g}_{n}(Y_{n}, z^{i})} K_{n+1}(z^{i}, dx^{j})

Thus, we see that the particles move according the following rules

1. Updating: When the observation Y_{n} = y_{n} is received, each particle examines the system of particles ξ_{n} = (ξ_{n}^{1}, …, ξ_{n}^{N}) and chooses randomly a site ξ_{n}^{i} with probability

\frac{\overline{g}_{n}(y_{n}, ξ_{n}^{i})}{∑_{j=1}^{N} \overline{g}_{n}(y_{n}, ξ_{n}^{j})}

2. Prediction: After the updating mechanism each particle evolves according the transition probability kernel of the signal process.

This particle approximation of the non linear filtering equation belongs to the class of algorithms called genetic algorithms. These algorithms are based on the genetic mechanisms which guide natural evolution: exploration/mutation and updating/selection. They were introduced by J.H. Holland [22] to handle global optimization problems on a finite set.

3.4 Large Deviation for Interacting Particle Systems

In [17] we proposed some exponential bounds to prove that for a fixed observation record Y=y, for every f ∈ C_{b}(E) and for every n ≥ 0, η^{N}(ξ_{n})f converges P − a.s. to η_{n}f as the size N of the systems is growing. Our aim is now to show how the LDP developed in section 2 can be applied to obtain the exact exponential rate of convergence of our random particle approximation. We will use the following assumptions

(H0) : For any time n ≥ 1, K_{n} is Feller so that μ → μK_{n} is continuous for the weak topology. For any time n ≥ 0, h_{n} is bounded continuous and g_{n} is a positive continuous function.

(H1) : For any time 1 ≤ k ≤ n there exists a reference probability measure λ_{k} ∈ M_{1}(E), α > 1, ϵ > 0 and a B(E)-measurable function φ so that

δ_{x}K_{k} ∼ λ_{k}

In addition z → log \frac{dδ_{x}K_{k}}{dλ_{k}} (z) is Lipschitz, uniformly on the parameter x such that

|log \frac{dδ_{x}K_{k}}{dλ_{k}} (z)| ≤ φ(z) and ∫ exp (αφ^{1+ϵ}) dλ_{k} < ∞  (32)

Let the condition (H0) be satisfied. Then, it is not hard to see that there exists positive functions a_{n} : IR^{d} → IR_{+} such that

a_{n}(y)^{−1} ≤ \overline{g}_{n}(y, x) ≤ a_{n}(y)  ∀(y, x) ∈ IR^{d} × E  (33)

We conclude that for any observation record Y = y, (ϕ_{n+1}(y_{n}, .), n ≥ 0) satisfies (C). Moreover, for any B(E)-measurable function f : E → IR_{+} and for every n ≥ 0, y ∈ IR^{d} and μ ∈ M_{1}(E) we have

a_{n}(y)^{−2} μK_{n+1}f ≤ ϕ_{n+1}(y, μ)f ≤ a_{n}(y)^{2} μK_{n+1}f

Therefore one concludes easily that under (H0) theorem 2.7 applies without further work. More precisely we have proved the following proposition Proposition 3.2 Assume that condition (H0) holds. Then, for any observation record Y = y and n ≥ 0, the laws {P_{n}^{N} : N ≥ 1}, of the particle density profiles

η^{N}(ξ_{n}) = \frac{1}{N} ∑_{i=1}^{N} δ_{ξ_{n}^{i}} N ≥ 1

satisfy a LDP with rate function H_{n} given by

H_{n}(μ) = sup_{V ∈C_{b}(E)} (μ(V) + inf_{ν∈M_{1}(E)} (H_{n−1}(ν) − log (ψ_{n−1}(y_{n−1}, ν)K_{n}e^{V})))  n ≥ 1
H_{0}(μ) = I(μ|ν)

H_{n}(μ) = 0 iff μ = η_{n}, for any n ≥ 0.

Under condition (H1) we now study LDP for the law Q_{n}^{N}, n ≥ 0, N ≥ 1, of the empirical distribution on path space

η^{N}(ξ_{[1,n]}) = \frac{1}{N} ∑_{i=1}^{N} δ_{(ξ_{1}^{i},...,ξ_{n}^{i})}

We see from (32) and (H0) that for any 1 ≤ k ≤ n, y ∈ IR^{d}, μ ∈ M_{1}(E) and z ∈ E

|log \frac{dϕ_{k}(y, μ)}{dλ_{k}}(z)| ≤ φ(z)

¿From this and corollary 2.3 we have

Proposition 3.3 Let (H0) and (H1) be satisfied. Then, for any observation record Y = y, {Q_{n}^{N} : N ≥ 1} obeys a LDP with rate function I_{n}(μ) = I(μ|Ψ_{n}(μ)) where

Ψ_{n}(μ) = ν ⊗ ψ_{0}(y_{0}, T_{0}μ)K_{1} ⊗ … ⊗ ψ_{n−1}(y_{n−1}, T_{n−1}μ)K_{n}

and T_{k}μ, 0 ≤ k ≤ n is the k-th marginal of a given probability measure μ.

\underline{Remark} 3.4: To see the strength of the preceding propositions, let us first quote that (H0) only depends on the functions g_{n} and h_{n} ; the LDP results stated in proposition 3.2 does not depend on the form of the Feller signal process X. In contrast to the latter, the condition (H1) depends on the transitions Markov kernels K_{n}, n ≥ 1. As the preceding proposition shows, so long as (H1) holds, the law of the empirical measure on path space satisfies a LDP. Moreover, referring to the remarks preceding section 3, the rate functions H_{n}, n ≥ 0, are smaller than the corresponding contractions of the rate functions I_{n}, n ≥ 0.

We now turn to some applications of these propositions.

Example 1 As a typical example of non linear filtering problem assume the functions h_{n} : E → IR^{d}, n ≥ 1, are bounded continuous and the densities g_{n} given by

g_{n}(v) = \frac{1}{((2π)^{d}|R_{n}|)^{1/2}} exp (−\frac{1}{2}v′ R_{n}^{−1} v)

where R_{n} is a d × d symmetric positive matrix. This correspond to the situation where the observations are given by

Y_{n} = h_{n}(X_{n}) + V_{n}  ∀n ≥ 1  (34)

where (V_{n})_{n≥1} is a sequence of IR^{d}-valued and independent random variables with Gaussian densities. After some easy manipulations one gets the bounds (33) with

log a_{n}(y) = \frac{1}{2} ∥R_{n}^{−1}∥ ∥h_{n}∥^{2} + ∥R_{n}^{−1}∥ ∥h_{n}∥ ∥y∥

where ∥h_{n}∥ = sup_{x∈E} |h_{n}(x)| and ∥R_{n}^{−1}∥ is the spectral radius of R_{n}^{−1}.

Let us now investigate assumption (H1) through the following example

Example 2 Suppose that E = IR^{m}, m ≥ 1 and K_{n}, n ≥ 1 are given by

K_{n}(x, dz) = \frac{1}{((2π)^{m}|Q_{n}|)^{1/2}} exp (−\frac{1}{2}(z − b_{n}(x))′ Q_{n}^{−1} (z − b_{n}(x)))

where Q is a m × m symmetric non negative matrix and b_{n} : IR^{m} → IR^{m} is a bounded continuous function. This correspond to the situation where the signal process is given by

X_{n} = b_{n}(X_{n}) + W_{n}  ∀n ≥ 1  (35)

where (W_{n})_{n≥1} is a sequence of IR^{m}-valued and independent random variables with Gaussian densities. It is not difficult to check that (H1) is satisfied with

λ_{n}(dz) = \frac{1}{((2π)^{m}|Q_{n}|)^{1/2}} exp (−\frac{1}{2}z′ Q_{n}^{−1} z) dz.

Indeed, we then find out that

log \frac{dδ_{x}K_{n}}{dλ_{n}} = const. − b_{n}(x)′Q_{n}^{−1}z

which insures the Lipschitz property as well as the growth property with

φ(z) = \frac{1}{2}∥b_{n}∥^{2}∥Q_{n}^{−1}∥ + ∥Q_{n}^{−1}∥ ∥b_{n}∥ |z| ∀z ∈ IR.

Thus, the Gaussian example satisfies (H1). Let us notice that it does not satisfies condition (B) ( or even (C)). We discuss this hypothesis below.

Example 3 Let us suppose that E = IR and

K_{n}(x, dz) = \frac{1}{\sqrt{2π}} e^{− \frac{1}{2} (z−b_{n}(x))^{2}} dz  (36)

where b_{n} : IR → IR is a bounded B(E)-measurable function such that b_{n}(0) = 0 and b_{n}(1) = −1. Then, hypothesis (C) is not satisfied. Suppose K_{n} satisfies (C) for some bounded function φ. Clearly there exists an absolutely continuous probability measure with density p_{n} such that

∀x, z ∈ IR c_{n}^{−1} p_{n}(z) ≤ e^{− \frac{1}{2} (z−b_{n}(x))^{2}} ≤ c_{n} p_{n}(z)

for some positive constant c_{n}. Using the fact that b_{n}(1) = −1 we obtain

lim_{z→∞} p_{n}(z)e^{\frac{z^{2}}{2}} = 0

On the other hand b_{n}(0) = 0 implies p_{n}(z)e^{\frac{z^{2}}{2}} ≥ c_{n}^{−1} which is absurd.

In fact, the failure of hypothesis (C) is linked in general with the non compactness of E. We have already pointed out that proposition 3.3 is a refinement of proposition 3.2. To be more precise the exponential moment condition (H1) allows us to prove a LDP for the empirical measure on the path space. Now, it is natural to examine some examples where the condition (H1) is not met but still hypothesis (H0) is fulfilled.

Example 4 Let us suppose that E = IR and

K_{n}(x, dz) = \sqrt{\frac{ϵ_{n}(x)}{2π}} exp (−\frac{1}{2}ϵ_{n}(x) z^{2}) dz

where ϵ_{n} : IR → IR is a continuous function such that

∀x ∈ IR  ϵ_{n}(x) > 0  and  lim_{|x|→∞} ϵ_{n}(x) = 0.

It is not difficult to see that K_{n} satisfies (H0). On the other hand, let us assume that K_{n} satisfies (H1) for some function φ. Since δ_{x}K_{n} is absolutely continuous with respect to Lebesgue measure for any x ∈ E, the probability measure λ_{n} described in (H1) is absolutely continuous with respect to Lebesgue measure. Therefore, there exists a probability density p_{n} such that

∀x, z ∈ IR e^{−φ(z)} p_{n}(z) ≤ \sqrt{ϵ_{n}(x)} exp (−\frac{1}{2}ϵ_{n}(x) z^{2}) ≤ e^{φ(z)} p_{n}(z).

Letting |x| → ∞ one gets e^{−φ(z)}p_{n}(z) = 0 for any z ∈ IR which is absurd since we also assumed ∫ e^{φ^{1+ϵ}(z)}p_{n}(z)dz < ∞.

Our interacting particle system approach is not restricted to non linear filtering problem with Gaussian transitions K_{n} or with observations corrupted by Gaussian perturbations. As a result we have a great freedom in the design and the physical construction of the non linear filtering model. It can be argued that in practice it is commonly assumed that the signal X and its noisy observation Y are given by (35) and (34). Under such assumptions the synthesis of the optimal filter is carried out recursively by the well known Kalman-Bucy filter. More precisely, the conditional distributions are Gaussian and the structure of the optimal filter is determined by a recursion relation on the conditional means and on the matrix of errors of observations. In several practical problems the conditional distribution may have several different modes and the conditional expectation is not meaningful. On the other hand the observed signal process X has no reason to be “linear and Gaussian” and we have to find a more realistic model. We now present some examples of other kind of densities that can be handled in our framework.

Example 5 Suppose that d = 1 and g_{n} is a Cauchy density

g_{n}(v) = \frac{θ_{n}}{π (v^{2} + θ_{n}^{2})} θ_{n} > 0

In this situation the weight functions \overline{g}_{n} is given by

\overline{g}_{n}(y, x) = \frac{y^{2} + θ_{n}^{2}}{(y − h_{n}(x))^{2} + θ_{n}^{2}} ∀(y, x) ∈ IR × E

Notice that

\frac{y^{2} + θ_{n}^{2}}{y^{2} + θ_{n}^{2} + ∥h_{n}∥^{2} + 2|y| ∥h_{n}∥} ≤ \overline{g}_{n}(y, x) ≤ 1 + (\frac{y}{θ_{n}} )^{2}

It follows that (33) holds with

a_{n}(y) = 1 + ((\frac{y}{θ_{n}} )^{2} ∨ \frac{(|y| + ∥h_{n}∥)^{2}}{y^{2} + θ_{n}^{2}} )

Example 6 Suppose d = 1 and g_{n} is a bilateral exponential density

g_{n}(v) = \frac{1}{2} α_{n} exp (−α_{n}|v|) α_{n} > 0

In this case the weight functions \overline{g}_{n} is given by

\overline{g}_{n}(y, x) = exp (α_{n} (|y| − |y − h_{n}(x)|))

Observe that

−∥h_{n}∥ ≤ |y| − |y − h_{n}(x)| ≤ ∥h_{n}∥ ∀(y, x) ∈ IR × E

One concludes that (33) is satisfied with a_{n}(y) = exp (α_{n}∥h_{n}∥).

Example 7 Suppose E = IR and K_{n}, n ≥ 1, are given by

K_{n}(x, dz) = \frac{1}{2} α exp (−α|z − b(x)|)dz α > 0 b ∈ C_{b}(IR)

This corresponds to the situation where the signal process X is given by

X_{n} = b(X_{n−1}) + W_{n} n ≥ 1

where (W_{n})_{n≥1} is a sequence of IR^{m}-valued and independent random variables with bilateral exponential densities. Note that K_{n} may be written

K_{n}(x, dz) = \frac{1}{2} α exp (α(|z| − |z − b(x)|)) λ_{n}(dz) with λ_{n}(dz) = \frac{1}{2} α exp (−α|z|) dz

It follows that (H1) holds since | log \frac{δ_{x}K_{n}}{dλ_{n}} (z)| has Lipschitz norm 2α + α∥b∥.

3.5 Large Deviations for Interacting and Branching Particle Systems

The interacting particle system approach described previously is the crudest of the random particle methods introduced in [17]. The goal of this section is to study large deviation of the particle density profiles associated to a branching refinement method. As we shall see this algorithm is a clear extension of the genetic type algorithm described in section 3.3. The description of the branching particle particle system under study first appears in [17]. It differs from the branching particle algorithms introduced by Crisan and Lyons in [8], [9] and [10]. Intuitively speaking, our branching approach consists in introducing at each mutations a fixed number of auxiliary branching particles but at the end of the selection mechanism most of them are killed. Several numerical investigations have revealed that a clear benefit can be obtained by introducing auxiliary branching particles. In [17] we proved that the corresponding particle density profiles weakly converge to the desired conditional distribution as the size of the system is growing but we let open the question whether or not much loss of performance is incurred by one of these algorithms. The main purpose of this section is to study the LDP associated to such approximations and to compare its rate function with the rate function H_{n} which governs the LDP associated to the interacting particle approach described in 3.3. From such constructions we will show that its rate function is greater than the rate function H_{n}.

Let us describe our new process. Let Y = y be a given sequence of observation records. The idea is to replace the Mutation/Prediction transition by a branching mechanism.

Namely, the system of particle is now described by the following Markov model

P_{[y]}(ζ_{0} ∈ dz) = ∏_{p_{1}=1}^{N_{1}} ∏_{p_{2}=1}^{N_{2}} ν(dz^{p_{1},p_{2}})

P_{[y]}(ζ̂_{n} ∈ dx/ ζ_{n} = z) = ∏_{p_{1}=1}^{N_{1}} ∑_{i_{1},i_{2}=1}^{N_{1},N_{2}} \frac{\overline{g}_{n}(y_{n}, z^{i_{1},i_{2}})}{∑_{j_{1},j_{2}=1}^{N_{1},N_{2}} \overline{g}_{n}(y_{n}, z^{j_{1},j_{2}})} δ_{z^{i_{1},i_{2}}} (dx^{p_{1}})

P_{[y]}(ζ_{n+1} ∈ dz/ζ̂_{n} = x) = ∏_{p_{1}=1}^{N_{1}} ∏_{p_{2}=1}^{N_{2}} K_{n+1}(x^{p_{1}}, dz^{p_{1},p_{2}})

where dx (resp. dz) is an infinitesimal neighborhood of x = (x^{1}, …, x^{N_{1}}) and z = (z^{i_{1},i_{2}})_{1≤i_{1}≤N_{1},1≤i_{2}≤N_{2}}. Note that

ϕ_{n+1} (y_{n}, η^{N_{1},N_{2}}(ζ_{n})) = ( ∑_{i_{1},i_{2}=1}^{N_{1},N_{2}} \frac{\overline{g}_{n}(y_{n}, ζ_{n}^{i_{1},i_{2}})}{∑_{j_{1},j_{2}=1}^{N_{1},N_{2}} \overline{g}_{n}(y_{n}, ζ_{n}^{j_{1},j_{2}})} δ_{ζ_{n}^{i_{1},i_{2}}} ) K_{n+1}

and

P_{[y]}(ζ̂_{n} ∈ dx/ ζ_{n} = z) = ∏_{p_{1}=1}^{N_{1}} ∑_{i_{1}=1}^{N_{1}} \frac{∑_{k_{2}=1}^{N_{2}} \overline{g}_{n}(y_{n}, z^{i_{1},k_{2}})}{∑_{j_{1},j_{2}=1}^{N_{1},N_{2}} \overline{g}_{n}(y_{n}, z^{j_{1},j_{2}})} ∑_{i_{2}=1}^{N_{2}} \frac{\overline{g}_{n}(y_{n}, z^{i_{1},i_{2}})}{∑_{k_{2}=1}^{N_{2}} \overline{g}_{n}(y_{n}, z^{i_{1},k_{2}})}δ_{z^{i_{1},i_{2}}} (dx^{p_{1}})

(37)

The evolution in time of the particle systems is now described as follows :

1. At the time n = 0 : The particle system ζ_{0} = (ζ_{0}^{i_{1},i_{2}} ; 1 ≤ i_{1} ≤ N_{2}, 1 ≤ i_{2} ≤ N_{2}) consists of N_{1}N_{2} i.i.d. variables with the same distribution ν.

2. At the time n ≥ 1 : At the time n, the particle system ζ_{n} = (ζ_{n}^{i_{1},i_{2}} ; 1 ≤ i_{1} ≤ N_{1}, 1 ≤ i_{2} ≤ N_{2}) consists of N_{1}N_{2} particles.

(a) When the observation Y_{n} = y_{n} is received, each particle ζ̂_{n}^{i_{1}}, 1 ≤ i_{1} ≤ N_{1} chooses a sub-system of auxiliary particles (ζ_{n}^{j_{1},1}, …, ζ_{n}^{j_{1},N_{2}}), 1 ≤ j_{1} ≤ N_{1}, at random with probability

\frac{∑_{k=1}^{N_{2}} \overline{g}_{n}(y_{n}, ζ_{n}^{j_{1},k})}{∑_{i=1}^{N_{1}} ∑_{j=1}^{N_{2}} \overline{g}_{n}(y_{n}, ζ_{n}^{i,j})}

and moves randomly to the site ζ_{n}^{j_{1},j_{2}}, 1 ≤ j_{2} ≤ N_{2}, in the chosen sub-system with probability

\frac{\overline{g}_{n}(y_{n}, ζ_{n}^{j_{1},j_{2}})}{∑_{k=1}^{N_{2}} \overline{g}_{n}(y_{n}, ζ_{n}^{j_{1},k})}

Therefore, the particle system ζ̂_{n} consists of N_{1} particles.

(b) In the branching mechanism each particle ζ̂_{n}^{i_{1}}, 1 ≤ i_{1} ≤ N_{1}, branches independently into a fixed number N_{2} of auxiliary i.i.d.particles with common law K_{n+1}(ζ̂_{n}^{i_{1}},.). Namely,

ζ̂_{n}^{i_{1}} ∈ E ⟶ (ζ_{n+1}^{i_{1},1}, …, ζ_{n+1}^{i_{1},N_{2}}) ∈ E^{N_{2}} i.i.d. ∼ K_{n+1}(ζ̂_{n}^{i_{1}},.)

Therefore, at the time (n + 1) the particle system ζ_{n+1} consists of N_{1}N_{2} particles.

\underline{Remark} 3.5: In view of the preceding description we see that the selection/updating mechanism (a) is decomposed into two separate transitions. In the first one each particle ζ̂_{n}^{i_{1}}, 1 ≤ i_{1} ≤ N_{1}, chooses one of the N_{1} sub-systems

{(ζ_{n}^{j_{1},k})_{1≤k≤N_{2}} : 1 ≤ j_{1} ≤ N_{1}}

in accordance with the observation and the position of the N_{2} auxiliary particles. When the sub-system (ζ_{n}^{j_{1},k})_{1≤k≤N_{2}}, 1 ≤ j_{1} ≤ N_{1} is chosen the particle ζ̂_{n}^{i_{1}} moves to a given site in this sub-system according to the distribution

∑_{k=1}^{N_{2}} \frac{\overline{g}_{n}(y_{n}, ζ_{n}^{j_{1},k})}{∑_{l=1}^{N_{2}} \overline{g}_{n}(y_{n}, ζ_{n}^{j_{1},l})} δ_{ζ_{n}^{j_{1},k}}

We begin by noting that the latter transition can be written

\frac{\overline{g}_{n}(y_{n}, x)}{∫ \overline{g}_{n}(y_{n}, z) \frac{1}{N_{2}} ∑_{l=1}^{N_{2}} δ_{ζ_{n}^{j_{1},l}}(dz)} \frac{1}{N_{2}} ∑_{k=1}^{N_{2}} δ_{ζ_{n}^{j_{1},k}}(dx)  (38)

By definition of the sub-system (ζ_{n}^{j_{1},k})_{1≤k≤N_{2}}, with n ≥ 1, the empirical measure

\frac{1}{N_{2}} ∑_{k=1}^{N_{2}} δ_{ζ_{n}^{j_{1},k}}(dx)

is a particle approximation of the probability measure K_{n}(ζ̂_{n−1}^{j_{1}}, dx). Thus, intuitively speaking, (38) approximates

\frac{\overline{g}_{n}(y_{n}, x)}{∫ \overline{g}_{n}(y_{n}, z) K_{n}(ζ̂_{n−1}^{j_{1}}, dz)} K_{n}(ζ̂_{n−1}^{j_{1}}, dx)

which is the conditional distribution of X_{n} with respect to Y_{n} = y_{n} and X_{n−1} = ζ̂_{n−1}^{j_{1}}. In other words the second transition in the mechanism (a) can be viewed as a mutation for each particle in accordance with the observation. In this situation we see that the particles track the unknown process by using mutations depending on the observation records.

Our next objective is to study large deviations upper bound for the laws P_{n}^{N_{1},N_{2}} of the particle density profiles

η^{N_{1},N_{2}}(ζ_{n}) = \frac{1}{N_{1}N_{2}} ∑_{i_{1}=1}^{N_{1}} ∑_{i_{2}=1}^{N_{2}} δ_{ζ_{n}^{i_{1},i_{2}}}

The arguments are similar to those used to prove theorem 2.7. We will also work with the condition (ET) page 12. If this condition takes place then, using the same line of arguments as those used in the proof of proposition 2.5, one has the following result

Proposition 3.6 Assume that condition (H0) holds. Then for any L > 0, N_{2} ≥ 1 and n ≥ 0 we can find a compact set K_{L} ⊂ M_{1}(E) so that

P (η^{N_{1},N_{2}}(ζ_{n}) ∈ K_{L}^{c}) ≤ 4 e^{−N_{1} L}.  (39)

We state now the main result of this section

Theorem 3.7 Assume that (H0) and (H1) hold. Then, for any n ≥ 0 and N_{2} ≥ 1, the family {P_{n}^{N_{1},N_{2}} : N_{1} ≥ 1} obeys a LDP with rate function H_{n}^{N_{2}} given by

H_{n}^{N_{2}}(μ) = sup_{V ∈C_{b}(E)} (μ(V) + inf_{η∈M_{1}(E)} (H_{n−1}^{N_{2}}(η) − log ψ_{n−1}(y_{n−1}, η)((K_{n}e^{\frac{V}{N_{2}}} )^{N_{2}})))

H_{0}^{N_{2}}(μ) = N_{2}I(μ|ν).

Moreover, H_{n} ≤ H_{n}^{N_{2}} ≤ N_{2} H_{n} for any n ≥ 0, where H_{n} is the rate function introduced in proposition 3.2.

Proof: By definition of ζ_{0}, for any N_{2} ≥ 1 {P_{0}^{N_{1},N_{2}} : N_{1} ≥ 1} obeys a LDP with rate function

H_{1}^{N_{2}}(μ) = sup_{V ∈C_{b}(E)} (μ(V) − N_{2} log ν (e^{\frac{V}{N_{2}}} )) = N_{2}I(μ|ν)

Let us examine how to obtain a LDP at time n from a LDP at time (n − 1). Assume that {P_{n−1}^{N_{1},N_{2}} : N_{1} ≥ 1} obeys a LDP with rate function H_{n−1}^{N_{2}}(μ) for some n ≥ 1. By definition of the particle system ζ_{n}, one gets for every V ∈ C_{b}(E)

\frac{1}{N_{1}} log E_{y} (exp (N_{1}η^{N_{1},N_{2}}(ζ_{n})(V))) ≤ \frac{1}{N_{1}} log E_{y} (exp (N_{1}F_{n}^{N_{2}}(η^{N_{1},N_{2}}(ζ_{n−1}))))

with

F_{n}^{N_{2}}(η) = log ∫ (∫ e^{\frac{V (z)}{N_{2}}} K_{n}(x, dz))^{N_{2}} ψ_{n−1}(y_{n−1}, η)(dx)

Under our assumptions we have F_{n}^{N_{2}} ∈ C_{b}(M_{1}(E)). Thus, Varadhan’s lemma and the induction hypothesis at rank (n − 1) imply that

lim_{N_{1}→∞} \frac{1}{N_{1}} log E_{y} (exp (N_{1}η^{N_{1},N_{2}}(ζ_{n})(V))) ≤ Λ_{n}^{N_{2}}(V)

with

Λ_{n}^{N_{2}}(V) =^{def} − inf_{η∈M_{1}(E)} (H_{n−1}^{N_{2}}(η) − F_{n}^{N_{2}}(η))

Thus, according to Dembo-Zeitouni [18], for any N_{2} ≥ 1 the family of probability measures {P_{n}^{N_{1},N_{2}} : N_{1} ≥ 1} obeys a LDP with rate function H_{n}^{N_{2}} with value at μ

inf_{η∈M_{1}(E)} (H_{n−1}^{N_{2}}(η) + sup_{V ∈C_{b}(E)} (μ(V) − log ∫ (∫ e^{\frac{V (z)}{N_{2}}} K_{n}(x, dz))^{N_{2}} ψ_{n−1}(y_{n−1}, η)(dx)))

A clear induction gives the last assertion. This completes the proof of the theorem.

Acknowledgments :

We gratefully acknowledge the European Community for the research fellowships CEC Contract No ERB-FMRX-CT96-0075 and INTAS-RFBR 95-0091. This work was also supported by EPSRC grant GR/ L354661. We heartly thank T. Lyons, D. Crisan and B. Zegarlinskii for their warm hospitality during our stay in the Imperial College of London where we started this work. We also wish to thank G. Ben Arous for encouraging and fruitful discussions.

References

[1] AZENCOTT R. (1980) Grandres déviations et applications, in “Ecoles d’Eté de Probabilités de Saint Flour VIII-1978”, Edited by P.L. Hennequin. Lecture Notes in Mathematics 774, Springer, Berlin, pp. 1-176.

[2] BEN AROUS, G., BRUNAUD, M. (1990). Methode de Laplace : Etude variationnelle des fluctuations de diffusions de type “champ moyen”. Stochastics 31-32, 79-144

[3] BENES B.E. (1981). Exact Finite-Dimensional Filters for Certain Diffusions with Nonlinear Drift. Stochastics, Vol.5, pp 65-92.

[4] BILLINGSLEY P. (1968). Convergence of probability measures. Wiley, New York

[5] CARVALHO H. (1995), Filtrage optimal non linéaire du signal GPS NAVSTAR en racalage de centrales de navigation, Thèse de L’Ecole Nationale Supérieure de l’Aéronautique et de l’Espace, Sept..

[6] CARVALHO H., DEL MORAL P., MONIN A., SALUT G. (1995). Optimal nonlinear filtering in GPS/INS Integration. IEEE Trans. on Aerospace and Electronic Systems.

[7] CHALEYAT-MAUREL M., MICHEL D. (1983), Des résultats de non existence de filtres de dimension finie. C.R.Acad.Sci. Paris, Serie I, t. 296.

[8] CRISAN D., LYONS T.J. (1997). Nonlinear Filtering And Measure Valued Processes. Proba. Theory and Related Fields, 109, 217-244.

[9] CRISAN D., LYONS T.J. (1996). Convergence of a Branching Particle Method to the Solution of the Zakai Equation. Imperial College London, preprint.

[10] CRISAN D., J. GAINES, LYONS T.J. (1998). A Particle Approximation of the Solution of the Kushner-Stratonovitch Equation. To appear in SIAM Journal of Applied Math. 1998.

[11] DAWSON D.A. .Stochastic Evolution Equation and Related Measure Processes. Journal of Multivariate Analysis, 5, 1-52.

[12] DAWSON, D.A., GARTNER, J. (1987) Large déviations from the Mc Kean-Vlasov limit for weakly interacting diffusions. Stochastics, 20, 247-308

[13] DEL MORAL P., RIGAL G., NOYER J.C., SALUT G. (1993), Traitement nonlinéaire du signal par reseau particulaire : Application Radar. quatorzième colloque GRETSI, Juan les Pins, 13-16 Septembre.

[14] DEL MORAL P., NOYER J.C., SALUT G. (1995). Résolution particulaire et traitement non-linéaire du signal : Application Radar/Sonar. Traitement du signal, Septembre.

[15] DEL MORAL P. (1996). Non linear filtering using random particles. Theor. Prob. Appl., Vol. 40, (4).

[16] DEL MORAL P. (1996). Non-linear Filtering: Interacting particle resolution. Markov Processes and Related Fields, Vol.2, 555-580.

[17] DEL MORAL P. (1996). Measure Valued Processes and Interacting Particle Systems. Application to Non Linear Filtering Problems.Publications du Laboratoire de Statistiques et Probabilités, Université Paul Sabatier, No 15-96.. To appear in Annals of Applied Proba. (1998).

[18] DEMBO, A., ZEITOUNI, O (1993) Large deviations techniques and Applications. Jones and Bartlett.

[19] DEUSCHEL, J-D., STROOCK, D.W.(1989) Larges deviations. Academic Press.

[20] GORDON N.J., SALMON D.J., SMITH A.F.M. (1993). Novel Approach to nonlinear/non-Gaussian Bayesian state estimation.,IEE

[21] HITSUDA, M., TANAKA, H.(1981) Central limit theorem for a simple diffusion model for interacting particles. Hiroshima Mathematical Journal,11, 415-423

[22] HOLLAND J.H. (1975) Adaptation in Natural and Artificial Systems.University of Michigan Press, Ann Arbor

[23] JAZWINSKI A.H. (1970). Stochastic Processes and Filtering Theory. Academic Press.

[24] KALLIANPUR G., STRIEBEL C. (1967). Stochastic differential equations occuring in the estimation of continuous parameter stochastic processes. Tech. Rep. No 103, Department of statistics, Univ. of Minnesota.

[25] KUNITA H. (1971). Asymptotic Behavior of Nonlinear Filtering Errors of Markov Processes. Journal of Multivariate Analysis, Vol. 1, No 4, p. 365-393

[26] LIANG D., McMILLAN J. (1989). Development of a marine integrated navigation system. In Kalman Filter Integration of Modern Guidance and Navigation Systems, AGARD-LS-166, OTAN.

[27] OCONE D.L. (1980). Topics in Nonlinear Filtering Theory. Ph.D. Thesis, MIT, Cambridge.

[28] PARDOUX E. (1991). Filtrage Non Linéaire et Equations aux Dérivés Partielles Stochastiques Associées. Ecole d’été de Probabilités de Saint-Flour XIX-1989, Lecture Notes in Mathematics, 1464, Springer-Verlag

[29] PARTHASARATHY K.R. (1968).

Probability measures on Metric Spaces.Academic Press Inc., New York.

[30] PINSKER M.S. (1964). Information and Information Stability of Random Variables and Processes. Holden Day, San Francisco.

[31] STETTNER L. (1988). On Invariant Measures of Filtering Processes, in K. Helmes, N. Kohlman (Eds.), Stochastic Differential Systems, Proc. 4th Bad Honnef Conf. 1988, Lecture Notes in Control and Information Sciences, 279-292.

[32] SHIRYAEV A.N. (1966). On stochastic equations in the theory of conditional Markov processes. Theor. Prob. Appl. (11) (179-184)

[33] STRATONOVICH R.L. (1960). Conditional Markov processes. Theor. Prob. Appl. (5), (156-178).

[34] STROOCK D.W. (1984). An Introduction to the Theory of Large Deviations. Universitext, Springer-Verlag New-York Inc.

[35] SZNITMAN A.S. (1984). Non linear reflecting diffusion process and the propagation of chaos and fluctuations associated. J. Functional Anal. 56 (3) 311-336.

[36] SZNITMAN A.S. (1989). Topics in Propagation of Chaos. Ecole d’été de Probabilités de Saint-Flour XIX-1989, Lecture Notes in Mathematics, No 1464.

[37] TANAKA, H. (1984) Limit theorems for certain diffusion processes. Proceedings of the Taniguchi Symp, Katata 1982, 469-488, Tokyo, Kinokuniya.

[38] VARADHAN S.R.S. (1966), Asymptotic probabilities and differential equations, Comm. Pure Applied Mathematics, 19, 261-286.