Pierre Del Moral
email: pierre.del-moral@inria.fr

Arnaud Doucet
email: arnaud@stat.ubc.ca

Interacting Markov Chain Monte Carlo Methods For Solving Nonlinear Measure-Valued Equations

Keywords: Markov chain Monte Carlo methods, sequential Monte Carlo, self-interacting processes, time-inhomogeneous Markov chains, Metropolis-Hastings algorithm, Feynman-Kac formulae Méthodes de Monte Carlo par chaînes de Markov, méthodes de

We present a new interacting Markov chain Monte Carlo methodology for solving numerically discrete-time measure-valued equations. The associated stochastic processes belong to the class of self-interacting Markov chains. In contrast to traditional Markov chains, their time evolution may depend on the occupation measure of the past values. This general methodology allows us to provide a natural way to sample from a sequence of target probability measures of increasing complexity. We develop an original theoretical analysis to analyze the behaviour of these algorithms as the time parameter tends to infinity. This analysis relies on measure-valued processes and semigroup techniques. We present a variety of convergence results including exponential estimates and a uniform convergence theorem with respect to the number of target distributions, yielding what seems to be the first results of this kind for this class of self-interacting models. We also illustrate these models in the context of Feynman-Kac distribution flows.

Introduction

1.1 Nonlinear measure-valued processes Let (S (l) , S (l) ) l≥0 be a sequence of measurable spaces. For every l ≥ 0 we denote by P(S (l) ) the set of probability measures on S (l) . Suppose we have a sequence of probability measures π (l) ∈ P(S (l) ) where π (0) is known and we have for l ≥ 1 the following nonlinear measure-valued equations Φ l (π (l-1) ) = π (l) (1)

for some mappings Φ l : P(S (l-1) ) → P(S (l) ). Except in some particular situations, these measure-valued equations do not admit a closed-form solution.

Being able to solve these equations numerically has numerous applications in nonlinear filtering, global optimization, Bayesian statistics and physics as it would allow us to approximate any sequence of fixed 'target' probability distributions (π (l) ) l≥0 . For example, in a nonlinear filtering framework π (l) corresponds to the posterior distribution of the state of an unobserved dynamic model at time l given the observations collected from time 0 to time l. In an optimization framework, π (l) could correspond to a sequence of annealed versions of a distribution π that we are interested in maximizing. In both cases, Φ l is a Feynman-Kac transformation [START_REF] Moral | Feynman-Kac formulae[END_REF].

In recent years, there has been considerable interest in the development of mean field interacting particle interpretations of measure-valued equations of the form (1) which we briefly review here.

Mean field particle interpretations

These mean field particle interpretations are sometimes referred to as sequential Monte Carlo methods, particle filters and population Monte Carlo methods when the mappings Φ l are Feynman-Kac transformations [START_REF] Moral | Feynman-Kac formulae[END_REF]. The central idea is to construct a Markov chain X (l) = (X (l) p ) 1≤p≤N taking values in the product spaces (S (l) ) N so that the empirical measures π (l)

N := 1 N N p=1 δ X (l)
p approximate the current distribution π (l) as N ↑ ∞. In the simpler version, we construct inductively X (l) = (X (l) p ) 1≤p≤N by sampling N independent random variables with common law Φ l (π (l-1) N

). The rationale behind this is that the resulting particle measure π (l)

N should be a good approximation of π (l) as long as π (l-1) N is a good approximation of π (l-1) . More formally, X (l) is an (S (l) ) N -valued Markov chain with elementary transitions given by the following formula

P (X (l) 1 , . . . , X (l) N ) ∈ dx | X (l-1) = N p=1 Φ l   1 N 1≤q≤N δ X (l-1) q   (dx p ) (2)
In the above display, dx = d(x 1 , . . . , x N ) = dx 1 × . . . × dx N stands for an infinitesimal neighborhood of a point in the product space (x 1 , . . . , x N ) ∈ (S (l) ) N . For Feynman-Kac transformations, these interacting particle models have recently become an extensively studied subject in nonlinear filtering and in Bayesian statistics; for a review see the pair of books [START_REF] Moral | Feynman-Kac formulae[END_REF][START_REF]Sequential Monte Carlo Methods in Practice[END_REF]. In this framework, the convergence analysis of these stochastic particle algorithms is now RR n°0123456789 inria-00227508, version 4 -5 Feb 2008 well understood. A variety of theoretical results are available, including sharp propagations of chaos properties, fluctuation and large deviations theorems, as well as uniform convergence results with respect to the parameter l.

A severe limitation of these stochastic algorithms is that, it is impossible to iteratively increase the precision of the numerical approximation. An alternative class of stochastic simulations algorithms which allows us to iteratively increase the precision are MCMC methods; see [START_REF] Robert | Monte Carlo Statistical Methods[END_REF] for a review. However, standard MCMC methods do not apply to this framework.

Self-interacting Markov chains

We propose here a new class of interacting Markov chain Monte Carlo methods (i-MCMC ) to solve these nonlinear measure-valued equations numerically. These i-MCMC methods can be described as adaptive and dynamic simulation algorithms which take advantage of the information carried by the past history to increase the quality of the next series of samples. One critical aspect of i-MCMC as opposed to standard MCMC methods is that it provides a natural adaptation and reinforced learning strategy of the physical or engineering evolution equation at hand. This type of reinforcement with the past is observed frequently in nature and society, where "beneficial" interactions with the past history tend to be repeated. Moreover, in contrast to more traditional mean-field type particle models and related sequential Monte Carlo techniques, these stochastic algorithms can increase the precision and performance of the numerical approximations iteratively.

The origins of i-MCMC methods can be traced back to a pair of articles [START_REF] Del Moral | Self-interacting Markov chains[END_REF][START_REF] Del Moral | On convergence of chains with time empirical self-interactions[END_REF] presented by the first author in collaboration with Laurent Miclo. These studies are concerned with biology-inspired self-interacting Markov chain models with applications to genetic type algorithms involving a competition between the natural reinforcement mechanisms and the potential attraction of a given exploration landscape [START_REF] Del Moral | Self-interacting Markov chains[END_REF][START_REF] Del Moral | On convergence of chains with time empirical self-interactions[END_REF]. These lines of research have been extended to the MCMC methodology in the joint articles of the authors with Christophe Andrieu and Ajay Jasra [START_REF] Andrieu | Non-Linear Markov chain Monte Carlo via self-interacting approximations[END_REF], as well as in the more recent article of the authors with Anthony Brockwell [START_REF] Brockwell | Sequentially interacting Markov chain Monte Carlo[END_REF]. Related ideas have also appeared in computational chemistry [START_REF] Lyman | Resolution exchange simulation with incremental coarsening[END_REF].

In the present article, we design a new general class of i-MCMC models. Roughly speaking, these stochastic models are defined as follows: Firstly, at level 0 we run an MCMC algorithm to obtain a chain X (0) n with a prescribed target distribution π (0) . Then, we use the occupation measure of the chain X (0) judiciously to design a second MCMC algorithm to generate X (1) n at level 1 with a target measure π (1) which is typically more complex than π (0) . These two mechanisms are combined online so that the pair process interacts with the occupation measure of the system at each iteration n. More formally, the elementary transition X

(1) n X (1)
n+1 of the chain X (1) at time n depends on the occupation measure of the chain X (0) p , from the origin p = 0, up to the current time p = n. This strategy allows us to design a series of MCMC samplers (X (l) ) l≥0 with a prescribed sequence of target distributions (π (l) ) l≥0 of increasing complexity. These i-MCMC samplers are sometimes called self-interacting Markov chains (SIMC ) in reference to the fact that the complete Markov chain X X m n+1 that depend on the occupation measure of the whole system X m p from the origin p = 0 up to the current time p = n. Note that here the time index n corresponds to the number of iterations of the i-MCMC algorithm.

From the pure mathematical point of view the convergence analysis of selfinteracting chains is essentially based on the study of the stability properties of sophisticated Markov chains with elementary transitions depending in a nonlinear way on the occupation measure of the chains. Hence the theoretical analysis of these models is much more involved than the one of traditional Markov chains. It also differs from the more traditional mean field interacting interpretations models developed in [START_REF] Moral | Feynman-Kac formulae[END_REF]. Besides the introduction of a new methodology, our main contribution is a refined theoretical analysis based on measure-valued processes and semigroup methods to analyze their asymptotic behavior as the time parameter n tends to infinity. Additionally, we also present a variety of convergence results including exponential estimates and a uniform convergence theorem with respect to the level index l. We make no restriction on the state spaces and we illustrate these models in the context of abstract Feynman-Kac distribution flows. Finally, we present an avenue of new research problems.

The rest of the paper is organized as follows:

The main notation and convention used in this work are introduced in the brief preliminary section 1.4. The i-MCMC methodology is detailed in section 1.5. The main results of the article are presented in section 1. [START_REF]Sequential Monte Carlo Methods in Practice[END_REF]. Several examples of i-MCMC models are provided in section 2, including Feynman-Kac path integral distributions and interacting Metropolis-Hasting algorithms. This section also provides a discussion on how to combine the mean field particle interpretation models with i-MCMC.

Section 3 is concerned with the asymptotic behavior of an abstract class of time inhomogeneous Markov chains. In section 3.2, we present a preliminary resolvent analysis to estimate the regularity properties of Poisson operator and invariant measure type mappings. In section 3.3, we apply these results to study the law of large numbers and the concentration properties of time inhomogeneous Markov chains.

In section 4 we discuss the regularity properties of a series of time averaged semigroups on distribution flow state spaces. The asymptotic analysis of i-MCMC models are discussed in section 5. The strong law of large numbers is presented in section 5.2. We also provide an L r -mean error bound for the occupation measures of the i-MCMC model at each level l. In section 5.3, we discuss the long time behavior of these stochastic models in terms of the exponential stability properties of a time averaged type semigroup associated with the flow of target measures. We prove a uniform convergence theorem with respect to the number of levels.

The asymptotic analysis of the occupation measures associated with the complete self-interacting model on a fixed series of levels is discussed in section 6. The L r -mean error bounds and the concentration analysis are presented respectively in section 6.1 and in section 6.2. The final section, section 7, is concerned with contraction properties of time averaged Feynman-Kac distribution flows.

RR n°0123456789

inria-00227508, version 4 -5 Feb 2008

Notation and conventions

For the convenience of the reader we have collected some of the main notation and conventions used in the article. We also recall some more or less well-known regularity properties of integral operators used further in the article.

We denote respectively by M(E), M 0 (E), P(E), and B(E), the set of all finite signed measures on some measurable space (E, E), the convex subset of measures with null mass, the set of all probability measures, and the Banach space of all bounded and measurable functions f on E. We equip B(E) with the uniform norm f = sup x∈E |f (x)|. We also denote by B 1 (E) ⊂ B(E) the unit ball of functions f ∈ B(E) with f ≤ 1, and by Osc 1 (E), the convex set of E-measurable functions f with oscillations less than one; that is,

osc(f ) = sup {|f (x) -f (y)| ; x, y ∈ E} ≤ 1
We let µ(f ) = µ(dx) f (x), be the Lebesgue integral of a function f ∈ B(E), with respect to a measure µ ∈ M(E). We slightly abuse the notation and sometimes denote by µ(A) = µ(1 A ) the measure of a measurable subset A ∈ E.

We recall that a bounded integral operator M from a measurable space (E, E) into an auxiliary measurable space (F, F) is an operator f → M (f ) from B(F ) into B(E) such that the functions

M (f )(x) = F M (x, dy) f (y) ∈ R
are E-measurable and bounded, for any f ∈ B(F ). A bounded integral operator M from a measurable space (E, E) into an auxiliary measurable space (F, F) also generates a dual operator µ → µM from M(E) into M(F ) defined by (µM )(f ) := µ(M (f )).

We denote by M := sup f ∈B1(F ) M (f ) the norm of the operator f → M (f ) and we equip the Banach space M(E) with the corresponding total variation norm µ = sup f ∈B1(E) |µ(f )|. In this slightly abusive notation, we have

M := sup x∈E sup f ∈B1(F ) |δ x M (f )| = sup x∈E δ x M
where δ x stands for the Dirac measure at the point x ∈ E. We recall that the norm of any bounded integral operator M with null mass M (1) = 0 satisfies

M = sup f ∈B1(F ) M (f ) = 2 sup f ∈Osc1(F ) M (f )
When M has a constant mass, that is M (1) (x) = M (1) (y) for any (x, y) ∈ E 2 , the operator µ → µM maps M 0 (E) into M 0 (F ). In this situation, we let β(M ) be the Dobrushin coefficient of a bounded integral operator M defined by the following formula

β(M ) := sup {osc(M (f )) ; f ∈ Osc 1 (F )}
By construction, we have M (f )/β(M ) ∈ Osc 1 (E) as soon as β(M ) = 0, so that

µM = 2 sup f ∈Osc1(F ) |µM (f )| ≤ β(M ) 2 sup f ∈Osc1(E) |µ(f )| =⇒ µM ≤ β(M ) µ INRIA
Using the fact that δ x -δ y = 2 for x = y and

β(M ) = sup f ∈Osc1(F ) sup (x,y)∈E 2 |(δ x M -δ y M )(f )| = sup (x,y)∈E 2 δ x M -δ y M δ x -δ y ≤ sup µ∈M0(E) µM µ
we prove that

β(M ) = sup µ∈M0(E) µM µ = 1 2 sup (x,y)∈E 2 δ x M -δ y M
is also the norm of the operator

µ ∈ M 0 (E) → µM ∈ M 0 (F )
That is, we have that

β(M ) = sup µ∈M0(E) ( µM / µ )
More generally, for every bounded integral operator K from an auxiliary measurable space (E , E ) into an measurable space (E, E), with null mass K(1) = 0, we have

KM = sup x∈E (δ x K)M ≤ β(M ) sup x∈E (δ x K) =⇒ KM ≤ β(M ) K
Unless otherwise stated, we use the letter C to denote a universal constant whose value may vary from line to line. Finally, we shall use the conventions ∅ = 0 and ∅ = 1.

The i-MCMC methodology

We describe here the i-MCMC methodology to numerically solve (1). We consider a Markov transition M (0) from S (0) into itself and a collection of Markov transitions M (l) µ from S (l) into itself, indexed by the parameter l ≥ 0 and the set of probability measures µ ∈ P(S (l-1) ). We further assume that the invariant measure of each operator M (l) µ is given by Φ l (µ); that is we have that

∀l ≥ 0 ∀µ ∈ P(S (l) ) Φ l (µ) = Φ l (µ)M (l) µ
For l = 0, we use the convention Φ 0 (π (-1) ) = π (0) and M (0) µ = M (0) . For every l ≤ m, we denote by η (l) ∈ P(S (l) ) the image measure of a measure η ∈ P( 0≤l≤m S (l) ) on the l-th level set S (l) . We also fix a series of probability measures ν k on S (k) , with k ≥ 0.

We let X (0) := (X (0) n ) n≥0 be a Markov chain on S (0) with initial distribution ν 0 and elementary Markov transitions M (0) . For every k ≥ 1, given a realization of the chain X (k-1) := (X of the chain at level (k-1); that is we have that

(k-1) n ) n≥0 , the k-th level chain X (k) n
P(X (k) n+1 ∈ dx | X (k-1) , X (k) n ) = M (k) η (k-1) n (X k n , dx) (3)
with

η (k-1) n := 1 n + 1 n p=0 δ X (k-1) p
The rationale behind this is that the k-th level chain X (k) n behaves asymptotically as a Markov chain with time homogeneous elementary transition

M (k) π (k-1)
as long as η (k-1) n is a good approximation of π (k-1) . In the special case where

M (k) µ (x k , .) = Φ k (µ), the k-th level chain (X (k) n ) n≥1 is a collection of independent random variables with distributions (Φ k (η (k-1)
n-1 )) n≥1 ; that is we have that

P((X (k) 1 , . . . , X (k) n ) ∈ dx | X (k-1) ) = n p=1 Φ k   1 p 0≤q<p δ X (k-1) q   (dx p ) (4)
In the above display dx = d(x 1 , . . . , x n ) = dx 1 × . . . × dx n stands for for an infinitesimal neighborhood of a generic path sequence (x 0 , . . . , x n ) ∈ (S (k) ) n . We end this section with a self-interacting Markov chain interpretation of the stochastic algorithm discussed above. We consider the product space E m := (S (0) × . . . × S (m) ) and we let (K (m) η ) η∈P(Em) be the collection of Markov transitions from E m into itself given by

∀x := (x 0 , . . . , x m ) ∈ E m K (m) η (x, dy) = 0≤l≤m M (l) η (l-1) (x l , dy l ) (5)
In the above display dy := dy 0 × . . . × dy m stands for for an infinitesimal neighborhood of a generic point y := (y 0 , . . . , y m ) ∈ E m , and η (l) ∈ P(S (l) ) stands for the image measure of a measure η ∈ P(E m ) on the l-th level set S (l) , with m ≥ l. In this notation, it is readily checked that

X m n := (X (0) n , . . . , X (m) n ) is an E m -valued self-interacting Markov chain with elementary transitions de- fined by P(X m n+1 ∈ dy | X m 0 , . . . , X m n ) = K (m) η [m] n (X m n , dy) with η [m] n = 1 n + 1 n p=0 δ X m n (6)

Statement of some results

We further assume that for any l ≥ 1, the mappings Φ l : P(S (l-1) ) → P(S (l) ) satisfy the following regularity condition for any pair of measures (µ, ν) ∈ P(S (l-1) )

2 ∀l ≥ 0 ∀f ∈ B(S (l) ) |[Φ l (µ) -Φ l (ν)] (f )| ≤ |[µ -ν] (g)| Γ l (f, dg) (7)
INRIA for some bounded integral operator Γ l from B(S (l) ) into B(S (l-1) ), with

B(S (l-1) ) Γ l (f, dg) g ≤ Λ l f and Λ l < ∞
We also suppose that there exist some integer n l ≥ 0 and some constant c l such that we have

M (l) µ -M (l) ν ≤ c l µ -ν and b l (n l ) := sup µ∈P(S (l-1) ) β((M (l) µ ) n l ) < 1 (8)
In the special case where

M (l) µ (x l , .) = Φ l (µ), the second condition is trivially met for n l = 1 with b l (n l ) = 0.
The first condition is related to the Lipschitz property of the mapping Φ l (µ). In this particular situation, it takes the following form

Φ l (µ) -Φ l (ν) ≤ c l µ -ν
Under the conditions ( 8), for every η ∈ P(E m ), the invariant measure 5) is given the tensor product measure

ω K (m) η (η) ∈ P(E m ) of K (m) η defined in (
ω K (m) η (η) = π (0) ⊗ Φ 1 (η (0) ) ⊗ . . . ⊗ Φ m (η (m-1) ) (9)
We observe that the tensor product measure

π [m] := π (0) ⊗ . . . ⊗ π (m) (10)
is a fixed point of the mapping ω K (m)

η : η ∈ P(E m ) → ω K (m) η (η) ∈ P(E m ).
In this notation, our main results are basically stated as follows.

Theorem 1.1 For any r ≥ 1, m ≥ 1, and any function f ∈ B(E m ) we have

sup n≥1 √ n E η [m] n (f ) -π [m] (f ) r < ∞
Under some addition regularity conditions, we have the exponential inequality

∀t > 0 lim sup n→∞ 1 n log P η [m] n -π [m] (f ) > t < - t 2 2σ 2 m
for some finite constant σ m < ∞ as well as the following uniform convergence estimate sup

k≥0 sup n≥1 n α/2 E η (k) n (f k ) -π (k) (f k ) r < ∞
for some parameter α ∈ (0, 1], and for any collection of functions

(f k ) k≥0 ∈ k≥0 B 1 (S (k) ).
We end this introduction with a series of comments and open research questions.

Firstly, the mean error bounds and the exponential estimates presented above suggest the existence of Gaussian fluctuations of the occupation measures η

[m] n around their limiting value π [m] , with a fluctuation rate √ n. We will study these fluctuations and the associated large deviations principles in a forthcoming article.

RR n°0123456789

inria-00227508, version 4 -5 Feb 2008

Surprisingly enough, the decays to equilibrium presented in theorem 1.1 differ from the three types of decays exhibited in the pair of articles [START_REF] Del Moral | Self-interacting Markov chains[END_REF][START_REF] Del Moral | On convergence of chains with time empirical self-interactions[END_REF] for evolutionary type self-interacting Markov chains. To understand the main differences between these classes of interacting processes, we recall that the decay rates to equilibrium often depends on the contraction coefficient of the invariant measure mapping associated with a given self-interacting model. In our context, these mappings are not necessarily contractive. Nevertheless, we shall see in section 6 that the semigroup associated with these mappings becomes constant after a sufficiently large number of iterations. In this sense, the selfinteracting models discussed in the present article are more regular than the one analyzed in [START_REF] Del Moral | Self-interacting Markov chains[END_REF][START_REF] Del Moral | On convergence of chains with time empirical self-interactions[END_REF].

Last but not least, the uniform convergence estimate with respect to the number of levels depends on the stability properties of a time average semigroup associated with the mappings Φ l . The contraction properties of this new class of nonlinear semigroups on the flow of measures are studied in section 7 in the context of Feynman-Kac models. Roughly speaking, we show that the stability properties of the reference Feynman-Kac semigroups can be transferred to study the associated time averaged models. In more general situations this question remains open.

Motivating applications 2.1 Feynman-Kac models

The main example of mappings Φ l considered here are the Feynman-Kac transformations given below

∀l ≥ 0 ∀(µ, f ) ∈ (P(S (l) ) × B(S (l+1) )) Φ l+1 (µ)(f ) := µ(G l L l+1 (f ))/µ(G l ) (11)
where G l is a positive potential function on S (l) , and L l+1 stands for a collection of Markov transitions from S (l) into S (l+1) . In this situation, the solution of the measure-valued equation ( 1) is given by the normalized Feynman-Kac distribution flow described below

π (l) (f ) = γ (l) (f )/γ (l) (1) with γ (l) (f ) := E   f (Y l ) 0≤k<l G k (Y k )  
where (Y l ) l≥0 stands for a Markov chain taking values in the state spaces (S (l) ) l≥0 , with initial distribution π (0) and Markov transitions (L l ) l≥1 . These probabilistic models arise in a variety of applications including nonlinear filtering and rare event analysis as well the spectral analysis of Schrödinger type operators and directed polymer analysis [START_REF] Moral | Feynman-Kac formulae[END_REF]. Even if they look innocent, these Feynman-Kac distribution flows are complex mathematical objects. For instance, the reference Markov chain may represent the paths from the origin up to the current time of an auxiliary sequence of random variables Y l taking values in some state spaces E l ; that is, we have that

Y l := (Y 0 , . . . , Y l ) ∈ S (l) := (E 0 × . . . × E l ) (12)
We also underline that the unnormalized measures γ (l) are expressed in terms of integrals on path spaces and we recall that γ (l) can be expressed in terms of the flow of measures (π (k) ) 0≤k<l with the following formulae

γ (l) (f ) = π (l) (f ) 0≤k<l π (k) (G k )
Thus, the i-MCMC methodology allows us to estimate these unnormalized flows and thus the normalizing constants γ (l) (1) by replacing in the above displayed formula the measures π (k) by their approximations.

In this context, the right hand side product of the formula (4) associated to the i-MCMC algorithm takes the following form

Φ k   1 p 0≤q<p δ X (k-1) q   = 0≤q<p G k-1 (X (k-1) q ) 0≤q <p G k-1 (X (k-1) q ) L k (X (k-1) q , .
)

From this observation, we see that each random state X (k)

p , with 1 ≤ p ≤ n, is sampled according to two separate genetic type mechanisms. Firstly, we randomly select one state X (k-1) q at level (k -1) with a probability proportional to its potential value G k-1 (X (k-1) q

). Then, we randomly evolve from this state according to the exploration transition L k . This biology-inspired i-MCMC model can be interpreted as a spatial branching and interacting process. In this interpretation, the k-th chain tends to duplicate individuals with large potential values, at the expense of individuals with low potential values. The selected offspring randomly evolve from the state space S (k-1) to the state space S (k) at the next level. The same description for path space models (12) coincides with the evolution of genealogical tree based i-MCMC models.

For the Feynman-Kac transformations (11), we proved in [START_REF] Moral | Feynman-Kac formulae[END_REF] that the condition (8) ensuring convergence of the algorithm is satisfied with c l = β(L l )/ l-1 (G) as soon as the potential functions satisfy the following condition (G) There exists a sequence ( l (G)) l≥0 ∈ (0, 1) N such that

∀l ≥ 0 ∀(x, y) ∈ (S (l) ) 2 G l (x) ≥ l (G) G l (y)

Interacting Metropolis-Hastings models

Suppose the reference state spaces S (l) are given for any l ≥ 1 by

S (l) = S (l-1) × E l
where E l is an auxiliary sequence of measurable spaces. For l = 0, we set S (0) = E 0 . Returning to the Feynman-Kac model presented in (11), we can choose

π (l) (d(x 0 , . . . , x l-1 , x l )) ∝ π (0) (dx 0 ) l k=1 L k (x k-1 , dx k ) ×   0≤k<l G k (x k )   ∝ π (l-1) (d(x 0 , . . . , x l-1 )) L l (x l-1 , dx l ) G l-1 (x l-1
).

RR n°0123456789 inria-00227508, version 4 -5 Feb 2008

We introduce the following integral operator from S (l-1) into E l

P l ((x 1 , . . . , x l-1 ), dx l ) = L l (x l-1 , dx l ) G l-1 (x l-1 ). ( 13
)
In this scenario, it is sensible to propose to use for

M (l)
µ in the i-MCMC algorithm the following Markov kernel on the product space S (l) indexed by the set of measures µ ∈ P(S (l-1) )

M (l) µ (x, dy) = (µ ⊗ Q l )(dy) (1 ∧ r l (x, y)) + 1 -S (l) (1 ∧ r l (x, z)) (µ ⊗ Q l )(dz) δ x (dy)
where Q l is a Markov transition from S (l-1) into E l and for every (u, v) and (w, z) ∈ (S (l-1) × E l )

r l ((u, v), (w, z)) := d (Q l (u, .) ⊗ P l (w, .)) d (P l (u, .) ⊗ Q l (w, .)) (v, z) (14)
where we assume that

Q l (u, .) ⊗ P l (w, .) << P l (u, .) ⊗ Q l (w, .). It can be checked that the kernel M (l) µ is nothing but a Metropolis-Hastings kernel of proposal distribution µ ⊗ Q l and invariant distribution Φ l (µ)(dx) = 1 µP l (1) (µ ⊗ P l ) (dx)
and that we indeed have Φ l (π (l-1) ) = π (l) . We can also easily establish that for any pair of measures (µ, ν) ∈ P(S (l-1) ) 2

M (l) µ -M (l) ν ≤ 2 µ -ν
so that the first condition on the left hand side of ( 8) is satisfied. Under the additional assumption that for any (u, v) ∈ (S (l-1) × E l )

dP l (u, .) dQ l (u, .) (v) ≤ C l it follows from [8, Theorem 2.1] that β(M (l) µ ) ≤ (1 -C -1 l )
from which we conclude that the second condition on the right hand side of ( 8) is met with n l = 1 and b l (n l ) = (1 -C -1 l ).

Mean field particle and i-MCMC models

As mentioned in the introduction, in contrast to mean field particle models presented in (1.2), we emphasize that the precision parameter n of i-MCMC models is not fixed but it increases at every time step. There exist several ways to combine a mean field particle model with an i-MCMC model.

For instance, suppose we are given a realization of a mean field algorithm

X (l) = (X (l)
p ) 1≤p≤N with a precision parameter N . One natural way to initialize the i-MCMC model is to start with a collection of initial random states X (l) 0 sampled according to the N -particle approximation measures

ν l = π (l) N := 1 N N i=1 δ X (l) i
Another strategy is to use the N -particle approximation measures π

η (N,k-1) n = n + 1 N + n + 1 η (k-1) n + N N + n + 1 π (k-1) N
The convergence analysis of these two natural combinations of a mean field particle model with an i-MCMC algorithm can be conducted easily using the techniques developed in this article.

Time inhomogeneous Markov chains 3.1 Description of the models

We consider a collection of Markov transitions K η on some measurable space (E, E) indexed by the set of probability measures η ∈ P(F ) on some possibly different measurable space (F, F). We further assume that for any pair of measures (η, µ) ∈ P(F ) 2 and some integer n 0 ≥ 0 we have

K η -K µ ≤ c η -µ and b(n 0 ) := sup η∈P(E) β(K n0 η ) < 1 (15)
We associate with the collection of transitions K η an E-valued inhomogeneous Markov chain X n with elementary transitions defined by

P(X n+1 ∈ dx | X 0 , . . . , X n ) = K µn (X n , dx)
where µ n is a sequence of possibly random distributions on F that only depends on the random sequence (X 0 , . . . , X n ). More precisely, µ n is a measurable random variable with respect to the σ-field generated by the random states X p from the origin p = 0, up to the current time horizon p = n. We further assume that the variations of the flow µ n are controlled by some sequence of random variables (n) in the sense that

∀n ≥ 0 µ n+1 -µ n ≤ (n)
We let (n) be the mean variation of the distribution flow (µ p ) 0≤p≤n ; that is we have

(n) := 1 (n + 1) n p=0 (p) RR n°0123456789

inria-00227508, version 4 -5 Feb 2008

For self-interacting Markov chains, we have F = E and the measures µ p coincide with the occupation measures of the chain up to the current time. In this particular situation, we have

µ n = η n := 1 (n + 1) n p=0 δ Xp =⇒ (n) ≤ 2 (n + 2) ( 16
)
This implies that

(n) ≤ 2 (n + 1) log (n + 2)
Under assumption (15), every elementary transition K µn (x, dy) admits an invariant measure

ω(µ n )K µn = ω(µ n ) ∈ P(E)
For sufficiently small variations (n) of the distribution flow µ n , we expect that the occupation measures η n have the same asymptotic behavior as the mean values ω n (µ) of the instantaneous invariant measures ω(µ p ) from the origin p = 0 up to the current time n. That is, in some sense, for large values of the time horizon we have

η n ω n (µ) := 1 n + 1 n p=0 ω(µ p ) (17)

A resolvent analysis

We recall that assumption (15) ensures that K η has a unique invariant measure for any η ∈ P(F ) ω(η)K η = ω(η) ∈ P(E)

and the pair of sums given by

α(η) := n≥0 β(K n η ) ∈ [1, ∞) and n≥0 K n η -ω(η) (f ) (18)
are absolutely convergent for any f ∈ B(E). The main simplification of these conditions comes from the fact that the resolvent operator

P η : f ∈ B(E) → P η (f ) := n≥0 K n η -ω(η) (f ) ∈ B(E)
is a well-defined solution of the Poisson equation

(K η -Id)P η = (ω(η) -Id) ω(η)P η = 0
Proposition 3.1 For any η ∈ P(F ), P η is a bounded integral operator on E and we have

( P η /2) ∨ β(P η ) ≤ α(η) ≤ n 0 1 -β(K n0 η ) INRIA inria-00227508,

version 4 -5 Feb 2008

Proof:

The fact that β (P η ) ≤ α(η) is readily deduced from the following decomposition

P η (f )(x) -P η (f )(y) := n≥0 K n η (f )(x) -K n η (f )(y)
Indeed, using this decomposition we find that osc(P η (f ))

≤ n≥0 osc(K n η (f )). Recalling that osc(K n η (f )) ≤ β(K n η ) osc(f ), we conclude that osc(P η (f )) ≤   n≥0 β(K n η )   osc(f ) ⇒ β(P η ) ≤ n≥0 β(K n η )
In much the same way, we use the fact that

P η (f )(x) = n≥0 K n η (f )(x) -K n η (f )(y) ω(η)(dy)
to check that

P η (f ) ≤ n≥0 osc(K n η (f ))
and

P η (f ) ≤   n≥0 β(K n η )   osc(f ) ⇒ P η ≤ 2 n≥0 β(K n η )
To prove that α(η) ≤ Since we have

β(K (p-1)n0+r η ) ≤ β(K (p-1)n0 η ) β(K r η ) ≤ β(K n0 η ) (p-1) β(K r η ) ≤ β(K n0 η ) (p-1)
we conclude that α(η)

≤ n 0 p≥0 β(K n0 η ) p = n0 1-β(K n 0 η )
. The end of the proof of the proposition is now completed. Proposition 3.2 For any pair of measures (η, µ) ∈ P(F ) 2 , we have

ω(η) -ω(µ) ≤ δ n0 (η, µ) η -µ (19)
and

P µ -P η ≤ α(η) [2c α(µ) + δ n0 (η, µ)] η -µ
for some finite constant δ n0 (η, µ) such that

δ n0 (η, µ) ≤ cn 0 1 -(β(K n0 η ) ∧ β(K n0 µ )) (20)
RR n°0123456789

inria-00227508, version 4 -5 Feb 2008

Proof:

The proof of the first assertion is based on the following decomposition

ω(η) -ω(µ) = ω(η)(K n0 η -K n0 µ ) + [ω(η) -ω(µ)] K n0 µ Using the fact that [ω(η) -ω(µ)] K n0 µ ≤ β(K n0 µ ) ω(η) -ω(µ)
we find that

ω(η) -ω(µ) ≤ 1 1 -(β(K n0 µ ) ∧ β(K n0 η )) ω(η)(K n0 η -K n0 µ ) (21)
On the other hand, we have

ω(η)(K n0 η -K n0 µ ) ≤ K n0 η -K n0 µ ω(η) = K n0 η -K n0 µ
Using the decomposition

K n0 η -K n0 µ = n0-1 p=0 K p µ (K η -K µ )K n0-(p+1)
η we find that

K n0 η -K n0 µ ≤ n0-1 p=0 K p µ (K η -K µ )K n0-(p+1) η
For any 0 ≤ p ≤ n 0 we have

K p µ (K η -K µ )K n0-(p+1) η ≤ K p µ K η -K µ K n0-(p+1) η ≤ K η -K µ ≤ c η -µ
from which we conclude that

K n0 η -K n0 µ ≤ cn 0 η -µ =⇒ ω(η)(K n0 η -K n0 µ ) ≤ cn 0 η -µ
The proof of ( 19) is now a direct consequence of (21)

The proof of the second assertion is based on the following decomposition

P η -P µ = P µ (K η -K µ )P η + [ω(µ) -ω(η)] P η
To check this formula, we first use the fact that K µ P µ = P µ K µ to prove that

P µ (K µ -Id) = (K µ -Id)P µ = (ω(µ) -Id)
This yields that P µ (K µ -Id)P η = (ω(µ) -Id)P η

Using the Poisson equation and using the fact that P µ (1) = 0 we also have the decomposition

P µ (K η -Id)P η = P µ (ω(η) -Id) = -P µ INRIA inria-00227508,

version 4 -5 Feb 2008

Combining these two formulae, we conclude that

P µ (K η -K µ )P η = [P η -P µ ] -[ω(µ) -ω(η)] P η
It follows that

P η -P µ ≤ P µ (K η -K µ )P η + [ω(µ) -ω(η)] P η
The term on the right hand side is easily estimated. Indeed, under our assumptions we readily find that

[ω(µ) -ω(η)] P η ≤ β(P η ) ω(η) -ω(µ) ≤ α(η) ω(η) -ω(µ) ≤ α(η) δ n0 (η, µ) η -µ
On the other hand, we have

P µ (K η -K µ )P η ≤ β(P η ) P µ (K η -K µ ) ≤ β(P η ) P µ K η -K µ
from which we conclude that

P µ (K η -K µ )P η ≤ 2c α(µ)α(η) η -µ
The end of the proof is now clear.

L r -inequalities and concentration analysis

Firstly, we examine some of the consequences of the pair of regularity conditions presented in (15). The second condition ensures that the functions α(η) and δ n0 (η, µ) introduced in (18) and (20) are uniformly bounded; that is we have

1 ≤ a(n 0 ) := sup η∈P(F ) α(η) ≤ n 0 1 -b(n 0 ) (22) and d(n 0 ) := sup (η,µ)∈P(F ) 2 δ n0 (η, µ) ≤ cn 0 1 -b(n 0 ) < ∞ (23)
We recall that ω n (µ) is defined in (17). We are now in a position to state and prove the main result of this section.

Theorem 3.3 For any n ≥ 0, f ∈ B 1 (E) and r ≥ 1 we have the estimate

E (|[η n -ω n (µ)] (f )| r ) 1 r ≤ e(r) n 0 1 -b(n 0 ) 2 1 √ n + 1 + c E( (n) r ) 1 r
for some finite constant e(r) < ∞ whose value only depends on the parameter r. In addition, for any δ ∈ (0, 1) and any time horizon n ≥ 1, the probability that

|[η n -ω n (µ)] (f )| ≤ n0 1-b(n0) 2 log (2/δ) n+1 + (1 + c) 4n0 1-b(n0) (n) ∨ 1 n+1
is greater than (1 -δ) (where c is the constant introduced in (15)).

RR n°0123456789 inria-00227508, version 4 -5 Feb 2008

Corollary 3.4 For the self-interacting Markov chain associated with the occupation measure distribution flow (16), we have for any n ≥ 0, f ∈ B 1 (E) and any r ≥ 1

√ n + 1 E (|[η n -ω n (µ)] (f )| r ) 1 r ≤ e(r) (1 + c) n 0 1 -b(n 0 ) 2
for some finite constant e(r) < ∞ whose value only depends on the parameter r. In addition, for any δ ∈ (0, 1) and any time horizon n ≥ 1, the probability that

|[η n -ω n (µ)] (f )| ≤ 2n 0 1 -b(n 0 ) 2 2 n + 1 log (2/δ) + 2(1 + c) is greater than (1 -δ).
Proof of theorem 3.3: Firstly, we examine some consequences of the regularity conditions presented in (15) on the resolvent function P η introduced in (18). Using proposition 3.1 and proposition 3.2 we find the following uniform estimates sup η∈P(F )

(( P η /2) ∨ β(P η )) ≤ n 0 1 -b(n 0 ) and P µ -P η ≤ 3c n 0 1 -b(n 0 ) 2 µ -η (24)
In addition, using proposition 3.2 again we find that the invariant measure mapping ω is uniform Lipschitz in the sense that

ω(η) -ω(µ) ≤ cn 0 1 -b(n 0 ) η -µ
For any n ≥ 0 and any function f ∈ B 1 (E), we set

I n (f ) := (n + 1) [η n -ω n (µ)] (f ) = n p=0 [f (X p ) -ω(µ p )(f )]
Using the Poisson equation, we have

[Id -ω(µ p )] = (Id -K µp )P µp
From this formula, we find the decomposition

[f (X p ) -ω(µ p )(f )] = P µp (f )(X p ) -K µp (P µp (f ))(X p ) = P µp (f )(X p ) -P µp (f )(X p+1 ) + ∆M p+1 (f ) (25)
with the increments

∆M p+1 (f ) := P µp (f )(X p+1 ) -K µp (P µp (f ))(X p )
of the martingale M n+1 (f ) defined by

M n+1 (f ) := n+1 p=1 ∆M p (f ) = n+1 p=1 P µp-1 (f )(X p ) -K µp-1 (P µp-1 (f ))(X p-1 )

INRIA

inria-00227508, version 4 -5 Feb 2008

For n = 0, we set M 0 (f ) = 0. The first term in the right hand side of (25) can also be rewritten in the following form

P µp (f )(X p ) -P µp (f )(X p+1 ) = P µp (f )(X p ) -P µp+1 (f )(X p+1 ) + P µp+1 (f )(X p+1 ) -P µp (f )(X p+1 )
This yields the decomposition

n p=0 P µp (f )(X p ) -P µp (f )(X p+1 ) = P µ0 (f )(X 0 ) -P µn+1 (f )(X n+1 ) +L n+1 (f )
with the random sequence

L n+1 (f ) := n p=0 P µp+1 -P µp (f )(X p+1 )
In summary, we have established the following decomposition

I n (f ) = M n+1 (f ) + L n+1 (f ) + P µ0 (f )(X 0 ) -P µn+1 (f )(X n+1 )
We estimate each term separately. Firstly, using (24) we prove that

P µ0 (f )(X 0 ) -P µn+1 (f )(X n+1 ) ≤ P µ0 + P µn+1 ≤ 4n 0 1 -b(n 0 )
In much the same way, using (24) we find that

L n+1 ≤ n p=0 P µp+1 -P µp ≤ 3c n 0 1 -b(n 0 ) 2 n p=0 µ p+1 -µ p = 3c (n + 1) n 0 1 -b(n 0 ) 2 (n)
From these two estimates, we conclude that

|I n (f )| ≤ |M n+1 (f )| + 3c (n + 1) n 0 1 -b(n 0 ) 2 (n) + 4n 0 1 -b(n 0 ) (26)
To estimate the martingale term, we recall that the unpredictable quadratic variation process [M (f ), M (f )] n of the martingale M n (f ) is the cumulated sum of the square of its increments from the origin up to the current time; that is, we have that

[M (f ), M (f )] n := n p=1 (∆M p (f )) 2
The main simplification of our regularity conditions comes from the fact that the increments |∆M p (f )| are uniformly bounded. More precisely, we have the almost sure estimates

|∆M p+1 (f )| = P µp (f )(X p+1 ) -K µp (P µp (f ))(X p ) = P µp (f )(X p+1 ) -P µp (f )(x) K µp (X p , dx) ≤ P µp (f )(X p+1 ) -P µp (f )(x) K µp (X p , dx) RR n°0123456789
inria-00227508, version 4 -5 Feb 2008

from which we conclude that

|∆M p+1 (f )| ≤ osc(P µp (f )) ≤ β(P µp ) ≤ n 0 1 -b(n 0 ) By definition of the quadratic variation process [M (f ), M (f )] n , this implies that [M (f ), M (f )] n ≤ n 0 1 -b(n 0 ) 2 n
The end of the proof is now a direct consequence of the Burkholder-Davis-Gundy inequality for discrete generation martingales. For any r ≥ 1, there exists some finite constant e(r) whose value only depends on r, and such that for any n

E max 1≤p≤n |M p (f )| r 1 r ≤ e(r) E [M (f ), M (f )] r 2 n 1 r ≤ e(r) n 0 1 -b(n 0 ) √ n
Combining this estimate with (26), we find that

E (|I n (f )| r ) 1 r ≤ e(r) n 0 1 -b(n 0 ) 2 (n + 1) + c (n + 1) E( (n) r ) 1 r
with again some finite constant e(r) whose values may vary from line to line, but only depends on r. Recalling the definition of I n (f ), we conclude that

E (|[η n -ω n (µ)] (f )| r ) 1 r ≤ e(r) n 0 1 -b(n 0 ) 2 1 (n + 1) + c E( (n) r ) 1 r
This ends the proof of the first assertion. To prove the concentration estimates, we use the fact that

|[η n -ω n (µ)] (f )| ≤ |M n+1 (f )| n + 1 + n 0 1 -b(n 0 ) 3c n 0 1 -b(n 0 ) (n) + 4 n + 1
from which we deduce the rather crude upper bound

|[η n -ω n (µ)] (f )| ≤ |M n+1 (f )| n + 1 + (1 + c) 2n 0 1 -b(n 0 ) 2 (n) ∨ 1 n + 1 (27)
The Chernov-Hoeffding exponential inequality states that for every martingale M n with M 0 = 0 and uniformly bounded increments sup n |∆M n | ≤ a, we have

P(|M n | ≥ tn) ≤ 2 e -nt 2 /2a 2
In our context, we have proved that sup

n |∆M n (f )| ≤ n 0 /(1 -b(n 0 )), from which we conclude that P |[η n -ω n (µ)] (f )| > t + (1 + c) 2n0 1-b(n0) 2 (n) ∨ 1 n+1 ≤ 2 exp -(n + 1) t 2 2 1-b(n0) n0 2
We conclude the proof of the theorem by choosing t = n0

1-b(n0) 2 log (2/δ) n+1
.

Distribution flows models

In this section, we have collected the definition of a series of semigroups on distribution flow state spaces. We also take the opportunity to describe some of their regularity properties we shall use in the further developments of the article.

We equip the sets of distribution flows P(S (l) ) N with the uniform total variation distance defined by

∀(η, µ) ∈ P(S (l) ) N 2 η -µ := sup n≥0 η n -µ n
We extend a given integral operator µ ∈ P(S (l) ) → µL ∈ P(S (l+1) ) into a mapping

η = (η n ) n≥0 ∈ P(S (l) ) N → ηL = (η n L) n≥0 P(S (l+1) ) N
Sometimes, we slightly abuse the notation and we denote by ν instead of (ν) n≥0 the constant distribution flows equal to a given measure ν ∈ P(S (l) ).

Time averaged semigroups

We associate with the mappings Φ l introduced in (1) the mappings

Φ (l) : η ∈ P(S (l-1) ) N → Φ (l) (η) = Φ (l) n (η) n≥0 ∈ P(S (l) ) N
defined by the coordinate mappings

∀η ∈ P(S (l-1) ) N ∀n ≥ 0 Φ (l) n (η) := Φ l (η n ) We denote by Φ (k,l) = Φ (k) • Φ (k-1,l)
with 0 ≤ l ≤ k, the semigroup associated with the mappings Φ (l) . We also consider the time averaged transformations

Φ (l) : η ∈ P(S (l-1) ) N → Φ (l) (η) = Φ (l) n (η) n≥0 ∈ P(S (l) ) N
defined by the coordinate mappings

∀η ∈ P(S (l-1) ) N ∀n ≥ 0 Φ (l) n (η) := 1 n + 1 n p=0 Φ (l) p (η) = 1 n + 1 n p=0 Φ l (η p ) ∈ P(S (l) )
For l = 0, we use the convention Φ 0 (η p ) = π (0) for any 0 ≤ p ≤ n, so that with some abusive but obvious notation Φ (0) (η) = π (0) represents the constant sequence (π (0) ) n≥0 such that π (0) n = π (0) . We also denote Φ (k,l) : P(S (l-1) ) N → P(S (k) ) N with 0 ≤ l ≤ k, the semigroup associated with the mappings Φ (l) and defined by

Φ (k,l) := Φ (k) • Φ (k-1) • . . . • Φ (l)
We use the convention Φ (k,l) = Id, the identity operator, for l > k.

RR n°0123456789

inria-00227508, version 4 -5 Feb 2008

Integral operators

We associate with the integral operator Γ k from B(S (k) ) into B(S (k-1) ) introduced in [START_REF] Lyman | Resolution exchange simulation with incremental coarsening[END_REF] the integral operator Γ (k) from (N × B(S (k) )) into the set

(N × B(S (k-1)
)) defined by

Γ (k) ((n, f ), d(p, g)) := Σ(n, dp) × Γ k (f, dg) with Σ(n, dp) := 1 n + 1 n q=0 δ q (dp)
The semigroup Γ (l2,l1) (0 ≤ l 1 ≤ l 2 ) associated with the integral operators Γ

(l)
ise defined by Γ (l2,l1) := Γ (l2) Γ (l2-1) . . . Γ

(l1)

For l 1 = l 2 = 0, we use the convention Γ (0,0) = Γ (0) = 0 for the null measure on (N × B(S (0) )). Also observe that

Γ (l2,l1) = Σ l2-l1+1 × Γ l2,l1
where the semigroups Σ l1 and Γ l2,l1 , 0 ≤ l 1 ≤ l 2 associated with the pair of integral operators Σ and Γ l are

Σ l1 = ΣΣ l1-1 = Σ l1-1 Σ and Γ l2,l1 := Γ l2 Γ l2-1 . . . Γ l1
We use the convention Σ 0 = Id. We end this section with a technical lemma relating the regularity properties (7) of the mappings Φ k to the regularity properties of the semigroups Φ (k,l) .

Lemma 4.1 For any 0 ≤ l 1 ≤ l 2 , n ≥ 0, any flow of measures η, µ ∈ P(S (l1-1) ) N and any function f ∈ B(S (l2) ) we have

Φ (l2,l1) n (η) -Φ (l2,l1) n (µ) (f ) ≤ (N×B(S (l 1 -1) )) |[η p -µ p ] (g)| Γ (l2,l1) ((n, f ), d(p, g))
Proof:

Notice that we have Γ (l,l) = Γ (l) . We also observe that Γ (l2,l1) is a bounded integral operator from (N × B(S (l2) )) into (N × B n (S (l1-1) )). We prove the lemma by induction on the parameter k = l 2 -l 1 . The result is clearly true for k = 0. Indeed, by [START_REF] Lyman | Resolution exchange simulation with incremental coarsening[END_REF] we find that for any l ≥ 0

Φ (l) n (η) -Φ (l) n (µ) (f ) ≤ 1 n + 1 n p=0 |[Φ l (η p ) -Φ l (µ p )] (f )| ≤ 1 n + 1 n p=0 B(S (l-1) ) |[η p -µ p ] (g)| Γ(f, dg)
Rewritten in terms of Γ (l) , we have proved that

Φ (l) n (η) -Φ (l) n (µ) (f ) ≤ (N×B(S (l-1) )) |[η p -µ p ] (g)| Γ (l) ((n, f ), d(p, g))

INRIA

This ends the proof of the result for k = 0. Now, suppose we have proved that

Φ (l2,l1) p (η) -Φ (l2,l1) p (µ) (g) ≤ |[η q -µ q ] (h)| Γ (l2,l1) ((p, g), d(q, h))
for any pair of integers l 1 < l 2 with l 2 -l 1 = k for some k ≥ 1. In this case, for any l < k and any function f ∈ B(S (l+1) ), we have

Φ (l+1,l-k) n (η) -Φ (l+1,l-k) n (µ) (f ) = Φ (l+1) n (Φ (l,l-k) (η)) -Φ (l+1) n (Φ (l,l-k) (µ)) (f )
and therefore

Φ (l+1,l-k) n (η) -Φ (l+1,l-k) n (µ) (f ) ≤ Φ (l,l-k) p (η) -Φ (l,l-k) p (µ) (g) Γ (l+1) ((n, f ), d(p, g))
Under our induction hypothesis, this implies that Φ

≤ |[η q -µ q ] (h)| Γ (l+1) ((n, f ), d(p, g)) Γ (l,l-k) ((p, g), d(q, h)) = |[η q -µ q ] (h)| Γ (l+1,l-k) ((n, f ), d(q, h)) (l+1,l-k) n (η) -Φ (l+1,l-k) n (µ) (f )
Letting l 1 = (l -k) and l 2 = (l + 1), we have proved that for any

l 1 < l 2 with l 2 -l 1 = (k + 1) Φ (l2,l1) n (η) -Φ (l2,l1) n (µ) (f ) ≤ |[η p -µ p ] (g)| Γ (l2,l1) ((n, f ), d(p, g))
This ends the proof of the lemma.

Path space semigroups

To simplify the presentation, we fix a time horizon m ≥ 1 and write ω instead of ω K (m) η , the invariant measure mapping defined in [START_REF] Robert | Monte Carlo Statistical Methods[END_REF]. We also write E instead of E m .

We extend the mapping ω on P(E) to P(E) N by setting

ω : η = (η n ) n≥0 ∈ P(E) N → ω(η) = (ω n (η)) n≥0 ∈ P(E) N
with the coordinate mappings ω n defined by

ω n (η) := ω(η n ) = π (0) ⊗ Φ 1 (η (0) n ) ⊗ . . . ⊗ Φ m (η (m-1) n ) RR n°0123456789

inria-00227508, version 4 -5 Feb 2008

For every l ≤ m, we recall that η

(l)
n stands for the image measure on S (l) of a given measure η n ∈ P(E m ). We also consider the mappings

ω : η ∈ P(E) N → ω(η) = (ω n (η)) n≥0 ∈ P(E) N defined by the coordinate mappings ∀η = (η n ) n≥0 ∈ P(E) N ∀n ≥ 0 ω n (η) := 1 n + 1 n p=0 ω p (η) = 1 n + 1 n p=0 ω(η p )
Lemma 4.2 For any 1 ≤ k ≤ m and any flow of measures η ∈ P(E) N , we have

ω k (η) = π [k-1] ⊗ m-k i=0 Φ (i+k,i+1) (η (i) ) For k = m + 1, we have ∀η ∈ P(E) N ω m+1 (η) = π [m]
Proof:

We use a simple induction on the parameter k. The result is clearly true for k = 1. Suppose we have proved the result at some rank k. In this case we have

ω k (ω(η)) = π [k-1] ⊗ Φ k,1 (ω(η) (0) ) ⊗ m-k i=1 Φ i+k,i+1 (ω(η) (i) ) = π [k-1] ⊗ π (k) ⊗ m-k i=1 Φ i+k,i (η (i-1) ) = π [k] ⊗ m-(k+1) i=0 Φ i+(k+1),i+1 (η (i) )
This ends the proof of the lemma.

Lemma 4.3 For any 1 ≤ k ≤ m and any η = (η n ) n≥0 ∈ P(E) N , we have

ω k n (η) = 1 n + 1 n p=0 π [k-1] ⊗ m-k i=0 Φ (i+k) p Φ (i+(k-1),i+1) (η (i) )
For k = m + 1, we have

∀η ∈ P(E) N ω m+1 (η) = π [m]
Proof:

We use a simple induction on the parameter k. The result is clearly true for k = 1. Indeed, we have in this case

ω n (η) = 1 n + 1 n p=0 π [k-1] ⊗ m-1 i=0 Φ (i+1) p η (i)

INRIA

We also observe that

ω n (η) (i) = 1 n + 1 n p=0 Φ (i) p η (i-1) = Φ (i) n η (i-1) ⇒ ω(η) (i) = Φ (i) η (i-1)
Suppose we have proved the result at some rank k. In this case, we have

ω k (ω(η)) = 1 n + 1 n p=0 π [k] ⊗ m-k i=1 Φ (i+k) p Φ (i+(k-1),i) (η (i-1) )
from which we conclude that

ω k+1 (η) = 1 n + 1 n p=0   π [k] ⊗ m-(k+1) i=0 Φ (i+(k+1)) p Φ (i+k,i+1) (η (i) )  
This ends the proof of the lemma.

5 Asymptotic analysis

Introduction

This section is concerned with the asymptotic behavior of i-MCMC models as the time index n tends to infinity. The strong law of large numbers is discussed in section 5.2. We present non-asymptotic L r -inequalities that allow us to quantify the convergence of the occupation measures η

(k) n = 1 n+1 n p=0 δ X (k)
p of i-MCMC models towards the solution π (k) of the measure-valued equation (1).

Section 5.3 is concerned with uniform convergence results with respect to the number of levels k. We examine this important question in terms of the stability properties of the time averaged semigroups introduced in section 4.1. We present non-asymptotic L r -inequalities for a series of i-MCMC models that do not depend on the number of levels. These estimates are probably the most important in practice since they allow us to quantify the running time of a i-MCMC to achieve a given precision independently of the time horizon of the limiting measure-valued equation [START_REF] Andrieu | Non-Linear Markov chain Monte Carlo via self-interacting approximations[END_REF].

Our approach is based on an original combination of nonlinear semigroup techniques with the asymptotic analysis of time inhomogeneous Markov chains developed in section 3. The following technical lemma presents a more or less well known generalized Minkowski integral inequality which will be used in our proofs.

RR n°0123456789

inria-00227508, version 4 -5 Feb 2008 Lemma 5.1 (generalized Minkowski integral inequality) For any pair of bounded positive measures µ 1 and µ 2 on some measurable spaces (E 1 , E 1 ) and (E 2 , E 2 ), any bounded measurable function ϕ on the product space (E 1 × E 2 ) any p ≥ 1, we have

E1 µ 1 (dx 1 ) E2 ϕ(x 1 , x 2 ) µ 2 (dx 2 ) p 1 p ≤ E2 E1 |ϕ(x 1 , x 2 )| p µ 1 (dx 1 ) 1 p µ 2 (dx 2 )
Proof:

Without loss of generality, we suppose that ϕ is a nonnegative function. For p = 1, the lemma is a direct consequence of Fubini's theorem. Let us assume that p > 1, and let p be such that 1 p + 1 p = 1. Firstly, we notice that the functions

ϕ 1 (x 1 ) := E2 ϕ(x 1 , x 2 ) µ 2 (dx 2 ) and φ p (x 2 ) := E1 |ϕ(x 1 , x 2 )| p µ 1 (dx 1 ) 1 p
are measurable for every p ≥ 1. In this notation, we need to prove that µ 1 (ϕ p 1 )

1 p ≤ µ 2 (φ p ).
It is also convenient to consider the function

ψ(x 1 , x 2 ) := ϕ(x 1 , x 2 )/φ p (x 2 ) 1 p
We use the convention ψ(x 1 , x 2 ) = 0, for every x 1 ∈ E 1 as long as φ p (x 2 ) = 0. We observe that E1 ψ(x 1 , x 2 ) p µ 1 (dx 1 )

1 p = φ p (x 2 )/φ p (x 2 ) 1 p = φ p (x 2 ) 1 p
By construction, we have

ϕ 1 (x 1 ) = E2 ψ(x 1 , x 2 ) φ p (x 2 ) 1 p µ 2 (dx 2 ) ≤ E2 ψ(x 1 , x 2 ) p µ 2 (dx 2 ) 1 p × µ 2 (φ p ) 1 p
from which we conclude that

µ 1 (ϕ p 1 ) ≤ µ 2 (φ p ) p p × E2 ψ(x 1 , x 2 ) p µ 1 (dx 1 )µ 2 (dx 2 ) = µ 2 (φ p ) p p × µ 2 (φ p ) = µ 2 (φ p ) p
The end of the proof is now clear.

INRIA inria-00227508, version 4 -5 Feb 2008

Strong law of large numbers

This section is mainly concerned with the proof of the following L r -inequalities for the occupation measure of an i-MCMC model at a given level set.

Theorem 5.2 Under the regularity conditions ( 7) and ( 8), we have for any k ≥ 0, any function f ∈ B 1 (S (k) ) and any n ≥ 0 and r ≥ 1

(n + 1) E η (k) n -π (k) (f ) r 1 r ≤ e(r) k l=0 (1+c l ) n l 1 -b l (n l ) 2 l+1≤i≤k 2Λ i (28) Proof:
We prove the theorem by induction on the parameter k. Firstly, we observe that the estimate (28) is true for k = 0. Indeed, by corollary 3.4 we have that

(n + 1) E η (0) n -π (0) (f ) r 1 r ≤ e(r) n0 1-b0(n0) 2
for some finite constant e(r) < ∞ whose value only depends on the parameter r. We further suppose that the estimate ( 28) is true at rank (k -1). To prove that it is also true at rank k, we use the decomposition

η (k) n -π (k) = η (k) n -Φ (k) n (η (k-1) ) + Φ (k) n (η (k-1) ) -Φ (k) n (π (k-1) ) (29)
For every k ≥ 0, given a realization of the chain X (k-1) := (X (k-1) p

) p≥0 the kth level chain X dependent on the current occupation measure of the chain at level (k -1). Therefore, using corollary 3.4 again we notice that

(n + 1) E η (k) n -Φ (k) n (η (k-1) ) (f ) r 1 r ≤ e(r) (1 + c k ) n k 1-b k (n k ) 2
for some finite constant e(r) < ∞ whose values only depends on the parameter r.

Using the decomposition (29) and lemma 4.1, we obtain

[ η (k) n -π (k) (f ) ≤ η (k) n -Φ (k) n (η (k-1) ) (f ) + η (k-1) p -π (k-1) (g) Γ (k) ((n, f ), d(p, g))
For every function f ∈ B 1 (S (l) ), and any n ≥ 0, k ≥ 0, r ≥ 1, we set

J (k) n (f ) := √ n + 1 E η (k) n -π (k) (f ) r 1 r and j (k) := sup n≥1 sup f : f ≤1 J (k) n (f )
By the generalized Minkowski integral inequality presented in lemma 5.1, we find that

J (k) n (f ) ≤ e(r)(1 + c k ) n k 1 -b l (n k ) 2 + √ n + 1 J (k-1) p (g) 1 √ p + 1 Γ (k) ((n, f ), d(p, g)) RR n°0123456789
inria-00227508, version 4 -5 Feb 2008

Since we have

N 1 √ q + 1 Σ(n, dq) = 1 n + 1 n q=0 1 √ q + 1 ≤ 2 √ n + 1 ( 30
)
we conclude that

J (k) n (f ) ≤ e(r)(1 + c k ) n k 1 -b l (n k ) 2 + 2 j (k-1) sup f g Γ k (f, dg)
and therefore

j (k) ≤ e(r)(1 + c k ) n k 1 -b k (n k ) 2 + j (k-1) 2Λ k
Under the induction hypothesis, we have

j (k-1) 2Λ k ≤ e(r) k-1 l=0 (1 + c l ) n l 1 -b l (n l ) 2 l+1≤i≤k 2Λ i and therefore j (k) ≤ e(r) (1 + c k ) n k 1 -b k (n k ) 2 + k-1 l=0 (1 + c l ) n l 1 -b l (n l ) 2 l+1≤i≤k 2Λ i   = k l=0 (1 + c l ) n l 1 -b l (n l ) 2 l+1≤i≤k 2Λ i
This ends the proof of the theorem.

A uniform convergence theorem

This section focuses on the behavior of an i-MCMC model associated with a large number of levels. We establish an uniform convergence theorem under the assumption that the time averaged semigroup Φ (k,l) introduced in section 4.1 is exponentially stable; that is there exist a pair of positive constants λ 1 , λ 2 > 0 and an integer k 0 such that for every l ≥ 0, η, µ ∈ P(S (l) ) N and any k ≥ k 0 we have Φ

(l+k,l+1) (η) -Φ (l+k,l+1) (µ) ≤ λ 1 e -λ2k (31)
We also assume that the parameters (b k , c k , n k , Λ k ) are chosen so that

A = sup k≥0 (1 + c k ) n k 1 -b k (n k ) 2 < ∞ and B := 2 sup k≥1 Λ k < ∞ (32)
For the Feynman-Kac transformations (11), we give in section 7 sufficient conditions on G l and L l+1 ensuring (31) is satisfied. If (31) and (32) are both satisfied, we have the following uniform convergence result.

INRIA

Theorem 5.3 If B = 1, then we have for any r ≥ 1, any parameter n such that (n + 1) ≥ e 2λ2(k0+1) , and for any

(f l ) l≥0 ∈ l≥0 Osc 1 (S (l) ) sup l≥0 E η (l) n -π (l) (f l ) r 1 r ≤ e(r) √ n + 1 A 1 + log (n + 1) 2λ 2 + λ 2 e λ2
If B > 1, then we have for any r ≥ 1, any n such that (n+1) ≥ e 2(λ2+log B)(k0+1) , and for any

(f l ) l≥0 ∈ l≥0 Osc 1 (S (l) ) sup l≥0 E η (l) n -π (l) (f l ) r 1 r ≤ e(r) AB B -1 + λ 1 e λ2 (n + 1) α/2
with α := λ2 (λ2+log B) .

Proof:

Firstly, we notice that for any k ≥ 0, we have the following estimate from (28) and (32)

(n + 1) E η (k) n -π (k) (f k ) r 1 r ≤ e(r) A B k+1 -1 B -1 (33)
For B = 1, we use the convention B k -1 B-1 = k. We have the following decomposition

η (l+k) n -π (l+k) = η (l+k) n -Φ (l+k,l+1) n (η (l) ) + Φ (l+k,l+1) n (η (l) ) -Φ (l+k,l+1) n (π (l) ) = l+k i=l+1 Φ (l+k,i+1) n (η (i) ) -Φ (l+k,i+1) n (Φ (i) (η (i-1) )) + Φ (l+k,l+1) n (η (l) ) -Φ (l+k,l+1) n (π (l) ) (34)
Recall that we use the convention Φ (l1,l2) = Id for l 1 < l 2 , so that

i = l + k =⇒ Φ (l+k,i+1) n (η (i) ) = Φ (l+k,l+k+2) n (η (l+k) ) = η (l+k) n Using lemma 4.1, we find that Φ (l2,l1+1) n (η (l1) ) -Φ (l2,l1) n (Φ (l1) (η (l1-1) )) (f l2 ) ≤ η (l1) p -Φ (l1) p (η (l1-1) ) (g) Γ (l2,l1+1) ((n, f l2 ), d(p, g))
By the generalized Minkowski integral inequality, this implies that

E Φ (l2,l1+1) n (η (l1) ) -Φ (l2,l1+1) n (Φ (l1) (η (l1-1) )) (f l2 ) r 1 r ≤ E η (l1) p -Φ (l1)
p (η (l1-1) ) (g)

r 1 r Γ (l2,l1+1) ((n, f l2 ), d(p, g)) RR n°0123456789
inria-00227508, version 4 -5 2008

Using corollary 3.4, we find that

E Φ (l2,l1+1) n (η (l1) ) -Φ (l2,l1+1) n (Φ (l1) (η (l1-1) )) (f l2 ) r 1 r ≤ e(r) (1 + c l1 ) n l 1 1-b l 1 (n l 1 ) 2 × {0,...,n} 1 (p + 1) Σ (l2-l1) (n, dp) × g Γ l2,l1+1 (f l2 , dg)
By (30) and

Γ k,l (f l2 , dg) g ≤ Λ k,l f l2 with Λ k,l ≤ l≤i≤k Λ i ≤ B k-l+1 < ∞ we conclude that (n + 1)E Φ (l2,l1+1) n (η (l1) ) -Φ (l2,l1+1) n (Φ (l1) (η (l1-1) )) (f l2 ) r 1 r ≤ e(r) A B l2-l1 f l2 (35)
Using the decomposition (34), we prove that for every f l+k ∈ B 1 (S (l+k) ) and

any k ≥ k 0 sup l≥0 E η (l+k) n -π (l+k) (f l+k ) r 1 r ≤ e(r) A √ n + 1 B k -1 B -1 + λ 1 e -λ2 k
Finally, by (33), we conclude that for every k ≥ k 0

sup l≥0 E η (l) n -π (l) (f l ) r 1 r ≤ e(r) A √ n + 1 B k+1 -1 B -1 + λ 1 e -λ2 k For B = 1, we have sup l≥0 E η (l) n -π (l) (f l ) r 1 r ≤ e(r) A (k + 1) √ n + 1 + λ 1 e -λ2 k
In this situation, we choose the parameters k, n such that

k = k(n) := log (n + 1) 2λ 2 ≥ k 0 Notice that k(n) is the largest integer k satisfying k ≤ log (n + 1) 2λ 2 ⇔ 1 √ n + 1 ≤ e -λ2 k Since (k(n) + 1) ≥ log (n+1) 2λ2
, we have

e -λ2 k(n) ≤ e λ2 e -λ2 log (n+1) 2λ 2 = e λ2 √ n + 1 INRIA from which we conclude that A (k(n) + 1) √ n + 1 + λ 1 e -λ2 k(n) ≤ 1 √ n + 1 A 1 + log (n + 1) 2λ 2 + λ 2 e λ2
For B > 1, we choose the parameters k, n such that

k = k(n) := log (n + 1) 2(λ 2 + log B) ≥ k 0 Notice that k(n) is the largest integer k such that k ≤ log (n + 1) 2(λ 2 + log B) ⇔ B k √ n + 1 ≤ e -λ2 k Since (k(n) + 1) ≥ log (n+1) 2(λ2+log B) , we have B k(n) √ n + 1 ≤ e -λ2 k(n) ≤ e λ2 e -λ2 log (n+1) 2(λ 2 +log B) = e λ2 (n + 1) α/2
with α := λ2 (λ2+log B) , from which we conclude that

A √ n + 1 B k(n)+1 -1 B -1 +λ 1 e -λ2 k(n) ≤ AB B -1 + λ 1 e λ2 (n + 1) α/2 - AB B -1 1 √ n + 1
This ends the proof of the theorem.

Path space models

In the previous section, we have established L r -mean error bounds and exponential estimates quantifying the convergence of the occupation measures η of the measure-valued equation [START_REF] Andrieu | Non-Linear Markov chain Monte Carlo via self-interacting approximations[END_REF]. We show here that it also possible to establish such results to quantify the convergence of the path-space occupation measures η

[m] n introduced in (6) towards the tensor product measure π (m) defined in (10).

L r -mean error bounds

Our main result is the following theorem. Theorem 6.1 For every f ∈ B(E m ), we have

sup n≥1 √ n E η [m] n -π (m) (f ) r 1 r < ∞ Proof:
To simplify the presentation, we fix a time horizon m ≥ 1 and write ω instead of ω K (m) η , the invariant measure mapping defined in [START_REF] Robert | Monte Carlo Statistical Methods[END_REF]. We also write E instead of E m , and η n instead of η and (η (i) ) j+1≤i≤m-k , we find that the random functions f (k,m),(j) n := R (k,m),(j) n (η (l) ) l , Φ (l) (η (l-1) ) l (f ) ∈ B(S (j+k) )

do not depend on the distribution flows η (j) and η (j-1) . This shows that f (k,m),(j) n are measurable with respect to F m,j n . From previous calculations (and again using the generalized Minkowski integral inequality presented in lemma 5.1) we find that This ends the proof of the theorem.

INRIA

On the other hand, if we chose the constant Dirac distribution flows η = (η n ) n≥0 and µ = (µ n ) n≥0 given by ∀n ≥ 0 η n = δ x and µ n = δ y for some x, y ∈ S (l-1) , we also have that Φ (k,l) (δ x ) -Φ (k,l) (δ y ) = δ x P l,k -δ y P l,k

This implies that sup η,µ Φ (k,l) (η) -Φ (k,l) (µ) ≥ sup

x,y δ x P l,k -δ y P l,k = 2 β(P l,k )

This ends the proof of the proposition.

Our next objective is to estimate the contraction coefficient β(P l,k ) in terms of the mixing type properties of the semigroup L l,k = L l L l-1 . . . L k associated with the Markov operators L l . We introduce the following regularity conditions.

(L) m There exists an integer m ≥ 1 and a sequence ( l (L)) l≥0 ∈ (0, 1) N such that ∀l ≥ 0 ∀(x, y) ∈ (S (l-1) ) 2

L l+1,l+m (x, .) ≥ l (L) L l+1,l+m (y, .)

It is well known that the above condition is satisfied for any aperiodic and irreducible Markov chain on a finite space. Loosely speaking, for non-compact spaces this condition is related to the tails of the transition distributions on the boundaries of the state space. For instance, let us suppose that S (l) = R and L l is the bi-Laplace transition given by L l (x, dy) = c(l) 2 e -c(l) |y-A l (x)| dy for some c(l) > 0 and some drift function A n with bounded oscillations osc(A l ) < ∞. In this case, it is readily checked that condition (L) m holds true for m = 1 with the parameter l-1 (L) = exp (-c(l) osc(A l )) Under the condition (G) presented on page 11 and the mixing condition (L) m stated above, we proved in [START_REF] Moral | Feynman-Kac formulae[END_REF]

  m n := (X (l) n ) 0≤l≤m associated with a fixed series of m levels evolves with ele-INRIA inria-00227508, version 4 -5 Feb 2008 mentary transitions X m n

  is a Markov chain with initial distribution ν k and with random Markov transitions M (k) η (k-1) n RR n°0123456789 inria-00227508, version 4 -5 Feb 2008 depending on the current occupation measures η (k-1) n

  evolution of the i-MCMC model. In other words we interpret the series of samples X (l) i , 1 ≤ i ≤ N , as the first N iterations of the i-MCMC model at level l. More formally, this strategy simply substitutes the current occupation measure η (k-1) n of the chain at level (k -1) in (3) by the occupation measure η (N,k-1) n of the whole sequence of random variables at level (k -1) defined by

version 4 - 5 ΠΠ

 45 [m] n . In this notation, (η(l) ) represents the flow of theRR n°0123456789 Feb 2008Moving one step further, we introduce the decompositionΠ (k,m) (µ) -Π (k,m) (k,m),(i) (ν) ⊗ Π (k,m),(j) (µ) -Π (k,m),(j) (ν) ⊗ m-k i=j+1 Π (k,m),(i) (µ)(38) for any µ = (µ (l) ) 0≤l≤m and ν = (ν (l) ) 0≤l≤m ∈ 0≤i≤m P(S (i) ) N , with the flow of signed measuresΠ (k,m),(j) n (µ) -Π (k,m),(j) n (ν) = Φ j+k Φ (j+(k-1),j+1) n (µ (j) ) -Φ j+k Φ (j+(k-1),j+1) n (ν (j) )For every f ∈ B(S (j+k) ), we find thatΠ (k,m),(j) n (µ) -Π (k,m),(j) n (ν) (f ) ≤ Φ (j+(k-1),j+1) n (µ (j) ) -Φ (j+(k-1),j+1) n (ν (j) ) (g) Γ j+k (f, dg)(39) We let F m,j n be the sigma field given byF m,j n = σ X (l) p : 0 ≤ p ≤ n, 0 ≤ l ≤ m, l = jCombining the generalized Minkowski integral inequality presented in lemma 5.1 with the inequality (35), we prove thatE Π (k,m),(j) n ((η (l) ) l ) -Π (k,m),(j) n Φ (l) (η (l-1) )Notice that the decomposition (38) can be rewritten for any f ∈ B (k,m),(j)n (µ) -Π (k,m),(j) n (ν) R (k,m),(j) n (µ, ν)(f )(40)RR n°0123456789 inria-00227508, version 4 -5 Feb 2008 with the integral operators R (k,m),(j) n (µ, ν) : B m l=k S (l) → B(S (j+k) ) given below R (k,m),(j) n(µ, ν)(f )(x k+j ) = f (x k , . . . , x k+(j-1) , x k+j , x k+j+1 , . . . , x m ) (l) ) l ) only depend on the distribution flow Φ (i) (η (i-1) ) 0≤i≤j-1

1 r≤

 1 We conclude that for any f ∈ B( k≤j≤m S (j) ) (m -k + 1) e(r) √ n+1 A B k f Using (40), it is now easily checked that for every f ∈ B(E)

  (see corollary 4.3.3 on page 141) that we have for any k ≥ m ≥ 1, and l ≥ 1 β(P l+1,l+k ) ≤ can be deduced from these estimates, we refer to chapter 4 of the book[START_REF] Moral | Feynman-Kac formulae[END_REF]. To give a flavor of these results, we further assume that (M ) m is satisfied with m = 1, and we have (L) = inf l l (L) > 0. In this case, we can check thatβ(P l+1,l+k ) ≤ 1 -(L)2 k INRIA inria-00227508, version 4 -5 Feb 2008

http://www.inria.fr ISSN 0249-6399

occupation measures η (l) n := 1 n+1 n p=0 δ X (l) p ∈ P(S (l) ) of the i-MCMC model on the l-th level set S (l) .

Using the fact that ω m+1 (η) = π (m) , we obtain the following decomposition for any η ∈ P(E)

Using proposition 4.3, the k-th iterate ω k of the mapping ω can be rewritten for any η ∈ P(E) N in the following form

Here the mappings with for any (µ (l) ) 0≤l≤m ∈ 0≤i≤m P(S (i) ) N and any 0 ≤ i ≤ m -k Π (k,m),(i) n ((µ (l) ) l ) := Φ i+k Φ (i+(k-1),i+1) n (µ (i) ) ∈ P(S (i+k) )

We emphasize that Π (k,m) n (µ) only depends on the flow of measures (µ (l) ) 0≤l≤m-k , and

with the convention Φ (0) (η (-1) )) = π (0) , for i = 0. This implies that for any

and therefore

Concentration analysis

This section is mainly concerned with exponential bounds for the deviations of the occupation measures η

n around the limiting tensor product measure π [m] . We restrict our attention to models satisfying the Lipschitz type condition [START_REF] Lyman | Resolution exchange simulation with incremental coarsening[END_REF] for some integral operators Γ k with uniformly finite support sup

To simplify the presentation, we fix a parameter m ≥ 1, and sometimes we write

n . We shall also use the letters c i , i ≥ 1 to denote some finite constants whose values may vary from line to line but do not depend on the time parameter n.

The main result of this section is the following concentration theorem.

Theorem 6.2 There exists some finite constant σ m < ∞ such that for any

The proof of this theorem is based on two technical lemmas.

Lemma 6.3

We let M = (M n ) n≥1 be a random process such that the following exponential inequality is satisfied for some positive constants a, b > 0 and for any t ≥ 0 and n ≥ 1

We consider the collection of random processes

n ) n≥1 defined for any n ≥ 0 and k ≥ 0 by the following formula

For every k ≥ 0, n ≥ 1, and t ≥ 0 we have the exponential inequalities

Proof:

We prove the lemma by induction on the parameter k. For k = 0, we have M (0)

n+1 := M n+1 so that the exponential estimate holds true with a(0) = a and b(0) = b. Suppose we have proved the result at rank k. Using the fact that

we prove the recursion formula

inria-00227508, version 4 -5 Feb 2008

On the other hand, we have 1 2

Under the induction hypothesis, we have for any 0

This implies that

from which we conclude that

This ends the proof of the lemma.

Lemma 6.4 For every l 1 < l 2 , there exists some non increasing function

such that for every n ≥ N (t) and any function f ∈ B 1 (S (l2) ) we have

Before getting into the details of the proof of this lemma, it is interesting to mention a direct consequence of the above exponential estimates. Firstly, we observe that N (t √ n + 1) ≤ N (t) so that for any t > 0 and n ≥ N (t) we have

Using the decomposition

we prove the following inclusion of events [η

By lemma 6.4 we can find a sufficiently large integer N (t) that may depend on the parameter k and such that for every n ≥ N (t)

This clearly implies the existence of some finite constant σ k < ∞ such that lim sup

Proof of lemma 6.4 : Using lemma 4.1, we find that

Arguing as in (27), we find that for any g ∈ B(S (l1 ), we have

with a sub-Gaussian process M (l1) n (g) satisfying the following exponential inequality for any t > 0 and any time parameter n ≥ 1

We notice that

Using lemma 6.3, we prove that

We observe that

In addition, using (41) and (42) we find that

Finally, under our assumptions we have

from which we check that

Using (43), we conclude that

≤ (c 5 (n + 1)) (l2-l1) exp -c 6 (n + 1)t 2 /c (l2-l1) 7

To take the final step, we observe that

We also notice that for any t > 0 we can find some non increasing function

This implies that for any n ≥ N (t) we have

The end of the proof is now straightforward.

We are now in position to prove theorem 6.2.

Proof of theorem 6.2: We use the same notation as we used in the proof of theorem 6.1. Using (39)

Therefore, using lemma 6.4 we can find a non-increasing function N (t) (that may depend on the parameter k), such that for every n ≥ N (t) and any f ∈ B 1 (S (j+k) ) we have

In much the same way, by the decomposition (40) we find the following assertion

) we have for every parameter n ≥ N (t)

In summary, we have proved that there exists some non-increasing function N (t) that may depend on the parameter m such that for any 0 ≤ k ≤ m, any f ∈ B 1 (E), and any n ≥ N (t) we have

Let (U n ) n≥1 be a collection of [0, 1]-valued random variables such that for any t there exists some non-increasing function N (t), so that for n ≥ N (t)

for some integer α ≥ 1 and some pair of positive constants (a, b). In this situation, we can find a non-increasing function N (t) and a pair of positive constants (a , b ) such that ∀n ≥ N (t)

INRIA

To prove this claim, we simply use the fact that for any n ≥ N (t) we have

This yields that for any n ≥ N (t)

We let N (t) be the smallest integer n such that N (t)/ √ n ≤ t. Recalling that N (t) is a non-decreasing function, we find that for any s ≥ t

This implies that N (s) ≤ N (t). Thus, we have constructed a non-increasing function N (t) such that for any n ≥ N (t)

This ends the proof of the assertion with (a , b ) = (a, b/2 4 ). Applying this property to the decomposition (37), we can find a non-increasing function N (t) such that for any n ≥ N (t) and any 0 ≤ k ≤ m

The end of the proof of the theorem is now a direct consequence of the decomposition (36).

7 Feynman-Kac semigroups

In section 5.3, we established a uniform convergence theorem under the assumption that the time averaged semigroup Φ (k,l) introduced in section 4.1 is exponentially stable; that is it satisfies (31). In this section, we study the mappings Φ (k,l) associated with the Feynman-Kac transformations discussed in (45).

In particular, we provide necessary conditions ensuring that (31) is satisfied in this case.

Description of the models

To precisely describe these mappings we need a few definitions.

Definition 7.1 We denote by Ψ G l the Boltzman-Gibbs transformation associated with a positive potential function G on S (l) , and defined for any f ∈ B(S (l) ) by the following formula

We let Q l be the integral operator from S (l-1) into S (l) given by

inria-00227508, version 4 -5 Feb 2008

By definition of the mappings Φ l given in (11), it is easy to check that l) be the semigroup associated with the Feynman-Kac transformations Φ l discussed in (45), and we denote by

the semigroup associated with the integral operator Q l introduced in (44).

Proposition 7.3 For any l ≤ k we have that

and the mapping Ψ (k,l) from P(S (l-1) ) N into itself given below

For l = k, we use the conventions

= Q l (1) and Ψ (l,l) = Ψ (l),Q l (1) .

Proof:

We prove the proposition by induction on the parameter m = (k -l). For k = l, we clearly have

Suppose we have proved formula (46) for some m = (k -l) ≥ 0. To check the result at level m + 1 = (k -l) + 1 = ((k + 1) -l), we first observe that

For any µ ∈ P(S (k) ), we also have that

INRIA

Using the induction hypothesis, we find that Φ (k,l) p (η)(Q k+1 (f )) = Ψ (k,l) (η)[P l,k (Q k+1 (f ))]

We also have

Ψ

(k,l) (η) P l,k+1 (f )

In summary, we have proved that Φ (k+1,l) (η) = Ψ (k+1,l) (η)P l,k+1 (f ) with Ψ (k+1,l) (η) = Ψ (l),H l,k+1 n

This ends the proof of the proposition.

Contraction inequalities


Héloïse Vigié
email: heloise.vigie@ensiacet.fr

Aurélie Soula
email: baurelie.soula@aircelle.fr

Bernard Viguier
email: cbernard.viguier@ensiacet.fr

Aging of the21S Titanium Alloy

Keywords: Ti-21S alloy, aging, mechanical properties, microstructure, beta titanium alloy

Ti-21S is a -metastable titanium alloy, currently used in industries such as aeronautics, because of its cold formability, good mechanical properties at elevated temperature, low density and its strong resistance to oxidation. This alloy is hardened by an -phase precipitation in the -matrix. The purpose of the present research is to establish the effect of aging on the microstructure and mechanical properties of Ti-21S. Different thermal aging tests have been carried out at 600°C and at 650°C for 500 hours in laboratory air. The evolution of the microstructure has been reported after each thermal treatment and associated with room temperature tensile tests results.

Introduction

Ti-21S is a recent alloy developed by Timet USA in 1990 [START_REF] Bania | Oxidation resistant titanium-base alloy[END_REF]. It was developed to be used as a matrix in composite materials and is currently used in aeronautics to produce covers, caps and nozzles [START_REF] Boyer | [END_REF]. It has good properties at high temperatures and a better creep resistance than Ti6Al4V, the most commonly used Ti alloy [3]. Highly resistant to corrosion, Ti-21S is often used in the presence of hot fluids. Aging treatments on Ti-21S sheets were performed at 600°C and 650°C for 500h in laboratory air, starting with i) a solution and ii)  precipitation treatments. The evolution of the microstructure and the mechanical properties were then studied using scanning electron microscopy (SEM) observations and tensile tests at room temperature.

Material and experimental procedure

The 1.0 mm thick Ti-21S sheets used were supplied in solution-state. The nominal composition of this alloy is: Ti-15Mo-3Al-2.7Nb-0.3Si (in wt%). Specimens of 50x50 mm² and tensile specimens were laser machined. A first batch of specimens corresponds to this as-received solution-state. A second batch underwent thermal treatments resulting in an -precipitated state. In these thermal states, aging treatments were performed in laboratory air at 600 ° C and 650 ° C for 500h. The heating rate was set to 6 -7 °C/min and the specimens were air-cooled at the end of treatment. For metallographic observations, the samples were mechanically ground on SiC paper down to grade 2400 and then polished using OPS solution to obtain a mirror surface. Each sample was then examined by SEM (using a LEO 435VP -EDS INCA Operating at 15 kV). Higher magnification observations necessitated the use of a JEOL field emission SEM JSM-7800F Prime, from the UMS Castaing Centre, operating at 5 kV. All analyses were carried out using the backscattered electrons mode. An MTS 810 servo-hydraulic machine was used for tensile tests at an imposed displacement rate of 0.013 mm/s. The gage length of specimens was 30 mm, the cross section was (7 x 1) mm ² and the elongation was measured by extensometry. All tensile tests were performed at room temperature.

Effect of heat treatment on the microstructure

SEM observations of the two types of specimens are reported in Fig. 1 for the initial and aged states. As expected, the initial state of the solution-treated alloy (Fig. 1a) shows a single-phased  material, and the precipitation-treated alloy shows  precipitates at the grain boundaries and within the  grains (Fig. 1b). The size of the  precipitates is heterogeneous, exhibiting bands of coarse precipitates along the grain boundaries and a fine and homogenous distribution in the centre of the grains. Aging treatments from the solution-treated alloy lead to an -phase precipitation at the grain boundaries and within the  grains, as shown in Fig. 1c for the thermal treatment at 600°C and Fig. 1e for the thermal aging at 650°C. The size of the precipitates is homogeneous showing nearly the same size in the vicinity of the grain boundaries and within the  grains. The size of the  precipitates increases as the temperature of thermal treatment increases [4]. For the precipitated state,  precipitates grow after aging treatment, and the morphology and precipitation density is more homogeneous, Fig. 1 (d andf). The precipitation of the  phase is thinner after aging from the solution-treated state than after aging from the precipitated microstructure. The  grain size of both states was also compared. A micrograph examination indicates that the grain size is higher in the precipitated state in comparison to the solution treatment, which is certainly due to previous steps in the thermal processing treatment. The grain size does not seem to vary during further aging treatment in both the solution and precipitated states.

Tensile behaviour of the alloy Ti-21S

Tensile tests were performed up to rupture in the various metallurgical states exposed above with constant displacement rate corresponding to about 4.4 10 -4 s -1 . The resulting true-stress-true-strain tensile curves are presented in Fig. 2. For the initial state of the solution treatment, the material shows a yield behaviour with 0.2% offset plastic strain flow stress  0.2 = 922 MPa. The yield is followed by a moderate hardening after a flow plateau and the rupture occurs with significant necking for a total strain of  rup = 19.6 %. The corresponding curve for the precipitated state exhibits a different behaviour, with  0.2 = 1012 MPa, no yield and a constant strain hardening rate. The rupture occurs quite suddenly for a total strain of  rup = 15.5 %. These tensile behaviours agree quite well with the microstructural observations: the lower flow stress and very weak strain hardening is associated to a single phased bcc alloy for the solution treated microstructure and the higher stress and strong strain hardening rate corresponds to precipitate hardened alloy for the precipitated state. In the same way, the results of tensile tests on specimens after thermal aging treatments at 600°C and 650°C for 500h can be compared with the results obtained from the specimen in initial state. The first observation concerns the drastic decrease in the fracture elongation from about 15 -20 % for the initial states down to less than 3 % after aging. Thermal aging was carried out in laboratory air. The metal thus reacts with oxygen as evidenced on the one hand by the formation of an outer oxide layer and on the other hand by the absorption of oxygen underneath the surface leading to microstructural evolution of the alloy. Such reactivity is commonly observed to have a strong detrimental effect on Ti alloy ductility [5,6]. For the solution state microstructure, flow stress increases after thermal aging treatment. Measurements found  0.2 = 1140 MPa for the thermal treatment at 600°C and 950 MPa at 650°C. Starting from the  single-phased microstructure in the initial solution treatment, aging at 600°C creates a homogeneous and fine  precipitation resulting in a strong increase of flow stress. By contrast, aging at 650°C results in a coarser precipitation state that slightly hardens the alloy in comparison to the solution state. For the precipitated microstructure, thermal aging at 600°C leads to an increase of  0.2 up to 1045 MPa whereas this value decreases to 949 MPa for the thermal treatment at 650°C. After aging at 600°C, the slight microstructure evolution in the centre of the sheet induces a small increase of the flow stress by 30 MPa. The decrease in flow stress after aging at 650°C is related to a coarsening of the  precipitates.

These mechanical test results are congruent with the microstructure evolution in -21S sheet. They highlight the effect of oxygen, mainly on the ductility of the alloy. The comparison of the aging treatment performed at 600°C for 500h shows different microstructures and mechanical resistances depending on the initial state. By contrast, aging at 650°C leads to comparable states for the two initial microstructures.

Conclusion

In this study, thermal aging treatments at 600°C and 650°C for 500 hours were conducted on two types of microstructures of the alloy -21S, solution-treated and precipitated microstructures. The tensile behaviour of the material was related to the microstructure evolution. A fine and homogeneous precipitation of -phase resulted in an increase of mechanical resistance, whereas aging oxygen absorption during aging treatment performed in air reduces the ductility of the alloy drastically. The initial microstructure has a dominant role in the evolution of material properties with respect to aging at 600°C unlike aging at 650°C. Another factor to take into account at this temperature is the diffusion of oxygen in the material. Further investigations should be conducted to explain the effect of oxygen on both microstructures and mechanical behaviour.

Fig 1 :

 1 Fig 1: Microstructure observations of Ti-21S for the two types of specimen used: as-received solution treatment (left column) and precipitation treatment (right column). The images shown correspond to the initial state (a,b), after thermal aging for 500 h at 600°C (c,d) and 650°C (e,f).

Fig 2 :

 2 Fig 2: Tensile true-stress-true-strain curves for the solution (left plot) and the precipitated (right plot) microstructures.