Qiming Du
email: qiming.du@upmc.fr

Arnaud Guyader
email: arnaud.guyader@upmc.fr

Variance Estimation in Adaptive Sequential Monte Carlo

Keywords: Sequential Monte Carlo, CLT, Variance estimation, Interacting particle systems, Feynman-Kac semigroups. 2010 Mathematics Subject Classi cation: 47D08, 65C35, 60J80, 65C05

. We prove that, under natural assumptions, the estimator introduced by Lee and Whiteley [LW18] in the nonadaptive case (i.e., SMC) is also a consistent estimator of the asymptotic variance for ASMC methods. To do this, we introduce a new estimator that is expressed in terms of coalescent tree-based measures, and explain its connection with the previous one. Our estimator is constructed by tracing the genealogy of the associated Interacting Particle System. The tools we use connect the study of Particle Markov Chain Monte Carlo methods and the variance estimation problem in SMC methods. As such, they may give some new insights when dealing with complex genealogy-involved problems of Interacting Particle Systems in more general scenarios.

A natural way to achieve this aim is by resimulating the IPS independently many times and by estimating σ n (f ) 2 with the crude variance estimator. However, since a single run of the algorithm may take a lot of time, this is usually intractable. In addition, as the estimator η N n (f ) of η n (f ) provided by SMC is typically biased, it is also nontrivial to implement parallel computing for a large number of IPS with N relatively small. As a consequence, a variance estimator available with a single run of the simulation is of crucial interest for applications.

The rst consistent estimator of this type was proposed by Chan and Lai [START_REF] Chan | A general theory of particle lters in hidden Markov models and some applications[END_REF], by using the ancestral information encoded in the genealogy of the associated IPS. Then, Lee and Whiteley [START_REF] Lee | Variance estimation in the particle lter[END_REF] proposed an unbiased variance estimator for the unnormalized measures γ N n and a term by term estimator, with insights on the genealogy of the IPS. Both estimators are studied in the classical SMC framework, meaning in a nonadaptive setting where the weight functions and the Markov proposal kernels are xed a priori.

In this article, we deal with adaptive SMC methods. At each resampling step, the weight functions and/or Markov proposal kernels depend upon the history of the simulated process. The idea is to approximate an ideal "limiting" SMC algorithm, which is usually out of reach, by exploiting the induced information tracked by some summary statistics. Such approaches are expected to be more e cient and more automated than the nonadaptive ones since they require less user-speci ed tuning parameters.

Speci cally, we are interested in the case where the adaptive SMC algorithm is asymptotically identical to a "limiting" SMC algorithm. More precisely, we expect the asymptotic variance of the adaptive SMC algorithm to be identical to the "ideal" nonadaptive one. This kind of stability property is at the core of the pair of articles [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF] and [START_REF] Cérou | Fluctuation analysis of adaptive multilevel splitting[END_REF]. The framework discussed in the present paper is just a slightly generalized version of the one presented in Section 2 in [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF] but still ensures the stability property of their Theorem 2.3.

Another remark is about Adaptive Multilevel Splitting (AMS), also known as Subset Simulation, see for example [AB01, AB03, CG07, CDMFG12, CG16]. This is a class of ASMC algorithms dedicated to rare event estimation and simulation. Despite the fact that our assumptions are not veri ed in the AMS framework, we expect that the variance estimator would also work in this context. Nonetheless, we believe that this case requires a speci c analysis as well as di erent assumptions. To account for this, one can notice that the proofs in [START_REF] Cérou | Fluctuation analysis of adaptive multilevel splitting[END_REF] and [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF] di er in many points, although the take-home message is the same. In a nutshell, the main di culty in the AMS framework comes from the indicator functions in the potential functions as well as in the transitions kernels, leading to severe regularity issues when dealing with CLT type results and asymptotic variances.

From a theoretical viewpoint, to prove the consistency of the variance estimator proposed in [START_REF] Lee | Variance estimation in the particle lter[END_REF], we were not able to adapt their technical tools. This is due to the additional randomness brought by the weight functions and Markov kernels in the adaptive case. As a consequence, we propose to develop new techniques in order to estimate the terms Γ b n that appear in the expansion of the variance given in [START_REF] Cérou | A nonasymptotic theorem for unnormalized Feynman-Kac particle models[END_REF]. The mains ideas are: rst, our term by term estimator is consistent and, second, the di erence between our estimator and the one of Lee and Whiteley goes to 0 in probability when the sample size N goes to in nity. However, in practice, one uses the estimator proposed by Lee and Whiteley, which is computationally very simple, while the one we introduce here may be seen as a handy tool to prove the consistency of the former.

The construction of our estimators Γ b n,N uses the idea of many-body Feynman-Kac models, which were designed in [START_REF] Del Moral | On particle Gibbs samplers[END_REF] to study propagation of chaos properties of Conditional Particle Markov Chain Monte Carlo methods [START_REF] Andrieu | Particle Markov chain Monte Carlo methods[END_REF]. Above the speci c context of the present article, these connections may give some insights on how to deal with complex genealogyinvolved problems in more general settings.

Notation

Before proceeding, let us provide some notation that will be of constant use in the following.

• For any Polish space E, we denote respectively by M(E), M + (E) and P(E) the sets of signed nite measures, nonnegative nite measures, and probability measures on E endowed with Borel σ -algebra B(E), while B b (E) denotes the collection of the bounded measurable functions from (E, B(E)) to (R, B(R)) equipped with uniform norm • ∞ .

• For any µ ∈ M(E) and any test function f ∈ B b (E), we write

µ(f ) := ∫ E f (x)µ(dx).
A nite nonnegative kernel Q from (E, B(E)) to (F, B(F )) is a function

Q : E × B(F ) → R +
such that, for all x ∈ E, Q(x, •) ∈ M + (F ) and, for all A ∈ B(F ), Q(x, A) is a B(E)measurable function. We say that Q is a Markov transition kernel if, moreover, for all

x ∈ E, Q(x, •) is a probability measure in P(F ). For a signed measure µ ∈ M(E) and a test function f ∈ B b (F ), we denote respectively by µQ ∈ M(E) and Q(f ) ∈ B b (E) the measure and function respectively de ned by

µQ(A) := ∫ E µ(dx)Q(x, A) ∀A ∈ B(F ), and
Q(f )(x) := ∫ F Q(x, d )f ( ) ∀x ∈ E.
Given two nite nonnegative kernels Q 1 and Q 2 respectively from E 0 to E 1 and E 1 to E 2 , Q 1 Q 2 is the nonnegative kernel from E 0 to E 2 de ned by

Q 1 Q 2 (x, A) := ∫ E 1 Q 1 (x, d )Q 2 ( , A) ∀(x, A) ∈ E 0 × B(E 2 ).
• For two functions f , ∈ B(E), their tensor product is the function

f ⊗ : E 2 (x, ) → f (x) ( ) ∈ R,
and, in particular, we denote f ⊗2 := f ⊗ f . For two nite nonnegative kernels Q and H from (E, B(E)) to (F, B(F )), we denote

(Q ⊗ H ) ((x, ), (A, B)) := Q(x, A) × H ( , B)
for all (x, ) ∈ E × E and all (A, B) ∈ B(F ) ⊗ B(F ). Accordingly, we write Q ⊗2 := Q ⊗ Q.

• In order to de ne the coalescent tree-based measures of size 2, we introduce the transition operators C 0 and C 1 as

C 0 ((x, ), d(x , )) := δ (x , ) d(x , ),
and

C 1 ((x, ), d(x , )) := δ (x ,x ) d(x , ).
In other words, for any measurable function

H : E × E → R, we have C 0 (H )(x, ) = H (x, ) and C 1 (H )(x, ) = H (x, x).
• For all x = (x 1 , . . . , x N ) ∈ E N , we de ne the empirical measure associated to x by

m(x) := 1 N N i=1 δ x i ∈ P(E).
We also denote

m ⊗2 (x) := 1 N 2 i,j δ (x i ,x j ) ∈ P(E 2 ), and
m 2 (x) := 1 N (N -1) i j δ (x i ,x j ) ∈ P(E 2 ).
A straightforward computation shows that

m ⊗2 (x) = N -1 N m 2 (x)C 0 + 1 N m 2 (x)C 1 . (1)
With a slight abuse of notation, considering [N ] := {1, 2, . . . , N }, we write

m([N ]) := 1 N N i=1 δ i and m ⊗2 ([N ]) := m([N ]) ⊗ m([N ]).

Adaptive Sequential Monte Carlo

This section presents the formal de nition and the regularity assumptions of the ASMC framework studied in this article. The motivation is mainly from ASMC via summary statistics introduced in Section 2 of [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF]. We refer the reader to the latter for details on motivating examples such as ltering or sequential Bayesian parameter inference.

Framework

The notations that are adopted are essentially those in the pair of books [START_REF] Moral | Feynman-Kac formulae: Genealogical and interacting particle systems with applications[END_REF][START_REF] Moral | Mean eld simulation for Monte Carlo integration[END_REF]. Let (E n , B(E n )) n ≥0 be a sequence of Polish spaces. For each level n ≥ 1, we consider a family of potential functions G n-1,z : E n-1 → R + and Markov kernels M n,z :

(E n-1 , B(E n )) → [0, 1] parametrized by z ∈ R d .
Accordingly, we de ne the family of nonnegative Feynman-Kac kernels

Q n,z by Q n,z (x, A) := G n-1,z (x)M n,z (x, A).
We suppose that there exists a sequence of reference parameters (z * n ) n ≥0 and, for each n ≥ 1, we denote

G n-1 := G n-1,z * n-1 , M n := M n,z * n-1 and Q n := Q n,z * n-1 .
Starting with a known probability measure γ 0 := η 0 ∈ P(E 0 ), we de ne the unnormalized Feynman-Kac measures γ n by

γ n := γ 0 Q 1 • • • Q n ,
along with the normalized measures

η n := 1 γ n (1) γ n .
Assumption 1 below ensures that, for all n ≥ 0, G n is strictly positive so that

γ n (1) = n-1 p=0 η p (G p ) > 0.
Another formulation of the connection between normalized and unnormalized measures is thus given by

γ n (f n ) = η n (f n ) n-1 p=0 η p (G p ). (2)
For p < n, we de ne the Feynman-Kac semigroup

Q p,n := Q p+1 • • • Q n ,
and Q n,n (x, A) := δ x (A). In this context, ASMC algorithms aim at approximating the sequences of measures (γ n ) n ≥0 and (η n ) n ≥0 by exploiting some summary statistics

ζ n : E n → R d
such that, for all n ≥ 0, we have

η n (ζ n ) = z * n .

ASMC algorithm

In practice, ASMC and SMC algorithms share the same selection/mutation mechanisms. However, since in most situations of interest the parameters (z * n ) n ≥0 are not analytically tractable, the potential functions (G n ) n ≥0 and transition kernels (M n ) n ≥1 are estimated on the y through the design of an adaptive algorithm.

Let N ∈ N * be the number of particles (or samples). The Interacting Particle System (IPS) associated to the ASMC algorithm is a Markov chain (X n ) n ≥0 taking values in (E N n , B(E n ) ⊗N ) n ≥0 with genealogy (A n ) n ≥0 tracking the indice of the parent of each particle at each level. Specifically, A i p-1 = j means that the parent of the particle X i p at layer p is X j p-1 at layer p -1. The estimation of the normalized measure η n is given by the empirical measure

η N n := 1 N N i=1 δ X i n .
At each level n ≥ 0, the estimated parameters are de ned by

Z N n := η N n (ζ n ).
In order to lighten the notation, we denote

G n-1,N := G n-1,Z N n-1 , M n,N := M n,Z N n-1 , and Q n,N := Q n,Z N n-1 .
Then, considering (2), the unnormalized Feynman-Kac measures are estimated by

γ N n (f n ) := η N n (f n ) n-1 p=0 η N p (G p,N ).
In the following sections, we use the convention

η N -1 = γ N -1 := η 0 .
Let us give the formal de nition of the IPS associated with the ASMC algorithm:

(i) Initial distribution: At step 0, let X 0 ∼ η ⊗N 0 . (ii) Transition kernels:

For all p ≥ 0, set Z N p = η N p (ζ p ). The transition X i p X i p+1 is decomposed into two steps: • Selection: given X p = x p , we make an independent multinomial selection of the parent of each particle by

S p,N (x p , da i p ) = N k=1 G p,N (x k p ) N j=1 G p,N (x j p ) δ k (da i p ). (3)
Thus, the genealogy of level p to level p + 1 is tracked by

A p ∼ N i=1 S p,N (X p , •)
• Mutation: given the parent indices A p = a p , each particle at level p evolves independently according to the transition kernel M p+1,N , meaning that for i ∈ [N ],

X i p+1 ∼ M p+1,N (X a i p p , •).
Said di erently, given X p and A p , we have

X p+1 ∼ N i=1 M p+1,N (X A i p p , •).

Assumptions

Our assumptions are introduced in a similar way as in [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF], but just slightly weaker. The reason why we can relax their assumptions is because we are only interested in the speci c situation where the asymptotic variance of the ASMC estimator is identical to the "limiting" SMC algorithm which uses ideal potential functions and proposal kernels, namely

G p = G p,z * p-1
and M p = M p,z * p-1 . Considering stability properties, Section 2.7 in [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF] explains why this case is particularly interesting in practice. In the following sections, we use A as a short-hand for Assumption.

Assumption 1. For each n ≥ 0, we assume that G n,z is strictly positive and bounded uniformly over

z ∈ R d , i.e., G n, • ∞ := sup (x ,z)∈E n ×R d G n,z (x) < +∞.
Notice that, under A1, Equation (3) above is always well-de ned for the denominator is always strictly positive. In the case where G p,z is only assumed to be nonnegative, as in the AMS framework, one may consider the stopping time τ N de ned by

τ N := inf p ∈ N : η N p (G p,N ) = 0 .
We believe that similar techniques can be applied to obtain results of the same taste as in the present paper, but at the cost of considerable technical complications which are out of the scope of this article. Let us mention that the strict positivity and boundedness of the potential functions is also required in [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF] (see page 1116 and Assumption 1 page 1118). In our second assumption, "

(E n × R d , B(E n ) ⊗ B(R d )) → (R d , B(R d )) such that, for all (x, z n ) ∈ E n × R d , Q n+1,z n (f n+1 )(x) -Q n+1 (f n+1 )(x) = h n (x, z n ), z n -z * n .
The function h n is assumed to satisfy the following properties:

• The Euclidean norm |h n | is bounded over E n × R d by h n ∞ .
• The application z → h n (x, z) is continuous at z * n uniformly over x ∈ E n . More precisely, for any ϵ > 0, there exists δ > 0, such that z nz * n < δ implies

sup x ∈E n h n (x, z n ) -h n (x, z * n ) < ϵ.
• h n satis es the equality

η n h n (•, z * n ) = 0. Moreover, the summary statistics ζ n = (ζ 1 n , . . . , ζ d n ) satis es z * n = η n (ζ n ) and is such that, for all k ∈ [d], ζ k n belongs to B b (E n ).
A2 guarantees some regularity properties of the transition kernels Q n,z with respect to the parameter z and is just a slight generalization of the framework studied in Section 2 of [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF]. Indeed, our function h n coincides with the function ω de ned in (2.17) of [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF], that is

h n (x, z n ) = ∫ 1 0 ∂ z Q n+1,z (f n+1 )(x) z=z * n +λ(z n -z * n ) dλ.
As such, the rst two conditions on h n are satis ed as soon as Assumption 2 in [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF] is veri ed. In this respect, our third condition on h n corresponds to their condition (2.19) in Theorem 2.3, which is precisely the "limiting" case mentioned above. Finally, the hypothesis that the summary statistics are bounded is also required in their Assumption 1, while the relation

z * n = η n (ζ n ) corresponds in their notation to ξn = η n-1 (ξ n ).
We also want to mention that the second point is equivalent to

∀ϵ > 0, ∃ n ∈ B b (E n ), ∃δ > 0, s.t . z n -z * n < δ =⇒ ∀x ∈ E n , h n (x, z n ) -h n (x, z * n ) < n (x)ϵ ≤ n ∞ ϵ.
We expect that, in this alternative formulation, the functions n and h n can be relaxed to some unbounded functions, belonging for example to L 2 (η n ), along with stronger conditions on the test function f n+1 . We believe that this is one of the main di erences between the ASMC framework studied in [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF] and the AMS framework studied in [START_REF] Cérou | Fluctuation analysis of adaptive multilevel splitting[END_REF].

In general, it is not easy to verify the existence of such h n . However, we have, at least, a direction to explore in the case where Q n,z (f ) is not globally di erentiable with respect to z. We also remark that we do not study the consistency of γ N n (f ) and η N n (f ) with weaker assumptions, as we are only interested in the CLT type result of Theorem 2.1 below and, more speci cally, in the estimation of the asymptotic variance. Nevertheless, let us brie y mention that to establish the consistency of γ N n and η N n , one just needs

γ N n-1 Q n,N (f n ) -γ N n-1 Q n (f n ) = o p (1)
for any test function f n ∈ B b (E n ). This does not require such a strong assumption as A2.

However, for CLT type results with the "stable" asymptotic variance, it is necessary that

γ N n-1 Q n,N (f n ) -γ N n-1 Q n (f n ) = o p 1 √ N .
A stronger regularity assumption like A2 over the parametrization is therefore required.

Central limit theorems

As explained before, the present article only deals with the case where the asymptotic variance is identical to the "limiting" one, which is only a special case of the Central Limit Theorem 2.2 given in [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF] under slightly weaker assumptions. This is why, in Section 4.2, we propose a di erent strategy for the proof.

Theorem 2.1. Assume A1-A2. For any test function f ∈ B n (E n ), we have

√ N γ N n (f ) -γ n (f ) d -----→ N →∞ N 0, σ 2 γ n (f ) , and √ N η N n (f ) -η n (f ) d -----→ N →∞ N 0, σ 2 η n (f -η n (f )) ,
where

σ 2 γ n (f ) := n p=0 γ p (1)γ p (Q p,n (f ) 2 ) -γ n (f ) 2 and σ 2 η n (f ) := σ 2 γ n (f )/γ n (1) 2 .
One can notice that the CLT for η N n is just a consequence of the CLT for γ N n , Slutsky's Lemma, and the decomposition

√ N η N n (f ) -η n (f ) = 1 γ N n (1) √ N γ N n (f -η n (f )) -γ n (f -η n (f )) .
The main goal of this paper is to estimate the asymptotic variances σ 2 γ n (f ) and σ 2 η n (f -η n (f )) by a single simulation of the particle system, exactly as is done by Lee and Whiteley in [START_REF] Lee | Variance estimation in the particle lter[END_REF] in a nonadaptive context.

Variance estimations

In this section, we recall the coalescent tree-based expansion of the variance rstly introduced in [START_REF] Cérou | A nonasymptotic theorem for unnormalized Feynman-Kac particle models[END_REF] from which we deduce a new variance estimator. We also recall the variance estimator proposed by Lee and Whiteley in [START_REF] Lee | Variance estimation in the particle lter[END_REF] and explain the connection between both estimators.

Coalescent tree-based variance expansion

n ∈ M + (E 2 n ) de ned for any F ∈ B b (E 2 n ) by Γ b n (F ) := η ⊗2 0 C b 0 Q ⊗2 1 C b 1 • • • Q ⊗2 n C b n (F ), and
Γb n (F ) := 1 γ n (1) 2 Γ b n (F ).
When there is only one coalescence at, say, level p, we write Γ (p) n (F ) and Γ(p) n (F ) instead of Γ b n (F ) and Γb n (F ) (see Figure 1). When there is no coalescence at all, that is b = (0, . . . , 0), we have It is easy to verify from the de nition that

Γ ( ) n (F ) = γ ⊗2 n (F ) and Γ( ) n (F ) = η ⊗2 n (F ).
Γ (p) n (f ⊗2 ) = γ p (1) γ p Q p,n (f ) 2 .
As noticed in [START_REF] Cérou | A nonasymptotic theorem for unnormalized Feynman-Kac particle models[END_REF], the latter yields alternative representations for the asymptotic variances of Theorem 2.1, namely

σ 2 γ n (f ) = n p=0 Γ (p) n (f ⊗2 ) -Γ ( ) n (f ⊗2 ) , (4)
and

σ 2 η n (f ) = n p=0 Γ(p) n (f ⊗2 ) -Γ( ) n (f ⊗2 ) . (5)
As a consequence, if for any coalescence indicator b := (b 0 , . . . , b n ) ∈ {0, 1} n+1 , we can construct a consistent estimator Γb n,N of Γb n , then we automatically deduce consistent estimators for the asymptotic variances of Theorem 2.1. This is the idea behind our next de nition.

In this de nition, ã[2] p = ( ã1 p , ã2 p ) and [2] p = ( 1 p , 2 p ) denote two couples of indices between 1 and N , while an (n + 1)-sequence of couples of indices such that 1

p 2 p for all 0 ≤ p ≤ n is written [2] 0:n = ( [2] 0 , • • • , [2] n ) ∈ (N ) 2 ×(n+1) .
Additionally, we use the notation X

[2] n n as a short-hand for (X

1 n n , X 2 n n ). De nition 3.2. For any test function F ∈ B b (E 2
n ) and any coalescence indicator b, we de ne the estimator Γb n,N of the measure Γb n by

Γb n,N (F ) := N n-1 (N -1) n+1 [2] 0:n ∈((N ) 2 ) ×(n+1) n-1 p=0 λ b p (A [2] p+1 p , [2] p ) C b n (F )(X [2] n n ),
where

λ b p ( ã[2] p , [2] p ) ∈ {0, 1} is an indicator function de ned by λ b p ( ã[2] p , [2] p ) := 1 {b p =0} 1 { ã1 p = 1 p ã2 p = 2 p } + 1 {b p =1} 1 { ã1 p = 1 p = ã2 p 2 p } . The estimator of Γ b n is de ned by Γ b n,N (F ) = γ N n (1) 2 Γb n,N (F ). Since 1 p 2
p , we also have

λ b p ( ã[2] p , [2] p ) = 1 {b p =0} 1 { ã1 p = 1 p , ã2 p = 2 p } + 1 {b p =1} 1 { ã1 p = 1 p = ã2 p } . Notice that, for n = 0, we get Γb 0,N (F ) := 1 N (N -1) [2] 0 ∈(N ) 2 C b 0 (F )(X [2] 0 0 ) = 1 N (N -1) i j C b 0 (F )(X i 0 , X j 0 ). (6)
We also adopt the convention

Γb -1,N (F ) = Γ b -1,N (F ) := η ⊗2 0 C b 0 (F ).
A toy example As the de nition of the estimator Γ b n,N is not completely straightforward, we illustrate the idea on a simple example. For this, we consider the IPS of Figure 2. Suppose we want to estimate Γ(3) 6 (F ) by Γ(3) 6,5 (F ). We denote b * = (0, 0, 0, 1, 0, 0, 0) the corresponding coalescence indicator. In the associated IPS, we have to nd the choices of [2] 0:6 such that

X 1 0 X 2 0 X 3 0 X 4 0 X 5 0 step 0 X 1 1 X 2 1 X 3 1 X 4 1 X 5 1 step 1 X 1 2 X 2 2 X 3 2 X 4 2 X 5 2 step 2 X 1 3 X 2 3 X 3 3 X 4 3 X 5 3 step 3 X 1 4 X 2 4 X 3 4 X 4 4 X 5 4 step 4 X 1 5 X 2 5 X 3 5 X 4 5 X 5 5 step 5 X 1 6 X 2 6 X 3 6 X 4 6 X 5 6 step 6
5 p=0 λ b * p (A [2] p+1 p , [2] p ) = 1. ( 7
)
step 0 step 1 step 2 step 3 step 4 step 5 step 6

Figure 3: The rst family of [2] 0:6 such that (7) is veri ed.

It turns out that there are 4 possible choices, taking into account that F (x, x ) is not necessarily symmetric in its variables. Namely, the rst couple of ancestral lines is (see Figure 3):

• [2] 0:6 = ((5, 3), (4, 3), (2, 5), (2, 4), (2, 5), (1, 3), (2, 4)) ; • [2] 0:6 = ((5, 3), (4, 3), (2, 5), (2, 4), (5, 2), (3, 1), (4, 2)) . The second couple of ancestral lines is (see Figure 4):

• [2] 0:6 = ((5, 3), (4, 3), (2, 5), (2, 1), (2, 5), (1, 3), (2, 4)) ; • [2] 0:6 = ((5, 3), (4, 3), (2, 5), (2, 1), (5, 2), (3, 1), (4, 2)) . Hence, the number of choices of [2] 0:6 where [2] 6 = (2, 4) is 2, and the number of choices of [2] 0:6

where [2] 6 = (4, 2) is also 2. As a consequence, we have

Γ(3) 6,5 (F ) = 2 × step 0 step 1 step 2 step 3 step 4 step 5 step 6
Figure 4: The second family of [2] 0:6 such that (7) is veri ed.

Theorem 3.1 (Convergence of Γ b n,N ). Assume A1-A2. For any test functions ϕ,ψ ∈ B b (E n ) and for any coalescence indicator b ∈ {0, 1} n+1 , we have

Γ b n,N (ϕ ⊗ ψ ) -Γ b n (ϕ ⊗ ψ ) = O p 1 √ N .
The proof is given in Section 4.3.

Term by term estimator

Considering (4), (5), and Theorem 3.1, we are now in a position to provide term by term variance estimators for σ 2 γ n (f ) and σ 2 η n (f ).

De nition 3.3 (Estimators of the asymptotic variances). Given a test function

f ∈ B b (E n ), we let σ 2 γ n,N (f ) := n p=0 Γ (p) n,N (f ⊗2 ) -Γ ( ) n,N (f ⊗2 ) , and
σ 2 η n,N (f ) := n p=0 Γ(p) n,N (f ⊗2 ) -Γ( ) n,N (f ⊗2 ) .
Theorem 3.1 ensures the consistency of both Γ (p) n,N (f ⊗2 ) and Γ ( ) n,N (f ⊗2 ). Returning to (4), this amounts to saying that

σ 2 γ n ,N (f ) = n p=0 Γ (p) n,N (f ⊗2 ) -Γ ( ) n,N (f ⊗2 ) P -----→ N →∞ n p=0 Γ (p) n (f ⊗2 ) -Γ ( ) n (f ⊗2 ) = σ 2 γ n (f ).
Similarly, for the consistency of σ 2 η n,N (fη N n (f )), since by (5) we know that

σ 2 η n (f ) = n p=0 Γ(p) n (f ⊗2 ) -Γ( ) n (f ⊗2 ) ,
it su ces to verify that, for any coalescent indicator b,

Γb n,N f -η N n (f ) ⊗2 P -----→ N →∞ Γb n f -η N n (f ) ⊗2 . (8)
Clearly, the linearity of Γb n,N yields Γb

n,N f -η N n (f ) ⊗2 = Γb n,N (f ⊗2 ) -η N n (f ) Γb n,N (1 ⊗ f ) + Γb n,N (f ⊗ 1) + η N n (f ) 2 Γb n,N 1 ⊗2 .
Mutatis mutandis, the same relation holds for Γb

n f -η N n (f ) ⊗2 . Since a by-product of The- orem 2.1 is that η N n (f ) -η n (f ) = O p 1 √ N
, the veri cation of ( 8) is just a consequence of Theorem 3.1 and Slutsky's Lemma. Hence, we have obtained the following result.

Theorem 3.2 (Consistency of σ 2 γ n,N and σ 2 η n,N ). Assume A1-A2. For f ∈ B b (E n ), we have σ 2 γ n,N (f ) -σ 2 γ n (f ) = O p 1 √ N ,
as well as

σ 2 η n,N (f -η N n (f )) -σ 2 η n (f -η n (f )) = O p 1 √ N .
Even if the term by term estimator is very natural in theory, the computational cost is quite heavy in practice since one has to trace the whole genealogy of a particle system and calculate all the corresponding terms one by one. Therefore, we do not provide an e cient algorithm to calculate this estimator. Instead, we show in the next section that this estimator can be connected to the one given by Lee & Whiteley in a nonadaptive context (SMC), which is very simple and fast to calculate. Let us also mention that our term by term estimator is di erent from the one introduced in Section 4.1 of [START_REF] Lee | Variance estimation in the particle lter[END_REF]. The interested reader can nd more details on this point in Appendix A.3.

Disjoint ancestral lines estimator

Let us now recall the variance estimator proposed in [START_REF] Lee | Variance estimation in the particle lter[END_REF], which can be seen as a disjoint ancestral lines estimator. Namely, given a test function

f ∈ B b (E n ), consider V N n (f ) := η N n (f ) 2 - N n-1 (N -1) n+1 E i n E j n f (X i n )f (X j n ), (9)
where E i n is the ancestor index of X i n at level 0. Returning to the toy example of Section 3.1, the couples (i, j) such that i < j and E i n E j n are: (1, 2), (1, 4), (2, 3), (2, 5), (3, 4), (4, 5). In a nonadaptive context (SMC), this is the variance estimator introduced in [LW18] when the number N of particles is the same at each step. The reader is referred to [START_REF] Lee | Variance estimation in the particle lter[END_REF] for an e cient algorithm to compute this estimator.

According to our notation, since E i n E j n corresponds to the case b = (0, . . . , 0) = ( ) of disjoint ancestral lines, we may also write

V N n (f ) = η N n (f ) 2 -Γ( ) n,N (f ⊗2 ).
The following proposition makes a connection between V N n (f ) and our estimators. Notice that this result does not depend on A2, but is provided by the structure of the IPS and the underlying multinomial selection scheme. The proof is housed in Section 4.5.

Proposition 3.1. Assume A1. For any test function f ∈ B b (E n ), we have

NV N n (f ) -σ 2 η n,N (f ) = O p 1 N ,
and

NV N n (f -η N n (f )) -σ 2 η n,N (f -η N n (f )) = O p 1 N .
By combining Theorem 3.2 and Proposition 3.1, we nally obtain the main result of the present article.

Theorem 3.3. Assume A1-A2. For any test function f ∈ B b (E n ), we have

Nγ N n (1) 2 V N n (f ) -σ 2 γ n (f ) = O p 1 √ N , and
NV N n (f -η N n (f )) -σ 2 η n (f -η n (f )) = O p 1 √ N .
Hence, the main message of the present work is that the computationally very simple estimator proposed by Lee and Whiteley in a nonadaptive framework (SMC) is still consistent in an adaptive one (ASMC). However, since we could not adapt easily their proof to our adaptive context, we propose a new approach to show this consistency result. More details on the connection between both estimators are given in Appendix A.3.

As emphasized before, among other ingredients, the tools we use connect the study of Particle Markov Chain Monte Carlo methods and the variance estimation problem in SMC methods. As such, more generally, they may give some new insights when dealing with complex genealogy-involved problems of Interacting Particle Systems.

Before going into the details of the proofs, let us mention that a numerical experiment on a toy example is proposed in Appendix B to illustrate the consistency of the Lee and Whiteley variance estimators in the adaptive and nonadaptive cases. Finally, Appendix C makes a connection between our term by term estimators and the truncated variance estimators recently proposed by Olsson and Douc in [START_REF] Olsson | Numerically stable online estimation of variance in particle lters[END_REF] to address the issue of degeneracy in the ancestral lines.

Proofs

Almost sure convergence

In this section, we provide classical almost sure convergence results on SMC framework under our speci c parameterization, namely with adaptive potential functions and transition kernels. We focus on the properties that do not use the additional information given by the genealogy of the associated IPS. Therefore, in order to simplify the story, we give a "rougher" de nition of the associated IPS without considering the genealogy.

• X 0 ∼ η ⊗N 0 • For p ≥ 1, we let X p ∼ N i=1 K p,η N p-1 (X i p-1 , •)
where, given

X p-1 , K p,η N p-1
is the Markov kernel de ned by

∀(x, A) ∈ E p-1 × B(E p ), K p,η N p-1 (x, A) := η N p-1 Q p,N (x, A) η N p-1 G p-1,N
.

It is easy to check that the distributions of the particles are identical to the ones de ned in Section 2.2. Let us begin with the consistency of the corresponding adaptive estimators. Recall that, by A2, the summary statistics

ζ n = (ζ 1 n , • • • , ζ d n ) satis es η n (ζ n ) = z * n and, for all k ∈ [d], ζ k n belongs to B b (E n ). Theorem 4.1. Assume A1-A2. For any f ∈ B b (E n ), we have γ N n (f ) a .s . -----→ N →∞ γ n (f ),
and η N n (f ) a .s . -----→ N →∞ η n (f ).
In particular, we also have

Z N n = η N n (ζ n ) a .s . -----→ N →∞ η n (ζ n ) = z * n .
Proof. By de nition, it is clear that the convergence of γ N n implies the convergence of η N n . Therefore, it is su cient to establish the rst one. We prove by induction that

∀f ∈ B b (E n ), γ N n (f ) a .s . -----→ N →∞ γ n (f ).
Step 0:

The almost sure convergence of γ N 0 = η N 0 to γ 0 = η 0 with respect to a test function in B b (E 0 ) is given by the strong law of large numbers.

Step n ≥ 1:

We assume that

Z N n-1 a .s . -----→ N →∞ z * n-1
and, for any ϕ ∈ B b (E n-1 ),

γ N n-1 (ϕ) a .s . -----→ N →∞ γ n-1 (ϕ).
For any f ∈ B b (E n ), the triangular inequality yields

γ N n (f ) -γ n (f ) ≤ γ N n (f ) -γ N n-1 Q n,N (f ) P 1 (N ) + γ N n-1 Q n,N (f ) -γ N n-1 Q n (f ) P 2 (N ) + γ N n-1 Q n (f ) -γ n-1 Q n (f ) P 3 (N )
. (10)

• For P 1 (N ), we denote

U i n,N := η N n-1 (G n-1,N )f (X i n ) -η N n-1 Q n,N (f ).
It is readily seen that

P 1 (N ) = γ N n-1 (1) 1 N N i=1 U i n,N .
Given F N n-1 := σ (X 0 , . . . , X n-1 ), the random variables (U i n,N ) 1≤i ≤N are i.i.d. and such that

E U i n,N F N n-1 = η N n-1 (G n-1,N ) η N n-1 Q n,N (f ) η N n-1 G n-1,N -η N n-1 Q n,N (f ) = 0.
Under A1, we can also see that

U i n,N ≤ C n := 2 G n-1, • ∞ f ∞ .
Therefore, for any ϵ > 0, Hoe ding's inequality gives

P N i=1 U i n,N ≥ N ϵ F N n-1 ≤ 2 exp -ϵ 2 N 2C 2 n .
Since this upper-bound is deterministic, this amounts to saying that

P N i=1 U i n,N ≥ N ϵ ≤ 2 exp -ϵ 2 N 2C 2 n .
Consequently, Borel-Cantelli Lemma ensures that

1 N N i=1 U i n,N a .s . -----→ N →∞ 0.
Combined with the induction hypothesis, we get

P 1 (N ) = γ N n-1 (1) 1 N N i=1 U i n,N a .s .
-----→ N →∞ 0.

• For P 2 (N ), A2 implies that there exists a function h n-1 such that

Q n,N (f )(x) -Q n (f )(x) = h n-1 (x, Z N n-1 ), Z N n-1 -z * n-1 .
Hence, since |h n-1 | and the potential functions G n,z are bounded, Cauchy-Schwarz inequality gives

P 2 (N ) ≤ γ N n-1 (1) h n-1 ∞ Z N n-1 -z * n-1 ≤ n-2 p=0 G p, • ∞ h n-1 ∞ Z N n-1 -z * n-1 .
By induction hypothesis, we conclude that

P 2 (N ) a .s .
-----→ N →∞ 0.

• For P 3 (N ), under A1, we have that

Q n (f ) ∈ B b (E n-1
). Thus, the induction hypothesis gives

P 3 (N )
a .s .

-----→

N →∞ 0.
Considering (10), the veri cation of the convergence

∀f ∈ B b (E n ), γ N n (f ) a .s . -----→ N →∞ γ n (f )
is then complete.

Proof of Theorem 2.1

We prove by induction that

√ N γ N n (f ) -γ n (f ) d -----→ N →∞ N 0, σ 2 γ n (f ) .
The veri cation of step 0 comes from the CLT for i.i.d. random variables. For step n ≥ 1, we suppose that

∀0 ≤ p ≤ n -1, √ N γ N p (f ) -γ p (f ) d -----→ N →∞ N 0, σ 2 γ p (f ) .
Notice that, by A2, this implies that

∀0 ≤ p ≤ n -1, √ N Z N p-1 -z * p-1 = O p (1) . ( 11
)
For any test function

f ∈ B b (E n ), we denote f p := Q p,n (f ) ∈ B b (E p ). For any (x, A) ∈ E 0 ×B(E 0 ) we set Q 0 (x, A) = Q 0,N (x, A) = δ x (A).
Taking into account the convention γ N -1 = γ 0 = η 0 and the fact that γ n = γ 0 Q 0,n , we have the telescoping decomposition

γ N n (f ) -γ n (f ) = n p=0 γ N p (f p ) -γ N p-1 Q p (f p ) = 1 N n p=0 N i=1 γ N p (1)f p (X i p ) -γ N p-1 Q p,N (f p ) + γ N p-1 Q p,N (f p ) -γ N p-1 Q p (f p ) .
For k ∈ [(n + 1)N ], we denote

p k := k N and i k := k -p k × N .
We de ne the ltration

∀k ∈ [(n + 1)N ], E N k = F N p k -1 ∨ σ (X 1 p k , • • • , X i k p k ).
Then, we set

U N k := 1 √ N γ N p k (1)f p k (X i k p k ) -γ N p k -1 Q p k ,N (f p k ) , and
D N p := √ N γ N p-1 Q p,N (f p ) -γ N p-1 Q p (f p ) , so that √ N γ N n (f ) -γ n (f ) = (n+1)N k =1 U N k + 1 N D N p k = (n+1)N k=1 U N k + n p=0 D N p . (12)
From A2, we know that there exists a function h p-1 such that

D N p = √ N γ N p-1 h p-1 (•, Z N p-1 ) , Z N p-1 -z * p-1 = √ N γ N p-1 h p-1 (•, Z N p-1 ) -h p-1 (•, z * p-1 ) , Z N p-1 -z * p-1 + √ N γ N p-1 h p-1 (•, z * p-1 ) , Z N p-1 -z * p-1 .
• For the rst part, we have by Cauchy-Schwarz inequality

√ N γ N p-1 h p-1 (•, Z N p-1 ) -h p-1 (•, z * p-1 ) , Z N p-1 -z * p-1 ≤ √ N γ N p-1 (1) Z N p-1 -z * p-1 sup x ∈E p-1 h p-1 (x, Z N p-1 ) -h p-1 (x, z * p-1 ) .
Then, let us consider

Ω p-1 = ω ∈ Ω : Z N p-1 (ω) -----→ N →∞ z * p-1 .
By Theorem 4.1, Ω p-1 has probability one. Therefore, by A2, for all ω ∈ Ω p-1 and all ϵ > 0, there exists N (ω, ϵ) > 0 such that, for all N > N (ω, ϵ),

sup x ∈E p-1 h p-1 (x, Z N p-1 (ω)) -h p-1 (x, z * p-1 ) < ϵ.
This means that sup

x ∈E p-1 h p-1 (x, Z N p-1 ) -h p-1 (x, z * p-1 )
a .s .

-----→

N →∞ 0.
Thus, we deduce from (11) that

√ N γ N p-1 h p-1 (•, Z N p-1 ) -h p-1 (•, z * p-1 ) , Z N p-1 -z * p-1 P -----→ N →∞ 0.
• For the second part, since Theorem 4.1 and A2 imply that

γ N p-1 (h p-1 (•, z * p-1 )) a .s . -----→ N →∞ γ p-1 (h p-1 (•, z * p-1 )) = 0,
we conclude by (11) that

√ N γ N p-1 h p-1 (•, z * p-1 ) , Z N p-1 -z * p-1 P -----→ N →∞ 0.
Hence we have proved that

D N p P -----→ N →∞ 0, which leads to n p=0 D N p P -----→ N →∞ 0.
Next, it is easy to check that

(U N k ) 1≤k ≤(n+1)N is an (E N k ) 1≤k ≤(n+1
)N -martingale di erence array. In order to apply Theorem 2.3 in [START_REF] Mcleish | Dependent central limit theorems and invariance principles[END_REF], we just have to check that

• By A1, max 1≤k ≤(n+1)N U N k ≤ 2 √ N f ∞ max 1≤p ≤n p-1 q=0 G q, • ∞ ≤ 2 √ N f ∞ n p=1 p-1 q=0 G q, • ∞ , (13)
which shows that

(max 1≤k ≤(n+1)N |U N k |) is uniformly bounded in L 2 -norm. • From (13), we also get that max 1≤k ≤(n+1)N U N k P -----→ N →∞ 0. • Standard calculation gives (n+1)N k=1 U N k 2 = n p=0 γ N p (1) 2 η N p (f 2 p ) + (γ N p-1 Q p,N (f p )) 2 -2γ N p (1)η N p (f p )γ N p-1 Q p,N (f p ) .
As shown above, the convergence of D N p indicates that

γ N p-1 Q p,N (f p ) -γ N p-1 Q p (f p ) P -----→ N →∞ 0.
Then, by applying Theorem 4.1, we obtain

(n+1)N k=1 U N k 2 P -----→ N →∞ σ 2 γ n (f ),
Therefore, we have the following central limit theorem

(n+1)N k =1 U N k d -----→ N →∞ N 0, σ 2 γ n (f ) .
Returning to (12), the conclusion follows from Slutsky's Lemma.

Proof of Theorem 3.1

We want to show that, under A1-A2, for any test functions ϕ,ψ ∈ B b (E n ) and for any coalescence indicator b ∈ {0, 1} n+1 , we have with the convention

Γ b n,N (ϕ ⊗ ψ ) -Γ b n (ϕ ⊗ ψ ) = O p 1 √ N .
Γ b -1,N = Γ b -1 := η ⊗2 0 C b 0 .
Note that, with this convention, we have

Γ b p = Γ b p-1 Q ⊗2 p C b p .
We also remark that, for any b n ∈ {0, 1} and any ϕ,ψ ∈ B b (E n ), there exists f and in

B b (E n-1 ) such that Q ⊗2 n C b n (ϕ ⊗ ψ ) = f ⊗ . ( 14
)
Speci cally, for b n = 0, it su ces to consider f = Q n (ϕ) and = Q n (ψ ), while for b n = 1 one can take f = Q n (ϕψ ) and = Q n (1) = G n-1 . As usual, the proof is done by induction.

-Step 0:

• If b 0 = 1, (6) and De nition 3.1 give

E Γ b 0,N (ϕ ⊗ ψ ) = E 1 N N i=1 ϕ(X i 0 )ψ (X i 0 ) = η 0 (ϕψ ) = Γ b 0 (ϕ ⊗ ψ ).
Hence, the central limit theorem yields

√ N Γ b 0,N (ϕ ⊗ ψ ) -Γ b 0 (ϕ ⊗ ψ ) d -----→ N →∞ N 0, η 0 (ϕ 2 ψ 2 ) -η 0 (ϕψ ) 2 , so that Γ b 0,N (ϕ ⊗ ψ ) -Γ b 0 (ϕ ⊗ ψ ) = O p 1 √ N .
• If b 0 = 0, the central limit theorem ensures that

η N 0 (ϕ) -η 0 (ϕ) = O p 1 √ N and η N 0 (ψ ) -η 0 (ψ ) = O p 1 √ N
.

Therefore, we have

η N 0 (ϕ)η N 0 (ψ ) -η 0 (ϕ)η 0 (ψ ) = η N 0 (ϕ) -η 0 (ϕ) η N 0 (ψ ) + η 0 (ϕ) η N 0 (ψ ) -η 0 (ψ ) = O p 1 √ N .
Thanks to (1), one has

Γ b 0,N (ϕ ⊗ ψ ) = N N -1 η N 0 (ϕ)η N 0 (ψ ) - 1 N 2 N i=1 ϕ(X i 0 )ψ (X i 0 ) .
Combined with De nition 3.1 and the law of large numbers, one deduces that

Γ b 0,N (ϕ ⊗ ψ ) -Γ b 0 (ϕ ⊗ ψ ) = Γ b 0,N (ϕ ⊗ ψ ) -η 0 (ϕ)η 0 (ψ ) = O p 1 √ N . -Step n ≥ 1:
We suppose that for any test functions f , ∈ B b (E n-1 ) and coalescence indicator b, we have

Γ b n-1,N (f ⊗ ) -Γ b n-1 (f ⊗ ) = O p 1 √ N .
Next, we consider the following decomposition

Γ b n,N (ϕ ⊗ ψ ) -Γ b n (ϕ ⊗ ψ ) = Γ b n,N (ϕ ⊗ ψ ) -Γ b n-1,N Q ⊗2 n,N C b n (ϕ ⊗ ψ ) R 1 (N ) + Γ b n-1,N Q ⊗2 n,N C b n (ϕ ⊗ ψ ) -Γ b n-1,N Q ⊗2 n C b n (ϕ ⊗ ψ ) R 2 (N ) + Γ b n-1,N Q ⊗2 n C b n (ϕ ⊗ ψ ) -Γ b n-1 Q ⊗2 n C b n (ϕ ⊗ ψ ). R 3 (N ) (15)
The tools to terminate the proof are the following ones:

• Lemma 4.1 shows that R 1 (N ) = O p 1 √ N .
• Lemma 4.2 and the fact that one may write C b n (ϕ ⊗ ψ ) as f ⊗ for any b n ensure that

R 2 (N ) = O p 1 √ N .
• Finally, the convergence rate

R 3 (N ) = O p 1 √ N .
is a direct consequence of ( 14) and the induction hypothesis.

Technical results

This section presents some useful technical results. Before going further, remind that

Γ b n,N (1) := γ N n (1) 2 N n-1 (N -1) n+1 [2] 0:n ∈((N ) 2 ) ×(n+1) n-1 p=0 λ b p (A [2] p+1 p , [2] p ) .
If we set

Λ [2] n n := [2] 0:n-1 ∈((N ) 2 ) ×n n-1 p=0 λ b p (A [2] p+1 p , [2] p ) (16)
together with the convention Λ

[2] 0 0 := 1, we may write

Γ b n,N (1) := γ N n (1) 2 N n-1 (N -1) n+1 [2] n ∈(N ) 2 Λ [2] n n , (17)
so that

Γ b n,N (1) 2 = γ N n (1) 4 N n-1 (N -1) n+1 2 ( [2] n , [2] n )∈((N ) 2 ) ×2 Λ [2] n n Λ [2] n n . (18)
Note that (17) is still true when n = 0. Then, for n ≥ 1, we have by de nition

Λ [2] n n = [2] n-1 ∈(N ) 2 Λ [2] n-1 n-1 λ b n-1 (A [2] n n-1 , [2] n-1 ). (19)
This decomposition will appear several times in the sequel for it is a keystone to study the behavior of the coalescent tree-based measures.

Proposition 4.1. Assume A1. For any coalescence indicator b, we have

sup N >1 E Γ b n,N (1) 2 < +∞.
In particular, the sequence (Γ b n,N (1); N ≥ 1) is uniformly tight.

Proof. We give a proof by induction. The veri cation for step 0 is trivial as Γ b 0,N (1) = 1. For n ≥ 1, we suppose that sup

N >1 E Γ b n-1,N (1) 2 < +∞.
As de ned in Section 2.2, the IPS associated with ASMC is a Markov chain (X n ) n ≥0 with genealogy (A n ) n ≥0 tracking the indice of the parent of each particle at each level. More precisely, A i p-1 = j means that the parent of the particle X i p is X j p-1 . Accordingly, the ltration (G N n ) n ≥0 with the genealogy of the IPS is de ned by

G N 0 := σ (X 0 )
and, for n ≥ 1, G N n := σ (A 0 , . . . , A n-1 , X 0 , . . . , X n ). By combining (18) and ( 19), and taking into account that

γ N n (1) = n-1 p=0 η N p (G p,N ) = γ N n-1 (1)η N n-1 (G n-1,N ) = γ N n-1 (1)m(X n-1 )(G n-1,N ) is G N n-1 -measurable, we have E Γ b n,N (1) 2 G N n-1 = γ N n-1 (1) 4 N n-1 (N -1) n+1 2 ( [2] n-1 , [2] n-1 )∈((N ) 2 ) ×2 Λ [2] n-1 n-1 Λ [2] n-1 n-1 ( [2] n , [2] n )∈((N ) 2 ) ×2 m(X n-1 )(G n-1,N ) 4 E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 . (20)
For the notation concerning the indices in the IPS, we use

[N ] q p := (i 1 , . . . , i q ) ∈ [N ] q : Card{i 1 , . . . , i q } = p .

In particular, we denote (N ) q := [N ] q q . We also write

(N ) 2 ×q := (N ) 2 × (N ) 2 × • • • × (N ) 2 q times .
With a slight abuse of notation, we admit that

((i, j), (k, l)) = (i, j, k, l).
With this notation, for N ≥ 4, we have the decomposition

((N ) 2 ) ×2 = ((N ) 2 ) ×2 ∩ [N ] 4 2 ∪ ((N ) 2 ) ×2 ∩ [N ] 4 3 ∪ (N ) 4 .
The idea of the proof consists in analyzing (20) with respect to the three terms that appear in the right-hand side of the latter. Recall from (3) that, given X n-1 , we make an independent multinomial selection of the parent of each particle at step n according to the discrete probability measure

S n-1,N (X n-1 , •) = N k=1 G n-1,N (X k n-1 ) N j=1 G n-1,N (X j n-1 ) δ k = N k =1 G n-1,N (X k n-1 ) N m(X n-1 )(G n-1,N ) δ k , with, for all k ∈ [N ], 0 < G n-1,N (X k n-1 ) N m(X n-1 )(G n-1,N ) ≤ G n-1, • ∞ N m(X n-1 )(G n-1,N ) .
We also recall that

λ b n-1 (A [2] n n-1 , [2] n-1 ) = 1 {b n-1 =0} 1 {A 1 n n-1 = 1 n-1 A 2 n n-1 = 2 n-1 } + 1 {b n-1 =1} 1 {A 1 n n-1 = 1 n-1 =A 2 n n-1 2 n-1 } . • Case 1: ( [2] n , [2] n ) ∈ ((N ) 2 ) ×2 ∩ [N ] 4 2 .
In this case, there are only two distinct random variables among A

1 n n-1 , A 2 n n-1 , A 1 n n-1 , A 2 n n-1 . Recall that 1 n 2
n by construction. Let us rst suppose that

1 n = 1 n and 2 n = 2 n .
Thus, we deduce that

E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 ≤ E λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 = 1 {b n-1 =0} P A 1 n n-1 = 1 n-1 , A 2 n n-1 = 2 n-1 G N n-1 + 1 {b n-1 =1} P A 1 n n-1 = 1 n-1 = A 2 n n-1 G N n-1 ≤ G n-1, • ∞ N m(X n-1 )(G n-1,N ) 2 .
The analysis for the case where

1 n = 2 n and 2 n = 1 n is analogue. Hence, we conclude that E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 ≤ G n-1, • ∞ N m(X n-1 )(G n-1,N ) 2 . ( 21
)
Meanwhile, we notice that

# ((N ) 2 ) ×2 ∩ [N ] 4 2 = 2N (N -1).
Putting all things together yields

( [2] n , [2] n )∈((N ) 2 ) ×2 ∩[N ] 4 2 m(X n-1 )(G n-1,N ) 4 E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 ≤ 2(N -1) N G n-1, • • Case 2: ( [2] n , [2] n ) ∈ ((N ) 2 ) ×2 ∩ [N ] 4 3 .
As noticed in the previous case, the number of di erent indices within ( [2] n , [2] n ) is the only thing that matters for the upper-bound in (21). Accordingly, the same reasoning gives this time

E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 ≤ G n-1, • ∞ N m(X n-1 )(G n-1,N ) 3 .
Since the total number of choices is

# ((N ) 2 ) ×2 ∩ [N ] 4 3 = 4N (N -1)(N -2), it comes ( [2] n , [2] n )∈((N ) 2 ) ×2 ∩[N ] 4 3 m(X n-1 )(G n-1,N ) 4 E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 ≤ 4(N -1)(N -2) N 2 G n-1, • 4
∞ .

• Case 3:

( [2] n , [2] n ) ∈ (N ) 4 . This time, we get E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 ≤ G n-1, • ∞ N m(X n-1 )(G n-1,N ) 4 , and
# (N ) 4 = N (N -1)(N -2)(N -3), so that ( [2] n , [2] n )∈(N ) 4 m(X n-1 )(G n-1,N ) 4 E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 ≤ (N -1)(N -2)(N -3) N 3 G n-1, • 4 ∞ .
As a consequence, since

2 + 4(N -2) N + (N -2)(N -3) N 2 ≤ 7,
an upper-bound for ( 20) is

E Γ b n,N (1) 2 G N n-1 ≤7 N n-1 (N -1) n+1 2 N -1 N G n-1, • 4 ∞ γ N n-1 (1) 4 ( [2] n-1 , [2] n-1 )∈((N ) 2 ) ×2 Λ [2] n-1 n-1 Λ [2] n-1 n-1 .
Replacing n with (n -1) in (18) allows us to conclude that

E Γ b n,N (1) 2 G N n-1 ≤ 7 N N -1 G n-1, • 4 ∞ Γ b n-1,N (1) 2 .
Finally, by applying the induction hypothesis, we have sup

N ≥4 E Γ b n,N (1) 2 = sup N ≥4 E E Γ b n,N (1) 2 G N n-1 ≤ 28 3 G n-1, • 4 ∞ sup N ≥4 E Γ b n-1,N (1) 2 < +∞,
which ends the proof of Proposition 4.1.

Lemma 4.1. Under A1, for any test functions f , ∈ B b (E n ), we have, for all n ≥ 1,

E Γ b n,N (f ⊗ ) G N n-1 = Γ b n-1,N Q ⊗2 n,N C b n (f ⊗ ), (22)
as well as

Γ b n,N (f ⊗ ) -Γ b n-1,N Q ⊗2 n,N C b n (f ⊗ ) = O p 1 √ N .
Proof. First, by exploiting the notation de ned in (16), we have

Γ b n,N (f ⊗ ) := γ N n (1) 2 N n-1 (N -1) n+1 [2] n ∈(N ) 2 Λ [2] n n C b n (f ⊗ )(X [2] n n ),
and ( 22) is then a direct consequence of Proposition A.1 since for any [2] n ∈ (N )

2 E γ N n (1) 2 N n-1 (N -1) n+1 Λ [2] n n C b n (f ⊗ )(X [2] n n ) G N n-1 = 1 N (N -1) Γ b n-1,N Q ⊗2 n,N C b n (f ⊗ ),
where the right-hand side does not depend on [2] n . Second, thanks to Chebyshev's inequality, it su ces to verify that

Var Γ b n,N (f ⊗ ) -Γ b n-1,N Q ⊗2 n,N C b n (f ⊗ ) = O 1 N .
For this, by ( 22), we just have to show that

E Γ b n,N (f ⊗ ) 2 -(Γ b n-1,N Q ⊗2 n,N C b n (f ⊗ )) 2 = O 1 N .
Then, recall that, by de nition,

Γ b n,N (f ⊗ ) 2 =γ N n (1) 4 N n-1 (N -1) n+1 2 ( [2] n , [2] n )∈((N ) 2 ) ×2 Λ [2] n n Λ [2] n n C b n (f ⊗ ) ⊗2 (X [2] n n , X [2] n n ) = γ N n (1) 4 N n-1 (N -1) n+1 2 ( [2] n , [2] n )∈(N ) 4 Λ [2] n n Λ [2] n n C b n (f ⊗ ) ⊗2 (X [2] n n , X [2] n n ) R 1 (N ) + γ N n (1) 4 N n-1 (N -1) n+1 2 ( [2] n , [2] n )∈((N ) 2 ) ×2 \(N ) 4 Λ [2] n n Λ [2] n n C b n (f ⊗ ) ⊗2 (X [2] n n , X [2] n n ) R 2 (N )
.

• For R 1 (N ), our goal is to establish that

E R 1 (N ) -(Γ b n-1,N Q ⊗2 n,N C b n (f ⊗ )) 2 = O 1 N .
In fact, for any

( [2] n , [2] n ) ∈ (N ) 4 , (A 1 n n , X 1 n n , A 2 n n , X 2 n n ) and (A 1 n n , X 1 n n , A 2 n n , X 2 n n )
are conditionally independent given G N n-1 by construction of the IPS. Hence, by applying Proposition A.1 respectively for [2] n and for [2] n , we have

E γ N n (1) 4 N n-1 (N -1) n+1 2 Λ [2] n n Λ [2] n n C b n (f ⊗ )(X [2] n n )C b n (f ⊗ )(X [2] n n ) G N n-1 = 1 N 2 (N -1) 2 (Γ N n-1 Q ⊗2 n,N C b n (f ⊗ )) 2 . Then, since # (N ) 4 = N (N -1)(N -2)(N -3), we deduce that E R 1 (N ) -(Γ b n-1,N Q ⊗2 n,N C b n (f ⊗ )) 2 G N n-1 = N (N -1)(N -2)(N -3) N 2 (N -1) 2 -1 (Γ N n-1 Q ⊗2 n,N C b n (f ⊗ )) 2 ,
and

E R 1 (N ) -(Γ b n-1,N Q ⊗2 n,N C b n (f ⊗ )) 2 = N (N -1)(N -2)(N -3) N 2 (N -1) 2 -1 E (Γ N n-1 Q ⊗2 n,N C b n (f ⊗ )) 2 = O 1 N ,
where the nal equality is due to Proposition 4.1, taking into account that f and are bounded, and so is G n-1,N uniformly with respect to N by A1.

• For R 2 (N ), the nonnegativity of

Λ [2] n n implies E[R 2 (N )] ≤ E       γ N n (1) 4 N n-1 (N -1) n+1 2 ( [2] n , [2] n )∈((N ) 2 ) ×2 \(N ) 4 Λ [2] n n Λ [2] n n       f 2 ∞ 2 ∞ .
So the proof will be nished once we have shown that

E       γ N n (1) 4 N n-1 (N -1) n+1 2 ( [2] n , [2] n )∈((N ) 2 ) ×2 \(N ) 4 Λ [2] n n Λ [2] n n       = O 1 N .
Once again, we proceed by induction. At step 0, we have

1 N 2 (N -1) 2 ( [2] 0 , [2] 0 )∈((N ) 2 ) ×2 \(N ) 4 1 = 1 - N (N -1)(N -2)(N -3) N 2 (N -1) 2 = O 1 N .
For step n ≥ 1, we suppose that

E        γ N n-1 (1) 4 N n-2 (N -1) n 2 ( [2] n-1 , [2] n-1 )∈((N ) 2 ) ×2 \(N ) 4 Λ [2] n-1 n-1 Λ [2] n-1 n-1        = O 1 N .
The adaptation of (20) to the present context gives

E       γ N n (1) 4 N n-1 (N -1) n+1 2 ( [2] n , [2] n )∈((N ) 2 ) ×2 \(N ) 4 Λ [2] n n Λ [2] n n G N n-1       = γ N n-1 (1) 4 N n-1 (N -1) n+1 2 ( [2] n-1 , [2] n-1 )∈((N ) 2 ) ×2 Λ [2] n-1 n-1 Λ [2] n-1 n-1 ( [2] n , [2] n )∈((N ) 2 ) ×2 \(N ) 4 m(X n-1 )(G n-1,N ) 4 E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 . Now, for N ≥ 4, it is clear that ((N ) 2 ) ×2 \(N ) 4 = ((N ) 2 ) ×2 ∩ [N ] 4 2 ∪ ((N ) 2 ) ×2 ∩ [N ] 4 3 .
-Case 1:

( [2] n , [2] n ) ∈ ((N ) 2 ) ×2 ∩ [N ] 4 2 . By de nition of S n-1,N in (3), E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 ≤ G n-1, • ∞ N m(X n-1 )(G n-1,N ) 2 1 {b n-1 =1, 1 n-1 = 1 n-1 } + 1 {b n-1 =0, 1 n-1 = 1 n-1 , 2 n-1 = 2 n-1 } ≤ G n-1, • ∞ N m(X n-1 )(G n-1,N ) 2 1 {#{ 1 n-1 , 1 n-1 , 2 n-1 , 2 n-1 }<4} , and since # ((N ) 2 ) ×2 ∩ [N ] 4 2 = 2N (N -1), it comes ( [2] n , [2] n )∈((N ) 2 ) ×2 ∩[N ] 4 2 m(X n-1 )(G n-1,N ) 4 E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 ≤ 2N (N -1) N 2 G n-1, • 4 ∞ 1 {#{ 1 n-1 , 1 n-1 , 2 n-1 , 2 n-1 }<4} .
-Case 2:

( [2] n , [2] n ) ∈ ((N ) 2 ) ×2 ∩ [N ] 4 3 . First, we suppose that 1 n = 1 n .
As for the previous case, we have

E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 ≤ G n-1, • ∞ N m(X n-1 )(G n-1,N ) 3 1 {b n-1 =1, 1 n-1 = 1 n-1 } + 1 {b n-1 =0, 1 n-1 = 1 n-1 } ≤ G n-1, • ∞ N m(X n-1 )(G n-1,N ) 3 1 {#{ 1 n-1 , 1 n-1 , 2 n-1 , 2 n-1 }<4} .
By the same reasoning, for 1 n = 2 n , 2 n = 1 n and 2 n = 2 n , we also have

E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 ≤ G n-1, • ∞ N m(X n-1 )(G n-1,N ) 3 1 {#{ 1 n-1 , 1 n-1 , 2 n-1 , 2 n-1 }<4} .
In addition, since

# ((N ) 2 ) ×2 ∩ [N ] 4 3 = 4N (N -1)(N -2), we get this time ( [2] n , [2] n )∈((N ) 2 ) ×2 ∩[N ] 4 3 m(X n-1 )(G n-1,N ) 4 E λ b n-1 (A [2] n n-1 , [2] n-1 )λ b n-1 (A [2] n n-1 , [2] n-1 ) G N n-1 ≤ 4N (N -1)(N -2) N 3 G n-1, • 4 ∞ 1 {#{ 1 n-1 , 1 n-1 , 2 n-1 , 2
n-1 }<4} . By gathering both cases, we have

E       γ N n (1) 4 N n-1 (N -1) n+1 2 ( [2] n , [2] n )∈((N ) 2 ) ×2 \(N ) 4 Λ [2] n n Λ [2] n n G N n-1       ≤γ N n-1 (1) 4 N n-2 (N -1) n 2 N 2 (N -1) 2 2N (N -1) N 2 + 4N (N -1)(N -2) N 3 G n-1, • 4 ∞ ( [2]
n-1 ,

[2] n-1 )∈((N ) 2 ) ×2 Λ [2] n-1 n-1 Λ [2] n-1 n-1 1 {#{ 1 n-1 , 1 n-1 , 2 n-1 , 2 n-1 }<4} ≤6 N 2 (N -1) 2 G n-1, • 4 ∞ γ N n-1 (1) 4 N n-2 (N -1) n 2 ( [2] n-1 , [2] n-1 )∈((N ) 2 ) ×2 \(N ) 4 Λ [2] n-1 n-1 Λ [2] n-1 n-1 .
The conclusion follows from the induction hypothesis by taking the expectation on both sides.

This ends the proof of Lemma 4.1.

Lemma 4.2. Assume A1-A2, then for any test functions f , ∈ B b (E n ) and for all n ≥ 1,

Γ b n-1,N Q ⊗2 n,N (f ⊗ ) -Γ b n-1,N Q ⊗2 n (f ⊗ ) = O p 1 √ N .
Proof. The veri cation shares some resemblance with the convergence of P 2 (N ) in the proof of Theorem 4.1. Speci cally, we start with the following decomposition:

Γ b n-1,N Q ⊗2 n,N (f ⊗ ) -Γ b n-1,N Q ⊗2 n (f ⊗ ) ≤ Γ b n-1,N Q ⊗2 n,N (f ⊗ ) -Γ b n-1,N (Q n,N ⊗ Q n )(f ⊗ ) D 1 (N ) + Γ b n-1,N (Q n,N ⊗ Q n )(f ⊗ ) -Γ b n-1,N Q ⊗2 n (f ⊗ ) D 2 (N )
.

For D 1 (N ), we may write

(Q ⊗2 n,N (f ⊗ ) -(Q n,N ⊗ Q n )(f ⊗ ))(x, ) = Q n,N (f )(x)(Q n,N ( )( ) -Q n ( )( )).
By A2, for any ∈ B b (E n ), there exists a bounded function h n-1 such that

Q n,N ( )( ) -Q n ( )( ) = h n-1 ( , Z N n-1 ), Z N n-1 -z * n-1 ≤ h n-1 ∞ Z N n-1 -z * n-1 .
Since, in addition,

|Q n,N (f )(x)| ≤ G n-1, • ∞ f ∞ , it comes D 1 (N ) ≤ Γ b n-1,N (1) G n-1, • ∞ f ∞ h n-1 ∞ Z N n-1 -z * n-1 . By Proposition 4.1, one has Γ b n-1,N (1) = O p (1)
. In addition, a by-product (11) of Theorem 2.1 is that

Z N n-1 -z * n-1 = O p 1 √ N .
Hence, one concludes that

D 1 (N ) = O p 1 √ N .
The reasoning for D 2 (N ) is the same.

Connection between the estimators

In this section, we give some combinatorial results on the coalescent tree-based measures Γ b n,N . In particular, they allow us to connect the variance estimator (9) of Lee & Whiteley and our term by term estimators. As mentioned before, these relations do not depend on A2: they are provided by the structure of the IPS and the underlying multinomial selection scheme. In this respect, recall that, under A1, Equation (3) is always well-de ned for the denominator is always strictly positive, and the same holds true for the IPS itself. This is in fact the only condition required here. Proposition 4.2. Provided that the IPS is well-de ned, then for any test function F ∈ B b (E 2 n ), we have the decompositions:

(γ N n ) ⊗2 (F ) = b ∈ {0,1} n+1 n p=0 (N -1) 1-b p N Γ b n,N (F ), and
(η N n ) ⊗2 (F ) = b ∈ {0,1} n+1 n p=0 (N -1) 1-b p N Γb n,N (F ). Proof. Since Γb n,N (F ) := N n-1 (N -1) n+1 [2] 0:n ∈((N ) 2 ) ×(n+1) n-1 p=0 λ b p (A [2] p+1 p , [2] p ) C b n (F )(X [2] n n ), we have b ∈ {0,1} n+1 n p=0 (N -1) 1-b p N Γb n,N (F ) = N n-1 (N -1) n+1 b ∈ {0,1} n+1 [2] 0:n ∈((N ) 2 ) ×(n+1) n p=0 (N -1) 1-b p N n-1 p=0 λ b p (A [2] p+1 p , [2] p ) C b n (F )(X [2] n n ).
Enumerating all the possibilities for the coalescence indicator b ∈ {0, 1} n+1 leads to

b ∈ {0,1} n+1 n p=0 (N -1) 1-b p N Γb n,N (F ) = [2] 0 ∈(N ) 2 • • • [2] n-1 ∈(N ) 2 n-1 p=0 1 N 1 {A 1 p+1 p =A 2 p+1 p = 1 p 2 p } + N -1 N 1 {A 1 p+1 p = 1 p A 2 p+1 p = 2 p } N N -1 n N -1 N m 2 (X n )C 0 (F ) + 1 N m 2 (X n )C 1 (F ) .
To conclude, one just has to observe that

[2] 0 ∈(N ) 2 • • • [2] n-1 ∈(N ) 2 n-1 p=0 1 N 1 {A 1 p+1 p =A 2 p+1 p = 1 p 2 p } + N -1 N 1 {A 1 p+1 p = 1 p A 2 p+1 p = 2 p } = N -1 N n , while, by (1)
,

N -1 N m 2 (X n )C 0 (F ) + 1 N m 2 (X n )C 1 (F ) = m ⊗2 (X n )(F ) = (η N n ) ⊗2 (F ).
Multiplying both sides by γ N n (1) 2 gives the corresponding relation for (γ N n ) ⊗2 (F ).

We can now proceed with the proof of Proposition 3.1. Recall that the goal is to show that

NV N n (f ) -σ 2 η n,N (f ) = NV N n (f ) - n p=0 Γ(p) n,N (f ⊗2 ) -Γ( ) n,N (f ⊗2 ) = O p 1 N , and
NV N n (f -η N n (f )) - n p=0 Γ(p) n,N f -η N n (f ) ⊗2 -Γ( ) n,N f -η N n (f ) ⊗2 = O p 1 N .
By construction, we have

V N n (f ) = η N n (f ) 2 -Γ( ) n,N (f ⊗2 ) = (η N n ) ⊗2 (f ⊗2 ) -Γ( ) n,N (f ⊗2
).

An implication of Proposition 4.1 is that, for any test function f and any coalescence indicator b, Γb n,N (f ⊗2 ) = O p (1) . Thus, a consequence of Proposition 4.2 is

(η N n ) ⊗2 (f ⊗2 ) = N -1 N n+1 Γ( ) n,N (f ⊗2 ) + 1 N N -1 N n n p=0 Γ(p) n,N (f ⊗2 ) + O p 1 N 2 .
The desired formula is then obtained by remarking that

N -1 N n = 1 -O 1 N and N -1 N n+1 -1 = - n + 1 N + O 1 N 2 .
Similarly, since Γb

n,N f -η N n (f ) ⊗2 = O p (1) ,
the same algebraic manipulation yields

NV N n (f -η N n (f )) - n p=0 Γ(p) n,N f -η N n (f ) ⊗2 -Γ( ) n,N f -η N n (f ) ⊗2 = O p 1 N .
This closes the proof of Proposition 3.1.

A Many-body Feynman-Kac models

The many-body Feynman-Kac model was proposed in [START_REF] Del Moral | On particle Gibbs samplers[END_REF] to study the propagation of chaos property of the Conditional Particle Markov Chain Monte Carlo introduced in [START_REF] Andrieu | Particle Markov chain Monte Carlo methods[END_REF].

The basic idea is to trace the information of all particles in the IPS along with its genealogy, and to construct an instrumental particle block which is heavily dependent (identical) to some speci c particles. We call these instrumental particles the coupled particle block of the IPS.

A.1 Duality formula

At each layer, the particles in the original IPS are denoted by X p , with its genealogy A p-1 . The coupled particle block of q particles is denoted by X [q] p , with its genealogy denoted by Ã[q] p-1 . The corresponding variables in the integral operators will be denoted by x p , a p-1 ,

x[q] p and ã[q] p-1 respectively.

Before giving speci c de nitions, we want to mention that the mathematical object we would like to look into is the whole particle system, namely the original IPS and the coupled particle block with genealogy. At each layer p, we are interested by the tuple:

(X p , A p-1 , X [q] p , Ã[q] p-1 ).
As for the basic idea of Particle Markov Chain Monte Carlo method [ADH10], we study respectively the distributions of

X p , A p-1 X [q] p , Ã[q] p-1 and X [q] p , Ã[q]
p-1 X p , A p-1 . Thanks to the speci c construction, as well as the relatively simple multinomial resampling scheme of Feynman-Kac IPS, Lemma A.1 provides a duality formula to connect both distributions and leads in particular to Proposition A.1. This latter result is crucial to prove the consistency of our term by term estimator in Theorem 3.1.

In this section, a transition kernel denoted by the letter Q is a Feynman-Kac kernel, meaning that its total mass is not necessarily 1, and it can be expressed by the product of a positive potential function and a Markov kernel. All transition kernels denoted by the letter M are Markov kernels.

Notice that the transition from level p -1 to level p of the IPS with its genealogy de ned in Section 2.2 can be expressed as

(A p-1 , X p ) ∼ N i=1 Φ p,N (X p-1 , d(A i p-1 , X i p ))
with Φ p,N de ned by

Φ p,N (x p-1 , d(a i p-1 , x i p )) = S p-1,N (x p-1 , da i p-1 ) × M p,N (x a i p-1
p-1 , dx i p ). We de ne the transition of the original IPS with its genealogy by

M p (x p-1 , d(a p-1 , x p )) := N i=1 Φ p,N (x p-1 , d(a i p-1 , x i p ))
and the potential function of the particle block of size q by G (q)

p-1 (x p-1 ) := m(x p-1 )(G p-1,N ) q . We denote the associated Feynman-Kac transition kernel

Q (q) p (x p-1 , d(a p-1 , x p )) := G (q) p-1 (x p-1 ) × M p (x p-1 , d(a p-1 , x p )). Given [q] p ∈ (N ) q , ã[q] p-1 ∈ [N ] q and x[q] p ∈ E q p , we de ne M ã[q] p-1 , [q] p , x [q] p p (x p-1 , d(a p-1 , x p )) := i ∈[N ]\{ 1 p ,..., q p } Φ p,N (x p-1 , d(a i p-1 , x i p )) × δ x [q] p (dx [q] p p ) × δ ã[q] p-1 (da [q] p p-1 )
the conditional transition for the original particle system given the coupled particle block X [q] p = x[q] p at position [q] p with frozen genealogy Ã[q] p-1 = ã[q] p-1 . In particular, we denote

M [q] 0 , x [q] 0 0 (dx 0 ) :=        i ∈[N ]\{ 1 0 ,..., q 0 } η 0 (dx i 0 )        × δ x [q] 0 (dx [q] 0 0 ).
We also de ne

Q (q) p (x p-1 , d( ã[q] p-1 , x[q] p )) := m([N ]) ⊗q (d ã[q] p-1 ) Q ⊗q p,N (x ã[q] p-1 p-1 , d x[q] p ), and
M [q] p p (a p-1 , x p ), d( ã[q] p-1 , x[q] p ) := δ a [q] p p-1 (d ã[q] p-1 ) δ x [q] p p (d x[q] p ).
Then we have the following pivotal duality formula, which is simply a generalization of Lemma 4.1 in [START_REF] Del Moral | On particle Gibbs samplers[END_REF]. We will apply it in the proof of Proposition A.1 with q = 2. Lemma A.1. For p ≥ 1, q ∈ [N ] and p ∈ (N ) q , we have the following duality formula between integral operators

Q (q) p (x p-1 , d(a p-1 , x p )) M [q] p p (a p-1 , x p ), d( ã[q] p-1 , x[q] p ) = Q (q) p (x p-1 , d( ã[q] p-1 , x[q] p )) M ã[q] p-1 , [q] p , x [q] p p (x p-1 , d(a p-1 , x p )), and
η ⊗N 0 (dx 0 ) δ x [q] 0 0 (d x[q] 0 ) = η ⊗q 0 (d x[q] 0 ) M [q] 0 , x [q] 0 0 (dx 0 ).
Proof.

Step 0 is clear. For p ≥ 1, it su ces to check that the nonidentical parts are equal, namely

G (q) p-1 (x p-1 ) n k =1 G p-1,N (x k p-1 ) N m(x p-1 )(G p-1,N ) δ k ⊗q (da [q] p p-1 ) M ⊗q p,N (x a [q] p p-1 p-1 , dx [q] p p ) M [q] p p (a p-1 , x p ), d( ã[q] p-1 , x[q] p ) = Q (q) p (x p-1 , d( ã[q] p-1 , x[q] p )) δ x [q] p (dx [q] p p ) δ ã[q]
p-1

(da

[q] p p-1 ).

Fixing

[q] p ∈ (N ) q and x p-1 ∈ E N p-1 , consider a function

F ∈ B b ([N ] q ×[N ] q ×E q p ×E q p
). Moreover, let a [q] = (a 1 , . . . , a q ) and x [q] = (x 1 , . . . , x q ) denote generic variables belonging respectively to [N ] q and E q p . Then, we may write

∫ m(x p-1 )(G p-1,N ) q N k =1 G p-1,N (x k p-1 ) N m(x p-1 )(G p-1,N ) δ k ⊗q (da [q] p p-1 ) M ⊗q p,N (x a [q] p p-1 p-1 , dx [q] p p ) δ x [q] p p (d x[q] p ) δ a [q] p p-1 (d ã[q] p-1 ) F( ã[q] p-1 , a [q] p p-1 , x [q] p p , x[q] p ) = ∫ m([N ]) ⊗q (da [q] ) G ⊗q p-1,N (x a [q] p-1 ) M ⊗q p,N (x a [q] p-1 , dx [q] ) F(a [q] , a [q] , x [q] , x [q] ) = ∫ m([N ]) ⊗q (da [q] ) Q ⊗q p,N (x a [q] p-1 , dx [q] ) F(a [q] , a [q] , x [q] , x [q] ) = ∫ m([N ]) ⊗q (d ã[q] p-1 ) Q ⊗q p,N (x ã[q] p-1 p-1 , d x[q] p ) δ x [q] p (dx [q] p p ) δ ã[q] p-1 (da [q] p p-1 ) F( ã[q] p-1 , a [q] p p-1 , x [q] p p , x[q] p ) = ∫ Q (q) p (x p-1 , d( ã[q] p-1 , x[q] p )) δ x [q] p (dx [q] p p ) δ ã[q] p-1 (da [q] p p-1 ) F( ã[q] p-1 , a [q] p p-1 , x [q] p p , x[q] p ).
This ends the proof of the duality formula.

Let us recall ( 16) and (19):

Λ [2] n n = [2] 0:n-1 ∈((N ) 2 ) ×n n-1 p=0 λ b p (A [2] p+1 p , [2] p ) = [2] n-1 ∈(N ) 2 Λ [2] n-1 n-1 λ b n-1 (A [2] n n-1 , [2] n-1 ). (23)
with the convention Λ

[2] 0 0 = 1. In fact, this gives another representation of the approximation of the coalescent tree-based measures:

Γ b n,N (f ⊗ ) = γ N n (1) 2 N n-1 (N -1) n+1 [2] n ∈(N ) 2 Λ [2] n n C b n (f ⊗ )(X [2] n n ).

Recall that

G N n-1 := σ (X 0 , . . . , X n-1 , A 0 , . . . , A n-2 ). The upcoming result is useful in the proof of Lemma 4.1.

Proposition A.1. Under A1, for any [2] n ∈ (N ) 2 , any coalescence indicator b, and any test functions f and in B b (E n ), we have, for all n ≥ 1, that

E γ N n (1) 2 N n-1 (N -1) n+1 Λ [2] n n C b n (f ⊗ )(X [2] n n ) G N n-1 = 1 N (N -1) Γ b n-1,N Q ⊗2 n,N C b n (f ⊗ ).
Proof. By applying (23), we obtain

γ N n (1) 2 N n-1 (N -1) n+1 Λ [2] n n C b n (f ⊗ )(X [2] n n ) = γ N n (1) 2 N n-1 (N -1) n+1 [2] n-1 ∈(N ) 2 Λ [2] n-1 n-1 λ b n-1 (A [2] n n-1 , [2] n-1 )C b n (f ⊗ )(X [2] n n ). Since Λ [2] n-1 n-1 is G N n-1 -measurable, it is su cient to show that for each [2] n-1 ∈ (N ) 2 , we have E m(X n-1 )(G n-1,N ) 2 λ b n-1 (A [2] n n-1 , [2] n-1 )C b n (f ⊗ )(X [2] n n ) G N n-1 = 1 N 2 C b n-1 Q ⊗2 n,N C b n (f ⊗ )(X [2] n-1 n-1 ). (24)
Before starting our reasoning, for the sake of simpli cation, we remark that

λ b n-1 (A [2] n n-1 , [2] n-1 )C b n (f ⊗ )(X [2] n n )
can be seen as a bounded measurable function of (A n-1 , X n ), rather than a measurable function of (X

[2] n n , A

[2] n n-1 ). With this in mind, for any test function

F ∈ B b ([N ] N × • • • × [N ] N (n-1) times ×E N 0 × • • • × E N n-1 ),
we have, by de nition of

Q (2) p (x p-1 , d(a p-1 , x p )), E m(X n-1 )(G n-1,N ) 2 λ b n-1 (A [2] n n-1 , [2] n-1 )C b n (f ⊗ )(X [2] n n )F (A 0:n-2 , X 0:n-1 ) = ∫ Q (2) n (x n-1 , d(a n-1 , x n ))λ n-1 (a [2] n n-1 , [2] n-1 )C b n (f ⊗ )(x [2] n n ) F (a 0:n-2 , x 0:n-1 )µ n-1 (da 0:n-2 , dx 0:n-1 ), (25)
where µ n-1 denotes the measure corresponding to the underlying joint distribution of the IPS from step 0 to step n -1 with genealogy. Taking into account that

M [2] n n (a n-1 , x n ), d( ã[2] n-1 , x[2] n ) = δ a [2] n n-1 (d ã[2] n-1 ) δ x [2] n n (d x[2] n )
is a Markov kernel, we can introduce it in the right-hand side of (25) to obtain

E m(X n-1 )(G n-1,N ) 2 λ b n-1 (A [2] n n-1 , [2] n-1 )C b n (f ⊗ )(X [2] n n )F (a 0:n-2 , x 0:n-1 ) = ∫ Q (2) n (x n-1 , d(a n-1 , x n ))M [2] n n (a n-1 , x n ), d( ã[2] n-1 , x[2] n ) λ n-1 (a [2] n n-1 , [2] n-1 )C b n (f ⊗ )(x [2] n n )F (a 0:n-2 , x 0:n-1 )µ n-1 (da 0:n-2 , dx 0:n-1 ).
The design of many-body Feynman-Kac models allows replacing (a

[2] n n-1 , x [2] n n ) with ( ã[2] n-1 , x[2]
n ) in the observation functions, as they are equal by de nition. Hence, one has the following Combining (26) and ( 27), we safely deduce that

∫ Q (2) n (x n-1 , d( ã[2] n-1 , x[2] n )) λ n-1 ( ã[2] n-1 , [2] n-1 )C b n (f ⊗ )( x[2] n ) F (a 0:n-2 , x 0:n-1 )µ n-1 (da 0:n-2 , dx 0:n-1 ) = ∫ 1 N 2 C b n-1 Q ⊗2 n,N C b n (f ⊗ )(x [2] n-1 n-1 )F (a 0:n-2 , x 0:n-1 )µ n-1 (da 0:n-2 , dx 0:n-1 ) =E 1 N 2 C b n-1 Q ⊗2 n,N C b n (f ⊗ )(X [2] n-1
n-1 )F (A 0:n-2 , X 0:n-1 ) .

In conclusion, we have established that

E m(X n-1 )(G n-1,N ) 2 λ b n-1 (A [2] n n-1 , [2] n-1 )C b n (f ⊗ )(X [2] n n )F (A 0:n-2 , X 0:n-1 ) =E 1 N 2 C b n-1 Q ⊗2 n,N C b n (f ⊗ )(X [2] n-1 n-1 )F (A 0:n-2 , X 0:n-1 ) ,
which terminates the veri cation of (24) and the proof of Proposition A.1.

A.2 Some intuition

In general, the coupled particle block does not necessarily have the parents-children relations.

Let us see a representation of the duality formula given in Lemma A.1 recursively applied in a mini IPS from level 0 to level 5 to some randomly chosen indices [2] 0:5 (see Figure 5).

= (4, 5), [2] 1 = (2, 4), [2] 2 = (2, 3), [2] 3 = (3, 5), [2] 4 = (1, 5) and [2] 5 = (1, 2).
However, we can get any ancestral relations or coalescent tree-based form by manipulating the genealogical information encoded in the coupled genealogy. This is the essential idea we used by introducing many-body Feynman-Kac models. To make it clearer, we consider an event de ned by

[2] p-2 = Ã[2] p-2 , 1 p-1 = Ã1 p-1 = Ã2 p-1 2 p-1 , [2] p = Ã[2] p . ( 28
)
and some random walk Metropolis kernels M n such that, at each step, M n is reversible with respect to η n . In this scenario, a popular choice for M n is based on the Gaussian proposal with covariance matrix Σ n . This is the "limiting" (nonadaptive) scenario that we will consider in the sequel. When one does not know the covariance matrices Σ n , a natural choice is to use the estimated covariance matrix Σ N n . Our goal is to compare the respective behaviors of adaptive SMC and nonadaptive SMC. In particular, we want to show that the Lee and Whiteley variance estimator, in an adaptive context, goes to the asymptotic variance of the "limiting" (nonadaptive) SMC when N grows.

For this, we consider the test function f : R 10 (x (1) , x (2) , . . . , x (10) ) → x (1) ∈ R. Keeping the notation of the previous sections, we illustrate the asymptotic variance estimators NV N n fη N n (f ) , which estimate the asymptotic variances of η N n (f ) respectively for the adaptive and nonadaptive SMC algorithms, see Figure 8. On the latter, the so-called reference value is the estimation of the theoretical asymptotic variance σ 2 η n (fη n (f )). This value is estimated via Crude Monte Carlo through 2 × 10 3 independent runs of nonadaptive SMC with N = 5 × 10 3 (notice that, stricto sensu, it does of course not depend on N). At each iteration of the algorithm, the random walk Metropolis kernel is applied 4 times in order to ensure a certain level of acceptance.

It is clear that when N is relatively small, the variance estimations are biased. However, as the number N of particles grows, we see that the behaviors of the adaptive and nonadaptive algorithms are similar in terms of asymptotic variance estimations. More precisely, the overlaps of the 95% con dential intervals indicate that the adaptive SMC algorithm is indeed very "close" to its nonadaptive "limiting" counterpart. As expected, both variance estimators converge to the reference value σ 2 η n (fη n (f )) as N grows.

C Truncated variance estimators

As mentioned in [START_REF] Lee | Variance estimation in the particle lter[END_REF], their variance estimators degenerate when n is very large compared to the number N of particles. Typically, no disjoint ancestral lines exist in such a particle system. In this case, we recommend to use the same kind of xed-lag variance estimators as the ones proposed in [START_REF] Olsson | Numerically stable online estimation of variance in particle lters[END_REF]. More precisely, we only use part of the genealogy of the particle system (e.g., truncated at time n -H for a relatively small lag H ∈ N * ) to construct the variance estimators. Hereafter, we provide a heuristic in order to justify the relevance of such estimators in practice.

In general, the application of SMC sampling on a large time scale requires some "forgetting" (mixing) properties of the underlying model. For example, in the toy example presented in Appendix B, if the Metropolis kernel is implemented a large amount of times at each iteration, the particles will somehow "forget" the dependence caused by the genealogy. Basically, in terms of coalescent tree-based measures, Γ(p) n would be very "close" to the disjoint ancestral lines based measure Γ( ) n . More concretely, if we look at the asymptotic variance σ 2 η n , we have

σ 2 η n (f ) = n-H -1 p=0 Γ(p) n (f ⊗2 ) -Γ( ) n (f ⊗2 )
small by the "forgetting" properties of the model

+ n p=n-H Γ(p) n (f ⊗2 ) -Γ( ) n (f ⊗2 ) .
Accordingly, a natural idea is to estimate only the second part of the right hand side in order to approximate the asymptotic variance. A truncated term by term estimator can therefore be de ned as Figure 8: Variance estimators for adaptive and nonadaptive "limiting" SMC for n = 10 and n = 50 with N varying from 100 to 2 × 10 4 . We trace the variance estimators and its 95% con dential intervals based on 500 independent runs of each algorithm. The reference values σ 2 η n (f -η n (f )) are obtained through 2×10 3 independent runs of nonadaptive "limiting" SMC with N = 5 × 10 3 .

Unfortunately, this estimator is not always numerically stable, as it requires that disjoint ancestral lines exist in the particle system from time 0 to time n -H . Following the same mechanism as in the proofs of Proposition 3.1 and Proposition 4.2, we can show that

N η N n (f ) 2 -Γ( ,H ) n,N (f ⊗2 ) ≈ n p=n-H Γ(p) n,N (f ⊗2 ) -Γ( ) n,N (f ⊗2 ) ,
where, if E i n (H ) denotes the index of the ancestor of X i n at step n -H , Γ( ,H ) n,N (f ⊗2 ) :=

N H -1 (N -1) H +1 E i n (H ) E j n (H ) f (X i n )f (X j n ).
The estimator N (η N n (f ) 2 -Γ( ,H ) n,N (f ⊗2 )) is more or less the one proposed in [START_REF] Olsson | Numerically stable online estimation of variance in particle lters[END_REF] and is indeed a truncated version of NV N n (f ) proposed in [START_REF] Lee | Variance estimation in the particle lter[END_REF]. We refer the interested reader to [START_REF] Olsson | Numerically stable online estimation of variance in particle lters[END_REF] for theoretical results as well as numerical illustrations. When H is properly chosen, the xedlag variance estimator is expected to be able to balance the memory and the degeneracy of the genealogy of the particle system. However, nding a suitable H in a speci c application is highly nontrivial. As explained in [START_REF] Olsson | Numerically stable online estimation of variance in particle lters[END_REF], it is then natural to consider adaptive mechanisms to determine H . Nevertheless, to the best of our knowledge, this is still an open problem, which is beyond the scope of the present paper.

  We call b := (b 0 , . . . , b n ) ∈ {0, 1} n+1 a coalescence indicator where b p = 1 indicates that there is a coalescence at level p. De nition 3.1. We associate with any coalescence indicator b ∈ {0, 1} n+1 the nonnegative measures Γ b n and Γb

Figure 1 :

 1 Figure 1: A representation of the coalescent tree-based measure Γ (p) n .

Figure 2 :

 2 Figure 2: An IPS with n + 1 = 7 levels and N = 5 particles at each level.

  Before proceeding, let us introduce some additional notation. With a slight abuse of notation, for a coalescence indicator b = (b 0 , . . . , b n ) ∈ {0, 1} n+1 , we denote, for all 0 ≤ p ≤ n, Γ b p := Γ (b 0 ,...,b p ) p and Γ b p,N := Γ (b 0 ,...,b p ) p,N

Figure 5 :

 5 Figure5: An illustration of the duality formula recursively applied to a mini IPS of n+1 = 6 levels with 5 particles at each level. Every straight black or dotted arrow within the original IPS represents a Markov transition M p,N and the black twisted ones pointing to the particles in the coupled particle block represent the Feynman-Kac transition kernels Q p,N . The red dotted bending arrows are identities. The indices of the original particles in the coupled particle block are[2] 0 = (4, 5),[2] 1 = (2, 4),[2] 2 = (2, 3),[2] 3 = (3, 5),[2] 4 = (1, 5) and

  n,N (f ⊗2 ) -Γ( ) n,N (f ⊗2 ) .

  Variance estimation of η N n (f ) with n = 10. Variance estimation of η N n (f ) with n = 50.

  •, • " stands for the Euclidean scalar product in R d and | • | for the associated norm. Assumption 2. For any test function f n+1 ∈ B b (E n+1 ), there exists a measurable function h n :

7 F (X 2 6 , X 4 6 ) + F (X 4 6 , X 2 6 ) .Our next result ensures the convergence of our estimators.

∞ .

Acknowledgements

This work was partially supported by the French Agence Nationale de la Recherche, under grant ANR-14-CE23-0012, and by the European Research Council under the European Union's Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement number 614492.

Introduction

Sequential Monte Carlo (SMC) methods are classical Monte Carlo techniques widely used in Bayesian inference, ltering, rare events simulations and many other elds (see for example [START_REF] Doucet | Sequential Monte Carlo methods in practice[END_REF] and references therein). The principle is to approximate a sequence of probability measures (η n ) n ≥0 by simulating an Interacting Particle System (IPS) via an importance sampling and resampling mechanism. The ow of measures is then approximated by the empirical version (η N n ) n ≥0 . A lot of convergence results when the sample size N goes to in nity can be found in the literature (see for example [START_REF] Moral | Feynman-Kac formulae: Genealogical and interacting particle systems with applications[END_REF][START_REF] Moral | Mean eld simulation for Monte Carlo integration[END_REF]).

In practice, when applying these SMC methods, it is also very important to have a control on the constructed estimators, such as con dence intervals. For this, if one has a CLT type theorem for the test function f such as (see, e.g., [START_REF] Moral | Feynman-Kac formulae: Genealogical and interacting particle systems with applications[END_REF][START_REF] Chopin | Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference[END_REF][START_REF] Douc | Limit theorems for weighted samples with applications to sequential Monte Carlo methods[END_REF]) equality:

Now, the duality formula given in Lemma A.1 yields

In addition, since

F (a 0:n-2 , x 0:n-1 )µ n-1 (da 0:n-2 , dx 0:n-1 ).

Next, let us recall that

Otherwise, if b n-1 = 1, we get, with the convention x

On this event, we are able to track the coalescent tree-based form as in Figure 6. The coupled particle block and its genealogy are de ned as the copies of certain particles and parents indices in the associated original IPS. On one hand, we select certain events such that the desired structure is trapped in the coupled particle block. On the other hand, we de ne the estimator based on the information re ected in the original IPS as no additional randomness are added by introducing the coupled particle block. Since their distributions are connected by the duality formula, we can use the information coded in the original IPS to estimate the measures corresponding to these coalescent tree-based particle blocks (see Figure 7).

The duality formula provides a way to touch the adaptive versions of the coalescent treebased measures Γ b n , i.e., all the Feynman-Kac transition kernels Q p in the de nition are replaced with the adaptive version Q p,N . This is the idea underlying the construction of the estimators Γ b n,N .

A.3 Connection with SMC

To conclude, let us say a few words about the behavior of Γ b n,N . One remark is that, in general, this estimator is not unbiased in the ASMC framework. This is a consequence of the adaptive parametrization, as witnessed by Lemma 4.2. On the opposite, in a nonadaptive case (SMC), the estimation is unbiased, exactly as γ N n is an unbiased estimation of γ n (see for example [DM04] Section 3.5.1). It turns out that the classical SMC framework corresponds to the case where the function h n in A2 is equal to zero, meaning that Q n,N = Q n for all n. Thus, Lemma 4.1 and (15) give the following proposition.

Proposition A.2. Assume A1-A2 and suppose that h n ≡ 0 for all n ≥ 0. Then, for all test functions

In particular, we also have

In fact, the essential technical results in Section 4.4 and Section 4.5 only require A1. In other words, A2 can be studied separately in order to adapt to applications not covered in this article.

Another remark is about the di erence between Γ b n,N and µ b as de ned in Section 3.2. of [START_REF] Lee | Variance estimation in the particle lter[END_REF] in the nonadaptive context. However, since it is not straightforward to compare these estimators that are extremely notation-heavy, we would just like to brie y and heuristically mention that the main di erence comes from the step where there is a coalescence, namely b p = 1. If we consider Figure 3 in Section 3.1, our estimator is not the most "precise" that one could propose. Let us look at the case where

[2] 0:6 = ((5, 3), (4, 3), (2, 5), (2, 4), (2, 5), (1, 3), (2, 4)) .

For the terminal point X 4 3 , the conditional distribution of A 4 2 is simply the categorical distribution since X 4 3 is a terminal point. Roughly speaking, once all the genealogy of the terminal points is calculated, one can deduce µ b . Hence, the take-home message is simple: if one is interested in estimating Γ b n numerically, then the estimator µ b proposed in [START_REF] Lee | Variance estimation in the particle lter[END_REF] is expected to be more accurate, meaning that the variance should be smaller in general.

Nevertheless, as a theoretical tool, our estimator is easier to deal with in the adaptive framework. Indeed, induction is highly involved in our proof of consistency, so estimators that are stepwise easy to manipulate are required. Another di erence is that we do not use instrumental random variables such as K 1 and K 2 in the de nition of µ b . This also simpli es the analysis in an adaptive context where there is already more randomness than in a nonadaptive context.

B Numerical experiment

We provide in this section a numerical experiment based on the same toy example as the one presented in Section 4.1 of [START_REF] Beskos | On the convergence of adaptive sequential Monte Carlo methods[END_REF]. In particular, this ensures that assumptions A1-A2 are satis ed. Namely, consider a sequence of centered Gaussian target distributions (η n ; 0 ≤ n ≤ 50) on R 10 given by

Denote by Id the identity matrix on R 10 and J the lower triangular matrix such that J i j = 1 for 1 ≤ j ≤ i -1 ≤ 9. The covariance matrices are de ned by Thus, the initial distribution η 0 consists in 10 centered and independent Gaussian components with variance 10. As n grows, the covariance structure becomes more complicated. We consider an implementation of SMC with (nonadaptive) potential functions