---
abstract: 'Sequential and Quantum Monte Carlo methods, as well as genetic type search algorithms can be interpreted as a mean field and interacting particle approximations of Feynman-Kac models in distribution spaces. The performance of these population Monte Carlo algorithms is strongly related to the stability properties of nonlinear Feynman-Kac semigroups. In this paper, we analyze these models in terms of Dobrushin ergodic coefficients of the reference Markov transitions and the oscillations of the potential functions. Sufficient conditions for uniform concentration inequalities w.r.t. time are expressed explicitly in terms of these two quantities. We provide an original perturbation analysis that applies to annealed and adaptive FK models, yielding what seems to be the first results of this kind for these type of models. Special attention is devoted to the particular case of Boltzmann-Gibbs measures’ sampling. In this context, we design an explicit way of tuning the number of Markov Chain Monte Carlo iterations with temperature schedule. We also propose and analyze an alternative interacting particle method based on an adaptive strategy to define the temperature increments.'
address:
- 'INRIA Bordeaux Sud-Ouest, team ALEA, Domaine Universitaire, 351, cours de la Libération, 33405 Talence Cedex, France.'
- 'CEA-CESTA, 33114 Le Barp, France.'
- 
author:
- François Giraud
- Pierre Del Moral
title: 'Non-Asymptotic Analysis of Adaptive and Annealed Feynman-Kac Particle Models'
---

Introduction {#introduction .unnumbered}
============

Feynman-Kac ([*abbreviate FK*]{}) particle methods, also called sequential, quantum or diffusion Monte Carlo methods, are stochastic algorithms to sample from a sequence of complex high-dimensional probability distributions. These stochastic simulation techniques are of current use in numerical physics [@Assaraf-overview; @Assaraf; @Hetherington] to compute ground state energies in molecular systems. They are also used in statistics, signal processing and information sciences [@Cappe; @DM-filt; @DM-D-J; @DM-Guionnet-2] to compute posterior distributions of a partially observed signal or unknown parameters. In the evolutionary computing literature, these Monte Carlo methods are used as natural population search algorithms for solving optimization problems. From the pure mathematical viewpoint, these advanced Monte Carlo methods are an interacting particle system ([*abbreviate IPS*]{}) interpretation of FK models. For a more thorough discussion on these models, we refer the reader to the monograph [@DM-FK], and the references therein. The principle (see also [@DM-D-J] and the references therein) is to approximate a sequence of target probability distributions $(\eta_n)_n$ by a large cloud of random samples termed particles or walkers. The algorithm starts with $N$ independent samples from $\eta_0$ and then alternates two types of steps: an acceptance-rejection scheme equipped with a selection type recycling mechanism, and a sequence of free exploration of the state space.\
In the recycling stage, the current cloud of particles is transformed by randomly duplicating and eliminating particles in a suitable way, similarly to a selection step in models of population genetics. In the Markov evolution step, particles move independently one each other (mutation step).

This method is often used for solving sequential problems, such as filtering (see e.g., [@Cappe; @Doucet-F-G; @DM-filt]). In other interesting problems, these algorithms also turn out to be efficient to sample from a single target measure $\eta$. In this context, the central idea is to find a judicious interpolating sequence of measures $(\eta_k)_{0\leq k\leq n}$ with increasing sampling complexity, starting from some initial distribution $\eta_0$, up to the terminal one $\eta_n=\eta$. Consecutive measures $\eta_k$ and $\eta_{k+1}$ are sufficiently similar to allow for efficient importance sampling and/or acceptance-rejection sampling. The sequential aspect of the approach is then an “artificial way” to introduce the difficulty of sampling gradually. In this vein, important examples are provided by annealed models. More generally, a crucial point is that large population sizes allow to cover several modes simultaneously. This is an advantage compared to standard MCMC methods that are more likely to be trapped in local modes. These sequential samplers have been used with success in several application domains, including rare events simulation (see [@Cerou-RE]), stochastic optimization and more generally Boltzmann-Gibbs measures sampling ([@DM-D-J]).

Up to now, IPS algorithms have been mostly analyzed using asymptotic (i.e. when number of particles $N$ tends to infinity) techniques, notably through fluctuation theorems and large deviation principles (see for instance [@DM-DA; @DM-Guionnet-3], [@DM-Guionnet-2; @DM-L; @DM-M],[@Kunsch], [@Chopin], [@DM-filt], [@Cappe] and [@DM-FK] for an overview).\
Some non-asymptotic theorems have been recently developped ([@Cerou-var; @DM-D-J-adapt]), but unfortunately none of them apply to annalyze annealed and adaptive FK particle models. On the other hand, these type of nonhomogeneous IPS algorithms are of current use for solving concrete problems arising in numerical physics and engineering sciences (see for instance [@Bertrand; @Giraud-RB; @Neal], [@Clapp; @Deutscher; @Minvielle], [@Jasra; @Schafer]). By the lack of non-asymptotic estimates, these particle algorithms are used as natural heuristics.\
The main contribution of this article is to analyze these two classes of time nonhomogeneous IPS models. Our approach is based on semigroup techniques and on an original perturbation analysis to derive several uniform estimates w.r.t. the time parameter.\
More precisely, in the case of annealed type models, we estimate explicitly the stability properties of FK semigroup in terms of the Dobrushin ergodic coefficient of the reference Markov chain and the oscillations of the potential functions. We combine these techniques with non-asymptotic theorems on $L^p$-mean error bounds ([@DM-M]) and some useful concentration inequalities ([@DM-Hu-Wu; @DM-Rio]). Then, we provide parameter tuning strategies that allow to deduce some useful uniform concentration inequalities w.r.t. the time parameter. These results apply to non homogeneous FK models associated with cooling temperature parameters. In this situation, the sequence of measures $\eta_n$ is associated with a nonincreasing temperature parameter. We mention that other independent approaches, such as Whiteley’s ([@Whiteley]) or Schweizer’s ([@Schweizer]), are based on, e.g., drift conditions, hyper-boundedness, spectral gaps, or non-asymptotic biais and variance decompositions. These approaches lead to convergence results that may also apply to non-compact state spaces. To our knowledge, these techniques are restricted to non-asymptotic variance theorems and they cannot be used to derive uniform and exponential concentration inequalities. It seems also difficult to extend these approaches to analyze the adaptive IPS model discussed in the present article. To solve these questions, we develop a perturbation technique of stochastic FK semigroups. In contrast to traditional FK semigroup, the adaptive particle scheme is now based on random potential functions that depend on a cooling schedule adapted to the variability and the adaptation of the random populations.\
\
The rest of the article is organized as follows. In a preliminary section, we recall a few essential notions related to Dobrushin coefficients or FK semigroups. We also provide some important non-asymptotic results we use in the further development of the article. Section \[section-analyse-generale-FK\] is concerned with the semigroup stability analysis of these models. We also provide a couple of uniform $L^p$-deviations and concentration estimates. In Section \[section-Gibbs\] we apply these results to Boltzmann-Gibbs models associated with a decreasing temperature schedule. In this context, IPS algorithm can be interpreted as a sequence of interacting simulated annealing algorithms ([*abbreviate ISA*]{}). We design an explicit way of tuning the number of Markov Chain Monte Carlo iterations with the temperature schedule. Finally, in Section \[section-adapt\], we propose an alternative ISA method based on an original adaptive strategy to design on the flow the temperature decrements. We provide a non-asymptotic study, based on a perturbation analysis. We end the article with $L^p$-deviation estimates as well as a couple of concentration inequalities.

Statement of Some Results {#statement-of-some-results .unnumbered}
=========================

Feynman-Kac particle algorithms consist in evolving an interacting particle system $(\zeta_n)_n = \left( \zeta_n^1, \ldots, \zeta_n^N \right)_n$ of size $N$, on a given state space $E$. Their evolution is decomposed into two genetic type transitions: a selection step, associated with some positive potential function $G_n$; and a mutation step, where the selected particles evolve randomly according to a given Markov transition $M_n$ (a more detailed description of these IPS algorithms is provided in Section \[algo-classique\]). In this context, the occupation measures $\displaystyle{ \eta_n^N := \frac{1}{N}\sum_{1\leq i\leq N}\delta_{\zeta^i_n}  }$ are $N$-approximations of a sequence of measures $\eta_n$ defined by the FK recursive formulae: $$\eta_n(f) = \frac{\eta_{n-1} \left( G_n \times M_n.f \right)}{\eta_{n-1}(G_n)} ,$$ for all bounded measurable function $f$ on $E$ (a more detailed discussion on these evolution equations is provided in Section \[section-flot-FK\]).\
To describe with some precision the main results of the article, we consider the pair of parameters $(g_n,b_n)$ defined below. $$g_n := \underset{x,y\in E}{\sup} \frac{G_n(x)}{G_n(y)} \quad \quad \textmd{and} \quad \quad   b_n = \beta(M_n) := \underset{\underset{A \subset E}{x,y\in E}}{\sup} \left| M_n(x,A) - M_n(y,A) \right|$$ The quantity $\beta(M_n)$ is called the Dobrushin ergodic coefficient of the Markov transition $M_n$. One of our first main results can be basically stated as follows:

\[theo-statement-unif\] We assume that $$\underset{p \geq 1}{\sup} \; g_p \leq M \quad \quad \textmd{and} \quad \quad  \underset{p \geq 1}{\sup} \; b_p \leq \frac{a}{a+M}$$ for some finite constant $M < \infty$ and some $a \in (0,1)$. In this situation, for any $n \geq 0$, $N \geq 1$, $y \geq 0$ and $f \in \mathcal{B}_1 (E)$, the probability of the event $$\vert \eta_n^N(f) - \eta_n(f) \vert \leq \frac{r_1^{\star} N + r_2^{\star} y}{N^2}$$ is greater than $1-e^{-y}$, where $r_1^{\star}$ and $r_2^{\star}$ are some constants that are explicitly defined in terms of $(a,M)$.

In Section \[section-result-unif\], under the same assumptions of Theorem \[theo-statement-unif\], we also prove uniform $L^p$-mean error bounds as well as new concentration inequalities for unnormalized particle models. We also extend the analysis to the situation where $g_n \underset{n \rightarrow + \infty}{\longrightarrow} 1$.\
We already mention that the regularity conditions on $b_n$ may appear difficult to check since the Markov kernels are often dictated by the application under study. However, we can deal with this problem as soon as we can simulate a Markov kernel $K_n$ such that $\eta_n . K_n = \eta_n$. Indeed, to stabilize the system, the designer can “add” several MCMC evolution steps next to each $M_n$-mutation step. From a more formal viewpoint, the target sequence $(\eta_n)_n$ is clearly also solution of the FK measure-valued equations associated with the Markov kernels $M_n^{\prime} =  M_n. K_n^{m_n}$, where iteration numbers $m_n$ are to be chosen loosely. This system is more stable since the corresponding $b_n^{\prime}$ satisfy $$b_n^{\prime} = \beta(M_n^{\prime}) \leq b_n . \beta(K_n^{m_n}) \leq b_n . \beta(K_n)^{m_n} .$$ In such cases, Theorem \[theo-statement-unif\] and its extension provide sufficient conditions on the iteration numbers $m_n$ to ensure the convergence and the stability properties of the algorithm.\
These results apply to stochastic optimization problems. Let $V : E \rightarrow \mathbb{R}$ be a bounded potential function, $\beta_n$ a sequence which tends to infinity, and $m$ a reference measure on $E$. It is well known that the sequence of Boltzmann-Gibbs measures $$\eta_n (dx) \propto e^{- \beta_n . V(x)} m(dx)$$ concentrates on $V$’s global minima (in the sense of $m$-$\textmd{essinf}(V)$). In the above display, $\propto$ stands for the proportional sign. One central observation is that these measures can be interpreted as a FK flow of measures associated with potential functions $G_n = e^{-(\beta_n - \beta_{n-1}).V}$ and Markov kernels $M_n = K_{\beta_n}^{m_n k_0}$ where $K_{\beta_n}$ is a simulating annealing kernel (see Section \[section-Gibbs-tuning\]) and $m_n$ and $k_0$ are given iteration parameters. In the further development of this section, we let $K$ be the proposal transition of the simulated annealing transition $K_{\beta}$. In this context, the IPS methods can be used to minimize $V$. The conditions on $b_n$ and $g_n$ can be turned into conditions on the temperature schedule $\beta_n$ and the number of MCMC iterations $m_n$. Moreover, combining our results with standard concentration properties of Boltzmann-Gibbs measures, we derive some convergence results in terms of optimization performance. In this notation, our second main result is basically stated as follows.

\[theo-statement-optim\]

Let us fix $a \in (0,1)$. We assume that for any $x \in E$, $K^{k_0} (x, \cdot) \geq \delta \nu(\cdot)$ for some measure $\nu$ on $E$, some $\delta>0$ and some $k_0 \geq 1$. We also assume that the temperature schedule $\beta_p$ and the iteration numbers $m_p$ satisfy the following conditions: $$\underset{p \geq 1}{\sup} \;  \Delta_p  \leq \Delta  \quad \quad \textmd{and} \quad \quad  m_p \geq  \frac{\log(\frac{e^{\Delta.\textmd{osc}(V)}+a}{a})e^{osc(V).\beta_p}}{\delta}$$ for some constant $\Delta$. For all $\varepsilon >0$, let $p_n^N (\varepsilon)$ be the proportion of particles $(\zeta_n^i)$ so that $ V (\zeta_n^i) \geq V_{\min} + \varepsilon$. Then, for any $n \geq 0$, $N \geq 1$, $y \geq 0$ and for all $\varepsilon^{\prime} < \varepsilon$, the probability of the event $$p_n^N (\varepsilon) \leq \frac{e^{-\beta_n(\varepsilon - \varepsilon^{\prime}) }}{m_{\varepsilon^{\prime}}} +  \frac{r_1^{\star} N + r_2^{\star} y}{N^2}$$ is greater than $1-e^{-y}$, with $ m_{\varepsilon^{\prime}} = m \left( V \leq V_{\min} + \varepsilon ^{\prime} \right)$, and the same constants $(r_1^{\star},r_2^{\star})$ as the one stated in Theorem \[theo-statement-unif\] (with $M=e^{\Delta}$).

It is instructive to compare the estimates in the above theorem with the performance analysis of the traditional simulated annealing model ([*abbreviate SA*]{}). Firstly, most of the literature on SA models is concerned with the weak convergence of the law of the random states of the algorithm. When the initial temperature of the scheme is greater than some critical value, using a logarithmic cooling schedule, it is well known that the probability for the random state to be in the global extrema levels tends to $1$, as the time parameter tends to $\infty$. The cooling schedule presented in Theorem \[theo-statement-optim\] is again a logarithmic one. In contrast to the SA model, Theorem \[theo-statement-optim\] allows to quantify the performance analysis of the ISA model in terms of uniform concentration inequalities, that doesn’t depend on a critical parameter.\
\
In practice, choosing the sequence of increments $\Delta_n = (\beta_n - \beta_{n-1})$ in advance can cause computational problems. To solve this problem, adaptive strategies, where increment $\Delta_n$ depends on the current set of particles $\zeta_{n-1}$, are of common use in the engineering community (see for instance [@Jasra; @Schafer], [@Clapp; @Deutscher; @Minvielle]). In this context, we propose to study the case where the increment $\Delta_n^N$ is chosen so that

$$\eta_{n-1}^N (e^{-{\Delta}_{n}^N \cdot V}) = \varepsilon ,$$ where $\varepsilon >0$ is a given constant (see Section \[description-algo-adapt\] for a detailed description of the algorithm). Computationally speaking, $\varepsilon$ is the expectation of the proportion of particles which are not concerned with the recycling mechanism in the selection step. We interpret this particle process as a perturbation of a theoretical FK sequence $\eta_n$ associated with a theoretical temperature schedule $\beta_n$. Our main result is the following $L^p$-mean error estimate.

\[theo-statement-adapt\] For any $p \geq 1$, $n \geq 0$, $N \geq 1$ and any bounded by $1$ function $f$, we have $$\mathbb{E} \left( \left| \eta_n^N(f) - \eta_n(f)  \right|^p \right)^{1/p} \leq   \frac{B_p}{\sqrt{N}} \sum_{k=0}^n \prod_{i=k+1}^n  \left( b_i g_i (1+c_i) \right) ,$$ with $\displaystyle{   c_n = \frac{ V_{\max} e^{{\Delta}_n V_{\max}} }{\varepsilon \cdot \eta_{n-1}(V)} }$, $\Delta_n = \beta_n - \beta_{n-1}$ and $B_p$ defined below. $$\label{def-Bp}
B_{2p}^{2p} = \frac{(2p)!}{2^p . p!} \quad  ;  \quad B_{2p+1}^{2p+1} = \frac{(2p+1)!}{2^p . p! \sqrt{2p+1} } .$$

Under appropriate regularity conditions on the parameters $b_n, g_n, c_n$, we mention that these $L^p$-mean error bounds also provide uniform concentration inequalities.\
The proofs of Theorem \[theo-statement-unif\], Theorem \[theo-statement-optim\], Theorem \[theo-statement-adapt\] and related uniform exponential estimates are detailed, respectively, in Sections \[section-result-unif\], Section \[section-Gibbs-tuning\] and Section \[gros-result-adapt\].

Some Preliminaries {#sec:1}
==================

Basic Notation
--------------

Let $(E,r)$ be a complete, separable metric space and let $\mathcal{E}$ be the $\sigma$-algebra of Borel subsets of $E$. Denote by $\mathcal{P}(E)$ the space of probability measures on $E$. Let $\mathcal{B}(E)$ be the space of bounded, measurable, real-valued functions on $E$. Let $\mathcal{B}_1(E) \subset \mathcal{B}(E)$ be the subset of all bounded by $1$ functions.\
\
If $\mu \in \mathcal{P}(E)$, $f \in \mathcal{B}(E)$ and $K, K_1, K_2$ are Markov kernels on $E$, then $\mu (f)$ denotes the quantity $\int_E f(x)  \mu(dx)$, $K_1 . K_2$ denotes the Markov kernel defined by $$(K_1.K_2) (x,A) = \int_E K_1(x,dy) K_2(y,A),$$ $K.f$ denotes the function defined by $$K.f(x) = \int_E K(x,dy) f(y)~$$ and $\mu . K$ denotes the probability measure defined by $$\mu.K(A) = \int_E K(x,A) \mu(dx)  .$$ If $G$ is a positive, bounded function on $E$, then $\psi_G:  \mathcal{P}(E) \rightarrow \mathcal{P}(E) $ denotes the Boltzmann-Gibbs transformation associated with $G$, defined by $$\forall \mu \in \mathcal{P}(E), \; \forall f \in \mathcal{B}(E), \quad \psi_G(\mu) (f) = \frac{\mu(G \times f)}{\mu(G)}  .$$ For any $ f \in \mathcal{B}(E)$, let $\displaystyle{ \Vert f \Vert_{\infty} = \underset{x \in E}{\sup} \vert f(x) \vert }$ and $osc(f) = (f_{\max}-f_{\min})$. Let $\mathcal{O}_1 (E) \subset \mathcal{B}(E) $ be the subset of functions $f$ so that $osc(f) \leq 1$. For any random variable $X: \Omega \rightarrow \mathbb{R}$ defined on some probability space $(\Omega,\mathcal{F},\mathbb{P})$, and any $p \geq 1$, $\Vert X \Vert_{p}$ stands for the $L^p$ norm $\displaystyle{ \mathbb{E} \left( |X|^p \right)^{1/p} }$. Let $\mathcal{P}_{\Omega}(E)$ be the set of random probability measures on $E$. For all $p \geq 1$, we denote by $d_p$ the distance on $\mathcal{P}_{\Omega}(E)$ defined for all random measures $ \hat{\mu} , \hat{\nu}$ by $$d_p(\hat{\mu} , \hat{\nu}) = \underset{f\in \mathcal{O}_1 (E)  }{\sup} \Vert \hat{\mu}(f) - \hat{\nu}(f)  \Vert_p .$$ Finally, for any $x\in E$, $\delta_x$ stands for the Dirac measure centered on $x$.

Dobrushin Ergodic Coefficient {#section-Dob-var-tot}
-----------------------------

Let us recall here the definitions as well as some simple properties that will be useful in the following.

Let $\mu , \nu \in \mathcal{P}(E)$, the total variation distance between $\mu$ and $\nu$ is defined by

$$\left\| \mu- \nu  \right\|_{tv} = \sup \{ \left| \mu(A) - \nu(A) \right| ; A \in \mathcal{E} \} .$$

To each Markov kernel $K$ on $E$, is associated its Dobrushin ergodic coefficient $\beta(K) \in [0,1]$ defined by

$$\beta(K)= \sup \{ K(x,A) - K(y,A) ; x,y\in E, A\in \mathcal{E}    \}$$ or in an equivalent way: $$\beta(K)= \sup \{ \frac{\left\| \mu.K - \nu.K \right\|_{tv}}  {\left\| \mu - \nu \right\|_{tv}} ; \mu, \nu \in \mathcal{P}(E) , \mu \neq \nu \} .$$

The parameter $\beta(K)$ caracterizes mixing properties of the Markov kernel $K$. Note that function $\beta$ is an operator norm, in the sense that $\beta(K_1.K_2) \leq \beta(K_1).\beta(K_2)$, for any couple of Markov kernels $K_1$, $K_2$. By definition, for any measures $\mu, \nu \in \mathcal{P}(E)$ and any Markov kernel $K$, we have $\left\| \mu.K - \nu.K  \right\|_{tv}  \leq  \beta(K). \left\| \mu- \nu  \right\|_{tv}$. Otherwise, for any function $f \in \mathcal{B}(E)$,

$$\label{prop-Dob}
osc(K.f) \leq \beta(K)\cdot osc(f).$$

Further details on these ergodic coefficients can be found in the monograph[@DM-FK], such as the following lemma that we will need hereinafter.

\[BG-tv\] Let $\mu, \nu \in \mathcal{P}(E)$ and $G$ a positive, bounded function on $E$ satisfying $\underset{x,y\in E}{\sup} \frac{G(x)}{G(y)} \leq g $, for some finite constant $g\geq 0$. In this situation, we have

$$\left\| \Psi_G(\mu) - \Psi_G(\nu)  \right\|_{tv}  \leq g. \left\| \mu - \nu \right\|_{tv} .$$

Feynman-Kac Models
------------------

We recall here some standard tools related to FK models. They provide useful theoretical background and notation to formalize and analyze IPS methods (see e.g. [@DM-Guionnet-2; @DM-Hu-Wu; @DM-M] for further details).

### Evolution Equations {#section-flot-FK}

Consider a sequence of probability measures $(\eta_n)_n$, defined by an initial measure $\eta_0$ and recursive relations $$\label{defeta}
\forall f \in \mathcal{B}(E), \quad  \eta_n(f) = \frac{\eta_{n-1} \left( G_n \times M_n.f \right)}{\eta_{n-1}(G_n)}$$ for positive functions $G_n \in \mathcal{B}(E)$ and Markov kernels $M_n$ with $M_n(x,\cdot) \in \mathcal{P}(E)$ and $M_n(\cdot,A) \in \mathcal{B}_1(E)$. This is the sequence of measures we mainly wish to approximate with the IPS algorithm. In an equivalent way, $(\eta_n)_n$ can be defined by the relation $$\eta_n = \phi_n(\eta_{n-1})$$ where $\phi_n: \; \mathcal{P}(E) \rightarrow \mathcal{P}(E)$ is the FK transformation associated with potential function $G_n$ and Markov kernel $M_n$ and defined by $$\phi_n(\eta_{n-1})=\psi_{G_{n}}(\eta_{n-1}).M_n$$ with $$\psi_{G_{n}}(\eta_{n-1})(dx):=\frac{1}{\eta_{n-1}(G_{n})}~G_{n}(x)~\eta_{n-1}(dx) .$$ The next formula provides an interpretation of the Boltzmann-Gibbs transformation in terms of a nonlinear Markov transport equation $$\Psi_{G_{n}}(\eta_{n-1})(dy)=\left(\eta_{n-1} S_{n,\eta_{n-1}}\right)(dy):=\int\eta_{n-1}(dx) S_{n,\eta_{n-1}}(x,dy)$$ with the Markov transition $ S_{n,\eta_n}$ defined below $$S_{n,\eta_{n-1}}(x,dy)=\varepsilon_n.G_n(x)~\delta_x(dy)+\left(1-\varepsilon_n.G_n(x)\right)~\Psi_{G_{n}}(\eta_{n-1})(dy),$$ (for any constant $\varepsilon_n > 0$ so that $\varepsilon_n.G_n \leq 1$). This implies $$\label{rec-eta-noyau}
 \eta_{n}=\eta_{n-1} K_{n,\eta_{n-1}}\quad\mbox{\rm with}\quad K_{n,\eta_{n-1}}= S_{n,\eta_{n-1}}M_{n}$$ Therefore, $\eta_n$ can be interpreted as the distributions of the random states $\overline{X}_n$ of a Markov chain whose Markov transitions $$\label{eta-interp-Markov}
 \mathbb{P} \left(\overline{X}_{n+1}\in dy~|~\overline{X}_n=x\right):=K_{n+1,\eta_n}(x,dy)$$ depend on the current distribution $\eta_n=\mbox{\rm Law}\left(\overline{X}_n\right)$.\
We finally recall that the measures $\eta_n$ admit the following functional representations: $$\eta_n (f) = \frac{\gamma_n(f)}{\gamma_n(1)}$$ ($1$ stands for the unit function) with the unnormalized FK measures $\gamma_n$ defined by the formulae $$\label{defgamma}
\gamma_0 = \eta_0  \quad ;  \quad \gamma_n(f) = \gamma_{n-1} (G_n \times M_n.f) .$$ Comparing this definition with (\[defeta\]), it is clear that the normalizing constant $\gamma_n(1)$ satisfies $$\label{defgamma1}
\gamma_n(1) = \prod_{p=1}^n \eta_{p-1}(G_p)  .$$ The special interest given to this quantity will be motivated in section \[section-Gibbs-motiv\].

### Feynman-Kac Semigroup {#semigroupFK}

An important point is that the semigroup transformations $$\phi_{p,n}:=\phi_n\circ\phi_{n-1}\circ \cdots \circ \phi_{p+1}$$ admit a comparable structure as each of the $\phi_k$. To be more precise, for each integer $p$, let us define the unnormalized integral operator $Q_p$ $$\label{defQ}
\forall f \in \mathcal{B}(E) \; , \quad Q_p.f = G_p.M_p.f$$ and the composition operators $Q_{p,n}$ defined by the backward recursion $$\label{defQpn}
Q_{p,n} = Q_{p+1}. \left( Q_{p+2} \ldots Q_n \right) =Q_{p+1}.Q_{p+1,n} .$$ We use the convention $Q_{n,n} = Id$ for $p=n$. Comparing these definitions with (\[defgamma\]), it is clear that $\gamma_n = \gamma_{n-1} . Q_n$ and more generally $$\gamma_n = \gamma_p . Q_{p,n} .$$ for any $p\leq n$. The semigroup $\phi_{p,n}$ can be expressed in terms of $Q_{p,n}$ with the following formulae $$\phi_{p,n}(\mu)(f) = \frac{\mu(Q_{p,n}.f)}{\mu(Q_{p,n}.1)}$$ for any $f \in \mathcal{B} (E)$ and $\mu \in \mathcal{P} (E)$. Finally, if we set $$P_{p,n}.f = \frac{Q_{p,n}.f}{Q_{p,n}.1}  \quad  \textmd{and} \quad  G_{p,n} = Q_{p,n}.1$$ then we find that $$\phi_{p,n}(\mu)(f) = \frac{\mu(G_{p,n}.P_{p,n}.f)}{\mu(G_{p,n})} ,$$ or in other words: $  \phi_{p,n}(\mu) = \psi_{G_{p,n}}(\mu).P_{p,n}  $.

The Interacting Particle System Model {#algo-classique}
-------------------------------------

The central idea is to approximate the measures $\eta_n$ by simulating an interacting particle system $(\zeta_n)_n = \left( \zeta_n^1, \ldots, \zeta_n^N \right)_n$ of size $N$ so that $$\eta^N_{n}=\frac{1}{N}\sum_{1\leq i\leq N}\delta_{\zeta^i_n}\rightarrow_{N\uparrow\infty}\eta_n  .$$ Of course, the main issue is to make precise and to quantify this convergence. The particle model is defined as follows.\
We start with $N$ independent samples $\zeta_0 = (\zeta_0^1, \ldots , \zeta_0^N)$ from $\eta_0$. Then, the particle dynamics alternates two genetic type transitions.\
During the first step, every particle $\zeta^i_{n}$ evolves to a new particle $\widehat{\zeta}^i_{n}$ randomly chosen with the distribution $$S_{n+1,\eta^N_{n}}( \zeta^i_{n},dx)
 :=\varepsilon_{n+1}.G_{n+1}( \zeta^i_{n})~\delta_{ \zeta^i_{n}}(dx)+
 \left(1-\varepsilon_{n+1}.G_{n+1}( \zeta^i_{n})\right)~ \Psi_{G_{n+1}}(\eta^N_n)(dx)$$ with the updated measures $$\Psi_{G_{n+1}}(\eta^N_n)=\sum_{j=1}^N\frac{G_{n+1}( \zeta^j_{n})}{\sum_{k=1}^N G_{n+1}( \zeta^k_{n})}
 \delta_{ \zeta^j_{n}} .$$ This transition can be interpreted as an acceptance-rejection scheme with a recycling mechanism. In the second step, the selected particles $\widehat{\zeta}^i_{n}$ evolve randomly according to the Markov transitions $M_{n+1}$. In other words, for any $1\leq i\leq N$, we sample a random state $ \zeta^i_{n+1}$ with distribution $M_{n+1}\left(\widehat{\zeta}^i_{n},dx\right)$.\
In view of (\[eta-interp-Markov\]), if we replace $\eta_n^N$ by $\eta_n$, then $\zeta_n$ coincide with $N$ independent copies of the Markov chains $\overline{X}_n$ defined in (\[rec-eta-noyau\]). On the other hand, by the law of large numbers, we have $\eta_0^N \simeq \eta_0$ so that $$\eta_1^N \simeq \eta_0^N . K_{1,\eta_0^N} \simeq \eta_0 . K_{1,\eta_0} = \eta_1 .$$ Iterating this approximation procedure, the empirical measure $\eta^N_{n}$ is expected to approximate $\eta_n$ at any time $n \geq 0$. As for the unnormalized measures $\gamma_n$, we define $$\gamma_n^N (1) = \prod_{p=1}^n \eta_{p-1}^N (G_p)$$ (mimicking formula (\[defgamma1\])) and more generally $\displaystyle{ \gamma_n^N (f) = \eta_n^N(f) \times \prod_{p=1}^n \eta_{p-1}^N (G_p)  }$. Let us mention (see for instance [@DM-filt]) that these particle models provide an unbiased estimate of the unnormalized measures; that is we have that $$\forall f \in \mathcal{B}(E), \quad \mathbb{E} \left( \gamma_n^N (f) \right) = \gamma_n(f) .$$ In addition to the analysis of $\eta_n^N$’s convergence, the concentration properties of the unbiased estimators $\gamma_n^N(1)$ around their limiting values $\gamma_n(1)$ will also be considered thereafter.

Some Non-Asymptotic Results {#section-Dob-estim}
---------------------------

To quantify the FK semigroup stability properties, it is convenient to introduce the following parameters.

For any integers $p<n$, we set

$$b_n := \beta(M_n) \quad \textmd{and}  \quad b_{p,n} := \beta(P_{p,n}).$$ $$g_n := \sup_{x,y \in E}\frac{G_n(x)}{G_n(y)}   \quad \textmd{and}  \quad  g_{p,n} := \sup_{x,y \in E}\frac{G_{p,n}(x)}{G_{p,n}(y)}.$$

The quantities $g_{p,n}$, and respectively $b_{p,n}$, reflect the oscillations of the potential functions $G_{p,n}$, and respectively the mixing properties of the Markov transition $P_{p,n}$ associated with the FK semigroup $\phi_{p,n}$ described in (\[semigroupFK\]). Several contraction inequalities of $\phi_{p,n}$ w.r.t. the total variation norm or different types of relative entropies can be derived in terms of these two quantities (see for instance[@DM-FK]).\
The performance analysis developed in Sections \[estim-generales\] and \[section-Gibbs-tuning\] is partly based on the three non asymptotic inequalities presented below.\
Firstly, the following $L^p$-mean error bound for all $f \in \mathcal{B}_1 (E)$ is proven in [@DM-M]:

$$\mathbb{E} \left( \left| \eta_n^N (f) - \eta_n (f) \right|^p \right)^{1/p} \leq  \; \; \; \frac{B_p}{\sqrt{N}} \sum_{k=0}^{n} g_{k,n}b_{k,n}  \label{born-Lp-DMM}$$

where $B_p$ are the constants introduced in (\[def-Bp\]).\
Secondly, the following exponential concentration inequality is derived in [@DM-Rio]. For all $f \in \mathcal{B}_1(E)$ and any $\varepsilon > 0$ we have: $$\frac{-1}{N} \log \mathbb{P} \left(  \vert \eta_n^N(f) - \eta_n(f) \vert  \geq  \frac{r_n}{N} + \varepsilon  \right)   \geq   \frac{\varepsilon^2}{2}  \left[  b_n^{\star} \overline{\beta}_n + \frac{\sqrt{2}r_n}{\sqrt{N}} + \varepsilon \left( 2r_n + \frac{b_n^{\star}}{3} \right)  \right]^{-1}         \label{ineg-conc}$$

where $r_n$, $\overline{\beta}_n$ and $b_n^{\star}$ are constants so that:

$$\left\{
    \begin{array}{llll}
         r_n& \leq & 4 \sum_{p=0}^{n}  g_{p,n}^3 b_{p,n}  \\
         & &\\
         {\overline{\beta_n}}^2 &  \leq & 4 \sum_{p=0}^{n}  g_{p,n}^2 b_{p,n}^2 \\
         & &\\
         b_n^{\star} &  \leq  & \displaystyle{ 2 \sup_{0 \leq p \leq n}  g_{p,n} b_{p,n}} 
         
           
    \end{array} 
\right.$$

Thirdly, the following concentration inequality for unnormalized particle models $\gamma_n^N$ is provided in [@DM-Hu-Wu] (see theorem $6.5$). Let

$$\label{def-fonctions-h}
\begin{array}{cll}
&  h_0 := x \mapsto 2(x+\sqrt{x})   &  \quad \textmd{and}  \\
&  \displaystyle{ h_1 := x \mapsto \frac{x}{3} + \sqrt{2x}  }. &
\end{array}$$

Then, $\forall \epsilon \in \{ +1,-1 \}$ and $\forall y \geq 0$:

$$\label{ineg-conc-nor}
\mathbb{P} \left( \frac{\epsilon}{n} \log \left( \frac{\gamma_n^N (1)}{\gamma_n(1)} \right)  \geq  \frac{\bar{r} (n) }{N} h_0 (y) + \tau_n^{\star} \bar{\sigma}_n^2 h_1 \left( \frac{y}{N.\bar{\sigma}_n^2} \right) \right)  \leq e^{-y}$$

where quantities $\tau_n^{\star}$, $\bar{\sigma}_n^2$ and $\bar{r} (n)$ can be estimated this way:

-   $\displaystyle{ \tau_n^{\star}  = \underset{0 \leq q \leq n}{\sup} \tau_{q,n} }$, where $\tau_{q,n}$ satisfy

    $$\label{estim-tau}
    \tau_{q,n} \leq  \frac{4}{n} \sum_{p=q}^{n-1} g_{q,p} . g_{p+1} . b_{q,p} \; ;$$

-   $ \displaystyle{  \bar{\sigma}_n^2 = \sum_{q=0}^{n-1} \sigma_q^2 \left( \frac{\tau_{q,p} }{\tau_n^{\star} }  \right)^2  }$ where $\sigma_q$ satisfy $\sigma_q \leq 1$;

-   $\bar{r} (n)$ satisfy

    $$\label{estim-r}
    \bar{r} (n) \leq \frac{8}{n} \sum_{0 \leq q \leq p <n} g_{p+1} . g_{q,p}^3  .b_{q,p} .$$

Non-Asymptotic Theorems {#section-analyse-generale-FK}
=======================

The formulae (\[born-Lp-DMM\]), (\[ineg-conc\]) and (\[ineg-conc-nor\]) provide explicit non asymptotic estimates in terms of the quantities $g_{p,n}$ and $b_{p,n}$. Written this way, they hardly apply to any IPS parameters tuning decision, since the only known or calculable objects are generally the reference Markov chain $M_p$ and the elementary potential functions $G_p$. We thus have to estimate $g_{p,n}$ and $b_{p,n}$ with some precision in terms of the $g_p$ and $b_p$. This task is performed in Section \[estim-generales\]. In the second section, Section \[section-result-unif\], we combine these estimates with the concentration results presented in Section \[section-Dob-estim\] to derive some useful uniform estimates w.r.t. the time parameter.

Semigroup Estimates {#estim-generales}
-------------------

We start with a series of technical lemmas.

\[lemmette1\] Let $K$ be a Markov kernel and $G$ a positive function on $E$ satisfying $\displaystyle{  \underset{x,y \in E}{\sup} \frac{G(x)}{G(y)} \leq g  }$, for some finite constant $g$. In this situation, we have that

$$\underset{x,y \in E}{\sup} \; \frac{K.G(x)}{K.G(y)} \leq 1 + \beta(K)(g-1) .$$

Let $x,y \in E$ be s.t. $K.G(x) \geq K.G(y)$. Let us write:

$$\frac{K.G(x)}{K.G(y)} \; \; =  \; \; \frac{K.G(x) - K.G(y)}{K.G(y)} +1  \; \; \leq  \; \; \frac{\beta(K) (G_{max} - G_{min})}{G_{min}}  +1$$

We check the last inequality using the fact that $$K.G(x) - K.G(y) \leq  osc(K.G)  \leq \beta(K). osc (G) = \beta(K).(G_{max}-G_{min}) .$$ On the other hand we have $ K.G(y) = \int_{u}G(u)K(y,du) \geq G_{min} $. The desired result is now obtained taking the supremum over all $(x,y) \in E^2$. Note that $\frac{\beta(K) (G_{max} - G_{min})}{G_{min}}  +1$ is exactly equal to $ 1+\beta(K) (g-1)$.\
This ends the proof of the lemma.

\[lemmette2\] Let $M$ be a Markov kernel, $Q$ a not necessarily normalized integral operator satisfying $ \displaystyle{ \underset{x,y \in E}{\sup} \frac{Q.1(x)}{Q.1(y)} \leq g  }$, for some finite constant $g \geq 1$ and $f$ a bounded, non negative function. In this situation, the Markov kernel $P$ defined by

$$P.f(x) := \frac{M.Q.f(x)}{M.Q.1(x)}$$

satisfies the following property

$$\beta(P) \leq g.\beta(M).\beta(P^{\prime}) .$$

In the above display formula, $P^{\prime}$ is the Markov transition defined by $ \displaystyle{ P^{\prime}.f(x) := \frac{Q.f(x)}{Q.1(x)}  }$.

Note that $P.f(x)$ can be written in this way $P.f(x)  =  \Psi_{Q.1}(\delta_x.M) \left(  P^{\prime}.f   \right)$. Thus, for any $ x,y \in E$, we have that

$$\begin{aligned}
\left|  P.f(x) - P.f(y)  \right|  & =  &  \left| \left(  \Psi_{Q.1}(\delta_x.M)  -  \Psi_{Q.1}(\delta_y.M) \right) \left(  P^{\prime}.f   \right)   \right|      \\
   &  \leq  &  \left\| \left(  \Psi_{Q.1}(\delta_x.M)  -  \Psi_{Q.1}(\delta_y.M) \right)  \right\|_{tv}.osc \left(  P^{\prime}.f   \right) .\end{aligned}$$

By Lemma \[BG-tv\], this implies that $$\left\| \left(  \Psi_{Q.1}(\delta_x.M)  -  \Psi_{Q.1}(\delta_y.M) \right)  \right\|_{tv}  \; \leq \;   g.  \left\| \delta_x.M  - \delta_y.M  \right\|_{tv} \; \leq \;  g.\beta(M) .$$

Using (\[prop-Dob\]), we have $osc \left(  P^{\prime}.f   \right)  \leq  \beta(P^{\prime}).osc(f)$.\
This ends the proof of the lemma.

\[estim-g-b\] For any integers $p \leq n$, we have: $$\begin{aligned}
 g_{p,n}-1  & \leq \sum_{k=p+1}^n (g_k -1) b_{p+1} \ldots b_{k-1} \label{estim-g}  \\
   b_{p,n} & \leq \prod_{k=p+1}^n b_k . g_{k,n}   \label{estim-b}\end{aligned}$$

Let us prove (\[estim-g\]). By definition, we have $G_{p,n} = Q_{p,n}.1$. Combining (\[defQ\]) and (\[defQpn\]) applied to unit function we have $$Q_{p-1,n}(1) \; = \; Q_{p+1}. \left[ \left( Q_{p+1} \ldots Q_n \right).1  \right] \; =  \; G_p \times M_p. \left( Q_{p,n}.1 \right) .$$ This implies that the functions $G_{p,n}$ satisfy the following “backward” relations: $$G_{n,n}=1  \quad ; \quad G_{p-1,n}=G_p \times M_p.G_{p,n}$$ Then, for any $x,y\in E$, we deduce that

$$\frac{G_{p-1,n}(x)}{G_{p-1,n}(y)}  =      \underbrace{\frac{G_p(x)}{G_p(y)}}_{E_1} \times \underbrace{  \frac{ \left(  M_{p}.G_{p,n} \right)(x) }{\left(  M_{p}.G_{p,n} \right)(y)}   }_{E_2} .$$

Notice that $E_1 \leq g_p$ (by definition), and by Lemma \[lemmette1\], we have $E_2 \leq 1 + \beta(M_{p}).(g_{p,n}-1)$. This shows the following backward inequalities:

$$\label{estim-rec-g}
g_{n,n}=1 \quad ; \quad  g_{p-1,n} \leq g_p \left( 1+ b_p(g_{p,n}-1) \right)$$

We end the proof of (\[estim-g\]) by induction.\
To prove (\[estim-b\]), we use the formulae $$P_{p-1,n}.f \; = \; \frac{Q_{p-1,n}.f}{Q_{p-1,n}.1}  \; = \; \frac{G_p \times M_p.Q_{p,n}.f}{G_p \times M_p.Q_{p,n}.1} \;  =  \;   \frac{ M_p.Q_{p,n}.f}{M_p.Q_{p,n}.1} .$$ Recalling that $\displaystyle{ P_{p,n}.f = \frac{Q_{p,n}.f}{Q_{p,n}.1}  } $, we apply Lemma \[lemmette2\] to check that $\beta(P_{p-1,n}) \leq \beta(M_p).g_{p,n}.\beta(P_{p,n})  $, from which we conclude that

$$b_{p-1,n}  \leq  b_p.g_{p,n}.b_{p,n} .$$

We end the proof of (\[estim-b\]) by induction.\
This ends the proof of the lemma.

We end this section with a useful technical lemma to control the quantity $g_{p,n} b_{p,n}$.

\[lemme-gpn-bpn\] For any $p \leq n$, we have

$$g_{p,n} b_{p,n} \leq \prod_{k=p+1}^n  ( b_k.g_{k-1,n} ) .$$

Using Lemma \[estim-g-b\], we have $$\begin{array}{ccl}
g_{p,n} b_{p,n} &  \; \; \leq   \; \; & \displaystyle{  g_{p,n} . \prod_{k=p+1}^n b_k g_{k,n} } \\
 &  \; \; =  \; \; & g_{p,n} . (b_{p+1}g_{p+1,n}) . (b_{p+2} g_{p+2,n}) \ldots (b_{n-1} g_{n-1,n}) . (b_n  \underbrace{g_{n,n}}_{=1} ) \\
 &  \; \; =  \; \; & (g_{p,n} b_{p+1}) . (g_{p+1,n}   b_{p+2}) \ldots (g_{n-1,n}   b_n) \; \; = \; \; \displaystyle{  \prod_{k=p+1}^n b_k g_{k-1,n}  } .
\end{array}$$ This ends the proof of the lemma.

The term $g_{p,n} b_{p,n}$ is central in the $L^p$-mean error bound (\[born-Lp-DMM\]). By Lemma \[lemme-gpn-bpn\] we have $$\displaystyle{\sum_{p=0}^{n} \prod_{k=p+1}^{n} b_k g_{k-1,n} < +\infty}\Longrightarrow\sum_{p=0}^{n} g_{p,n} b_{p,n} < +\infty  .$$ This gives a sufficient condition for a uniform $L^p$ bound w.r.t. time $n$. $g_{p,n} b_{p,n}$ is also involved in the estimates of all the quantities defined in section \[section-Dob-estim\] such as $r_n$, ${\overline{\beta_n}}^2$, and others. In addition, by Lemma \[BG-tv\], we have the stability property

$$\Vert \phi_{p,n} (\mu)  -  \phi_{p,n} (\nu) \Vert_{tv} \leq  g_{p,n} b_{p,n} \Vert \mu - \nu \Vert_{tv} .$$

This shows that the term $g_{p,n} b_{p,n}$ is central to quantify the stability properties of the semigroup $\phi_{p,n}$.

Uniform Concentration Theorems {#section-result-unif}
------------------------------

To obtain uniform bounds w.r.t. the time horizon, Lemma \[lemme-gpn-bpn\] naturally leads to a sufficient condition of the following type:

$$\underset{k \leq n}{\sup} \; b_k . g_{k-1,n} \leq a\quad \mbox{\rm for some} \quad a \in (0,1)$$

In this situation, we prove that $\displaystyle{ g_{p,n} b_{p,n} \leq a^{n-p}  }$, and therefore, using (\[born-Lp-DMM\]), $$\underset{f \in \mathcal{B}_1 (E)}{\sup} \; \mathbb{E} \left( \left| \eta_n^N (f) - \eta_n (f) \right|^p \right)^{1/p} \leq \frac{B_p}{\sqrt{N}}~\frac{1}{1-a} ,$$ with the constants $B_p$ introduced in (\[def-Bp\]). We then fix the parameter $a \in (0,1)$ and we look for conditions on the $b_p$ so that $b_k g_{k-1,n} \leq a$. This parameter $a$ can be interpreted as a performance degree of the $N$-approximation model. In order to explicit relevant and applicable conditions, we study two typical classes of regularity conditions on the potential functions $G_p$. The first one relates to bounded coefficients $g_p$ (Theorem \[reg born\]). In the second one, the parameters $g_p$ tend to $1$ as $p \rightarrow \infty$ (Theorem \[reg dec\]).\
The concentration inequalities developed in Theorem \[reg born\] will be described in terms of the parameters $(r_1^{\star },r_2^{\star })$ defined below. $$\label{def-r-star-12}
 \left\{
    \begin{array}{lll}
         r_1^{\star }&=& \frac{9}{2} \frac{(M+a)^2}{1-a} + \sqrt{\frac{8}{\sqrt{1-a^2}} + \frac{18(M+a)^2}{\sqrt{N}} } \\
         & &\\
         r_2^{\star} &=&  18 \frac{(M+a)^2}{1-a} + \sqrt{\frac{8}{\sqrt{1-a^2}} + \frac{18 (M+a)^2}{\sqrt{N}}} 
    \end{array} 
\right.$$

\[reg born\] We assume that $$\label{condition-born}
\underset{p \geq 1}{\sup} \; g_p \leq M  \quad \quad \textmd{and} \quad \quad  \underset{p \geq 1}{\sup} \; b_p \leq \frac{a}{a+M}$$

for some finite $M \geq 1$. In this situation we have the following uniform estimates.

-   The $L^p$-error bound:

    $$\label{reg-born-Lp}
    \underset{n \geq 0}{\sup} \; \;  d_p \left( \eta_n^N , \eta_n \right)  \leq  \frac{B_p}{2 (1-a) \sqrt{N} } \;$$

-   For any $n\geq 0$, $N \geq 1$, $y \geq 0$ and $f \in \mathcal{B}_1 (E)$, the probability of the event

    $$\label{reg-born-eta}
     \vert \eta_n^N(f) - \eta_n(f) \vert \leq \frac{r_1^{\star} N + r_2^{\star} y}{N^2}$$

    is greater than $1-e^{-y}$, with the parameters $(r_1^{\star },r_2^{\star })$ defined in (\[def-r-star-12\]).

-   For any $n\geq 0$, $N \geq 1$, $\epsilon \in \{ +1 , -1 \}$, $y \geq 0$ and $f \in \mathcal{B}_1 (E)$, the probability of the event

    $$\label{reg-born-gamma}
     \frac{\epsilon}{n} \log \left( \frac{\gamma_n^N (1)}{\gamma_n(1)} \right) \leq  \frac{\tilde{r}_1}{N} h_0(y) + \tilde{r}_2.h_1 \left( \frac{y}{n.N} \right)$$

    is greater than $1-e^{-y}$, with the parameters $ \tilde{r}_1 = \frac{8 M (M+a)^2}{1-a}   $ and $  \tilde{r}_2 = \frac{4M}{1-a}  $.

Firstly, we prove the inequalities

$$\label{estim-gpn-prod-born}
\left\{
    \begin{array}{llll}
         g_{p,n}&\leq &M+a   \\
         b_p . g_{p-1,n}&\leq&a
           
    \end{array} 
\right.$$

Let us assume that $b_p \leq \frac{1}{A}$ for some $A > 1$. Then, by Lemma \[estim-g-b\], $$(g_{p,n}-1) \leq \sum_{k=p+1}^{n} \frac{M-1}{A^{k-(p+1)}}  = (M-1) \frac{1-(\frac{1}{A})^{n-p}}{1-\frac{1}{A}} \leq \frac{A}{A-1} (M-1) .$$ On the one hand, this estimation implies that $g_{p,n}\leq M+a$ as soon as $\displaystyle{ A \geq \frac{M+a-1}{a} =: A_1  }$. On the other hand, we can write

$$b_p . g_{p-1,n} \leq \frac{1}{A} (g_{p-1,n} -1)  + \frac{1}{A} = \frac{M-1}{A-1} + \frac{1}{A},$$

from which we check that $b_p . g_{p-1,n}\leq a$ as soon as $ A \geq \frac{M+a+\sqrt{(M+a)^2 - 4a}}{2a} =:A_2  $. The inequalities (\[estim-gpn-prod-born\]) are then proven using the fact that $A_1$ and $A_2$ are both lower than $\frac{M+a}{a}$.

-   By Lemma \[lemme-gpn-bpn\] and (\[estim-gpn-prod-born\]) we have $g_{p,n}b_{p,n} \leq a^{n-p}$. Combining this with (\[born-Lp-DMM\]), the $L^p$-error bound (\[reg-born-Lp\]) is clear.

-   Let us prove (\[reg-born-eta\]), which is a consequence of the concentration inequality (\[ineg-conc\]). Combining the estimations of $r_n$, ${\overline{\beta_n}}^2$ and $b_n^{\star}$ given in section \[section-Dob-estim\] with (\[estim-gpn-prod-born\]) and $g_{p,n}b_{p,n} \leq a^{n-p}$, we deduce that

    $$r_n \leq \frac{4(M+a)^2}{1-a} \, , \quad {\overline{\beta_n}}^2  \leq \frac{4}{1-a^2} \quad \textmd{and} \quad  b_n^{\star} \leq 2.$$

    These estimations applied in (\[ineg-conc\]) lead to

    $$- \log \; \mathbb{P} \left( \vert \eta_n^N(f) - \eta_n(f) \vert \geq \frac{r_1}{4N} + \varepsilon \right) \geq \frac{N \varepsilon^2}{r_2 + r_1(\frac{1}{\sqrt{N}} + \varepsilon)}$$

    with $r_1 = \frac{18(M+a)}{1-a}$ and $r_2 =  \frac{8}{\sqrt{1-a^2}}$. We set $y = \frac{N \varepsilon^2}{r_2 + r_1(\frac{1}{\sqrt{N}} + \varepsilon)} > 0$. Given some $y >0$, we have

    $$\varepsilon(y) =  \frac{ r_1 y + \sqrt{r_1^2 y^2 + 4N(r_2 + \frac{r_1}{\sqrt{N}} )y    }          }{2N^2}  \; \Longrightarrow \;   y = \frac{N {\varepsilon(y)}^2}{r_2 + r_1(\frac{1}{\sqrt{N}} + \varepsilon(y))}$$

    and then it is clear that

    $$\mathbb{P} \left( \vert \eta_n^N(f) - \eta_n(f) \vert \geq \frac{r_1}{4N} + \varepsilon(y) \right) \leq e^{-y}.$$

    After some various but elementary calculations we prove that

    $$\frac{r_1}{4N} + \varepsilon(y) \leq \frac{r_1^{\star} N + r_2^{\star} y}{N^2} .$$

-   The last concentration inequality (\[reg-born-gamma\]) is a consequence of (\[ineg-conc\]) and (\[estim-gpn-prod-born\]). Indeed, from estimations (\[estim-tau\]) and (\[estim-r\]), we can easily show that the quantities $\tau_n^{\star}$ and $\bar{r}(n)$ satisfy $$\tau_n^{\star}  \leq  \frac{4M}{n(1-a)}  \quad \textmd{and}  \quad \bar{r}(n) \leq  \frac{8.M(M+a)^2}{1-a} .$$

    On the other hand, $\bar{\sigma}_n^2$ is trivially bounded by $n$. Then we find that

    $$\frac{\bar{r} (n) }{N}  h_0 (y) + \tau_n^{\star} \bar{\sigma}_n^2 h_1 \left( \frac{y}{N.\bar{\sigma}_n^2} \right)  =   \frac{\bar{r} (n) }{N} h_0 (y) + \frac{y \tau_n^{\star}}{3N}  +  \sqrt{ \frac{2y(\tau_n^{\star} \bar{\sigma}_n^2)}{N}  } \; .$$

    Finally, (\[reg-born-gamma\]) is obtained by making the suitable substitutions.

This ends the proof of the theorem.

Let us now consider the case where $g_p$ decreases to $1$ as $p \rightarrow \infty$. The idea of the forthcoming analysis is to find a condition on the $b_p$ so that the $g_{p,n}$ are uniformly bounded w.r.t. $n$ by $g_{p+1}^{1+\alpha}$ with

$$\alpha = \frac{a}{1-a} > 0    \quad \left(  \Longleftrightarrow   a = \frac{\alpha}{1 + \alpha} \right) .$$

The concentration inequalities developed in Theorem \[reg dec\] will be described in terms of the parameters $r_3^{\star}(n),r_4^{\star}(n)$ and $\tilde{r}_3(n),\tilde{r}_4,\tilde{r}_5(n)$ defined below. $$\label{def-r-star-34}
\left\{
    \begin{array}{lll}
         r_3^{\star } (n) &=& \frac{9. u_1(n)}{2(1-a)} + \sqrt{\frac{8}{\sqrt{1-a^2}} + \frac{18 . u_1(n)}{\sqrt{N}} } \\
         & &  \\
         r_4^{\star} (n) &=& \frac{18 . u_1(n)}{1-a} + \sqrt{\frac{8}{\sqrt{1-a^2}} + \frac{18 . u_1(n)}{\sqrt{N}} } 
    \end{array} 
\right.$$

$$\label{def-r-tilde-345}
 \left\{
    \begin{array}{cllll}
         \tilde{r}_3(n)&=&  \frac{16.u_2(n)}{1-a}  & & \\
         &&&&\\
         \tilde{r}_4 &=&  \frac{4}{3} \; \sum_{n \geq 0} g_{n+1}.a^n & \leq  & \frac{4.g_1}{3(1-a)}  \\
         & &\\
         \tilde{r}_5(n) &=&  \frac{4\sqrt{2}. u_3(n) }{1-a}  &  &
         
         
    \end{array} 
\right.$$

The sequences $u_1(n)$, $u_2(n)$ and $u_3(n)$ used in the above formulae are defined by $$\begin{cases}
 u_1(n) \; = \; (1-a) \; \sum_{p \geq 0} g_{n-p+1}^{2(1+\alpha)} a^p \; \; \underset{n \rightarrow \infty}{\longrightarrow} 1  \\
 u_2(n) \; = \; \frac{1}{n} \; \sum_{p=1}^n g_p^{3+2\alpha}  \; \; \underset{n \rightarrow \infty}{\longrightarrow} 1  \\
 u_3(n) \; = \; \left(  \frac{1}{n} \; \sum_{p=0}^{n-1} g_{p+1}^2  \right)^{1/2}  \; \; \underset{n \rightarrow \infty}{\longrightarrow} 1   .
\end{cases}$$ Notice that the sequence $u_1(n)$ tends to $1$ by dominated convergence. Sequences $u_2(n)$ and $u_3(n)$ tend to $1$ by Cesaro’s theorem.

\[reg dec\]

We assume that $g_p \downarrow 1$ as $p \rightarrow \infty$ and the sequence $b_p$ satisfies for any $p \geq 1$

$$\label{cond-bp-gpun}
         b_p \leq    \displaystyle{\frac{g_p^{\alpha} -1} {g_p^{\alpha+1} -1}}  \left( \underset{p \rightarrow +\infty}{\longrightarrow} a \right)  \quad\mbox{\rm and}\quad
         b_p \leq    \displaystyle{\frac{a} {g_p^{\alpha+1}}}  \left( \underset{p \rightarrow +\infty}{\longrightarrow} a \right) .$$

In this situation, we have the following uniform estimates.

-   The $L^p$-error bound

    $$\label{reg-dec-Lp}
    \underset{n \geq 0}{\sup} \; \;  d_p \left( \eta_n^N , \eta_n \right)  \leq  \frac{B_p}{2 (1-a) \sqrt{N} } \;$$

    with the constants $B_p$ introduced in (\[def-Bp\]).

-   For any $n\geq 0$, $N \geq 1$, $y \geq 0$ and $f \in \mathcal{B}_1 (E)$, the probability of the event

    $$\label{reg-dec-eta}
     \vert \eta_n^N(f) - \eta_n(f) \vert \; \; \leq  \; \;  \frac{r_3^{\star}(n). N + r_4^{\star}(n). y}{N^2}$$

    is greater than $1-e^{-y}$, with the parameters $r_3^{\star } (n),r_4^{\star} (n)$ defined in (\[def-r-star-34\]).

-   For any $n\geq 0$, $N \geq 1$, $\epsilon \in \{ +1 , -1 \}$, $y \geq 0$ and $f \in \mathcal{B}_1 (E)$, the probability of the event

    $$\label{reg-dec-gamma}
     \frac{\epsilon}{n} \log \left( \frac{\gamma_n^N (1)}{\gamma_n(1)} \right) \; \; \leq  \; \;  \tilde{r}_3(n) \left( \frac{y + \sqrt{y} }{N} \right) + \tilde{r}_4 \left( \frac{y}{n.N} \right) + \tilde{r}_5(n) \sqrt{ \frac{y}{n.N} }$$

    is greater than $1-e^{-y}$, with the parameters $\tilde{r}_3(n),\tilde{r}_4,\tilde{r}_5(n)$ defined in (\[def-r-tilde-345\]).

Firsly, we prove that $$\label{estim-gpn-prod-dec}
 \textmd{(\ref{cond-bp-gpun})} \quad \Longrightarrow \quad \forall p \leq n, \; \left\{
    \begin{array}{llll}
         g_{p,n}& \leq &(g_{p+1})^{1 + \alpha} \\
         g_{p-1,n} . b_p & \leq & a
           
    \end{array} 
\right.$$

The proof of the first inequality comes from a simple backward induction on $p$ (with fixed $n$), using formula $g_{p-1,n} \leq g_p \left( 1+ b_p(g_{p,n}-1) \right)$ (see (\[estim-rec-g\])). For $p=n$, $g_{p,n}$ is clearly smaller than $g_{p+1}^{1+\alpha}$ because $g_{n,n} = 1$. The second assertion is now immediate.

Now we assume that $g_{p,n} \leq g_{p+1}^{1+\alpha}$. In this case, $g_{p-1,n} \leq g_{p}^{1+\alpha}$ is met as soon as

$$b_p \leq \frac{g_p^{\alpha} -1} {g_{p+1}^{\alpha+1} -1}.$$

Notice that this estimate is met as soon as $b_p \leq \frac{g_p^{\alpha} -1}{g_{p}^{\alpha+1} -1}$, the sequence $(g_p)_p$ being decreasing.

-   Now that we proved (\[estim-gpn-prod-dec\]) (which implies $g_{p,n}b_{p,n} \leq a^{n-p}$ by Lemma \[lemme-gpn-bpn\]), the $L^p$-mean error bound (\[reg-born-Lp\]) comes from a simple substitution in (\[born-Lp-DMM\]).

-   To prove (\[reg-dec-eta\]), we focus on the quantities ${\overline{\beta_n}}^2$, $b_n^{\star}$ and $r_n$ arising in the concentration inequality (\[ineg-conc\]). With (\[estim-gpn-prod-dec\]) and $g_{p,n}b_{p,n} \leq a^{n-p}$, we readily verify that

    $${\overline{\beta_n}}^2 \leq \frac{4}{1-a^2}  \quad  \textmd{and}  \quad  b_n^{\star} \leq 2 .$$

    The term $r_n$ can be roughly bounded by $\frac{4}{1-a} g_1^{2(1+\alpha)}$, but another manipulation provides a more precise estimate. Indeed, using the fact that $b_{p,n} . g_{p,n} \leq a^{n-p}$ and $g_{p,n} \leq g_{p+1}^{1+ \alpha}$, we prove that

    $$\begin{array}{ccccccc}
    r_n  & \; \; \leq \; \; & \displaystyle{4 \sum_{p=0}^{n} g_{p,n}^2 a^{n-p}  }
    & \; \; \leq  \; \; & \displaystyle{ 4 \sum_{p=0}^{n} g_{p+1}^{2(1+ \alpha)} a^{n-p}  }
    &\; \; \leq \; \; & \displaystyle{  4 \sum_{p=0}^{n} g_{n-p+1}^{2(1+ \alpha)} a^{p} }\\
     &&&&& \; \; \leq \; \; & \displaystyle{ 4 \sum_{p \geq0} g_{n-p+1}^{2(1+ \alpha)} a^{p}  }  \\
      &&&&& \; \; \leq \; \; & \displaystyle{ \frac{4.u_1(n)}{1-a}  }.
    \end{array}$$

    We prove (\[reg-dec-eta\]) using the same line of arguments as in the proof of Theorem \[reg born\].

-   Let us prove the last concentration inequality (\[reg-dec-gamma\]). It is mainly a consequence of the inequality (\[ineg-conc-nor\]). Starting from the following decomposition

    $$\label{osef}
    \frac{\bar{r} (n) }{N} h_0 (y) + \tau_n^{\star} \bar{\sigma}_n^2 h_1 \left( \frac{y}{N.\bar{\sigma}_n^2} \right)  =   \frac{2 \bar{r} (n) }{N} \left( y + \sqrt{y} \right) + \frac{y \tau_n^{\star}}{3N}  +  \sqrt{ \frac{2y(\tau_n^{\star} \bar{\sigma}_n^2)}{N}  } \; ,$$

    we need to find some refined estimates of the quantities $\tau_n^{\star}$, $\bar{r}_n$ and $(\tau_n^{\star} . \bar{\sigma}_n^2)$. To estimate $\tau_n^{\star}$, we notice that $\forall q, \; g_{p+1} \leq g_{p-q+1}$, so that

    $$\begin{array}{ccccccc}
    \tau_{q,n} & \; \; \leq  \; \; & \displaystyle{ \frac{4}{n}  \sum_{p=q}^{n-1} g_{p+1} a^{p-q} } &  \; \; \leq  \; \;  & \displaystyle{ \frac{4}{n}  \sum_{p=q}^{n-1} g_{p-q+1}  a^{p-q} }
    & \; \; \leq \; \; & \displaystyle{ \frac{4}{n}  \sum_{p=0}^{n-q-1} g_{p+1} a^p  }    \\
    &&&&& \; \;  \leq  \; \; & \displaystyle{ \frac{4}{n}  \sum_{p=0}^{n-1} g_{p+1} a^p } .
    \end{array}$$ Finally, we have that $\displaystyle{ \tau_n^{\star} \leq \frac{4.U_0}{n}  }$, where $\displaystyle{ U_0 = \sum_{p \geq 0} g_{p+1} a^p  \leq \frac{g_1}{1-a}  }$.\
    We estimate $\bar{r}_n$, using the following inequalities:

    $$\begin{array}{ccccc}
    \bar{r}_n & \; \; \leq  \; \; & \displaystyle{ \frac{8}{n}  \sum_{0\leq q \leq p <n} g_{p+1} . g_{p,q}^3 . b_{p,q}  } &  \; \; \leq  \; \;  & \displaystyle{ \frac{8}{n}  \sum_{p=0}^{n-1} \; \sum_{q=p-n}^p  g_{p+1}^{3+2\alpha}  a^{p-q} }   \\
    &&& \; \;  \leq  \; \; & \displaystyle{ \frac{8}{1-a} \cdot  \underbrace{\frac{1}{n} \sum_{p=1}^{n} g_{p}^{3+2\alpha} }_{=u_2(n)} }
    \end{array}$$ Let us conduct a last useful estimation:

    $$\begin{array}{ccccc}
     \tau_n^{\star} . \bar{\sigma}_n^2 & \; \; \leq  \; \; & \displaystyle{  \sum_{q =0}^{n-1} \tau_{q,n}^2} &  \; \; \leq  \; \;  & \displaystyle{ \sum_{q =0}^{n-1} \left( \frac{4}{n} \; \sum_{p=0}^{n-q+1} \; g_{p+q+1} . a^p \right)^2 }   \\
    &&& \; \;  \leq  \; \; & \displaystyle{ \sum_{q =0}^{n-1} \; \frac{16}{n^2} \cdot g_{q+1}^2 \cdot \frac{1}{(1-a)^2}  }  \\
    &&& \; \;  \leq  \; \; & \displaystyle{  \frac{16}{n.(1-a)^2} \times \underbrace{ \frac{1}{n} \sum_{q =0}^{n-1} g_{q+1}^2}_{= \left(u_3(n)\right)^2}  }
    \end{array}$$ At last, we make the suitable substitutions in (\[osef\]) and obtain the desired inequality (\[reg-dec-gamma\]).

This ends the proof of the theorem.

Interacting Simulated Annealing Models {#section-Gibbs}
======================================

Some Motivations {#section-Gibbs-motiv}
----------------

We consider the Boltzmann-Gibbs probability measure associated with an inverse “temperature” parameter $\beta \geq 0$ and a given potential function $V \in \mathcal{B}(E)$ defined by

$$\label{def-mes-Gibbs}
\mu_{\beta} (dx) = \frac{1}{Z_{\beta}} e^{- \beta.V(x)} m(dx) ,$$

where $m$ stands for some reference measure, and $Z_{\beta}$ is a normalizing constant. We let $\beta_n$ a strictly increasing sequence (which may tend to infinity as $n \rightarrow \infty$). In this case, the measures $\eta_n = \mu_{\beta_n}$ can be interpreted as a FK flow of measures with potential functions $G_n = e^{-(\beta_n - \beta_{n-1})V}$ and Markov transitions $M_n$ chosen as being MCMC dynamics for the current target distributions. Indeed, we have $$\mu_{\beta_{n}} (dx) =    \frac{e^{- \beta_n.V(x)}}{Z_{\beta_n}} m(dx) = \frac{   Z_{\beta_{n-1}}   }    {Z_{\beta_n}} \underbrace{e^{-(\beta_n - \beta_{n-1})V(x)}}_{=G_n(x)}  \underbrace{ \left( \frac{e^{- \beta_{n-1}.V(x)}}{Z_{\beta_{n-1}}} m(dx) \right)  }_{=\mu_{\beta_{n-1}} (dx)}.$$ This shows $\displaystyle{ \mu_{\beta_{n}} = \psi_{G_n} (\mu_{\beta_{n-1}}) } $. Let $\phi_n$ stand for the FK transformation associated with potential function $G_n$ and Markov transition $M_n$. We have

$$\phi_n(\mu_{\beta_{n-1}}) =  \psi_{G_n} (\mu_{\beta_{n-1}}) = \mu_{\beta_{n}} . M_n = \mu_{\beta_{n}} .$$

Sampling from these distributions is a challenging problem in many application domains. The simplest one is to sample from a complex posterior distribution on some Euclidian space $E=\mathbb{R}^d$, for some $d \geq 1$. Let $x$ be a variable of interest, associated with a prior density $p(x)$ (easy to sample) with respect to Lebesgue measure $dx$ on $E$, and $y$ a vector of observations, associated with a calculable likelihood model $p(y \mid x)$. In this context, we recall that $p(y \mid x)$ is the density of the observations given the variable of interest. The density $p(x \mid y)$ of the posterior distribution $\eta$ is given by Bayes’ formula $$p(x \mid y) \propto  p(x). p(y \mid x).$$ In the case where $\eta$ is highly multimodal, it is difficult to sample from it directly. As an example, classic MCMC methods tend to get stuck in local modes for very long times. As a result, they converge to their equilibrium $\eta$ only on unpractical time-scales. To overcome this problem, a common solution is to approximate the target distribution $\eta$ with a sequence of measures $\eta_0, \ldots , \eta_n$ with density $$\eta_k(dx) \propto p(x). p(y \mid x)^{\beta_k} dx$$ where $\displaystyle{ (\beta_k)_{0 \leq k \leq n} }$ is a sequence of number increasing from $0$ to $1$, so that $\eta_0$ is the prior distribution of density $p(x)$, easy to sample, and the terminal measure $\eta_{n}$ is the target distribution $\eta$ (see for instance [@Bertrand; @Giraud-RB; @Minvielle; @Neal]). If we take $V:= x \mapsto - \log(p(y \mid x))$ and $m(dx) := p(x) dx$, then the $\eta_k$ coincide with the Boltzmann-Gibbs measures $\mu_{\beta_k}$ defined in (\[def-mes-Gibbs\]). In this context, IPS methods arise as being a relevant approach, especially if $\eta$ is multimodal, since the use of a large number of particles allows to cover several modes simultaneously.\
The normalizing constant $\gamma_n(1)$ coincide with the marginal likelihood $p(y)$. Computing this constant is another central problem in model selection arising in hidden Markov chain problems and Bayesian statistics.\
Next, we present another important application in physics and chemistry, known as free energy estimation. The problem starts with an un-normalized density of the form $$q \left( \omega \mid T,\alpha \right) = \exp \left( -\frac{H(\omega , \alpha)}{k.T} \right)$$ where $H(\omega, \alpha)$ is the energy function of state $\omega$, $k$ is Boltzmann’s constant, T is the temperature and $\alpha$ is a vector of system characteristics. The free energy $F$ of the system is defined by the quantity $$F(T,  \alpha) =  -k.T.\log(z(T,  \alpha)),$$ where $z(T,  \alpha)$ is the normalizing constant of the system density. See for instance [@Ceperley; @Ciccotti-Hoover; @Frankel-Smit] for a further discussion on these ground state energy estimation problems.\
Last, but not least, it is well known that Boltzmann-Gibbs measures’ sampling is related to the problem of minimizing the potential function $V$. The central idea is that $\mu_{\beta}$ tends to concentrate on $V$’s minimizers as the inverse temperature $\beta$ tends to infinity. To be more precise, we provide an exponential concentration inequality in Lemma \[lemme-conc-Gibbs\].\
In this context, the IPS algorithm can be interpreted as a sequence of interacting simulated annealing ([*abbreviate ISA*]{}) algorithms. As they involve a population of $N$ individuals, evolving according to genetic type processes (selection, mutation), ISA methods also belong to the rather huge class of evolutionary algorithms for global optimization. These algorithms consist in exploring a state space with a population associated with an evolution strategy, i.e. an evolution based on selection, mutation and crossover. See [@Goldberg] or [@Le-Riche] and the references therein for an overview. As these algorithms involve complex, possibly adaptive strategies, their analysis is essentially heuristic, or sometimes asymptotic (see [@Cerf] for general convergence results on genetic algorithms). The reader will also find in [@DM-M-Efini] a proof for a ISA method of the a.s. convergence to the global minimum in the case of a finite state space, when the time $n$ tends to infinity, and as soon as the population size $N$ is larger than a critical constant that depends on the oscillations of the potential fitness functions and the mixing properties of the mutation transitions.\
The results of the previous sections apply to the analysis of ISA optimization methods. Our approach is non-asymptotic since we estimate at each time $n$, and for a fixed population size $N$ the distance between the theoretical Boltzmann-Gibbs measure $\eta_n$ and its empirical approximation $\eta_n^N$. In some sense, as $\beta_n \rightarrow + \infty$, $\eta_n$ tends to the Dirac measure $\delta_{x^{\star}}$ where $x^{\star} = \underset{x \in E}{\textmd{argmin}} \; V(x)$, as soon as there is a single global minimum. So intuitively, we guess that if this distance admits a uniform bound w.r.t. time $n$, then for large time horizon we have $\eta_n^N \simeq \delta_{x^{\star}} $.\
In this section we propose to turn the conditions of Theorem \[reg born\] and Theorem \[reg dec\] into conditions on the temperature schedule to use, and the number of MCMC steps that ensure a given performance degree. Then we combine the concentration results of section \[section-result-unif\] with Lemma \[lemme-conc-Gibbs\] to analyze the convergence of the IPS optimization algorithm.

An ISA Optimization Model {#section-Gibbs-tuning}
-------------------------

We fix an inverse temperature schedule $\beta_n$ and we set

-   $\eta_n(dx) = \mu_{\beta_n}(dx)= \frac{1}{Z_{\beta_n}} e^{- \beta_n V(x)} m(dx)$;

-   $G_n(x) = e^{-\Delta_n .V(x)}$ ;

-   and then $g_n = e^{\Delta_n . \textmd{osc} (V)}$,

where $\Delta_n$ are the increments of temperature $\Delta_n = \beta_n - \beta_{n-1}$. We let $K_{\beta}$ the simulated annealing Markov transition with invariant measure $\mu_{\beta}$ and a proposition kernel $K(x,dy)$ reversible w.r.t. $m(dx)$. We recall that $K_{\beta}(x,dy)$ is given by the following formulae: $$\begin{array}{llll}
         K_{\beta}(x,dy)= K(x,dy). \min \left( 1 , e^{-\beta \left( V(y) - V(x)  \right)}  \right) & \forall y \neq x & \\
         & &\\
         K_{\beta}(x,\{ x \}) = 1 - \int_{y \neq x} K(x,dy). \min \left( 1 , e^{-\beta \left( V(y) - V(x)  \right)}  \right)
         
         
    \end{array}$$ Under the assumption $K^{k_0}(x,\cdot) \geq \delta  \nu(\cdot)$ for any $x$ with some integer $k_0 \geq 1$, some measure $\nu$ and some $\delta >0$, one can show (see for instance [@Bartoli]) that

$$\beta(K_{\beta}^{k_0}) \leq \left( 1- \delta e^{- \beta \overline{\Delta V}(k_0)} \right)  \label{dob-MH}$$

where $\overline{\Delta V}(k_0)$ is the maximum potential gap one can obtain making $k_0$ elementary moves with the Markov transition $K$. One way to control the mixing properties of the ISA model is to consider the Markov transition $M_p = K_{\beta_p}^{{k_0}.{m_p}}$, the simulated annealing kernel iterated $k_0.m_p$ times. In this case, the user has a choice to make on two tuning parameters, namely the temperature schedule $\beta_p$, and the iteration numbers $m_p$. Note that for all $b \in (0,1)$, condition $b_p \leq b$ is turned into $\left( 1 - \delta e^{- \beta_p \overline{\Delta V}(k_0)} \right)^{m_p} \leq b,$ which can also be rewritten as follows.

$$m_p \geq  \frac{\log(\frac{1}{b})e^{\overline{\Delta V}(k_0).\beta_p}}{\delta}$$

We prove now is a technical lemma that we will use in the following. It deals with Boltzmann-Gibbs measures’ concentration properties.

\[lemme-conc-Gibbs\] For any $\beta > 0$, and for all $0 < \varepsilon^{\prime} < \varepsilon$, the Boltzmann-Gibbs measure $\mu_{\beta}$ satisfies $$\mu_{\beta} \left( V \geq V_{\min} + \varepsilon \right) \leq \frac{e^{-\beta(\varepsilon - \varepsilon^{\prime}) }}{m_{\varepsilon^{\prime}}} ,$$ where $m_{\varepsilon^{\prime}} = m \left( V \leq V_{\min} + \varepsilon ^{\prime} \right) >0$.

The normalizing constant $Z_{\beta}$ of the definition (\[def-mes-Gibbs\]) is necessary equal to $\underset{E}{\displaystyle{\int}} e^{-\beta V} dm  $. Then we have $$\begin{aligned}
  \mu_{\beta} \left( V \geq V_{\min} + \varepsilon \right)  & \; \;  = \; \;  \frac{ \underset{V \geq V_{\min} + \varepsilon}{\displaystyle{\int}}  e^{-\beta V} dm  }{  \underset{V \geq V_{\min} + \varepsilon}{\displaystyle{\int}} e^{-\beta V} dm  + \underset{V < V_{\min} + \varepsilon}{\displaystyle{\int}} e^{-\beta V} dm  }  \\
  & \; \; \leq  \; \;  \underbrace{ \left( \underset{V \geq V_{\min} + \varepsilon}{\displaystyle{\int}} e^{-\beta V} dm \right) }_{A_1} \;  \underbrace{ \left( \underset{V < V_{\min} + \varepsilon}{\displaystyle{\int}} e^{-\beta V} dm  \right)^{-1} }_{A^{-1}_2} .\end{aligned}$$ Firstly, it is clear that $\displaystyle{  A_1 \leq e^{- \beta (V_{\min} + \varepsilon )} }$. Secondly, $\varepsilon^{\prime} < \varepsilon$ implies $\{ V \leq V_{\min} + \varepsilon^{\prime} \} \subset \{ V < V_{\min} + \varepsilon \} $, then we have

$$A_2 \; \geq   \underset{V \leq V_{\min} + \varepsilon^{\prime}}{\displaystyle{\int}} e^{-\beta V} dm \; \; \geq \; \;  m \left( V \leq V_{\min} + \varepsilon ^{\prime} \right) e^{- \beta (V_{\min} + \varepsilon^{\prime} )} .$$ We end the proof by making the appropriate substitutions.

Combining this Lemma \[lemme-conc-Gibbs\], the theorems of section \[section-result-unif\] (with indicator test function $f = \mathbf{1}_{\lbrace V \geq V_{\min} + \varepsilon \rbrace}$) , and the Dobrushin ergodic coefficient estimate (\[dob-MH\]) we prove the following theorem:

\[theo-optim-base\] Let us fix $a \in (0,1)$. For any $\varepsilon >0$, $n\geq 0$ and $N \geq 1$, let $p_n^N (\varepsilon)$ denote the proportion of particles $(\zeta_n^i)$ s.t. $ V (\zeta_n^i) \geq V_{\min} + \varepsilon$. We assume that the inverse temperature schedule $\beta_p$ and the iteration numbers $m_p$ satisfy one of these two conditions:

1.  $ \underset{p \geq 1}{\sup} \;  \Delta_p \leq \Delta < \infty$ (e.g. linear temperature schedule) and $$\displaystyle{m_p \geq  \frac{\log(\frac{e^{\Delta.\textmd{osc}(V)}+a}{a})e^{\overline{\Delta V}(k_0).\beta_p}}{\delta}} .$$

2.  $\Delta_p \downarrow 0$ (as $p \rightarrow \infty$) and $\displaystyle{ m_p \geq \left( \textmd{osc}(V). \Delta_p + \log (\frac{1}{a}) \right) \frac{e^{\overline{\Delta V}(k_0).\beta_p}}{\delta}}$ .

In this situation, for any $\varepsilon >0$, $n\geq 0$, $N \geq 1$, $y \geq 0$, and $\varepsilon^{\prime} \in (0, \varepsilon)$, the probability of the event

$$p_n^N (\varepsilon) \; \; \leq \; \; \frac{e^{-\beta_n(\varepsilon - \varepsilon^{\prime}) }}{m_{\varepsilon^{\prime}}} +  \frac{r_i^{\star} N + r_j^{\star} y}{N^2}$$

is greater than $1-e^{-y}$, with $(i,j) = (1,2)$ (and $M=e^{\Delta}$) in the case of bounded $\Delta_{p}$, and $(i,j) = (3,4)$ in the second one.

We distinguish two error terms. The first one, $\displaystyle{ \left( \frac{e^{-\beta_n(\varepsilon - \varepsilon^{\prime}) }}{m_{\varepsilon^{\prime}}} \right) }$, is related to the concentration of the Boltzmann-Gibbs measure around the set of global minima of $V$. The second one, $\displaystyle{ \left( \frac{r_i^{\star} N + r_j^{\star} y}{N^2} \right) }$, is related to the concentration of the occupation measure around the limiting Boltzmann-Gibbs measure. Besides the fact that Theorem \[theo-optim-base\] provides tuning strategies which ensure the performance of the ISA model, the last concentration inequality explicits the relative importance of other parameters, including the probabilistic precision $y$, the threshold $t$ on the proportion of particles possibly out of the area of interest, the final temperature $\beta_n$ and the population size $N$. A simple equation, deduced from this last theorem, such as $\displaystyle{ \left( \frac{e^{-\beta_n(\varepsilon - \varepsilon^{\prime}) }}{m_{\varepsilon^{\prime}}} = \frac{r_i^{\star} N + r_j^{\star} y}{N^2}  = \frac{t}{2} \right) } $ may be applied to the global tuning of an ISA model, which is generally a difficult task.\
One natural way to choose $\Delta_p$ is to look at the number of iterations $n_1$ we need to proceed to move from $\beta_p$ to $\beta_n$, and to compare it to $n_2$, the iteration number we need to proceed to move from $\beta_p$ to $\beta_q$, and then from $\beta_q$ to $\beta_n$, with $\beta_p < \beta_q < \beta_n$. Roughly speaking, we have seen that the convergence condition was $b_p \leq \frac{a}{g_p}$, then

-   $n_1 \simeq \left( osc(V).\Delta_{p,n}+ \log (\frac{1}{a}) \right) \frac{e^{\overline{\Delta V}(k_0).\beta_n}}{\delta}$

-   $n_2 \simeq \left( osc(V).\Delta_{p,q}+ \log (\frac{1}{a}) \right) \frac{e^{\overline{\Delta V}(k_0).\beta_q}}{\delta} +
    \left( osc(V). \Delta_{q,n}+ \log (\frac{1}{a}) \right) \frac{e^{\overline{\Delta V}(k_0).\beta_n}}{\delta}$

 \
where $\Delta_{p,q} := \beta_p - \beta_q$ for $p > q$. After some approximation technique we find that

$$n_1 \leq n_2 \Longleftrightarrow \Delta_{p,q} \Delta_{q,n} \geq \frac{\log (\frac{1}{a} )}{osc(V). \overline{\Delta V}(k_0)}.$$

This condition doesn’t bring any relevant information in the case where $\Delta_p \longrightarrow 0$ exept that the error decomposition $\eta_n^N-\eta_n = \sum_{p=0}^{n} \phi_{p,n}(\eta_p^N)- \phi_{p,n} \phi_{p}(\eta_{p-1}^N)$, underlying our analysis, is not adapted to the case where $\Delta_p \longrightarrow 0$ (which can be compared to the continuous time case). Nevertheless, this condition is interesting in the case of constant inverse temperature steps. In this situation, the critical parameter $\Delta_{\beta}$ is given by

$$\Delta_{\beta} = \sqrt{ \frac{\log (\frac{1}{a} )}{osc(V).\overline{\Delta V}(k_0)} } .$$

More precisely, above $\Delta_{\beta}$ the algorithm needs to run too many MCMC steps to stabilize the system. In the reverse angle, when the variation of temperature is too small, it is difficult to reach the disired target measure.

An Adaptive Temperature Schedule in ISA {#section-adapt}
=======================================

As we already mentioned in the introduction, the theoretical tuning strategies developed in section \[section-Gibbs-tuning\] are of the same order as the logarithmic cooling schedule of traditional simulated annealing ([@Bartoli; @Cerf; @DM-M-Efini]). In contrast to SA models, we emphasize that the performance of the ISA models are not based on a critical initial temperature parameter. Another advantage of the ISA algorithm is to provide at any time step an $N$-approximation of the target measure with a given temperature. In other words, the population distribution reflects the probability mass distribution of the Boltzmann-Gibbs measure at that time. Computationally speaking, the change of temperature parameter $\Delta_p$ plays an important role. For instance, if $\Delta_p$ is taken too large, the selection process is dominated by a minority of well fitted particles and the vast majority of the particles are killed. The particle set’s diversity, which is one of the main advantage of the ISA method, is then lost. On the contrary, if $\Delta_p$ is taken too small, the algorithm doesn’t proceed to an appropriate selection. It wastes time by sampling from MCMC dynamics while the set of particles has already reached its equilibrium. The crucial point is to find a relevant balance between maintaining diversity and avoiding useless MCMC operations.\
Designing such a balance in advance is almost as hard as knowing the function $V$ in advance. Therefore, it is natural to implement adaptive strategies that depend on the variability and the adaptation of the population particles (see for instance [@Jasra; @Schafer], [@Clapp; @Deutscher; @Minvielle] for related applications). In the general field of evolutionary algorithms, elaborating adaptive selection strategies is a crucial question (see, e.g. [@Baker]) and a challenging problem to design performant algorithms. In the case of ISA methods, the common ways to choose $\Delta_p$ are based on simple criteria such as the expected number of particle killed (see section \[description-algo-adapt\]), or the variance of the weights (Effective Sample Size). All of these criteria are based on the same intuitive idea; that is to achieve a reasonable selection. As a result, all of these adaptive ISA models tend to perform similarly.\
In [@DM-D-J-adapt], the reader will find a general formalization of adaptive IPS algorithms. The idea is to define the adaptation as the choice of the times $n$ at which the resampling occurs. These times are chosen according to some adaptive criteria, depending on the current particle set, or more generally on the past process. Under weak conditions on the criteria, it is shown how the adaptive process asymptotically converges to a static process involving deterministic interaction times when the population size tends to infinity. A functional central limit theorem is then obtained for a large class of adaptive IPS algorithms.\
\
The approach developed in the following section is radically different, with a special focus on non-asymptotic convergence results for the ISA algorithm defined in section \[description-algo-adapt\]. The adaptation consists here in choosing the $\beta$ increment ${\Delta}_{n+1}^N$ so that $$\eta_n^N (e^{-{\Delta}_{n+1}^N \cdot V})  =  \varepsilon$$ where $\varepsilon > 0$ is a given constant, at each iteration $n$. We show that the associated stochastic process can be interpretated as a perturbation of the limiting FK flow.

Feynman-Kac Representation
--------------------------

Let $V \in \mathcal{B}(E)$. To simplify the analysis, without any loss of generality, we assume $V_{\min}=0$. Let us fix $\varepsilon > 0$. For any measure $\mu \in \mathcal{P}(E)$, we let the function $\lambda_{\mu}$ defined by

$$\begin{array}{rccc}
   &  [0,+\infty)  &  \longrightarrow  &  (0,1]  \\
\lambda_{\mu} =  &  x   & \mapsto  &  \mu \left( e^{-x \cdot V}  \right)  \\
    \end{array}$$

This function is clearly decreasing ($\lambda_{\mu} (0) = 1$), convex, and differentiable infinitely. Moreover, if $\mu \left( \{ V=0 \} \right) =0$, then it satisfies $\lambda_{\mu}(x) \longrightarrow 0$ when $x \to +\infty$. Therefore, we can define its inverse function $\kappa_{\mu}$:

$$\begin{array}{rccl}
   &   (0,1]  &  \longrightarrow  & \; [0,+\infty)  \\
\kappa_{\mu} =  &  \varepsilon   & \mapsto  & \;  x \; \; \textmd{so that} \; \mu \left( e^{-x \cdot V}  \right) = \varepsilon \\
    \end{array}$$ This function is again decreasing, convex, infinitely differentiable, takes value $0$ for $\varepsilon=1$, and it satisfies $\kappa_{\mu}(\varepsilon)\longrightarrow + \infty$ when $\varepsilon \to 0^+$.\
Now, we let $m$ be a reference measure on $E$ s.t. $m \left( \{ V=0 \} \right) =0$. We consider the sequence $(\beta_n)_n$ and its associated Gibbs measures $\eta_n = \mu_{\beta_n} \propto e^{-\beta_n V}. m$, defined recursively by the equation

$${\Delta}_{n+1} := (\beta_{n+1} - \beta_{n}) = \kappa_{\eta_n}(\varepsilon) . \label{increment-theo}$$

In an equivalent way, we have

$$\lambda_{\eta_n}({\Delta}_{n+1}) = \varepsilon   \quad \textmd{or}  \quad  \eta_n (e^{-{\Delta}_{n+1} \cdot V})  =  \varepsilon.$$

The main objective of this section is to approximate these target measures. Formally speaking, $(\eta_n)$ admits the FK structure described in section \[section-Gibbs-motiv\], with potential functions $G_n(x) = e^{-\Delta_n .V(x)}$, and some dedicated MCMC Markov kernels $M_n$. We let $g_n$, $b_n$, be the associated oscillations, Dobrushin ergodic coefficients and the corresponding FK transformations $\phi_n$.\
\
The solving of the equation $\displaystyle{ \eta_n (e^{-{\Delta}_{n+1} \cdot V})  =  \varepsilon }$ can be interpreted as a way to impose some kind of theoretical regularity in the FK flow. Indeed, according to the formula (\[defgamma1\]) (and definition (\[def-mes-Gibbs\]) ), it is equivalent to find $\Delta_{n+1}$ s.t. $$\frac{\gamma_{n+1} (1) }{\gamma_n(1)} = \varepsilon  \; \; \left( = \frac{Z_{\beta_n + \Delta_{n+1}  }}{Z_{\beta_n}}  \right).$$ In other words, the sequence $\Delta_n$ is defined so that the normalizing constants $\gamma_n(1)$ increase geometrically, with the ratio $\gamma_{n+1} (1)  / \gamma_n(1) = \varepsilon$. Notice that these increments $\Delta_n$ are only theoretical, and the corresponding potential functions $G_n$ are not explicitly known.

An Adaptive Interacting Particle Model {#description-algo-adapt}
--------------------------------------

As in the classic IPS algorithm, we approximate the measures $\eta_n$ by simulating an interacting particle system $(\zeta_n)_n = \left( \zeta_n^1, \ldots, \zeta_n^N \right)_n$ of size $N$ so that $$\eta^N_{n}=\frac{1}{N}\sum_{1\leq i\leq N}\delta_{\zeta^i_n}\rightarrow_{N\uparrow\infty}\eta_n.$$

We start with $N$ independent samples from $\eta_0$ and then alternate selection and mutation steps, as described in section \[algo-classique\]. As we mentioned above, in contrast to the classic IPS model, the potential function $G_{n+1}$ arising in the selection is not known. The selection step then starts by calculating the empirical increment $\Delta_{n+1}^N$ defined by

$${\Delta}_{n+1}^N :=  \kappa_{\eta_n^N}(\varepsilon)$$

or $\lambda_{\eta_n^N}({\Delta}_{n+1}^N) =  \eta_n^N (e^{-{\Delta}_{n+1}^N \cdot V})  =  \varepsilon $. As the quantity $\displaystyle{\eta_n^N (e^{-{\Delta} \cdot V}) = \frac{1}{N} \sum_{1 \leq i \leq N} e^{-\Delta . V(\zeta_n^i)} } $ is easy to calculate for all $\Delta \geq 0$, one can calculate $\Delta_{n+1}^N$ by, e.g., performing a dichotomy algorithm. If we consider the stochastic potential functions

$$G_{n+1}^N = e^{-{\Delta}_{n+1}^N .V}$$

then every particle $\zeta^i_{n}$ evolves to a new particle $\widehat{\zeta}^i_{n}$ randomly chosen with the following stochastic selection transition $$S_{n+1,\eta^N_{n}}^N( \zeta^i_{n},dx)
 :=G_{n+1}^N( \zeta^i_{n})~\delta_{ \zeta^i_{n}}(dx)+
 \left(1-G_{n+1}^N( \zeta^i_{n})\right)~ \Psi_{G_{n+1}^N}(\eta^N_n)(dx) .$$ In the above display formula, $\Psi_{G_{n+1}^N}(\eta^N_n)$ stands for the updated measure defined by $$\Psi_{G_{n+1}^N}(\eta^N_n)=\sum_{j=1}^N\frac{G_{n+1}^N( \zeta^j_{n})}{\sum_{k=1}^N G_{n+1}^N( \zeta^k_{n})}
 \delta_{ \zeta^j_{n}} .$$ Note that $V_{\min}=0$ ensures $0 < G_{n+1}^N \leq 1$. The mutation step consists in performing Markov transitions $M_{n+1}^N(\widehat{\zeta}^i_{n},\cdot)$, defined as $M_{n+1}(\widehat{\zeta}^i_{n},\cdot)$ by replacing $\beta_{n+1}$ by $\beta_{n+1}^N = \beta_n^N + \Delta_{n+1}^N$. Thus, conditionally to the previous particle set $\zeta_n$, the new population of particles $\zeta_{n+1}$ is sampled from distribution $$\begin{aligned}
 & \mbox{\rm Law} \left( \zeta_{n+1}^1,...,\zeta_{n+1}^N  \mid  \zeta_{n}^1,...,\zeta_{n}^N \right)  \nonumber  \\
 &=\; \; \left( \delta_{\zeta_{n}^1}.S^N_{n+1,\eta_{n}^N}.M_{n+1}^N \right) \otimes \cdots \otimes    \left( \delta_{\zeta_{n}^N}.S^N_{n+1,\eta_{n}^N}.M_{n+1}^N \right) .    \label{loi-algo-adapt} \end{aligned}$$ The definition of $\Delta_{n+1}^N$ is to be interpreted as the natural approximation of the theoretical relation (\[increment-theo\]). On the other hand, it admits a purely algorithmic interpretation. As a matter of fact, conditionnaly to the n-th generation of particles $ \left( \zeta_n^1, \ldots, \zeta_n^N \right)$, the probability for any particle $ \zeta_n^i $ to be accepted, i.e. not affected by the recycling mechanism, is given by $G_{n+1}^N(\zeta_n^i) = e^{-\Delta_{n+1}^N . V(\zeta_n^i)}$. Then, the expectation of the number of accepted particles is given by $\sum_i e^{-\Delta_{n+1}^N . V(\zeta_n^i)}$. But it turns out that this quantity is exactly $N \times \eta_n^N (e^{-{\Delta}^{N}_{n+1} \cdot V})$, which is equal to $N . \varepsilon$ by definition of $\Delta_{n+1}^N$. Therefore, $\varepsilon$ is an approximation of the proportion of particles which remain in place during the selection step. In other words, at each generation $n$, the increment $\Delta_{n+1}^N$ is chosen so that the selection step kills less than $(1-\varepsilon).N$ particles. This type of tuning parameter is very important in practice to avoid degenerate behaviours.

A Perturbation Analysis
-----------------------

This section is mainly concerned with the convergence analysis of a simplified adaptive model. More precisely, we only consider the situation where the mutation transition in (\[loi-algo-adapt\]) is given by the limiting transition $M_{n+1}$. The analysis of the adaptive model (\[loi-algo-adapt\]) is much more involved, and our approach doesn’t apply directly to study the convergence of this model.\
Despite the adaptation, the sequence $\eta_n^N$ can be analyzed as a random perturbation of the theoretical sequence $\eta_n$. Let us fix $n$ and a population state $\zeta_n$ at time $n$. If $\phi_{n+1}^N$ denotes the FK transformation associated with potential $G_{n+1}^N$ and kernel $M_{n+1}$, then, by construction, the measure $\eta_{n+1}^N$ is close to $\phi_{n+1}^N(\eta_{n}^N)$. In particular, by the Khintchine’s type inequalities presented in [@DM-FK] we have

$$\label{MZ-cond}
\forall f \in \mathcal{B}_1 (E), \quad \mathbb{E} \left( \left| \eta_{n+1}^N (f) - \phi_{n+1}^N(\eta_{n}^N) (f) \right|^p \mid \zeta_n \right)^{1/p} \leq \frac{B_p}{\sqrt{N}},$$

with the constants $B_p$ introduced in (\[def-Bp\]). A simple, but important remark about the Boltzmann-Gibbs transformations is that for any measure $\mu$ and any positive functions $G$ and $\tilde{G}$ we have $$\psi_{\tilde{G}} (\mu)  \; = \;  \psi_G \left( \psi_{\frac{\tilde{G}}{G}} (\mu) \right).$$ Therefore, if we take $\displaystyle{H_{n+1}^N:= \frac{G^N_{n+1}}{G_{n+1}} }$, then the perturbed transformation $\phi_{n+1}^N$ can be written in terms of the theoretical one $\phi_{n+1}$ by

$$\label{mes-virt}
\phi_{n+1}^N = \phi_{n+1} \circ \psi_{H_{n+1}^N}.$$

If we use an inductive approach, we face the following problem. Let $\eta$ be a deterministic measure ($\eta_n$ in our analysis) and $\hat{\eta}$ a random measure ($\eta_n^N$ in our analysis), close to $\eta$ under the $d_p$ distance (induction hypothesis). We also consider a Markov kernel $M$ and the potential functions $$\label{def-G-etc}
G = e^{-\kappa_{\eta}(\varepsilon).V} , \quad \hat{G} = e^{-\kappa_{\hat{\eta}}(\varepsilon).V}, \quad \hat{H} = \frac{\hat{G}}{G}$$ and we let $\phi$ (respectively $\hat{\phi}$) be the FK transformation associated with the potential function $G$ (respectively $\hat{G}$). The question is now: how can we estimate $d_p(\phi(\eta),\hat{\phi}(\hat{\eta}))$ in terms of $d_p(\eta,\hat{\eta})$ ?\
To answer to this question, we propose to achieve a two-step estimation. Firstly we estimate the distance between $\hat{\eta}$ and $\psi_{\hat{H}}(\hat{\eta}) $ (Lemma \[lemme-fonda-adapt\]). Secondly we analyze the stability properties of the transformation $\phi$ (Lemma \[lemme-phi-Lp\]). This strategy is summerized by the following synthetic diagram.

$$\begin{array}{ccc}
\eta & \underset{\phi}{-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!\longrightarrow}  &  \phi(\eta)  \\
\hat{\eta}  &   &  \\
\downarrow &    &  \\
\psi_{\hat{H}}(\hat{\eta})  &  \underset{\phi}{-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!-\!\!\!\!\longrightarrow} & \hat{\phi}(\hat{\eta})
\end{array}$$

\[lemme-fonda-adapt\] Let $\eta \in \mathcal{P}(E)$, $\hat{\eta} \in \mathcal{P}_{\Omega}(E)$ and let $G$, $\hat{G}$, $\hat{H}$ be the positive functions on $E$ defined by equations (\[def-G-etc\]). If $\eta( \{V=0 \}) = \hat{\eta}( \{V=0 \}) = 0$ (a.s.), then for all $\varepsilon > 0$, we have

$$d_p \left( \psi_{\hat{H}}(\hat{\eta}), \eta \right) \leq  \frac{V_{\max} \cdot e^{\kappa_{\eta}(\varepsilon).V_{\max} } }{\eta(V)}      \cdot  d_p \left( \hat{\eta}, \eta \right)  .$$

We simplify the notation and we set $x:=\kappa_{\eta}(\varepsilon)$ and $\hat{x} := \kappa_{\hat{\eta}}(\varepsilon)$.\
We start with the following observation,

$$\label{prem-decomp}
\psi_{\hat{H}} (\hat{\eta}) (f) - \hat{\eta} (f) = \frac{\hat{\eta} (\hat{H}.f )}{\hat{\eta}(\hat{H})} - \hat{\eta}(f) = \underbrace{\frac{1}{\hat{\eta}(\hat{H})}}_{A_1} \underbrace{\hat{\eta} \left[ \left(\hat{H} - \hat{\eta}(\hat{H}) \right).f \right]}_{A_2}$$

for any $f \in \mathcal{B}(E)$. We notice that $\hat{H} = \hat{G}/G = e^{(x-\hat{x}) \cdot V}$, which leads to the lower bound $\hat{\eta}(\hat{H}) = \hat{\eta} \left( e^{(x-\hat{x}) \cdot V} \right) \geq  \hat{\eta} \left( e^{-\hat{x} \cdot V} \right) = \varepsilon$. The last equality comes from the definition of $\hat{x}$. We just proved: $|A_1| \leq \varepsilon^{-1}$. On the other hand, we have $ osc(\hat{H})  =  \left| e^{(x-\hat{x}) \cdot V_{\max}} - 1 \right| $, so that

$$\begin{aligned}
 \left| A_2 \right|  \leq \hat{\eta} \left( \left| \hat{H} - \hat{\eta}(\hat{H}) \right| \right) \cdot \left\| f \right\|_{\infty} & \leq osc(\hat{H}) \cdot \left\| f \right\|_{\infty}  \nonumber \\
  & \leq \left| e^{(x-\hat{x}) \cdot V_{\max}} - 1 \right| \cdot \left\| f \right\|_{\infty} .  \label{apparition-u}\end{aligned}$$

The quantity $\displaystyle{ \hat{u} :=  \left( e^{(x-\hat{x}) \cdot V_{\max}} - 1 \right)  }$ is intuitively small. Next, we provide an estimate in terms of the functions $\lambda_{\eta}$ and $\lambda_{\hat{\eta}}$. Given $\omega \in \Omega$, if $x \geq \hat{x}$, then we can write

$$( \lambda_{\hat{\eta}}(x) - \underbrace{\lambda_{\eta}(x)}_{=\varepsilon=\lambda_{\hat{\eta}}(\hat{x})}  )  = \left( \lambda_{\hat{\eta}}(x) - \lambda_{\hat{\eta}}(\hat{x})  \right) =   \int_{\hat{x}}^{x} -\lambda^{'}_{\hat{\eta}} (s) ds . \\$$

Furthermore, for all $\mu \in \mathcal{P}(E)$ and $s \geq 0$, we have

$$\begin{array}{rcl}
 -\lambda_{\mu}^{'}(s) = \mu \left( V \cdot e^{-sV} \right) & \geq & \mu \left( V \cdot e^{-s V_{\max}} \right) \\
 &    \geq & \mu(V) \cdot e^{-s V_{\max}}.
 \end{array}$$

Then, we have $$\begin{aligned}
 \left( \lambda_{\hat{\eta}}(x) - \lambda_{\eta}(x) \right) & \geq   \hat{\eta}(V) \frac{-1}{V_{\max}} \left[ e^{-s V_{\max}} \right]_{\hat{x}}^{x}   \\
& = \hat{\eta}(V) \frac{e^{-x V_{\max}} }{V_{\max}} \left( e^{(x-\hat{x})V_{\max}} - 1 \right)  \\
& = \hat{\eta}(V) \frac{e^{-x V_{\max}} }{V_{\max}} \hat{u} .\end{aligned}$$ By symmetry, we have $$x \leq \hat{x} \; \Longrightarrow \; \left( \lambda_{\eta}(x)  -  \lambda_{\hat{\eta}}(x)  \right)  \geq \hat{\eta}(V) \frac{e^{-x V_{\max}} }{V_{\max}} (-\hat{u}) .$$ This yields the almost sure upper bound $$\left| \hat{u} \right| \cdot \hat{\eta}(V) \frac{e^{-x V_{\max}} }{V_{\max}}  \leq  \left| \lambda_{\eta}(x)  -  \lambda_{\hat{\eta}}(x) \right| .$$

Using the decomposition $\hat{\eta}(V) = \eta(V) + (\hat{\eta}(V) - \eta(V) )$, by simple manipulation, we prove that

$$\left| \hat{u} \right|  \leq  \frac{V_{\max} e^{x V_{\max}} }{\eta(V)} \underbrace{\left| \lambda_{\eta}(x)  -  \lambda_{\hat{\eta}}(x) \right|}_{A_3}  +   \underbrace{\frac{(\hat{\eta}(V) - \eta(V))}{\eta(V)}}_{A_4}  \cdot \underbrace{\left| \hat{u} \right|}_{A_5}$$

Considering the $L^p$ norm of the right hand side of this inequality, one can check that

-   $A_3 = (\eta - \hat{\eta}) \left( e^{-x \cdot V} \right) $ so, as $osc \left( e^{-x \cdot V} \right) \leq 1$, $\Vert A_3 \Vert_p  \leq d_p(\hat{\eta},\eta)$;

-   as $osc(V) = V_{\max}$, $\Vert A_4 \Vert_p \leq \frac{V_{\max}}{\eta(V)} \cdot d_p(\hat{\eta},\eta)$;

-   $A_5 = \left| \hat{u} \right| = e^{x V_{\max}} \left| e^{-\hat{x} V_{\max}} - e^{-x V_{\max}} \right| \leq e^{x V_{\max}} $.

Making the appropriate substitutions, we have

$$\Vert \hat{u} \Vert_p  \leq  \frac{2 V_{\max} e^{x \cdot V_{\max}} }{\eta(V)} \cdot d_p(\hat{\eta},\eta).$$

Combining this result with (\[prem-decomp\]) and (\[apparition-u\]), we check that

$$\left\Vert \psi_{\hat{H}} (\hat{\eta}) (f) - \hat{\eta} (f) \right\Vert_p   \leq  \frac{2 V_{\max} e^{x V_{\max}} }{\varepsilon \cdot \eta(V)} \cdot d_p(\hat{\eta},\eta) \cdot \left\| f \right\|_{\infty}$$

We finally go from $\left\| f \right\|_{\infty}$ to $\frac{osc(f)}{2}$ by noticing that $\psi_{\hat{H}} (\hat{\eta}) (f) - \hat{\eta} (f)$ is equal to $0$ for any constant function $f$, and by considering the above inequality taken for $\tilde{f}=f-\frac{f_{\max}+f_{min}}{2}$, which satisfies $\left\| \tilde{f} \right\|_{\infty} = \frac{osc(f)}{2}$.\
This ends the proof of the lemma.

\[lemme-phi-Lp\] Let $\eta \in \mathcal{P}(E)$, $\hat{\eta} \in \mathcal{P}_{\Omega}(E)$, and let $\phi$ be a FK transformation associated with a positive function $G$ and a Markov kernel $M$. If we set $\displaystyle{ g:= \underset{x,y \in E}{\sup} G(x) / G(y) }$ and $b := \beta(M)$, then we have

$$d_p \left( \phi(\hat{\eta}), \phi(\eta) \right)  \leq  g \cdot b \cdot d_p \left( \hat{\eta}, \eta \right) .$$

Let us fix $f \in \mathcal{B}(E)$. We have $$\begin{aligned}
\phi(\hat{\eta})  (f) - \phi(\eta)  (f)  & =  \frac{\hat{\eta}(G \times M . f)}{\hat{\eta}(G)} - \phi(\eta)  (f) \\
 &  =   \frac{\hat{\eta} \left( G \times \left[ M. \left( f-\phi(\eta) (f) \right) \right]  \right)}{\hat{\eta} \left( G   \right)} .
    \end{aligned}$$ Let $\displaystyle{ \tilde{f} =  M . \left( f-\phi(\eta) (f) \right) } $. By property (\[prop-Dob\]), $\tilde{f}$ satisfies $osc(\tilde{f}) = osc(M.f) \leq b \cdot osc(f)$.\
Additionally we have $\eta(G \times \tilde{f}) = \eta(G \times M.f) - \eta \left( G \times \frac{\eta(G \times M.f)}{\eta(G)} \right) = 0 $. So we obtain

$$\begin{aligned}
\phi(\hat{\eta})  (f) - \phi(\eta)  (f)   = \frac{\hat{\eta}(G \times \tilde{f})  }{\hat{\eta}(G)} - \underbrace{\frac{\eta(G \times \tilde{f})  }{\hat{\eta}(G)}}_{=0} & = \frac{1}{\hat{\eta}(G)} (\hat{\eta} - \eta) (G \times \tilde{f}) \\
 &  =  \frac{G_{\max}}{\hat{\eta}(G)} (\hat{\eta} - \eta) (\frac{G}{G_{\max}} \times \tilde{f}).\end{aligned}$$

Firstly, we notice that $\displaystyle{ \left| \frac{G_{\max}}{\hat{\eta}(G)} \right|  \leq \frac{G_{\max}}{G_{\min}} \leq g }$. On the other hand, we notice that $\tilde{f}$ can be rewritten as

$$\tilde{f} = M. \left( f - \psi_G(\eta)(M.f) \right) = (M.f) - \psi_G(\eta)(M.f).$$

It follows that $ \tilde{f}_{\max} \geq 0$ and $ \tilde{f}_{\min} \leq 0$. Under these conditions, $osc \left( \frac{G}{G_{\max}} \times \tilde{f} \right) \leq osc(\tilde{f}) \leq b \cdot osc(f) $. We conclude that

$$\begin{aligned}
 \left( E \left|  \frac{G_{\max}}{\hat{\eta}(G)} (\hat{\eta} - \eta) \left( \frac{G}{G_{\max}} \times \tilde{f} \right)  \right|^p \right)^{1/p}  & \leq g \cdot E \left[  E \left| (\hat{\eta} - \eta) \left( \frac{G}{G_{\max}} \times \tilde{f} \right)  \right|^p  \right]^{1/p}  \\
  &  \leq   g \cdot b \cdot d_p \left( \hat{\eta}, \eta \right) \cdot osc(f) .\end{aligned}$$

This ends the proof of the lemma.

Non-Asymptotic Convergence Results {#gros-result-adapt}
----------------------------------

This section is mainly concerned with the proof of Theorem \[theo-statement-adapt\] stated on page . We also deduce some concentration inequalities of the ISA adaptive model. We start with the proof of Theorem \[theo-statement-adapt\].\
\
[*Proof of Theorem \[theo-statement-adapt\]:*]{}\
We fix $p \geq 1$ and we let $ \tilde{e}_n = \sum_{k=0}^n \prod_{i=k+1}^n b_i g_i (1+c_i) $. We notice that this sequence can also be defined with the recurrence relation $\tilde{e}_{n+1} = 1+g_{n+1} b_{n+1}(1+c_{n+1}) \cdot \tilde{e}_{n}$ starting at $\tilde{e}_0 = 1$. We also consider the following parameter. $$e_n :=  \frac{\sqrt{N}}{2 B_p} \cdot \underset{f \in \mathcal{O}_1 (E)}{\sup}  \left\Vert \eta_n^N (f) - \eta_n (f) \right\Vert_p$$ We use an inductive proof to check that the proposition $ {\textbf{IH}(n) = \{ e_n \leq \tilde{e}_n \} }$ is met at any rank $n$. As $\eta_0^N$ is obtained with $N$ independant samples from $\eta_0$, $\textbf{IH}(0)$ is given by the Khintchine’s inequality. Now suppose that $\textbf{IH}(n)$ is satisfied.\
According to the identity (\[mes-virt\]), we can write the following decomposition. $$\begin{aligned}
 \eta_{n+1}^N - \eta_{n+1}  &  =  \left( \eta_{n+1}^N - \phi_{n+1}^N (\eta_{n}^N) \right)  +   \left(\phi_{n+1}^N (\eta_{n}^N) - \eta_{n+1}  \right)  \nonumber  \\
  &   =  \underbrace{\left(  \eta_{n+1}^N - \phi_{n+1}^N (\eta_{n}^N)  \right)}_{A_1}   +   \underbrace{\left( \phi_{n+1} \left( \psi_{H_{n+1}^N} (\eta_{n}^N) \right) - \phi_{n+1}(\eta_{n}) \right)}_{A_2}  \label{decompAA}\end{aligned}$$ Given $\zeta_n$, and using (\[MZ-cond\]), we know that for all function $f \in \mathcal{O}_1 (E)$, we have $ \displaystyle{ \frac{\sqrt{N}}{2 B_p} \left\Vert A_1 (f) \right\Vert_p \leq 1 } $. To estimate $A_2$, we start by decomposing $ \left( \psi_{H_{n+1}^N} (\eta_{n}^N) - \eta_{n} \right)$ in this way:

$$\psi_{H_{n+1}^N} (\eta_{n}^N)  -  \eta_{n}  =  \underbrace{ \left( \psi_{H_{n+1}^N} (\eta_{n}^N) - \eta_{n}^N \right) }_{Q_1}   +  \underbrace{\left(  \eta_{n}^N - \eta_{n}  \right)}_{Q_2} .$$

By the induction hypothesis, we have $\frac{\sqrt{N}}{2 B_p} \cdot \underset{f \in \mathcal{O}_1 (E)}{\sup}  \left\Vert Q_2 (f) \right\Vert_p  \leq \tilde{e}_{n}$. Therefore, by Lemma \[lemme-fonda-adapt\], we find that

$$\frac{\sqrt{N}}{2 B_p} \cdot \underset{f \in \mathcal{O}_1 (E)}{\sup}  \left\Vert Q_1 (f) \right\Vert_p   \leq  c_{n+1} \cdot \tilde{e}_{n} .$$

Thus the measures $\psi_{H_{n+1}^N} (\eta_{n}^N)$ et $\eta_{n}$ satisfy

$$\frac{\sqrt{N}}{2 B_p} \cdot \underset{f \in \mathcal{O}_1 (E)}{\sup}  \left\Vert \psi_{H_{n+1}^N} (\eta_{n}^N) (f)  -  \eta_{n} (f) \right\Vert_p \leq (1+c_{n+1}) \cdot \tilde{e}_{n}  .$$

Applying Lemma \[lemme-phi-Lp\] we also have

$$\frac{\sqrt{N}}{2 B_p} \cdot \underset{f \in \mathcal{O}_1 (E)}{\sup}  \left\Vert A_2 (f) \right\Vert_p  \leq g_{n+1} b_{n+1} (1+c_{n+1}) \cdot \tilde{e}_{n} .$$

Back to (\[decompAA\]), we conclude that $ e_{n+1} \leq 1+ g_{n+1} b_{n+1} (1+c_{n+1}) \cdot \tilde{e}_{n}  = \tilde{e}_{n+1}$.\
This ends the proof of the theorem. $\mathbin{\vbox{\hrule\hbox{\vrule height1.4ex \kern0.6em\vrule height1.4ex}\hrule}}$\
\
We are now in position to obtain a sufficient condition for uniform concentration and $L^p$-mean error bounds w.r.t. time.

If the condition $b_n g_n (1+c_n) \leq a$ is satisfied for some $a < 1$ and any $n$, then we have the uniform error bounds

$$\label{Lp-unif-adapt}
d_p \left( \eta_n^N , \eta_n \right)  \leq  \frac{B_p}{2(1-a)\sqrt{N}} .$$

for any $p$, with the constants $B_p$ introduced in (\[def-Bp\]). In addition, for any $f \in \mathcal{B}_1(E)$, we have the following concentration inequalities:

$$\label{conc-adapt-un}
 \forall s \geq 0, \quad \mathbb{P} \left( \vert \eta_n^N(f) - \eta_n(f) \vert \geq s \right) \leq r_1 (\sqrt{N}.s) e^{-r_2 N s^2}$$

and

$$\label{conc-adapt-deux}
 \forall y \geq 1, \quad \mathbb{P} \left( \vert \eta_n^N(f) - \eta_n(f) \vert \geq \frac{r(1+\sqrt{y})}{\sqrt{N}} \right) \leq e^{-y} ,$$

with the parameters

$$\left\{
    \begin{array}{lll}
         r_1&=& \displaystyle{ e^{1/2} (1-a) }  \\
         r_2&=& \displaystyle{ \frac{1}{2} (1-a)^2 }    \\
         r  &=& \displaystyle{ \frac{2}{1-a} } . 
         
         
    \end{array} 
\right.$$

The inequality (\[Lp-unif-adapt\]) is a direct consequence of Theorem \[theo-statement-adapt\].\
Let us fix $n$, $f \in \mathcal{B}_1(E)$ and set

$$X := \vert \eta_n^N(f) - \eta_n(f) \vert \quad  \textmd{and} \quad \epsilon_N := \frac{1}{(1-a) \sqrt{N}} .$$

In this notation, we have $\displaystyle{ \left\Vert X \right\Vert_p \leq  B_p \cdot \epsilon_N } $ for any $p \geq 1$. Let us fix $s\geq0$. By Markov inequality, for all $t\geq0$ we have

$$\label{ineg-markov-expo}
\mathbb{P} \left( X \geq s \right)  =  \mathbb{P} \left( e^{t  X} \geq e^{t s} \right)  \leq e^{-st} \mathbb{E} \left( e^{t X} \right).$$

Using (\[def-Bp\]), we estimate the Laplace transform $\displaystyle{ \mathbb{E} \left( e^{t X} \right) }$.

$$\begin{aligned}
 \mathbb{E} \left( e^{t X} \right) & = \sum_{p \geq 0} \mathbb{E} \left( \frac{t^p . X^p}{p!} \right) \\
   &  \leq \sum_{p \geq 0} \frac{t^{2p}  \epsilon_N^{2p} }{(2p)!} \frac{(2p)!}{2^p. p!}  +  \sum_{p \geq 0} \frac{t^{2p+1}  \epsilon_N^{2p+1} }{(2p+1)!} \frac{(2p+1)!}{2^p. p! \sqrt{2p+1}}  \\
   &  \leq (1+ t \epsilon_N) e^{\frac{t^2 \epsilon_N^2}{2}}\end{aligned}$$

Taking the inequality (\[ineg-markov-expo\]) with $\displaystyle{ t= \frac{1}{\epsilon_N} \left( \frac{s}{\epsilon_N} -1 \right)  }$, we obtain

$$\mathbb{P} \left( X \geq s \right) \leq  \frac{s}{\epsilon_N} e^{-\frac{1}{2} \left[  \left(\frac{s}{\epsilon_N} \right)^2 -1 \right] } ,$$

which is equivalent to the first concentration inequality (\[conc-adapt-un\]).\
For the second one, we use the inequality

$$u e^{-\frac{u^2}{2} }  =  e^{-(\frac{u^2}{2} - \log u)} \leq  e^{-(\frac{u^2}{2} - u+1)}$$

with $u=\frac{s}{\epsilon_N}$. Then, one can easily show that for all $y\geq1$ and $u\geq 2$, the equation $y = \frac{-u^2}{2} - u+1$ is equivalent to $u = 1+ \sqrt{1+4(y-1)} \leq 2(1+\sqrt{y}) $. Thus $\forall y\geq1$:

$$\mathbb{P} \left( X \geq 2 \epsilon_N (1+\sqrt{y}) \right) \leq e^{-y} ,$$

which is equivalent to (\[conc-adapt-deux\]).\
This ends the proof of the corollary.

[99.]{}

Assaraf, R., Caffarel, M.: A Pedagogical Introduction to Quantum Monte Carlo. Mathematical models and methods for ab initio Quantum Chemistry, 45-73 Springer (2000) doi: 10.1007/978-3-642-57237-1\_ 3

Assaraf, R., Caffarel, M., Khelif, A.: Diffusion Monte Carlo with a fixed number of walkers. Physical Revue E (2000)

Bartoli, N., Del Moral, P.: Simulation & Algorithmes Stochastiques. Cépaduès (2001)

Baker, J. E.: Adaptive Selection Methods for Genetic Algorithms. ICGA1, pp. 101-111. (1985)

Bertrand, C., Hamada, Y., Kado, H.: MRI Prior Computation and Parallel Tempering Algorithm: A Probabilistic Resolution of the MEG/EEG Inverse Problem, Brain Topography, vol 14 num 1. (2001)

Cappé,O., Moulines, E., Rydén, T.: Inference in Hidden Markov Models. Springer, New York, (2005)

Ceperley, D. M.: Path Integrals in the Theory of Condensed Helium. Rev. Modern Phys. 67 279-355. (1995)

Cerf R.: Une théorie asymptotique des algorithmes génétiques. PhD thesis, Université de Montpellier 2, France. (1994)

Ciccotti, G., Hoover, W. G. Molecular-Dynamics Simulation of Statistical-Mechanical Systems. North-Holland, Amsterdam (1986).

Cérou, F., Del Moral, P., Furon, T., Guyader, A.: Sequential Monte Carlo for Rare Event Estimation. Statistics and Computing, vol 22, no 3, 795–808 (2012) doi: 10.1007/s11222-011-9231-6

Cérou, F., Del Moral, P., Guyader, A.: A nonasymptotic variance theorem for unnormalized Feynman-Kac particle models. Annales de l’Institut Henri Poincaré, Probabilités et Statistiques, 47, 629–649 (2011)

Chopin, N.: Central Limit Theorem for Sequential Monte Carlo methods and its application to Bayesian inference. Annals of Statistics, 32, 2385-2411 (2004)

Clapp, T.: Statistical Methods in the Processing of Communications Data. Ph.D. thesis, Cambridge University Engineering Department. (2000)

Del Moral, P.: Feynman-Kac formulae. Genealogical and interacting particle approximations Springer New York, \[575p.\] Series: Probability and Applications (2004).

Del Moral, P.: Nonlinear Filtering: Interacting Particle Solution. Markov Processes and Related Fields, Vol. 2, No. 4 555–579 (1996).

Dawson D.A., Del Moral P.: Large deviations for interacting processes in the strong topology. Statistical Modeling and Analysis for Complex Data Problem P. Duchesne and B. Rémillard Editors, pp. 179–209, Springer (2005)

Del Moral, P., Doucet, A., Jasra, A: On Adaptive Resampling Procedures for Sequential Monte Carlo Methods. Bernoulli, Vol. 18, No. 1, pp. 252-278. (2012)

Del Moral, P., Doucet, A., Jasra, A.: Sequential Monte Carlo Samplers. Journal of the Royal Statistical Society B, 68, 411–436 (2006)

Del Moral, P., Guionnet, A.: On the stability of interacting processes with applications to filtering and genetic algorithms. Annales de l’Institut Henri Poincaré, vol 37, No. 2, 155-194 (2001).

Del Moral P., Guionnet A. A Central Limit Theorem for Non Linear Filtering using Interacting Particle Systems. Annals of Applied Probability, Vol. 9, No. 2, 275-297 (1999).

Del Moral P., Guionnet A. Large Deviations for Interacting Particle Systems. Applications to Non Linear Filtering Problems. Stochastic Processes and their Applications, vol. 78, pp. 69-95 (1998).

Del Moral P., Hu P., Wu L.: On the Concentration Properties of Interacting Particle Processes. Technical Report INRIA Bordeaux Sud-Ouest (ALEA) no 7677 (2011).

Del Moral P., Ledoux M. On the Convergence and the Applications of Empirical Processes for Interacting Particle Systems and Nonlinear Filtering. Journal of Theoret. Probability, Vol. 13, No. 1, pp. 225-257 (2000).

Del Moral P., Miclo L.: On the Convergence and the Applications of the Generalized Simulated Annealing. SIAM Journal on Control and Optimization, Vol. 37, No. 4, 1222-1250, (1999).

Del Moral, P., Miclo, L.: Branching and interacting particle systems approximations of Feynman-Kac formulae with applications to nonlinear filtering. Séminaire de Probabilités XXXIV, Lecture Notes in Mathematics, vol 1729, Springer, Berlin, pp. 1-145 (2000)

Del Moral, P., Rio, E.: Concentration Inequalities for Mean Field Particle Models. Annals of Applied Probabilities, vol 21, no 3, 1017-1052 (2011).

Deutscher, J., Blake, A., Reid, I.: Articulated body motion capture by annealed particle filtering. IEEE Conference on Computer Vision and Pattern Recognition. Vol. 2, pp. 126-133.(2000)

Doucet, A., De Freitas, N., Gordon, N.: Sequential Monte Carlo Methods in Practice. Statistics for engineering and Information Science. Springer, New York. (2001)

Frankel, D., Smit,B. Understanding Molecular Simulation. Academic Press, New York. (1996)

Giraud, F., Minvielle, P., Sancandi, M., Del Moral, P.: Rao-Blackwellised Interacting Markov Chain Monte Carlo for Electromagnetic Scattering Inversion. arXiv stat.AP/1209.4006v2. (2012)

Goldberg, D. E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley (1989)

Hetherington, J. H.: Observations on the statistical iteration of matrices. Physical Revue A, vol 30, 2713-2719 (1984).

Jasra, A., Stephens, D., Doucet, A., Tsagaris, T.: Inference for Lévy Driven stochastic volatility models via adaptive sequential Monte Carlo. Scand. J. Stat. (2008) Künsch, H. R.: Recursive Monte-Carlo filters: algorithms and theoretical analysis. Annals of Statistics, 33, 1983–2021 (2005)

Le Riche, R., Schoenauer, M., Sebag, M.: Un état des lieux de l’optimisation évolutionnaire et de ses implications en sciences pour l’ingénieur, chapter in Modélisation Numérique: défis et perspectives, Vol. 2, Traité Mécanique et Ingénierie des Matériaux, P. Breitkopf and C. Knopf-Lenoir eds., Hermes publ., pp. 187-259 (2007).

Minvielle, P., Doucet, A., Marrs, A., Maskell, S.: A Bayesian approach to joint tracking and identification of geometric shapes in video sequences. Image and Vision Computing. Vol. 28, pp. 111-123. (2010) Neal, R. M.: Annealed importance sampling, Statistics and Computing, vol. 11, pp. 125-139. (2001)

Schäfer, C., Chopin, N.: Sequential Monte Carlo on large binary sampling spaces. Statistics and Computing. (2011) Schweizer, N.: Non-asymptotic error bounds for sequential MCMC and stability of Feynman-Kac propagators. Working Paper, University of Bonn (2012)

Whiteley, N.: Sequential Monte Carlo samplers: error bounds and insensitivity to initial conditions. Working Paper, University of Bristol (2011)
