François Ernoult

Antoine Lejay

Ludovic Goudenège

Mathias Rousset

Je Remercie Grandement

Hugo Touchette D'

Nathalie Krell

Hélène

Sandra

Florian

Éric

M Bernard

Merci Aux

Hélène Guérin

Jean-Christophe Breton

Mihai Gradinaru

Magalie Fromont Renoir

Mathématiques et leurs interactions Par

On ne peut jamais juger les routes empruntées. » Dufresne-Lamy, Les Bienheureux REMERCIEMENTS Mes premiers remerciements vont tout naturellement à mon directeur de thèse Mathias Rousset, ainsi qu'à son partenaire de bureau, Frédéric Cérou. Merci d'avoir ouvert votre porte au petit étudiant de M2 que j'étais, pour me présenter vos thématiques de recherche. Merci d'avoir accepté de m'encadrer sur l'épreuve de séminaire, sans véritablement savoir en quoi cela consistait, d'avoir été aussi moyennement motivés que moi à entamer une thèse (partiellement) financée par le domaine militaire, et d'avoir été à la fois disponibles et compréhensifs durant ces années. Merci aussi d'être venus me chercher à chaque fois, à l'accueil hautement sécurisé de l'INRIA.

Mathias, merci pour votre patience devant mon air souvent incrédule face au tableau, de m'avoir finalement évité les questions de viscosité, de m'avoir expliqué concrètement certains (étranges) concepts d'analyse, ou encore l'apprentissage dans la douleur du choix à propos des notations. Fred, merci pour ton oeil avisé, particulièrement sur mon code Python, puis sur sa transcription en Julia, mais surtout merci pour la découverte d'ouvrages russes de Probabilités. Enfin, et surtout, merci à tous les deux pour votre compréhension dénuée de jugement lors des moments plus difficiles qui ont pu subvenir durant ces trois années.

• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 232 • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • THÈSE DE DOCTORAT DE L'UNIVERSITÉ DE RENNES ÉCOLE DOCTORALE N O 601
Je profite de ces remerciements pour glisser une mention particulière aux membres actuels, et anciens, de la commission parité de l'IRMAR : mon passage n'y aura été que trop court, mais comme l'aura dit un jour Rozenn Texier-Picard "Ce n'est pas toujours facile, il y a des hauts et des bas, mais cela mérite de s'y accrocher". On ne peut que lui donner raison : merci à vous d'être encore accroché.e.s, et je vous souhaite de le rester très longtemps ! Je remercie également les doctorants de l'IRMAR, à commencer par nos aînés : merci Mercedes de nous avoir installé dans un bureau devenu par la suite légendaire, merci Fabrice de nous avoir donné de nombreuses clés (au sens figuré) à notre arrivée, et merci Mégane et Jérémy pour les chouettes moments. Merci également à nos contemporains et à nos cadets, plus particulièrement Marie, Benjamin, Théo, Marc, Théo, Daphnée et Robin.

Enfin, je tiens à m'adresser à l'ensemble des membres de l'IRMAR qui se reconnaîtront dans les termes suivants : disponibles, bienveillants et attentionnés. Je rêve que l'IRMAR, l'ENS Rennes, l'Université de Rennes, l'enseignement supérieur et plus globalement le monde entier en soit rempli. Un jour peut-être ?

J'envoie à présent une vague de remerciements à la majorité de la promo MathsKL2016, et plus particulièrement à Silvère, le plus Rennais des Nantais (ou l'inverse ?), à Antoine Sabut le colocataire anglais, à Nicolas Masson, le co-tonton, et à Émilie, la meilleure amie british le temps d'une après-midi.

Une grosse pensée pour les camarades du Voeu toujours là : Amélie, dont on attend toujours l'invitation au barbecue, Alizée, à qui il fallait essorer le poulet mariné, Ségolène, qui détient à jamais le record de longévité d'amitié, et Corentin, l'heureux propriétaire de Polochon, mais aussi d'Effy ! Merci pour ces années de complicité et de partage.

En particulier, merci Corentin de m'avoir accompagné dans l'aventure du FIL. (C'était mon idée, n'en déplaise à un certain Éric.) Nous y avons rencontrés des personnes incroyables ensemble : Fanny, Philou, Dédé, Elisa et bien sûr Danièle, notre cheffe pour l'éternité. Merci aussi à toute la famille Le Lannier pour m'avoir aussi régulièrement accueilli, ramené, cherché : vous êtes tous adorables (sauf la tortue). Corentin, merci aussi de poursuivre nos aventures : celle du FIL (n'oublie pas que c'est moi, le propriétaire) et les autres.

Merci aux Rennais avec qui mes relations sont dé-corrélées des Mathématiques : mes différents colocataires, déjà, pour les moments passés ensemble et ce qu'il en restera. Merci particulièrement à Raphaël pour les confinements/restrictions : cela aurait été très différent et bien moins agréable sans toi ! Merci aux copains du judo : merci Quentin, mon partenaire d'étranglement échauffement, d'avoir subi une entorse du genou en guise de présentations, et merci Rémi, l'éternel ceinture jaune, de m'avoir cassé un os et causé deux entorses aux doigts (il serait temps de boucler la boucle des blessures entre nous). Grosse pensée aussi aux membres, et affiliés, des cirques Pinder, Painder, PAINder, P1der et P2DER. Tout particulièrement, merci à Fredo et son pneu crevé, à Énora et les biscuits apéritifs "un peu" périmés, à Capitaine Marteau, le roi de la récolte, et au petit singe aussi foufou qu'attachant.

Merci Émeline d'avoir eu l'excellente idée de passer un an avant moi/nous : grâce à toi, nous avons pu profiter allègrement d'informations et de ressources très précieuses, moi sans doute plus que les autres. Merci pour tous les échanges à propos de nos cours, de nos TD et de nos étudiants. Et bravo pour avoir mené une lutte aussi exemplaire que héroïque sur un certain serveur Discord. Enfin, merci pour tes précieux conseils et pour avoir partagé avec moi ton expérience en lycée.

Merci Paul Pistol [Cavallazzi, 2023] d'être aussi incroyable. J'ai adoré partagé un TD avec toi, en première année de thèse, presque autant que tous ces moments d'incompréhension au RU, ou au 232. Cependant, j'attends de te voir jouer au badminton : on m'en a parlé pendant deux ans, j'attends toujours. À ton retour d'outre-Atlantique j'espère ?! L'histoire du sport retient deux choses : les séries d'invincibilité, et le résultat de l'ultime confrontation. Comme promis, je rétablis la vérité en écrivant ici que l'incroyable Alice Bouillet a bien remporté notre dernier affrontement : bravo pour ça, et accessoirement pour la personne incroyable que tu es. J'ai ouvert les yeux sur beaucoup de choses à ton contact, particulièrement durant notre première année de thèse. Merci pour la motivation mutuelle durant cette année, et merci d'être une personne aussi gentille.

Merci à Lisa pour tout : tu es indéniablement la plus belle rencontre de ces dernières années. Tu n'as aucun égal sur cette Terre quand il s'agit de me gronder durant un jeu de société (mais arrête de vouloir nous séparer, Rémi et moi, au Eskisse), pas plus qu'en terme de conversation (je continue d'attendre le petit manuel). J'ai adoré les essais culinaires, les déménagements, les films/séries, les voyages en voitures en ta/votre compagnie (Oui, moi, j'écris ça), les discussions, les découvertes sportives, les jeux de pistes, les expériences de supporter, celle de dinosaure aussi, et tout ça avec toi. Au fait, j'ai (encore) caché quelque chose chez vous : bonne recherche.

Thomas, tu es le premier de nous quatre dans l'ordre alphabétique, alors que je commence par toi. Tu es l'une des personnes les plus gentilles que je connaisse. Tu ne réalises certainement pas à quel point tu as pu nous aider et nous inspirer durant ces trois années : mathématiquement bien sûr (je te prêterai Pies pour la remise de la médaille Fields, si jamais ...) mais surtout humainement. Toujours disponible pour les autres, avec une volonté sincère de bien faire, sans calculs ni intérêts. J'espère avoir gagné auprès de toi un peu de cette simplicité, et te souhaite le meilleur, mon désormais presque voisin.

Monsieur Le Babenchon Barbencho Brbenchon Pierre. J'ai toujours eu cette image de toi de quelqu'un d'inépuisable, de tenace, avec toujours trop d'idées et de projets en cours, et pas assez de jours dans la semaine.

Malgré ça, tu sais être à l'écoute et à ne pas lâcher quand il le faut. Te rejoindre dans cette collocation a été une excellente décision, insister pour que tu nous rejoignes dans le bureau un encore meilleure. Les soirées çà imaginer et à préparer notre film à tous les quatre, celles à en regarder d'autres, les moments musicaux, les jeux de société, les aventures de ton mollet/tibia : merci pour tout ça ! Si je compte bien ne jamais avoir un emploi du temps aussi rempli que le tien, tu es l'exemple vivant qu'il faut simplement prendre les choses, comme elles viennent, les unes après les autres.

Mon cher Momo, depuis ce tout premer covoiturage, avec Vincent, pour aller à notre premier cours à l'ENS, jusqu'à la dernière ballade dans le centre-ville bondé de Sarrancolin, il se sera passé beaucoup de choses. Durant nos années rennaises, j'ai trouvé en toi quelqu'un d'aussi enthousiasme que moi, aux idées incongrues de l'autre, comme Si tu n'es pas un des zouzous du 232, tu ferais mieux de t'amuser avec les petits jeux disséminés dans nos thèses respectives, car tu n'auras probablement pas les clés pour ce qui va suivre ...

Mes chers petits co-bureau, maintenant, on peut clairement dire qu'on a eu une chance unique et exceptionnelle. Venir travailler, dans un bureau, entouré de trois amis, sans aucune relation hiérarchique, rien qui puisse compliquer les relations entre nous. Pendant ces années de thèse, je venais au bureau en sachant que je rigolerai durant la journée avec vous, même si ça n'allait pas fort, et ça c'est magique. Malheureusement, je pense que je ne retrouverai jamais ça. Et heureusement, je pense que je ne retrouverai jamais ça, car cela montre à quel point c'était incroyable, et impossible à reproduire ! Alors gros bisous sur vous les amis

Vous me connaissez, j'allais forcément, moi aussi, cacher une petite énigme dans cette thèse. Je vous donne le point de départ, sans aucune ambiguïté. Je vous préviens qu'il y a plusieurs étapes pour arriver à la fin. Et aussi que vous aurez besoin de vous y attaquer tous les trois ! Bon courage ... Je vous propose de partir du film Rush, de Ron Howard, de sa page Wikipedia par exemple. Je ne sais pas si vous connaissez, c'est un film sur la Formule 1. Non, je n'ai pas vu ce film, vous vous imaginez quoi ? Faîtes attention aux détails et dîtes-vous que parfois, perdre, revient à gagner.

Ah, et Eg2SPdMl#link

FE et Pies

Marie-Claude et Philippe, merci de m'avoir accueilli lorsque j'étais tout petit, petit, moyen, presque grand et grand. Christian, merci d'avoir partagé ton expertise sur les fines bulles des boissons gazeuses.

Enfin, je termine ces pages avec les membres de ma famille : ceux qui sont et seront toujours les plus importants.

Mamette, je suis très heureux des moments que l'on partage, que ce soit au téléphone, à Angers ou à Lorient. Je sais que tu penses fort à moi en ce jour, et je te dis à très vite. Josselin, j'ai beaucoup apprécié bricoler dans tous les sens avec toi. Merci aussi d'avoir grandement contribué à la bicyclettisation familiale : c'est toujours un plaisir de discuter/travailler/faire un truc avec toi. Martin, merci de m'avoir accueilli à chaque période de grande chaleur à Paris, mais garde bien en tête que JE reste le spécialiste d'Astérix dans la famille. Agathe, je te laisse le soin de lire cette phrase à Maëlle et Octave : vous êtes les trois (grands) enfants les plus incroyables du monde, je vous aime très fort tous les trois. Agnès, merci d'avoir été la soeur aînée idéale : Claire et Odile ne me contrediront pas sur ce point.

Merci pour les fêtes organisées, les recettes créées et les vacances dans ta vieille voiture, avec l'atlas des routes sur les genoux. Je n'oublie cependant pas que tu m'as laissé dormir sur le parquet, devant ta porte. Claire, merci pour les jeux durant notre enfance, mais surtout merci d'être la personne que tu es : je suis très heureux d'être ton frère.

complicité : nous avons brillamment dissimulé notre amour fraternel durant l'adolescence ! Pour autant, le monde n'avait qu'à voir que vous partagions les mêmes goûts, blagues, centres d'intérêts, ainsi que la co-présidence du fan club du vieux toutou familial. Je n'oublie cependant pas que tu as mis près de 20 ans à reconnaître publiquement que tu acceptais ma présence dans la famille.

Enfin, merci Papa & Maman d'être ... Papa & Maman ! Je me permets de contre-dire la première phrase de cette thèse : vous avez réussi votre chemin avec brio. Merci Papa pour tes expressions bizarres quand nous étions petit.

Merci Maman d'être là, en refusant de calculer la probabilité de tirer deux chaussettes de la même couleur. Mais surtout, merci d'être les meilleurs parents du monde, d'être aussi gentils, à l'écoute, tout en ayant toujours tout un tas de solutions aux problèmes. Merci d'avoir été, et de continuer d'être, les meilleurs soutiens possibles. Je vous aime. In the last decades, the available computational resources and the quality of stochastic models used in science and engineering have dramatically increased. In the same time, the levels of requirement in industry and in scientific fields, concerning for example quality standards and safety, have become higher. One consequence, among many others, is the need for Monte Carlo simulation and estimation of rare events associated with random models. The paper [START_REF] Kahn | Estimation of particle transmission by random sampling[END_REF], which is commonly stated as the first one dealing with Monte Carlo rare event studies, was motivated by the simulation of neutron transport, and more generally, the transmission of physical particles through an obstacle. For instance, in nuclear field, the probability that a radioactive particle goes through a nuclear shielding device without being absorbed should be extremely low. More recently, rare events also became of great interest in other domains, such that communication network [Garvels, 2000], optical fiber [Garnier and Del Moral, 2006], climatology [START_REF] Ragone | Computation of extreme heat waves in climate models using a large deviation algorithm[END_REF], Blanchet et al., 2009], financial engineering [Carmona andCrépey, 2010, Giesecke et al., 2010],

TABLE OF CONTENTS

traffic air management [START_REF] Prandini | Air traffic complexity and the interacting particle system method: An integrated approach for collision risk estimation[END_REF] or electricity network reliability [Wadman et al., 2013].

Naive methods

The first algorithm that comes to mind is naive Monte Carlo. Even though, theoretically, naive Monte Carlo methods provide estimators with noticeable properties, such as unbiasedness, consistency or asymptotic normality, depending on the context of course, these are going to be extremely computational costly. To illustrate this, let us look at a probability, of say p ≃ 10 -9 . We take X 1 , ..., X N a sample of N independent identically distributed (i.i.d.) random variables, and assume p = P (X ∈ R), where R is some set. The Monte Carlo estimator is given by

p MC := 1 N N n=1 1 X N ∈R ,
and by the Law of Large Numbers, we know that the estimator converges almost surely to the probability p. Yet, we would like to have an idea of the sample size n which is required to get a correct estimate. In order to do this, we look at the relative variance of the estimator which is

σ 2 ( p MC ) p 2 = p(1 -p) Np 2 ≃
and new methods of simulation in the rare event context. In this short example, we pointed out two important things that motivate what is coming further: the practical relevance (meaning that computational costs should not be too important) and the reduction of the variance.

We also refer to [START_REF] Kroese | Handbook of Monte Carlo methods[END_REF] for a discussion in part 10.1 about the efficiency of the estimators in the rare event context (notions such that asymptotically vanishing relative error, bounded relative error and logarithmically efficient). In particular, the Example 10.1 from this book points out the fact that the classical Monte Carlo estimator p MC is not logarithmically efficient.

Importance Sampling

Importance sampling (IS) is a useful tool in simulation. It is not only used in rare event context, but also in classical situations to get better rates of convergence, or more accurate estimators. The idea of importance sampling can be found in statistical physics from the 50s [Goertzel, 1949, Kahn and[START_REF] Kahn | [END_REF], even if it is to [Kloek and van Dijk, 1976] that the first rigorous introduction is generally attributed. It is based on changing probability distributions to, roughly speaking, make rare events less rare. Let us illustrate Importance Sampling in a simple situation. For this, we imagine we wish to estimate some probability p = P (X ∈ R), where R is a set and X is a random variable with probability density function f . For any density function f * which does not vanish, sometimes referred as a biasing density, we have

p = 1 x∈R f (x) f * (x) f * (x)dx = E * [1 x∈R w (X)] ,
where w = f / f * and E * is the expectancy associated to the probability measure given by the density f * . This last equality motivates to set, as an estimator of p,

p IS = 1 N N n=1 1 X n ∈R w (X n ) ,
where X 1 , ..., X N are i.i.d. with probability density function f * . The estimator p IS is unbiased and its variance is

Var * ( p IS ) = 1 N E [1 X∈R w (X)] -p 2 ,
where Var * is the variance associated to the probability measure given by f * .

This means that a well chosen density f * leads to a reduction of the variance. As we already mentioned, a low variance is a non-negligible property for an estimator, however, Importance Sampling is not always applicable as it requires to have some knowledge about the density f , to choose well the density f * . Actually, a nonoptimal choice could make the estimator p IS even worse than the classical Monte Carlo p MC one, see for example [START_REF] Glasserman | Counterexamples in importance sampling for large deviations probabilities[END_REF].

Importance Splitting

There is a huge amount of literature on Importance Sampling, we might mention [START_REF] Kroese | Handbook of Monte Carlo methods[END_REF] which present a few algorithms in quite general situations, in Section 9.7. In the rare event context, we can mention [START_REF] Cottrell | Large deviations and rare events in the study of stochastic algorithms[END_REF], Norros and Virtamo, 1989, Parekh and Walrand, 1989, Bucklew, 2013] and [START_REF] Lelièvre | Partial differential equations and stochastic methods in molecular dynamics*[END_REF] for illustrations in molecular dynamics. A theoretical study of the efficiency of IS in a large deviation setting (see also Chapter 3) can be found in [START_REF] Guyader | Efficient large deviation estimation based on importance sampling[END_REF].

Importance Splitting

In this thesis, we will focus on Splitting Methods and especially on Adaptive Multilevel Splitting (AMS) first formalized in [START_REF] Cérou | Adaptive multilevel splitting for rare event analysis[END_REF] which will be presented later. The idea of Importance Splitting (also called Multilevel Splitting) is the following: we simulate particles, according to the original distribution, we discard the ones far away from the set of interest R, and we split/branch/clone those which are closer. In a way, we focus on the particles approaching areas of interest. This description will be detailed further. Importance Splitting, also called, Multilevel Splitting was first introduced in [START_REF] Kahn | Estimation of particle transmission by random sampling[END_REF], to deal with problems in physics, with the following description 'Whenever a particle passes from a less important to a more important region, it is split in two. Each of the resulting particles is given one-half the weight of the original particle and is treated independently from then on.' Many variants have been then worked out since, such as [Bayes, 1970] (who called his version 'Importance Sampling', in conflict with standard terminology), [START_REF] Hopmans | Importance sampling in systems simulation : A practical failure? research memorandum[END_REF],

[ Villén-Altamirano and Villén-Altamirano, 1991] and [START_REF] Cérou | Adaptive multilevel splitting for rare event analysis[END_REF]. A summary of different methods can be found in [L' Ecuyer et al., 2007[START_REF] Ecuyer | Splitting Techniques[END_REF] and comparisons in [START_REF] Garvels | A comparison of restart implementations[END_REF]. In this work we will mainly be interested in a subclass of variants called Fixed Multilevel Splitting methods (AMS is one of them); the latter fits the framework of Sequential Monte Carlo (SMC) and can be seen as the approximation of Feynman-Kac distributions which is an effective way to get some properties or convergence of the Multilevel Splitting estimators (see for example [START_REF] Cérou | Limit theorems for the multilevel splitting algorithm in the simulation of rare events[END_REF], Cérou et al., 2019a] and [Del Moral and[START_REF] Del Moral | Genealogies and increasing propagation of chaos for feynman-kac and genetic models[END_REF] for Feynman-Kac distributions).

One important thing to notice is that there is no connection between Multilevel Splitting methods, and Multilevel Monte Carlo developed by Giles (see [Giles, 2008, Giles, 2015]), even if there are some attempts to use both in conjunction (see [START_REF] Ullmann | Multilevel estimation of rare events[END_REF]).

Just like in Importance Sampling, where the difficulty remains in the selection of a new probability measure, in Importance Splitting, we wish to select wisely the intermediate regions. This choice is delicate because the variance highly depends on these regions. A possible approach is to take an arbitrary set of regions, and then to retain the ones minimizing the variance: this is presented in [Wadman et al., 2013], using results from [START_REF] Amrein | A variant of importance splitting for rare event estimation: Fixed number of successes[END_REF].

In the context of air traffic management, the regions are chosen as zones in which the risks of collision are more and more critical: see [START_REF] Blom | Free flight collision risk estimation by sequential monte carlo simulation[END_REF], Prandini et al., 2011]. Another possibility is to define the intermediate regions using quantiles [Garvels, 2000, Cérou andGuyader, 2007]. This is the context we will work in later, with AMS in Algorithm 3. The regions which are optimal, in the sense of minimizing the variance, are only described in [START_REF] Kahn | Estimation of particle transmission by random sampling[END_REF], heuristically justified in [START_REF] Garvels | On the importance function in splitting simulation[END_REF] and proved in [START_REF] Cérou | Genetic genealogical models in rare event analysis[END_REF].

Another natural question concerns the transition probabilities: is there a value we would like to set for the probability to pass from an intermediate region to the next one ? In a simplified context, [Lagnoux, 2006] shows that the value e -2 for the probability to reach the next region, starting from the previous one, is optimal. [START_REF] Garvels | On the importance function in splitting simulation[END_REF] proves the same thing, in the situation where the transition probability does not depend of the starting point.

Dynamical settings

In this thesis, we will work on the so-called 'dynamic case'. This means we will have X a strong Markov process such that

t → X t ∈ R d
is almost surely continuous (diffusion), ξ the score function which will be continuous, and the rare event set is defined through

R = x : ξ (x) > l max ,
where l max is a given real number. For simplicity, we will consider fixed initial conditions:

X 0 = x 0 ,
generalization to random ones being quite straightforward.

Dynamical rare events problems are defined in path space. We are interested in the probability that a process X reaches R before a terminal stopping time

T end (X).
If l max is large enough, or equivalently if X is unlikely to hit R before T end , this will be a rare event. The considered rare event is the following measurable set in path space:

R := (x t ) t≥0 : T R (x) < T end (x) ,
and the associated probability p of interest is

p := P(X ∈ R) = P (T R (X) < T end (X)) ,
where R is the rare event set, T R (X) is its first hitting time by the process X and T end (X) is the ending time. The only assumption we make about T end is that it is a stopping time for the natural filtration of X. In the last Chapter of this thesis, we will simply consider T end = +∞ : the rare event becomes so 'reaching R in finite time'.

For simplicity, we will also work with processes which are strong Markov for their natural filtration, and for which

entrance time of open level sets,

T l (X) := T {ξ>l} (X)
are stopping time. For diffusion processes, this amounts to assume that processes starting at level ξ (x 0 ) = l immediately enters the open set {ξ > l}. In particular, we will always assume, almost surely,

T {ξ>l} (X) = T {ξ≥l} (X) ,
so that one does not have to care about the difference between open or closed level sets.

We will also work with processes for which the natural filtration is right-continuous, for simplicity. This way, the hitting time T of any measurable set by X will be a stopping time, and by the strong Markov property, the law of X from T , conditionally on its past, will be the law of X, starting from X T .

Problems described above in the dynamic case are of primary interest in different fields, such as in molecular simulation [Lopes andLelièvre, 2018, Rolland and[START_REF] Rolland | [END_REF], particle transport [START_REF] Louvin | Adaptive multilevel splitting for monte carlo particle transport[END_REF] and climate forecast [START_REF] Lestang | Computing return times or return periods with rare event algorithms[END_REF], Ragone et al., 2018]. An important remark is that Multilevel Splitting methods can be interpreted as Sequential Monte Carlo methods as presented in [Del Moral et al., 2006], whose structure is defined by a Feynman-Kac model. This leads, as we already mentioned, to unbiased estimates, as studied in [START_REF] Del Moral | Feynman-Kac Formulae[END_REF].

Let us detail the Importance Splitting in the dynamical context. In particular, the intermediate regions are going to be defined through the (continuous) importance, or score, function ξ : R d → R, as {ξ > l}. We can also consider intermediate regions of the form {ξ ≥ l}, or R = {ξ ≥ l max }: in a dynamic case this is the same. Usually, as we may not know a lot about the typical trajectories reaching R, the choice of ξ is often based on intuitions or loose qualitative knowledge about the rare event and/or the dynamics. It is now accepted that the efficiency of the methods highly rests on this choice. Theoretically, the optimal choice of ξ is given by the so called committor function which is defined by

Φ (x 0 ) = -ln P T R (X) < T end (X) X 0 = x 0 ,
and with the final level l max = 0. We recall that x 0 iserreurs de typos sur les notations qui ont été changées the initial condition, and so the probability of the rare event clearly depends on it. In most situations, the computation of the committor function is yet out of reach. In Chapter 2, a small noise parameter is introduced which amounts to assume that X = X ε is solution to a Stochastic Differential Equation (SDE) with driving Wiener processes multiplied by a factor √ ε. The appropriately scaled committor function will then be:

Φ ε,l (x 0 ) = -ε ln P T R (X) < T end (X) X 0 = x 0
Static settings Note that the so-called 'static case' corresponds to the situation where, typically, X is a random vector in R d , s is a function from R d to R and the probability is p = P (s (X) > q), where q is known and such that p is strictly positive, but very low. In a way, a dynamical setting can be understood as a specific 'static' case considered in (infinite dimensional) path space with an additional Markov assumption on the considered distribution.

Splitting Methods for dynamic problems

The first Importance Splitting method we describe here is the one introduced by [START_REF] Kahn | Estimation of particle transmission by random sampling[END_REF], called Multilevel Splitting. The idea is to clone all the particles that reach the successive intermediate regions. Let us detail a bit in the context of [START_REF] Kahn | Estimation of particle transmission by random sampling[END_REF]: at each stage, if a particle has reached the current intermediate region,

we duplicate it (we choose for now the cloning rates as all equal to 2).

In the following, we will frequently use the notation

T l (X) := T {ξ>l} (X) = inf {t ≥ 0 : X t > l} ,
and always assume that the distribution of X is such that

T l (X) = T {ξ≥l} (X)
for any l ∈ R. We will also, when the context is clear, define for any suitable integer i the hitting time of the set above the i-th level

T ℓ i (X) = inf t ≥ 0 : ξ (X t ) > ℓ i .
We also set, here, p ℓ i the probability

p ℓ i := P (T ℓ i (X) ≤ T end (X)) = P (T ℓ i (X) ≤ T end (X)) ,
and θ i the transition probability rates

θ i := p ℓ i /p ℓ i-1 = P T ℓ i (X) ≤ T end (X) T ℓ i-1 (X) ≤ T end (X) .
Remark 0.6.1 (Ideal case with splitting in two). In general, the computations of the conditional probabilities are unattainable, otherwise we would have no difficulties computing directly the rare event probabilities. Let us nonetheless imagine that we are in an idealized case where we can take the conditional probability (also called hereafter the 'committor' fonction) as the importance function:

ξ (x) = P ( X ∈ R| X 0 = x) .
By construction and by the Markov property, any particle that starts from ξ (x) = 2 i has exactly (whatever its state) probability θ i = 1/2 to reach ξ (x) = 2 i+1 . As a consequence, we consider the levels:

x : ξ (x) = 2 i ,
and for any i ∈ 1, ..., ⌊ log p log(1/2) ⌋ , we split each trajectory which does reach the surface ξ (x) = 2 i into two indepen-dent trajectories in order to exactly compensate failures without splitting too many clones (critical trade-off related to population size). We iterate this until stage i = ⌊ log p log(1/2) ⌋, or until extinction.

We present now Multilevel Splitting in a more general setting, where the cloning rates are integers, not necessarily equal to 2. We need for this N(0) particles at the beginning, i MS the numbers of levels, ξ (x 0 ) = ℓ 0 < ... < ℓ i MS = l max the levels and r 1 , ..., r i MS strictly positive integers.

To ensure the algorithm will be useful , we require r i θ i to be close to 1. In the case where the r i θ i are too small, there will be a very high probability that no trajectory hits the rare event set R, and if they are too large, the algorithm will produce a very large number of correlated paths. An analysis of the cost/variance trade-off of this can be found in [Lagnoux-Renaudie, 2009, Lagnoux and[START_REF] Lagnoux | [END_REF]. As a final remark concerning the cloning rates, the products r i θ i on the example we gave, with ξ = 2 i , were exactly equal to 1.

Figure 1 presents two steps of MS algorithm, where the rare event area is R = {ξ > l max }, the ending time is the hitting time of the region {ξ < -1}, and the cloning rates are r 1 = 2 and r 2 = 3. The particles in black are the initial ones, the blue ones are the one we obtained after the first stage, and the red ones after the second stage.

ξ = ℓ i MS = l max {ξ = ℓ 3 } {ξ = ℓ 2 } {ξ = ℓ 1 } {ξ = ℓ 0 } {ξ = -1} R r 2 = 3 r 1 = 2 Figure 1 -Two iterations of MS algorithm
Multilevel Splitting algorithm, as the first algorithm presented among the splitting methods, has already been studied. In particular, it is well-known that the estimator of the probability and the estimator of the conditional distribution of X are unbiased, see for example [START_REF] Amrein | A variant of importance splitting for rare event estimation: Fixed number of successes[END_REF].

Algorithm 1 Multilevel Splitting (MS)

Require: N(0) initial particles X 1 , ..., X N(0) with the same initial condition x 0 , cloning rates r 1 , ..., r i MS , importance function ξ, levels ξ (x 0 ) = ℓ 0 < ... < ℓ i MS = l max . for i = 1 to i MS do for n = 1 to N (i -1) do Run trajectory n until the level set {ξ > ℓ i } or, if it occurs first, until its ending time T end (X n ). end for Discard the trajectories that did not pass level ℓ i .

Clone r i times the remaining trajectories and denote N(i) the number of resulting trajectories.

Index trajectories from 1 to N(i).

end for for n ∈ 1, ..., N (i MS ) do Run trajectory n until final time T end (X n ). end for Estimate the probability of the rare event p = P T R (X) < T end (X) , where R = ξ > ℓ i SMC by

p MS := 1 N(0) N (i MS ) i MS i=1 r i . If ψ is a pathwise function, denote the conditional distribution of X γ (ψ) := E ψ(X) 1 T R (X)<T end (X) ,
and estimate it by:

γ MS (ψ) := p MS η MS = p MS 1 N (i MS ) N(i MS ) n=1 ψ (X n ) .
From their construction, the particles at stage i ∈ ⟦1, i MS ⟧ have scores higher than ℓ i , meaning

∀i ∈ ⟦0, i MS ⟧, ∀n ∈ ⟦1, N(i)⟧, ξ (X n i ) ≥ ℓ i .

Sequential Monte Carlo

We introduce now a second algorithm that we call Sequential Monte Carlo Algorithm (SMC in short). We will no longer clone the successful particles, but only erased the unsuccessful ones, and re-branch on the other ones. This way, the number of particles remains constant and so there is less requirement.

This algorithm can also be called Multilevel Splitting with fixed effort as the number of clones is kept fixed during the simulation.

To run SMC algorithm, we need to take N ≥ 2, the number of particles, we also choose i SMC ≥ 1 the number of levels, and ξ(x 0 ) = ℓ 0 < ... < ℓ i SMC = l max the levels. The idea is, at each level, to discard the particles which did not reach the level, and to replace them, cloning the particles which did. Each trajectory will be run until it reaches the next level, or until its ending time T i end .

ξ = ℓ i SMC = l max {ξ = ℓ 3 } {ξ = ℓ 2 } {ξ = ℓ 1 } {ξ = ℓ 0 } {ξ = -1} R Figure 2 -Two iterations of SMC algorithm, with N = 3
On Figure 2, a particle is discarded at first stage, as it did not reach the first level ℓ 1 , and is re-branched on another one picked randomly: the left one. At the second stage, both sided particles did not reach level ℓ 2 , so they are discarded and re-branched on the third one. The third stage would discard both left particles and re-branch them on the right one.

Algorithm 2 is sometimes called as Fixed Effort, but the choice of terminology we made is coherent with [START_REF] Cérou | Adaptive multilevel splitting: Historical perspective and recent results[END_REF]. Moreover, as it is mentioned above, this is a particular case of very general methods called Sequential Monte Carlo (see [START_REF] Doucet | [END_REF]).

Note that in the static case, where X is a random vector in R d , S a score function from R d → R and we want to estimate p = P (S (X) > q), where q is known, variants of Algorithm 2 can be constructed. It has be done and studied in [Botev andKroese, 2008, Del Moral et al., 2006], and more recently a more general context has been proposed in [START_REF] Gobet | Rare event simulation using reversible shaking transformations[END_REF] to include both cases: static and the dynamical.

Algorithm 2 Sequential Monte Carlo (SMC)

Require: N initial particles with initial condition x 0 , importance function ξ and levels ξ(x 0 ) = ℓ 0 < ... < ℓ i SMC = l max . for i = 1 to i SMC do for n = 1 to N do Run trajectory of particle n until the hitting time T ℓ i (X n ) of the strict level ξ (X n ) > ℓ i or, if it occurs first, until its ending time T end (X n ). end for Discard the trajectories X n that did not reach level ℓ i .

Denote N(i) = |I i | the number of remaining trajectories and I i the set of their indices. for n ∈ {1, ..., N} \ I i do Take uniformly at random an index m in I i , clone the trajectory m and replace the unsuccessful trajectory n by the clone.

end for

Denote by (X 1,i , . . . , X N,i ) ← (X 1 , . . . , X N ) the resulting particle system. end for Run the trajectories of all particles from T ℓ i SMC (X) until their ending times T end (X). Estimate the probability of the rare event p = P T R (X) < T end (X) , where R = ξ > ℓ i SMC by

p SMC := i SMC i=1 N(i) N .
If ψ is a pathwise function, denote its average in the rare event by

γ (ψ) := E ψ(X) 1 T R (X)<T end (X) ,
and estimate it using:

γ S MC (ψ) := p SMC η S MC = p SMC 1 N N n=1 ψ X n,i SMC .
Just like in MS Algorithm 1, all unsuccessful particles have been replaced by a successful clone at the end of an iteration i, in such a way that the sample size of successful particles is N.

It is interesting to consider Algorithm 2 tuned with different number of levels. If we take many levels, the algorithm will simply do nothing for many stages, since all particles will likely reach a much higher level. However, if there are not enough levels, the algorithm could lead to extinction, in the sense that all particles might be unsuccessful and all fail to reach the next level at the same stage. In this situation, we would have no more particles to re-branch on the erased trajectories, and the algorithm would stop, providing as an estimator the trivial value 0. We can also think to a situation in which it is harder and harder to 'go up', so taking levels ℓ i = l max • i/ i SMC might be convenient at the beginning for example, but not when we get closer to the rare set R, leading to extinction. On contrary, having enough levels close to R, and many at the beginning might not lead to extinction, but would imply having a lot of levels. Of course, the choice of the levels relies on the choice of the importance function ξ.

A main difference between SMC algorithm and MS algorithm we stated previously is that, in MS, the number of particles is random. One of the most important thing is to choose well the cloning rates in Multilevel Splitting algorithm, which is not necessary in SMC.

The first proof of this document is the demonstration that p SMC is unbiased. This is not a difficult result, already well-known, but it is the starting point of such methods.

Proposition 0.6.2. The estimators of SMC algorithm p SMC and γ S MC are unbiased.

Proof. We are going to prove this result using a martingale argument, and a stopping time result.

We take i ∈ ⟦0, i SMC ⟧ a step in SMC Algorithm 2, and we use an intermediate value of particles denoted X n,-,i 1≤n≤N defined as the trajectories we dispose at the middle of stage i, just before the killing step occurs. This means that we know, by construction, that these particles have strictly higher scores than ℓ i-1 , but we have not yet selected those which have reached and been stopped at ℓ i .

More precisely, at the beginning of stage i, we have already denoted the particles X n,i-1 . We then extend their trajectories by sampling starting from their current first entrance state of level ℓ i-1 , up to ℓ i if they manage to. Formally, we will denote this sampling with the probability transition:

M i (x, . ) := Law(X t , t ≤ T ℓ i (X) ∧ T end(X) | X T ℓ i-1 (x) = x T ℓ i-1 (x) ).
(N.B.: one could also have used the notation M i-1,i ) The resulting particles are then denoted X n,-,i .

Next, at the killing step, if the n-th trajectory does reach the i-th level ℓ i , it will remain unchanged, so we will set

X n,i t := X n,-,i t , t ≤ T ℓ i (X n,i )
and else if the n-th trajectory does not reach level ℓ i , we define the new trajectory using cloning as in the algorithm

X n,i t := X
We define η -,i the empirical distribution of the intermediate system at step i as

η -,i := 1 N N n=1 δ X n,-,i ,
and the un-normalized empirical distribution

γ -,i :=          i-1 j=1 N( j) N          η -,i .
Let us denote g i the potential functions, meaning that for any suitable continuous function f , we have

         g i (x) = 0 if sup ξ (x) < ℓ i , g i (x) = 1 if sup ξ (x) ≥ ℓ i .
As a direct consequence of the SMC definition, we have, for

any i ∈ ⟦1, i SMC ⟧ η -,i (g i ) = 1 N N n=0 g i X n,-,i = N(i) N ,
and so

γ -,i =          i-1 j=0 η -, j (g j )          η -,i .
This last relation justifies the interest of the potential functions: the empirical distribution, applied the potential functions, is nothing else than the proportion of particles which survived at stage i.

When a particle X n,-,i is killed, it is replaced by a clone according to the law

η -,i (g i . ) η -,i (g i ) = N n=1 g i X n,-,i δ X n,-,i N n=1 g i X n,-,i .
As a consequence, X n,-,i+1 is sampled using the Markov transition M i+1 , and so

• if g i X n,-,i = 0, X n,-,i+1 ∼ η -,i (g i M i+1 . ) η -,i (g i ) • if g i X n,-,i = 1, X n,-,i+1 ∼ M i+1 ., X n,-,i .
We recall that γ S MC is the estimator at final step of the distribution, so with the previous notations, we can compute the latter with f a bounded test function as follows: by construction of the final killing step, the average number of clones (the cloned particle included) per surviving particle is:

N N(i SMC ) .
The latter is a consequence of keeping the total population equal to N. As a consequence, by defintion of the estimator γ S MC , if f (x t , t ≤ T l max (x t )) denotes a path functional up to the first hitting time of the final level:

E γ S MC ( f ) F N -,i SMC = i SMC i=1 N(i) N 1 N N n=1 E f X n,i | F N -,i SMC = i SMC i=1 N(i) N 1 N N n=1 N N(i SMC ) g i X n,-,i f X n,-,i = γ -,i SMC (g i SMC f ),
where we have denoted

F N -,i 0≤i≤i SMC
the filtration gathering all the information of Algorithm 2 up to the middle of each stage i, that is up to the sampling of X n,-,i for n = 1, . . . , N.

Hence, our final goal is to prove

E [ γ -,i SMC (g i SMC f )] = γ S MC ( f ) ,
which is exactly the unbiasedness property. For that purpose, we will show that, for any measurable function f , the

process ( γ -,i (Q i,i SMC f )) 0≤i≤i SMC
is a martingale with respect to the filtration F N -,i 0≤i≤i SMC , where by definition

Q i,i SMC = g i M i+1 g i+1 . . . M i SMC .
Note that one can define the measure:

γ -,i := η -,1 g 1 M 2 g 3 . . . M i = η -,1 Q 1,i
and so that γ -,i+h := γ -,i g i M i+1 g i+1 . . . M i+h = γ -,i Q i,i+h , and justify the convention

Q i,i = Id. E γ -,i+1 (Q i+1,i SMC f ) F N -,i = E                   i j=0 η j (g j )          η -,i+1 (Q i+1,i SMC f ) F N -,i          =          i j=0 η j (g j )          E η -,i+1 (Q i+1,i SMC f ) F N -,i ,
by measurability, and then

E γ -,i+1 (Q i+1,i SMC f ) F N -,i =          i j=0 η j (g j )          E         1 N N n=1 (Q i+1,i SMC f ) X n,-,i+1 F N -,i         =          i j=0 η j (g j )          1 N N n=1 E (g i+1 M i+2 g i+2 ...M i SMC g i SMC f ) X n,-,i+1 F N -,i =          i j=0 η j (g j )          1 N N n=1 g i X n,-,i M i+1 (Q i+1,i SMC f ) X n,-,i + 1 -g n X n,-,i 1 η -,i (g i ) η -,i (g i M i+1 Q i+1,i SMC f )
by construction. Thus, we have

E γ -,i+1 (Q i+1,i SMC f ) F N -,i =          i j=0 η j (g j )          η i (Q i,i SMC f ) + η -,i (1 -g i ) η i (Q i,i SMC f ) η -,i (g i ) =          i j=0 η j (g j )          η -,i Q i,i SMC f η -,i (g i ) =          i-1 j=0 η j (g j )          η -,i Q i,i SMC f = γ -,i (Q i,i SMC f ) .
By the martingale property, we deduce that

E [ γ -,i SMC (Q i SMC ,i SMC (g i SMC f ))] = E [ γ -,i SMC (g i SMC f )] = E [ γ -,0 (Q 0,i SMC (g i SMC f ))] ,
and this latter expression can be computed, by induction

E [ γ -,1 (Q 1,i SMC (g i SMC f ))] = E [Q 1,i SMC (g i SMC f ) (X)] = E [g 1 (X)M 2 Q 2,i SMC g i SMC (X)] = E [g 1 (X) × Q 1,i SMC (g i SMC f ) (X)] = ... = E          g i SMC f (X) i SMC -1 j=1 g j (X)          = γ ( f ) .

□

As we already mentioned, one of the main issues in the SMC Algorithm 2 is the extinction. Just like MS Algorithm 1, the trajectories might not reach some levels ℓ i , if the discretization is too rough, for example. In the case of SMC, we can bound the probability of extinction (see [START_REF] Del Moral | Feynman-Kac Formulae[END_REF], Cérou et al., 2006]) exponentially, as stated in the following proposition. For the following results of convergence, we will denote E the extinction event of SMC algorithm.

Proposition 0.6.3 ([Del [START_REF] Del Moral | Feynman-Kac Formulae[END_REF]). There exists two constants a, b > 0 independent of the problem we study such that, for any N ≥ 1, we have

P (E) ≤ ae -b N .
There exists versions of SMC algorithm without extinction: see [START_REF] Legland | A sequential particle algorithm that keeps the particle system alive[END_REF] for a biased version, [START_REF] Amrein | A variant of importance splitting for rare event estimation: Fixed number of successes[END_REF] for an unbiased version and [Del Moral et al., 2015] for a version with non-negative potentials. Note that in versions where there is no extinction, the computation time is not bounded.

Algorithm 2 satisfies some classical convergence theorems, such as Law of Large Numbers and Central Limit Theorem. We do not give the proof here, but it can be done using Feynman-Kac's framework. This can be seen as the extension of what we just did using martingale arguments. Description of the Feynman-Kac formula approach, and convergence results in this situation can be found in [START_REF] Del Moral | Feynman-Kac Formulae[END_REF], Cérou et al., 2006].

Theorem 0.6.4 (Law of Large Numbers, [START_REF] Del Moral | Feynman-Kac Formulae[END_REF]). For any bounded measurable function in path space ψ → R, we have

           γ S MC (ψ) P ------→ N→+∞ γ (ψ) , p SMC P ------→ N→+∞ p.
Let us now state a central limit theorem for p SMC . We recall the notation of the intermediate probabilities

p ℓ i := P (T ℓ i ≤ T end ) ,
where T ℓ i is the hitting time of the level ℓ i , and

θ i := p ℓ i /p ℓ i-1 = P T ℓ i ≤ T end T ℓ i-1 ≤ T end .
We also introduce the conditional distributions

η ℓ i (ψ) := E ψ X T ℓ i T ℓ i ≤ T end ,
and

q := P X T R ∧T end ∈ R X 0 = x 0 = γ (1) (x 0 ). ( 1
)
Theorem 0.6.5 (Central Limit Theorem, [START_REF] Del Moral | Feynman-Kac Formulae[END_REF]). The SMC estimator of the probability satisfies

1 E c √ N ( p SMC -p) Law ------→ N→+∞ N 0, σ 2 ,
where

σ 2 = i SMC -1 i=1 θ i p 2 ℓ i-1 -p 2 ℓ i Var η ℓ i (q) + p 2 i SMC i=1 1 θ i -1 . (2)
Note that the form of the asymptotic variance in Theorem 0.6.5 is not the form in [START_REF] Del Moral | Feynman-Kac Formulae[END_REF], but was derived in [START_REF] Cérou | Adaptive multilevel splitting: Historical perspective and recent results[END_REF]. Also note that it is specific to the choice of the resampling method in Algorithm 2.

See [START_REF] Ma | Random assignment versus fixed assignment in multilevel importance splitting for estimating stochastic reach probabilities[END_REF] for a discussion on the effect of the resampling strategy on the variance of the probability estimate.

Similar Central Limit Theorem can be obtained for others estimators of un-normalized and normalized averages given by γ S MC and by the final empirical distribution η S MC , respectively (keeping the notations introduced in the proof of the unbiasedness of p SMC in Proposition 0.6.2). Normalized averages characterize the law of the full trajectory, conditionally to reach the rare event. We refer to [START_REF] Cérou | Adaptive multilevel splitting: Historical perspective and recent results[END_REF] for the values of the asymptotic variances in the Central Limit Theorem for these last two quantities.

In summary, we know that the estimator p SMC and γ S MC are unbiased, consistent and asymptotically Gaussian, when the number of particles grows up to infinity. In this thesis, we will work with Algorithm 2 with fixed number of particles N, so we will only rely on the unbiasedness result to perform accurate simulations. This can be done simply using independent realisations of the full algorithm.

Adaptive Multilevel Splitting

Contrary to both the previous algorithms, we will not choose the levels a priori, but only the number k of particles we want to discard at each stage. Of course, we will take k ∈ ⟦1, N -1⟧: if k = 0, there is no sequential algorithm, and if k = N, this is Classical Monte Carlo. The levels will be then defined as empirical quantile of the maximum values of the paths. The first mention of this algorithm can be found in [Garvels, 2000], but it was formalized and studied in [START_REF] Cérou | Adaptive multilevel splitting for rare event analysis[END_REF].

A way to see that AMS algorithm as a natural evolution of MS and SMC is to consider the variance, and to remark that the optimal way to choose, a priori, the intermediate levels, is to set them such that the intermediate probabilities are constant. A reasonable idea to perform this task empirically is to use the quantiles of the scores of particles at each iteration of splitting algorithms. We introduced k as the number of particles we will re-branch at each stage, but it might not be totally accurate in general settings. Yet, working in a dynamical case, we already mentioned the fact that the particles are going to have different scores almost surely: Algorithm 3 is stated in this context.

In the case k = 1, this is the so called last particle situation. This case deals with the maximal number of iterations, and it has been shown in [Cérou et al., 2019a] that if X is a uniformly elliptic diffusion, then the number of iterations is of order

O P (-N log p) .
It grows linearly with N, but only logarithmically with 1/p which is a critical property. Require: N initial independent trajectories (X n ) 1≤n≤N with common law L (X), the number k of trajectories to dis- card at each step, importance function ξ and final level l max .

{ξ = l max } {ξ = L 3 } {ξ = L 2 } {ξ = L 1 } {ξ = x 0 } {ξ = -1} R
j ← 1 (iteration index) for n = 1 to N do Run trajectory n until its ending time T end (X n ).

Set score

Ξ n ← max 0≤t≤T end (X n ) ξ (X n (t)).
end for Sort the scores in ascending order, so Ξ (1) < . . . < Ξ (N) .

Set the level L 1 ← Ξ (k) .

while L j < l max do Discard the trajectories that did not go strictly further level L j , i.e. the ones with a score Ξ n ≤ L j .

Set I j the set of the indices of the remaining trajectories, we have

I j = N -k.
for n ∈ {1, ..., N} \ I j do Pick uniformly at random an index N j ∈ I j .

Clone the trajectory with index N j until its first enter time of ξ > L j :

T L j (X N j ) := inf t ≥ 0 : ξ X N j t > L j .
From time T L j (X N j ), simulate a new trajectory X up to the hitting time T end (X).

Replace the former trajectory n by this new one.

Denote by (X 1, j , . . . , X N, j ) ← (X 1 , . . . , X N ) the resulting particle system. Set Ξ n ← max 0≤t≤T n end ξ (X n s ). end for Sort the new maxima Ξ n in ascending order, such that L j-1 < Ξ (1) < . . . < Ξ (N) .

j ← j + 1 Set next level L j ← Ξ (k) .

end while

Set J AMS = j -1 the total number of 'while' iterations. Set X n,J AMS = X n the final trajectories. Estimate the probability of the rare event by

p AMS := 1 - k N J AMS ,
and the conditional distribution of trajectories conditioned by the rare event by:

γ AMS := p AMS η AMS = 1 N N n=1 δ X n,J AMS .
Remark 0.6.6. In Algorithm 3, we have assumed that the distribution of the score max 0≤t≤T end (X) ξ(X t ) for any initial condition X 0 = x 0 is atomless, so that no equality case are possible almost surely. Thus, as the ordered sample Ξ (1) < . . . < Ξ (N) is (almost surely) well-defined, we will sometimes order the particles at the end of stage j according to their scores and use the notation:

X (n), j 1≤n≤N .
A first non obvious property is the following.

Proposition 0.6.7. The estimators of AMS algorithm p AMS and γ AMS are unbiased.

These unbiasedness properties are consequences of a general result which can be found in [START_REF] Bréhier | Unbiasedness of some generalized adaptive multilevel splitting algorithms[END_REF]].

Yet, as we will see further, we present here an alternative proof of the unbiasedness of p AMS in the last particle situation, based on the unbiasedness of p SMC (Proposition 0.6.2) and on a coupling between these two algorithms.

This will be the main topic of the second chapter of this thesis.

Just like SMC Algorithm 2, there is a CLT for p AMS , and for the final empirical η AMS , in the last particle situation (k = 1).

Theorem 0.6.8 (Central Limit Theorem, [Cérou et al., 2019a]). The unbiased estimator p AMS satisfies

√ N ( p AMS -p) Law ----→ N→∞ 0, σ 2 ,
where

σ 2 = -p 2 ln p - l max -∞ Var η ℓ (q) d p 2 ℓ = -p 2 ln p -2 l max -∞ Var η ℓ (q) p ℓ dp ℓ , (3)
with q defined in (1).

In this formula, the integration is with respect to ℓ, which means that ℓ goes from -∞ to l max . The two terms are positive, as 0 < p < 1, and the map ℓ → p ℓ is decreasing, implying that dp ℓ is negative. Just like for SMC algorithm, we can obtain a Central Limit Theorem see ( [START_REF] Cérou | Adaptive multilevel splitting: Historical perspective and recent results[END_REF]) for the final empirical distribution and for the distribution of the pathwise bounded and continuous (with respect to uniform convergence on compact time intervals).

0.7 Summary of the contributions 0.7.1 Convergence of the SMC algorithm towards the last particle AMS algorithm (Chapter 1)

Our first contribution establishes a link between SMC Algorithm 2 and AMS Algorithm 3, in the last particle situation, i.e. k = 1. More precisely, we have shown that, under mild technical assumptions, the SMC algorithm converges towards the AMS when the number of levels i SMC in SMC tends to infinity.

The argument is the following: if we take i SMC very large (with sup i ℓ i+1 -ℓ i small), at least compared to N, there will be many useless iterations in algorithm SMC: nothing will happen at those stages. In the same way, in the few stages where a particle is unsuccessful and is re-branched, there is a good chance there will be only one such particle concerned (in a setting where all the particles have, almost surely, different maxima). So, if we take enough discrete levels, only the particle with the lowest score will be erased, just like in AMS algorithm. Moreover, the starting point of the new piece of SMC trajectory, which is the first hitting place of the next level set, will be very close to the hitting place of the current level set, again like in AMS algorithm. In summary, SMC performs the following situation: "only the lowest scored particle is erased and rebranched on another particle at an entrance point near the level defined by the maximum of the discarded particle". This is exactly what AMS Algorithm 3 does in the last particle situation.

This similitude between SMC and AMS can also be noticed from their respective estimators of the probability p.

We recall (in the last particle case k = 1):

p SMC := i SMC i=1 N(i) N p AMS := J AMS j=1 1 - 1 N = 1 - 1 N J AMS
, and the estimators of the conditional density

γ S MC := p SMC 1 N N n=1 δ X n,i SMC S MC γ AMS := p AMS 1 N N n=1 δ X n,J AMS AMS .
As we have argued, if only a single particle is unsuccessful in SMC, we get

N(i)/ N ∈ {1, 1 -1/ N} ,
so that indexing the number of branchings in SMC using the index j we obtain:

p SMC := J S MC j=1 1 - 1 N = 1 - 1 N J S MC
, where J S MC is the number of branchings in SMC. At a formal level, the estimators associated with SMC and AMS are thus identical.

Another similar viewpoint that helps understanding the convergence of SMC towards AMS consists in considering a discontinuous importance functions ξ taking a finite number of values ξ : R d → ℓ 0 , . . . , ℓ i SMC .

One can then modify slightly the AMS Algorithm 3 to allow a random number of unsuccessful particles that have the same minimal score. It can be checked that AMS and SMC are then exactly the same, and we can interpret SMC as a discretization of AMS. This will be more detailed at the beginning of Chapter 1.

All the latter motivations, already suggested in [START_REF] Cérou | Adaptive multilevel splitting: Historical perspective and recent results[END_REF], led us to define a coupling between SMC and AMS, in the last particle situation. The idea of this coupling is first to perform AMS, and then to consider a (small) discretization of SMC levels quantified by

δ := max 0≤i≤i SMC -1 (ℓ i+1 -ℓ i ) .
When we re-branch a SMC particle, we construct a coupling as follows, if possible:

• the index of the cloned particle at the j-th branching event is the same in SMC and in AMS.

• the trajectory of the cloned particle (starting from the entrance time of the respective current level) is simulated using the same Brownian motion.

Using this coupling, we proved, under some mild technical hypotheses the almost surely convergence of the SMC branching points to the AMS ones, when i SMC goes to infinity. The technical hypotheses we required are, broadly speaking, the following.

Assumptions.

• The AMS algorithm is almost surely well-define (it stops almost surely after a (random) finite number of iterations).

• X is a (strong) solution to a Stochastic Differential Equation (SDE) with Lipschitz coefficients.

• The set h ≤ h 0 : ξ(X h ) > ξ(x 0 ) is almost surely infinite for any h 0 and any choice of initial condition X 0 = x 0 (immediate strict increase of levels).

Consequently, we have the following two corollaries of our main Theorem 1.4.4 (convergence of SMC branching points to AMS ones):

Corollary 0.7.1. Let N be fixed. There exists a coupling between the SMC Algorithm 2 and the AMS Algorithm 3 such that, under the assumptions above,

p SMC a.s ---→ δ→0 p AMS ,
where δ := max 0≤i≤i SMC -1

(ℓ i+1 -ℓ i ) .
Corollary 0.7.2. The same coupling and assumptions ensure that, for any pathwise continuous (for the uniform on compacts topology) test function ψ: γ S MC (ψ)

a.s --→ δ↓0 γ AMS (ψ) .
0.7.2 Small noise limit of the AMS Algorithm for two particles (Chapter 2) Some facts about the small noise problem The second result considers a small noise context. We still work in a dynamical case, with a diffusion X in R d satisfying a stochastic differential equation taking the general form

d X t = α (X t ) dt + √ εβ (X t ) dW X t , (4)
with some given initial condition

X 0 = x 0 .
The small noise denomination means that we will have a (small) coefficient before our Brownian motion, that we will denote it √ ε > 0. In the following, we will assume that α and β are at least Lipschitz continuous.

Denoting, just like previously ξ : R d → R a smooth score, or importance, function and T l max the hitting time of the level set {ξ > l max }, we are interested in the event 'the process X reaches the level set {ξ > l max } in finite time', (so T end (X) = +∞) where l max is a given positive number, or equivalently

T l max (X) < ∞ .
The event 'the process X reaches the set {ξ > l max } in finite time' is a rare event set in a small noise context when for instance the diffusion is transient (it goes to infinity almost surely) in a direction opposite to the set {ξ > l max }:

lim t→+∞ ξ(X t ) = -∞.
The first thing we can do is to underline that SDE (4) satisfies a Large Deviations Principle, and more specifically, the Freidlin-Wentzell theorem. The Freidlin-Wentzell theorem states that, if X is the unique solution to SDE (4) for 0 ≤ t ≤ t max , t max being fixed and X 0 = x 0 , then (X t ) 0≤t≤t max satisfies a Large Deviations Principle (LDP) in C ([0, t max ]) (for the uniform topology) with the good rate function I x 0 ,t max (.) defined as follows:

I x 0 ,t max (x) = inf g∈H 1 ([0,t max ]) : x(t)=x 0 + t 0 α(x(s))ds+ t 0 β(x(s)) ġ(s)ds 1 2 t max 0 ġ (t) 2 dt.
In very general setting, we recall that a family of probability measure (µ ε ) ε>0 on some space S is said to satisfy a Large Deviations Principle with a rate function I if, for any set Γ ⊂ S , inf

• Γ I ≤ lim inf ε↓0 ε log µ ε (Γ) ≤ lim sup ε↓0 ε log µ ε (Γ) ≤ -inf Γ I,
where a rate function I is a function, which is not trivially +∞ and lower semi-continuous, i.e. the sets

x ∈ S I(x) ≤ c , for c ≥ 0, are closed in S . If, furthermore, these sets are compact, the rate function I is said to be good. We refer to [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF] for more details about the Large Deviations Theory, including Freidlin-Wentzell.

As a consequence of the Freidlin-Wentzell theory, we will prove under some assumptions that the committor

function Φ ε,l (x 0 ) := -ε log P (T l (X) < +∞ | X 0 = x 0 )
does converge to the minimizer of the rate functions over trajectories that reaches {ξ > l max } in finite time:

Φ 0,l (x 0 ) := lim ε→0 Φ ε,l (x 0 ) = inf x: T l (x)<+∞ I x 0 ,T l (x) (x). (5)
Assumptions required to obtain this convergence typically involve a drift condition towards negative values of ξ (see Lemma 2.2.1) . This means that the rare event probability is asymptotically (up to sub-exponential constants) of order exp (-Φ 0,l (x)/ε), for small ε.

Two important facts are well-known in the literature on variational calculus. First, Φ 0,l is solution, at least in the sense of viscosity solution, to the Hamilton-Jacobi equation with boundary condition:

         1 2 ββ T (DΦ 0,l , DΦ 0,l ) = DΦ 0,l α, Φ 0,l = 0 on {ξ = l} . (6)
Second, at least in a formal sense, rate function minimizing trajectories in the definition of Φ 0,l (x) in (2.5) are solution to the Ordinary Differential Equation:

         x 0 = x 0 , ẋ(t) = α(x(t)) -DΦ 0,l ββ T (x(t)). (7)
Of course, the above ODE is well-defined only under the quite strong assumption that DΦ 0,l is Lipschitz. Note that d dt Φ 0,l (x(t)) = -1 2 ββ T (DΦ 0,l , DΦ 0,l ) < 0. As a consequence, the latter ODE indeed reach {ξ > l max } if DΦ 0,l β is uniformly bounded from below away from 0 in the whole space, an assumption we will have to make in our study. Interestingly, the above facts imported from variational calculus can be reinterpreted using probability arguments.

First, the committor function is defined using h ε (x 0 ) := P T l (X) < +∞ X 0 = x 0 , which is solution to the usual elliptic Dirichlet problem:

         Dh ε α + 1 2 β T D 2 (h ε ) β = 0, h ε = 1 on {ξ = l} .
Introduction ing the process X conditioned to reach {ξ > l} at a finite time ( T l (X) < +∞ ), and then look at its distribution when ε → 0. Using Girsanov theorem, we will show that the latter conditioned process is solution to the SDE

d X t = α(X t )dt -DΦ ε,l ββ T (X t )dt + √ εβ (X t ) dW t ,
in which W t is a Brownian motion under the probability defined by conditioning with respect to T l (X) < +∞ . This type of ODE is called the effective process in the systematic approach of [START_REF] Chetrite | Nonequilibrium markov processes conditioned on large deviations[END_REF]. The latter also converges when ε → 0 towards the above ODE (7). The convergence is rigorous when the committor function DΦ ε,l is Lipschitz continuous uniformly with respect to ε ∈ R + , which is quite a very strong assumption at ε = 0 (it is related to the existence of a classical solution of the Hamilton-Jacobi equation (2.8), see comments in Section 2.3).

Simulation with the AMS Algorithmin in a specific case Among the three algorithms presented in the introduction, we will use AMS Algorithm 3 to simulate a conditional trajectory. We recall that the empirical distribution of the trajectories sampled by AMS is unbiased:

E         p AMS 1 N N n=1 ψ(X n,J AMS )         = E ψ(X) 1 T lmax (X)<+∞ .
The main question is then, when ε decreases to zero, in which situation the trajectories sampled using AMS do coincide with the limit expected by the Freidlin-Wentzell theory and given by the ODE (7).

In Chapter 2, we will be working in a quite specific case: we will work with N = 2 particles, and in the last particle version (k = 1). In particular, when ε is small, there is essentially only one common trajectory starting from x 0 and reaching the rare event set (there are two branches in the genealogical tree formed by the particles only the last few iterations). We recall that AMS gives unbiased non-normalized quantities for any number of particles, this is our main practical justification as convergence theorems such that the CLT in Theorem 0.6.8 do hold only when N goes to infinity. A description of AMS algorithm, in the N = 2 setting in question will be presented in Algorithm 4 page 91.

As a consequence, in the whole Chapter 2, we will focus, for simplicity, on the branching points given by the AMS algorithm in order to study the trajectory selected by the algorithm. The main purpose of this chapter will be in fact to study the convergence of the Markov chain given by time and position of particles at the branching (in dimension one, these are only the levels) when ε decreases to zero and to compare it to the ideal ODE (7).

As already mentioned in the introduction, in the last particle situation and in a regular situation, the number of iterations is expected to be of order -N log p = O(1/ε). As a consequence, we can expect to have a total number of iterations J AMS of order 1/ε. This order can also be computed more precisely in the special case of the dimension one: we will do it at the beginning of Chapter 2. This will be done by considering the Markov Chain given by AMS algorithm for a number ⌊r/ε⌋ of iterations where r is a given real number that represents the number of iterations divided by the scale 1/ε.

Second, we will consider a diffeomorphic change of variable in which

X = (L, A) ∈ R × R d-1 ,
where

L = ξ (X)
is a real valued process and A = fn(X) has values in R d-1 . The choice of notation here is justified by the terminology: L is the level coordinate, i.e. the one which will give the successive levels L j in AMS, and A is the auxiliary coordinate.

The auxiliary variable is constructed in such a way that the line manifold x : fn(x) = cst is always orthogonal to the level set sub-manifold x : ξ(x) = cte for the metric given by ββ T (x). The SDEs verified by the processes L and A are in the following form:

         d L t = -b (L t , A t ) dt + √ ε • σ (L t , A t ) dW L t , L 0 = l 0 , (8a)
and

         d A t = f (L t , A t ) dt + √ ε • θ (L t , A t ) dW A t , A 0 = a 0 , (8b)
where W L and W A are independent. This is easy to do locally in a neighbourhood of x : ξ(x) = cte but it is not generally global. We will assume here that such a change of variable is possible globally. This is the first assumption we state here. It will be recalled in Chapter 2, with other technical assumptions, but we need it to state Theorem 0.7.3.

This assumption is fundamental: even if the processes L and A influence each other, we need the independence of the Brownian motions. Once again, it seems that some geometric conditions influence the situation: if we can write the Brownian part of X with orthogonal coordinates, we would be able to decompose it in independent parts, using

Cochran's theorem.

In ( 8), to fit to the rare event T l max (X) < ∞ , we assume that the drift function b of L is strictly positive, so the level coordinate is, roughly speaking, attracted by -∞, for small ε. Running AMS, we will get a Markov chain corresponding to the branchings: we will have the levels L 1 , ..., L J AMS , the state of the auxiliary coordinate at the branching point A 1 , ..., A J AMS and the branching times T 1 , ..., T J AMS . Chapter 2 studies the limit of this Markov chain.

The first spatial terms of the Markov chain, given by AMS, are in blue on Figure 4. Using the notations of Algorithm 3, we have

(L j , A j ) = X (2), j-1 T (2) j , T j = T (2) j .
In the above we have used the notation

         X (1), j-1
killed particle,

X (2), j-1 surviving particle,
this is a slight abuse of notations as the indices (1) and (2) do depend of the level j.

L 1

L 2 L 3 X (2),0 = X (2),1 = X (1),2
X (1),0

X (1),1 X (2),2 X (2),0 T 1 X (2),1 T 2 X (2),3 T 3
Figure 4 -A few steps of AMS with N = 2 and k = 1

Main result

The following theorem will be discussed in Chapter 2. It is the main result of this chapter, and of this thesis. The required assumptions will be detailed further, but a sufficient informal summary is given by the following:

Assumptions.

• The coefficients of ( 8) are bounded with continuous first derivatives bounded.

• The drift coefficient and the diffusion coefficient of the level variable are bounded away from zero:

b ≥ 1/c > 0, σ ≥ 1/c > 0
for some constant c.

• For each level l ∈ R, the committor function ϕ ε,l is: i) sufficiently regular near the boundary (a, l ′ ) :

l ′ = l ⊂ R d ,
ii) is uniformly strictly decreasing with respect to l:

∂ l ϕ ε,l 1 (l, a) ≤ -1/c, ∀l ≤ l 1 , a ∈ R d-1 ,
for some constant c. All the latter properties must be uniform in ε.

Note that l → ϕ ε,l 1 (l, a) is decreasing by the Markov property.

The latter assumption is the most restrictive, at least because it is unclear how to check it in practice.

Theorem 0.7.3. Under the assumptions above, the map r → (L ⌊r/ε⌋ , A ⌊r/ε⌋ , T ⌊r/ε⌋ ) converges in probability, for the uniform topology, when ε decreases to 0, uniformly on every compact set, to a function r → (l(r), a(r), t(r)), given by the differential systems

           ˙l(r) = σ 2 (l(r),a(r)) 4b(l(r),a(r)) , ȧ(r) = f (l(r), a(r)) σ 2 (l(r),a(r)) 4(b(l(r),a(r))) 2 , and ṫ(r) = σ 2 (l(t), a(t)) 4 (b (l(t), a(t))) 2 .
We can combine these ODEs to formally write the time evolution of l and a as

         dl(t) dt = b (l(t), a(t)) , da(t) dt = f (l(t), a(t)) . (9)
From those expressions, we can make very interesting observations.

• Firstly, we see clearly that the run of AMS has no effect on the flow followed by the auxiliary coordinate, when we are able to split X in a level coordinate and an auxiliary one, with independent Brownian motions.

• Secondly, we see that the drift function -b in the definition of L (8) has become +b in the limit ODE, in time.

We can interpret this as the following: the simplest way to go up, to l max , while the drift attracts the process to -∞ is simply to reverse the drift.

• Thirdly, the writing expression ( 9) is enjoyable in the common situation (b, f ) = ∇V, where V is a potential, and the diffusion coefficient is the identity (σ, θ) = Id. In such a situation, it is well-known (and can be easily checked) that the optimal trajectories with initial condition at a local minimum of V in the Freidlin-Wentzell theory are solutions of gradient flow

d x(t) dt = +∇V(x(t)),
corresponding to a 'time-reversed' gradient descent. However the AMS limit ODE is nothing but

         d l(t) dt = +∂ l V (l(t), a(t)) , d a(t) dt = -∂ a V (l(t), a(t)) ,
which means that the optimum of Freildin-Wentzell, and the limit trajectory coincide in this situation if, and only if, the part corresponding to the auxiliary coordinate ∂ a V is equal to zero.

We can then compare the limiting ODE of the AMS algorithm with the ideal ODE derived from the small noise process conditioned to hit {ξ = l}.

Corollary 0.7.4. Let x 0 be an initial condition is given. Assume that the quasi-potential function Φ 0,l is Lipshitz continuous. Assume that for each point of the solution to the ODE (9) followed by the small noise AMS algorithm, the quasi-potential function level set is tangent to the importance function level set:

∂ a Φ 0,l (l(t), a(t)) = 0,
then the AMS ODE (9) and the ideal ODE (7) described the process conditioned to hit {ξ = l} are the same.

This corollary will be illustrated further with some numerical simulations.

We finally provide an additional corollary, which compares to the optimal case the total number of iterations (hence the log of the probability estimator) in AMS multiplied by ε (in some sense) when ε → 0. The later is denoted by r AMS and can be expressed using the ODE in Theorem 0.7.3 by the equation:

r AMS := t(l max ) 0 4 b 2 σ 2 (l(t), a(t)) dt,
where t(l max ) is the first hitting time of {ξ = l max } by the limiting ODE. Indeed, it will be recalled in Chapter 2 that the total number of iteration in an idealized case (e.g. when the importance function ξ is given by the committor function)

is given by a Poisson distribution of parameter -2 log p = -2Φ ε,l max (x 0 )/ε. This implies that in the ideal case, the total number of iterations multiplied by ε converges for small ε towards

r ideal := lim ε→0 -ε2 log p ε = 2Φ 0,l max (x 0 ).
We will prove the following corollary.

Corollary 0.7.5. Under the same conditions as in Corollary 0.7.4, the total number of iterations is asymptotically optimal, that is:

r AMS = r ideal .

Résumé des contributions

Cette section ne constitue qu'une version française de la section 0.7 et n'apporte rien de nouveau par rapport à cette dernière. La similitude entre SMC et AMS peut aussi être remarquée à partir des estimateurs respectifs de la probabilité p que l'on rappelle (dans le cas de la dernière particule k = 1) :

p SMC := i SMC i=1 N(i) N p AMS := J AMS j=1 1 - 1 N = 1 - 1 N J AMS
, et des estimateurs de la densité conditionnelle

γ S MC := p SMC 1 N N n=1 δ X n,i SMC S MC γ AMS := p AMS 1 N N n=1 δ X n,J AMS AMS .
Si, comme nous en avons discuté, une seule particule échoue dans SMC, on obtient

N i / N ∈ {1, 1 -1/ N} ,
et donc, en indexant le nombre de branchements dans SMC par j, on obtient

p SMC := J S MC j=1 1 - 1 N = 1 - 1 N
une fonction de score discontinue ξ qui prend un nombre fini de valeurs ξ : R d → ℓ 0 , . . . , ℓ i SMC .

On peut alors légèrement modifier l'algorithme AMS 3 pour permettre à un nombre aléatoire de particules ayant échoué qui ont le même score. On peut ensuite vérifier que AMS et SMC sont exactement identiques, et on peut interpréter SMC comme une discrétisation de AMS. Cela sera détaillé davantage au début du Chapitre 1.

Toutes ces dernières motivations, déjà mentionnées dans [START_REF] Cérou | Adaptive multilevel splitting: Historical perspective and recent results[END_REF], nous ont conduit à introduire un couplage entre SMC et AMS, dans le cadre de la dernière particule. L'idée de ce couplage est d'abord de réaliser AMS, et de considérer une (petite) discrétisation des niveaux SMC quantifiés par

δ := max 0≤i≤i SMC -1 (ℓ i+1 -ℓ i ) .
Quand on re-branche une particule SMC, on construit un couplage comme suit, si possible :

• l'indice de la particule clonée au j-ième évènement de branchement est le même dans SMC et dans AMS,

• la trajectoire de la particule clonée (partant du temps d'atteinte du niveau actuel) est simulée en utilisant le même mouvement brownien.

En utilisant ce couplage, nous avons montré, sous certaines hypothèses techniques, la convergence presque sûre des points de branchements de SMC vers ceux d'AMS, quand i SMC tend vers l'infini. Les hypothèses techniques que nous nous sommes données sont, dans l'ensemble, les suivantes.

Hypothèses.

• L'algorithme AMS est presque sûrement bien défini (il s'arrête après un nombre fini d'itérations aléatoire).

• X est une solution (forte) d'une Équation Différentielle Stochastique (EDS) avec des coefficients lipschitziens.

• L'ensemble h ≤ h 0 : ξ(X h ) > ξ(x 0 ) est presque sûrement infini pour tout h 0 et pour n'importe quelle condition initiale X 0 = x 0 (stricte croissance immédiate des niveaux).

Sous ces hypothèses, le théorème principal 1.4.4 (convergence des points de branchement de SMC vers ceux de AMS) s'applique et induit les deux corollaires suivants.

Corollaire 0.8.1. Soit N fixé. Sous les hypothèses ci-dessus, il existe un couplage entre l'algorithme SMC 2 et l'algorithme AMS 3, tel que

p SMC p.s. ---→ δ→0 p AMS , où δ := max 0≤i≤i SMC -1 (ℓ i+1 -ℓ i ) .
Corollaire 0.8.2. Sous les mêmes hypothèses et pour le même couplage, pour toute fonction test ψ continue sur l'espace des trajectoires (pour la topologie de la convergence uniforme sur les compacts) :

γ S MC (ψ) p.s.
--→ δ↓0 γ AMS (ψ) .

0.8.2 Limite en petit bruit de l'algorithme AMS à deux particules (Chapitre 2)

Généralités sur le problème petit bruit Le second axe s'inscrit dans un contexte petit bruit. On travaille encore dans un cadre dynamique, avec une diffusion X dans R d satisfaisant une EDS de la forme

d X t = α (X t ) dt + √ εβ (X t ) dW X t , (10)
avec pour condition initiale

X 0 = x 0 .
La dénomination « petit bruit » signifie qu'il y a un (petit) coefficient devant le mouvement brownien que l'on notera ε > 0. On supposera que α et β sont au moins lipschitziennes.

En notant, comme précédemment ξ : R d → R la fonction de score et T l max le temps d'atteinte de l'ensemble {ξ > l max }, on s'intéresse à l'évènement «le processus X atteint l'ensemble niveau {ξ > l max } en temps fini», (c'est-àdire T end (X) = +∞.) où l max est un nombre positif donné, ou de manière équivalente

T l max (X) < ∞ .
L'évènement « le processus X atteint l'ensemble {ξ > l max } en temps fini » est souvent un évènement rare, dans un contexte petit bruit. Typiquement, c'est le cas lorsque la diffusion est transiente (elle va à l'infini presque sûrement) dans une direction opposée à l'ensemble {ξ > l max } :

lim t→+∞ ξ(X t ) = -∞.
La première chose que l'on peut faire est de souligner que l'EDS (10) satisfait un Principe de Grandes Déviations, et plus précisément, le théorème de Freidlin-Wentzell. Le théorème de Freidlin-Wentzell stipule que, si X est l'unique solution de l'EDS (10) pour 0 ≤ t ≤ t max , avec t max fixé, et X 0 = x 0 , alors (X t ) 0≤t≤t max satisfait un Principe de Grandes Déviations (PGD) dans C ([0, t max ]) avec pour bonne fonction de taux I x 0 ,t max (•) définie comme suit :

I x 0 ,t max (x) = inf g∈H 1 ([0,t max ]) : x(t)=x 0 + t 0 α(x(s))ds+ t 0 β(x(s)) ġ(s)ds 1 2 t max 0 ġ (t) 2 dt.
De manière générale, on rappelle qu'une famille de mesures de probabilités (µ ε ) ε>0 sur un espace S satisfait un PGD avec fonction de taux I si, pour tout ensemble Γ ⊂ S ,

-inf • Γ I ≤ lim inf ε↓0 ε log µ ε (Γ) ≤ lim sup ε↓0 ε log µ ε (Γ) ≤ -inf Γ I,
où une fonction de taux est une fonction non trivialement égale à +∞ et semi-continue inférieurement i.e. les ensemble x ∈ S I(x) ≤ c , pour c ≥ 0, sont fermés dans S . Si, de plus, ces ensembles sont compacts, la fonction de taux I est dite bonne. Nous renvoyons vers [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF]] pour davantage de détails concernant la théorie des Grandes Déviations, y compris celle de Freidlin-Wentzell.

En conséquence de Freidlin-Wentzell, nous allons montrer sous certaines hypothèses que la fonction committor

Φ ε,l (x 0 ) := -ε log P (T l (X) < +∞ | X 0 = x 0 )
converge vers le minimiseur des fonctions de taux sur les trajectoires qui atteignent {ξ > l max } en temps fini :

Φ 0,l (x 0 ) := lim ε→0 Φ ε,l (x 0 ) = inf x: T l (x)<+∞ I x 0 ,T l (x) (x). ( 11
)
Les hypothèses requises pour obtenir cette convergence sont typiquement une condition sur la dérive vers les valeurs négatives de ξ (voir Lemme 2.2.1). Cela signifie que la probabilité de l'évènement rare est asymptotiquement (à des constantes sous-exponentielles près) d'ordre exp (-Φ 0,l (x)/ε), pour de petits ε.

Deux choses importantes sont bien connues en calcul variationnel. Premièrement, Φ 0,l est solution, au moins au sens des solutions de viscosité, d'une équation d'Hamilton-Jacobi avec des conditions de bord

         1 2 ββ T • (DΦ 0,l , DΦ 0,l ) = DΦ 0,l α, Φ 0,l = 0 on {ξ = l} . ( 12
) où DΦ = (∂ 1 Φ, ..., ∂ d Φ) = (∇Φ) T est le co-gradient.
Deuxièmement, au moins dans un sens formel, les trajectoires minimisantes de la définition de Φ 0,l (x), voir (2.5), sont solutions de l'Équation Différentielle Ordinaire :

         x 0 = x 0 , ẋ(t) = α(x(t)) -DΦ 0,l ββ T (x(t)). ( 13
)
Bien sûr, l'EDO ci-dessus est bien définie sous l'hypothèse relativement forte que ∇Φ 0,l est lipschitzien. On remarquera que d dt Φ 0,l (x(t)) = -1 2 ββ T (∇Φ 0,l , ∇Φ 0,l ) < 0. En conséquence, l'EDO précédente atteint bel et bien {ξ > l max } si DΦ 0,l β est uniformément minorée par une constante strictement positive sur tout l'espace : une hypothèse que nous devrons faire.

Les faits précédents, qui proviennent du calcul variationnel, peuvent être interprétés en utilisant des arguments probabilistes. D'une part, la fonction committor est définie comme h ε (x 0 ) := P T l (X) < +∞ X 0 = x 0 , qui est solution du problème elliptique de Dirichlet standard

         Dh ε α + 1 2 β T D 2 (h ε ) β = 0, h ε = 1 on {ξ = l} .
En écrivant l'EDP vérifiée par Φ ε,l = -ε log h ε , on retrouve directement (mais formellement en prenant ε → 0) l'équation d'Hamilton-Jacobi ( 12) satisfaite par Φ 0,l lorsque ε tend vers 0. D'autre part, grâce aux Grandes Déviations et au théorème de Girsanov, on peut retrouver l'EDO (13) satisfaite par la trajectoire minimisante associée comme suit. En utilisant formellement le principe de conditionnement de Gibbs (voir [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF]), on peut identifier la trajectoire minimisante dans la définition de Φ 0,l en considérant le processus X conditionné par atteindre {ξ > l} en temps fini T l (X) < +∞ , puis à regarder sa loi quand ε → 0. En utilisant le théorème de Girsanov, nous allons montrer que ce dernier processus conditionné est solution de l'EDS

d X t = α(X t )dt -ββ T ∇Φ ε,l (X t )dt + √ εβ (X t ) dW t ,
où W t est un mouvement brownien sous la probabilité conditionnelle relative à T l (X ε ) < +∞ . Cette équation converge aussi quand ε → 0 vers l'EDO (13). Cette convergence est rigoureuse lorsque la fonction committor ∇Φ ε,l est lipschitziennepar rapport à ε ∈ R + , qui est une hypothèse assez forte en ε = 0 (voir commentaires ci-dessous).

Simulation avec l'algorithme AMS dans un cas particulier Parmi les trois algorithmes présentés dans l'introduction, nous utiliserons l'algorithme AMS 3 pour simuler une trajectoire conditionnelle. On rappelle que la distribution empirique des trajectoires échantillonnées par AMS est sans biais

E         p AMS 1 N N n=1 ψ(X n,J AMS )         = E ψ(X) 1 T lmax (X)<+∞ .
La question principale est alors, quand ε décroît vers zéro, dans quelle situation les trajectoires échantillonnées en utilisant AMS coïncident effectivement avec la limite obtenue par la théorie de Freidlin-Wentzell et donnée par l'EDO (13).

Dans le chapitre 2, nous travaillerons dans un cadre quelque peu spécifique. On travaillera avec N = 2 particules, et dans le cas dernière particule (k = 1). En particulier, quand ε est petit, il y a essentiellement une seule trajectoire partant de x 0 qui atteint l'ensemble de l'évènement rare (il y a deux branches dans l'arbre généalogique formé par les particules, seulement lors des dernières itérations). On rappelle que AMS donne des quantités non-normalisées non-biaisées pour n'importe quel nombre de particules, il s'agit là de notre principale justification pratique, puisque les théorèmes de convergence tels que le Théorème Central Limite 0.6.8 ne sont valides que lorsque N tend vers l'infini. Une description de l'algorithme AMS avec N = 2 sera présentée dans l'algorithme 4 page 91.

En conséquence, dans tout le chapitre 2, nous nous concentrerons, par simplicité, sur les points de branchement donnés par l'algorithme AMS, avec l'objectif d'étudier la trajectoire sélectionnée par l'algorithme. Le but principal de ce chapitre sera, en effet, d'étudier la convergence de la chaîne de Markov donnée par le temps et la position des particles aux branchements (en dimension un, cette dernière ne concerne que les niveaux) quand ε décroît vers zéro, et de la comparer à l'EDO idéale (13).

Comme cela a déjà été mentionné dans l'introduction, dans le cadre de la dernière particule, dans un cas régu- Deuxièmement, nous allons considérer un changement de variables difféomorphe

X = (L, A) ∈ R × R d-1 , où L = ξ (X)
est un processus à valeurs réelles et A = fn(X) est à valeurs dans R d-1 . Le choix de notation ici est justifié par la terminologie : L est la coordonnée niveau, i.e. celle qui nous donnera les niveaux successifs L j dans AMS et A est la coordonnée auxiliaire. La coordonnée auxiliaire est construite de telle façon que x : fn(x) = cte est toujours orthogonale à la sous-variété x : ξ(x) = cte pour la métrique donnée par ββ T (x). Les EDS vérifiées par les processus L et A sont de la forme suivante Dans ( 14), pour convenir au cadre des évènements rares donné par T l max (X) < ∞ , nous supposerons que la dérive b de L est strictement positive, afin que la coordonnée niveau soit en quelque sorte attirée par -∞, pour de faibles valeurs de ε > 0.

       d L t = -b (L t , A t ) dt + √ ε • σ (L t , A t ) dW L t , L 0 = l 0 , (14a) et        d A t = f (L t , A t ) dt + √ ε • θ (L t , A t ) dW A t , A 0 = a 0 , (14b)
En réalisant AMS avec le processus décomposé (L, A), nous obtiendrons une chaîne de Markov correspondant aux branchements : nous aurons les niveaux L 1 , ..., L J AMS , les états de la coordonnée auxiliaire aux points de branchements A 1 , ..., A J AMS et les temps de branchements T 1 , ..., T J AMS . Le chapitre 2 est consacré à l'étude de la limite de cette chaîne.

Les premiers termes spatiaux de celle-ci, donné par AMS, sont en bleu sur la Figure 5.

En reprenant les notations de l'algorithme 3, on a

(L j , A j ) = X N j , j-1 T N j j , T j = T N j j . L 1 L 2 L 3 X (2),0 = X (2),1 = X (1),2
X (1),0

X (1),1 X (2),2 X (2),0 T 1 X (2),1 T 2 X (2),3 T 3
Figure 5 -A few steps of AMS with N = 2 and k = 1

Résultat principal Le théorème suivant sera détaillé dans le chapitre 2. Il s'agit du principal résultat de ce chapitre, ainsi que de cette thèse. Les hypothèses seront détaillées plus loin, mais nous allons faire les suivantes :

Hypothèses.

• Les coefficients de (14) sont bornés avec des dérivés premières continuees et bornées.

• Les coefficients de dérive et de diffusion de la variable niveau sont uniformément minorés par des quantités strictement positives :

b ≥ 1/c > 0, σ ≥ 1/c > 0 avec c une certaine constante.
• Pour tout niveau l ∈ R, la fonction committor ϕ ε,l est : i) suffisamment régulière au voisinage de (a, l ′ ) :

l ′ = l ⊂ R d ,
ii) est uniformément strictement décroissante par rapport à l :

∂ l ϕ ε,l 1 (l, a) ≤ -1/c, ∀l ≤ l 1 , a ∈ R d-1 ,
avec c une certaine constante. Toutes les propriétés précédentes doivent être uniformes en ε.

On souligne que l → ϕ ε,l 1 (l, a) est décroissante par propriété de Markov fort.

Théorème 0.8.3. Sous les hypothèses précédentes, l'application r → (L ⌊r/ε⌋ , A ⌊r/ε⌋ , T ⌊r/ε⌋ ) converge uniformément sur tout compact en probabilité, quand ε décroît vers 0, vers une fonction r → (l(r), a(r), t(r)), donnée par les systèmes différentiels

           ˙l(r) = σ 2 (l(r),a(r)) 4b(l(r),a(r)) , ȧ(r) = f (l(r), a(r)) σ 2 (l(r),a(r)) 4(b(l(r),a(r))) 2 , et ṫ(r) = σ 2 (l(r), a(r)) 4 (b (l(r), a(r))) 2 .          dl(t) dt = b (l(t), a(t)) , da(t) dt = f (l(t), a(t)) . (15)
De ces expressions, on peut souligner plusieurs observations intéressantes.

• Premièrement, on voit clairement que la réalisation complète d'AMS n'a pas d'effet sur le flow suivi par la coordonnée auxiliaire, lorsqu'il est possible de séparer X en une coordonnée niveau, et une coordonnée auxiliaire, avec deux mouvements browniens indépendants.

• Deuxièmement, on voit que la dérive -b dans la définition de L (14) est devenu +b dans l'EDO limite en temps.

On peut interpréter cela comme suit : la façon la plus simple de monter, jusqu'à l max alors que la dérive attire le processus vers -∞ est simplement de renverser la dérive.

         d l(t) dt = +∂ l V (l(t), a(t)) , d a(t) dt = -∂ a V (l(t), a(t)) ,
ce qui signifie que l'optimum de la théorie de Freidlin-Wentzell, et la trajectoire limite coïncident dans cette situation si, et seulement si, la partie correspondant à la coordonnée auxiliaire ∂ a V est égale à zéro.

On peut ensuite comparer l'EDO limite de l'algorithme AMS à l'EDO qui découle du processus à petits bruits, conditionné par atteindre {ξ = l}.

Corollaire 0.8.4. Soit x 0 une condition initiale donnée. On suppose que le quasi-potentiel Φ 0,l est lipschitzien. On suppose que pour tout point de la solution de l'EDO (15), le quasi-potentiel est tangent à la ligne de niveau de la fonction d'importance :

∂ a Φ 0,l (l(t), a(t)) = 0,
alors l'EDO AMS (15) et l'ODE idéale (13) décrivant le processus conditionné par atteindre {ξ = l} sont égales/ Ce corollaire sera illustré plus loin dans le document à l'aide de simulations numériques.

On énonce un corollaire supplémentaire, qui compare, au cas optimal, le nombre d'itérations totales (le log de l'estimateur de la probabilité) dans AMS multiplié par ε (dans un certain sens) quand ε → 0. Ce dernier est noté r AMS et peut-être exprimé en utilisant l'EDO dans le Théorème 0.8.3 par :

r AMS := t(l max ) 0 4 b 2 σ 2 (l(t), a(t))
r ideal := lim ε→0 -ε2 log p ε = 2Φ 0,l max (x 0 ).
Nous montrerons le corollaire suivant.

Corollaire 0.8.5. Sous les même hypothèses que le corollaire précédent, on a

r AMS = r ideal .
Chapter 1

AMS IS THE LIMIT OF SMC WITH A GROWING NUMBER OF LEVELS

This chapter is a joint work with Benjamin Dufée, who was also a PhD student in Rennes, at INRIA.

Introduction and main results

Let us first recall the main algorithms of interest with associated notation. We recall that the goal is estimate the rare event:

T R (X) < T end (X) ,

where

R = ξ = ℓ i SMC = l max = x : ξ(x) = ℓ i SMC = l max ⊂ R d ,
and T end is some ending time: in our context, we will work for simplicity with

T end = T -1 .
X denotes a strong Markov diffusion, T R (X) denotes the hitting time of the set R and ξ is a continuous importance function.

We recall the SMC Algorithm 2 and AMS Algorithm 3. However, we underline there is a slight difference between the SMC algorithm we state right after, and the one presented in the introduction. Indeed, in SMC Algorithm 2 bis, at each discrete level ℓ, SMC always simulate new trajectories until the end (and not only until they reach the next SMC level). This modification does not change the distribution of the whole algorithm: see [START_REF] Bréhier | Unbiasedness of some generalized adaptive multilevel splitting algorithms[END_REF] for a formal proof, although this is arguably obvious by a simple application of the Markov property level by level and could be done directly in our context using a precise algorithmic construction making explicit the random seed dependence.

Algorithm 2 bis Sequential Monte Carlo (SMC)

Require: N initial particles with initial condition x 0 , importance function ξ and levels ξ(x 0 ) = ℓ 0 < ... < ℓ i SMC = l max .

for n = 1 to N do Run trajectory of particle n until its ending time. T end (X n ) end for

for i = 1 to i SMC do
Discard the trajectories X n that did not reach level ℓ i .

Denote N(i) the number of remaining trajectories and I i the set of their indices.

for n ∈ {1, ..., N} \ I i do Take uniformly at random an index m in I i , clone the trajectory m from time 0 up to time T ℓ i (X m ), and replace the unsuccessful trajectory of particle n by the clone.

Run (the cloned) trajectory of particle n from

T ℓ i (X n ) (which is equal to T ℓ i (X m ) from cloning) until its ending time T end (X n ). end for
Denote by (X 1,i , . . . , X N,i ) ← (X 1 , . . . , X N ) the resulting particle system. end for Estimate the probability of the rare event p = P T R (X) < T end (X) , where R = ξ > ℓ i SMC by

p SMC := i SMC i=1 N(i) N .
If ψ is a pathwise function, denote its average in the rare event by

γ (ψ) := E ψ(X) 1 T R (X)<T end (X) ,
and estimate it using:

γ S MC (ψ) := p SMC 1 N N n=1 ψ X n,i SMC .
Algorithm 3 Adaptive Multilevel Splitting (AMS), k-th particle version Require: N initial independent trajectories (X n ) 1≤n≤N with common law L (X) and initial condition x 0 , the number k of trajectories to discard at each step, importance function ξ, final level l max .

j ← 1 (iteration index) for n = 1 to N do Run trajectory n until its ending time

T end (X n ). Set score Ξ n ← max 0≤t≤T end (X n ) ξ (X n (t)).
end for Sort the scores in ascending order, so

Ξ (1) < . . . < Ξ (N) . Set the level L 1 ← Ξ (k) .
while L j < l max do Discard the trajectories that did not go strictly further level L j , i.e. the ones with a score Ξ n ≤ L j .

Set I j the set of the indices of the remaining trajectories, we have

I j = N -k.
for n ∈ {1, ..., N} \ I j do Pick uniformly at random an index N j ∈ I j .

Clone the trajectory with index N j until its first enter time T L j (X N j ) of ξ > L j . From time T L j (X N j ), simulate a new trajectory X up to the hitting time T end (X).

Replace the former trajectory n by this new one

Set Ξ n ← max 0≤t≤T n end ξ (X n s ). end for
Denote by (X 1, j , . . . , X N, j ) ← (X 1 , . . . , X N ) the resulting particle system. Sort the new maxima Ξ n in ascending order, such that L j-1 < Ξ (1) < . . . < Ξ (N) .

j ← j + 1 Set level L j ← Ξ (k) .

end while

Set J AMS = j -1 the total number of 'while' iterations. Estimate the probability of the rare event by

p AMS = 1 - k N J AMS .
If ψ is a pathwise function, denote its average in the rare event by

γ (ψ) := E ψ(X) 1 T R (X)<T end (X) ,
and estimate it using:

γ AMS (ψ) := p AMS 1 N N n=1 ψ X n,J AMS .
As mentioned in the introduction, there are connections between AMS and SMC.

Firstly, AMS is an adaptive version of SMC, by the way it has been introduced: the levels are no longer given a priori, but are defined from the particles.

Secondly, we will develop in this section another vision of AMS, as a limit of SMC with growing number of levels, or as a SMC with a continuum of levels. We will focus on the last particle situation, meaning k = 1 in AMS.

We recall that, in the dynamic case, the number of particles erased at each stage is then almost surely equal to 1, and not only at least equal to 1.

Thirdly, let us discuss a bit about the algorithms with a discrete importance function ξ. Let us assume that ξ takes its values in a finite set ℓ 0 , ..., ℓ i SMC . This situation does not fit to our context, as the scores of two particles might be equal, but we still present it, as it is a good argument to see the link between these two algorithms. When particles can have same maxima, there exists a natural variant of AMS in which the number of killed trajectories might not be exactly k: it is random and is given by those scores not strictly greater than the k-th one:

N -N(i) := n ∈ ⟦1, N⟧ : Ξ n ≤ Ξ (k) .
In this discrete importance function situation, AMS with the last particle k = 1 tuning and SMC will then be exactly the same see Figure 1.1. Let us quickly present a way to fit to the previous description in a slightly more general context, where the importance function ξ is no longer supposed to take discrete values. We choose i SMC ∈ N * , we set ℓ 0 the first SMC level as the score of the initial condition, i.e.

{ ξ = ℓ0 } { ξ = ℓ1 } { ξ = ℓ2 } ξ = ℓ i SMC = l max
ℓ 0 := ξ (x 0 ) , and define the other SMC levels as follows

ℓ i := l max -ℓ 0 i SMC • i + ℓ 0 .
This way, running AMS with a discrete importance function

ξ AMS = l max -ℓ 0 i SMC • i SMC l max -ℓ 0 • ξ + ℓ 0 ,
brings us back the discrete situation (this transformation is interesting to link SMC and AMS algorithms, but has no real practical interest).

This similitude between SMC and AMS can also be noticed from their respective estimators of the probability p we recall (in the last particle case k = 1):

p SMC := i SMC i=1 N(i) N p AMS := J AMS j=1 1 - 1 N = 1 - 1 N J AMS
, and the estimator of the conditional density

γ S MC := p SMC 1 N N n=1 δ X n,i SMC S MC , γ AMS := p AMS 1 N N n=1 δ X n,J AMS AMS .
If, as we will argue below, either no or a single particle is unsuccessful in SMC (with an overwhelmingly high probability), we get

N(i)/ N ∈ {1, 1 -1/ N} ,
so that indexing the number of branchings in SMC using the index j we obtain:

p SMC := J S MC j=1 1 - 1 N = 1 - 1 N J S MC
, where J S MC is the number of branchings in SMC. At a formal level, the estimators associated with SMC and AMS are thus identical.

Remark 1.1.1. The similitude is not restricted to the estimators: it is interesting to compare the asymptotic variances, in Central Limit Theorems 0.6.5 and 0.6.8. For this, let us first recall that for any suitable integer i,

p ℓ i := P (T ℓ i ≤ T R ∧ T end ) θ i := p ℓ i /p ℓ i-1 ,
where T ℓ i is the first hitting time of the level set {ξ = ℓ i }. The p ℓ i s are the intermediate probabilities, the θ i are the transition probabilities between two consecutive intermediate regions. Let us assume, for simplicity in the coming computations, that the first intermediate probability p ℓ 1 is equal to 1, then, one has

i SMC i=1 1 θ i -1 = i SMC i=1 - p ℓ i -p ℓ i-1 p ℓ i ------→ i SMC →∞ i SMC ℓ 1 dp ℓ p ℓ = -p ln p l max = -ln p,
as the final SMC level is the level we aim at pass. What we just did is, formally, show that the asymptotic variance in CLT 0.6.8 is the continuous levels limit of the asymptotic variance in CLT 0.6.5. Identically, we formally have

i SMC i=1 f (ℓ i ) p 2 ℓ i-1 -p 2 ℓ i ------→ i SMC →∞ - l max ℓ 1 f (ℓ) d p 2 ℓ ,
which allows us the same interpretation for the asymptotic variance of the Central Limit Theorems for the final empirical distributions. In a way, as the Central Limit Theorems for SMC algorithm are only valid on the non-extinction event, the convergence of the asymptotic variances would suggest that they would remain true in a general setting, as soon as the extinction probability gets small enough, typically for N → ∞.

Our main contribution is a rigorous proof, under mild technical assumptions, that the SMC algorithm converges towards the AMS algorithm, in the last particle k = 1, when the number of levels i SMC in SMC tends to infinity. The argument is the following: if we take i SMC very large (with sup i ℓ i+1 -ℓ i small), at least compared to N, there will be many useless iterations in algorithm SMC: nothing will happen at those stages. In the same way, in the few stages where some particle is unsuccessful and is re-branched, there is a good chance there will be only one such particle concerned (in a setting where all the particles have, almost surely, different maxima). So, if we take enough discrete levels, only the lowest score particle will be erased, just like in AMS algorithm. Moreover, the starting point of the new piece of SMC trajectory, which is the first hitting place of the next level set, will be very close to the hitting place of the current level set, again like in AMS algorithm. In summary, the following situation: "only the lowest scored particle is erased and rebranched on a point near the level set given by the maximum of the discarded particle" is exactly what AMS Algorithm 3 does in the last particle situation.

All the latter motivations led us to define a coupling between SMC and AMS, in the last particle situation. The idea of this coupling is first to perform AMS, and consider a (small) discretization of SMC levels quantified by

δ := max 0≤i≤i SMC -1 (ℓ i+1 -ℓ i ) .

Assumptions

When we re-branch a SMC particle, we construct a coupling as follows, if possible:

• the index of the cloned particle at the j-th branching event is the same in SMC and in AMS,

• the trajectory of the cloned particle (starting from the entrance time of the respective current level) is simulated using the same Brownian motion.

Using this coupling, we proved, under some mild technical hypotheses the almost surely convergence of the SMC branching points to the AMS ones, when i SMC goes to infinity. The technical hypotheses we required are given in the next section. Broadly speaking, they are the following:

• the AMS algorithm is almost surely well-define (it stops almost surely after a (random) finite number of iterations),

• X is a (strong) solution to a Stochastic Differential Equation (SDE) with Lipschitz coefficients,

• the set h : ξ(X t+h ) > ξ(X t ) is almost surely infinite near h = 0 (immediate strict increase of levels).

Thus, as consequences we have the following two corollaries of our main Theorem 1.4.4:

Corollary 1.1.2. Let N be fixed. There exists a coupling between the SMC Algorithm 2 and the AMS Algorithm 3 such that, under the assumptions above,

p SMC a.s ---→ δ→0 p AMS , where δ := max 0≤i≤i SMC -1 (ℓ i+1 -ℓ i ) .
Corollary 1.1.3. The same coupling and assumptions ensure that, for any pathwise continuous (for the uniform on compacts topology) test function ψ: γ S MC (ψ)

a.s ---→ δ→0 γ AMS (ψ) .
This chapter will be organized as follows

• We first give the assumptions we will require, about the process X, its hitting times and AMS algorithm.

• We will then prove some Lemmas. The first one states than the sequence of the levels is strictly increasing, almost surely. The second one states that the hitting times are continuous on some sets, the third one gives a right convergence of these same hitting times, and the last one deals with the almost surely regularity of two processes, in relation to their initial condition.

• We will then describe the coupling, prove the convergence between the genealogical trees, and conclude about the unbiasedness property inherited.

Assumptions

Firstly, we want to ensure we use the AMS algorithm in a non-degenerate case: we will assume that the total number of iterations of AMS Algorithm 3 is almost surely finite. We will make this assumption in this whole chapter, and refer to [Cérou et al., 2019a] (see also Chapter 2) to provide some explicit conditions implying Assumption 1.2.1.

and that we assume, for simplicity, that T end = T -1 .

Assumption 1.2.4. We assume that, almost surely, its ending time is finite, for any initial condition x ∈ R d , i.e.

T -1 (X x ) = T end (X x ) < ∞,
where X x t is the unique solution to the SDE (1.1) with the initial condition X 0 = x.

Remark 1.2.5. (Implied restriction on ξ) If one thinks of ξ as a function with a maximum at x * in a neighborhood of x * with ξ(x * ) = l, then Assumption 1.2.3 cannot not hold for B = {ξ > l} at initial point x * . So it seems that some analytic conditions on ξ are hidden in Assumption 1.2.3. Indeed, when it came to exhibit some sufficient conditions so that this assumption holds true (in the diffusion case), the authors of [Cérou et al., 2019a] pointed out (see Lemma 2.3) the following: there exists δ > 0 such that, in R d :

|Dξ| ≥ δ > 0.
This kind of condition prevents from the "flatness" of ξ on any neighbourhood. In particular, ξ indeed cannot have any local extremum (Dξ 0).

Continuity properties and hitting times

We begin this section with a lemma which is a direct consequence of Assumption 1.2.3 This lemma is stated in [Cérou et al., 2019a].

Lemma 1.3.1. Assumption 1.2.3 ensures the following related properties: i) there are almost surely no equality case in scores of particles in AMS (Algorithm 3), ii) (L j ) j is almost surely strictly increasing.

Proof. For this we remind the definition of L j+1 ,

L j+1 := min 1≤n≤N          sup t≤T n, j R ∧T n, j end ξ X n, j t          .
Let us take j a suitable integer and focus on the construction of the particles at stage j + 1. First, we know that the particles X 1, j , ..., X N, j all have scores at least equal to L j , by construction in AMS Algorithm 3. Let us denote

T n j := T L j X n, j := inf t ≥ 0, ξ X n, j t > L j ,
the first hitting time of L j by the n-th particle at the end of stage j.

For each n, because of Assumption 1.2.3, we have for all h, almost surely, sup

T n j+1 ≤t≤h+T n j+1 ξ X n, j t > ξ X T n j = L j ,
and so

sup t≥0 ξ X n, j t > L j ,
which proves that L j+1 > L j , almost surely.

We can similarly prove the fact that the scores of particles are almost surely different by induction. We quickly give the argument. A re-branched and newly sampled particle can be stopped at the first hitting time T of the score (denoted L) of another different particle or at its ending time Tend . If T = Tend , one has by continuity and Assumption 1.2.4

(trajectories are finite) that the score of the re-branched particle is almost surely strictly lower than L. If T < Tend is finite, by Assumption 4 and the strong Markov property, we obtain that the score of the re-branched particle is strictly greater than L. Induction enables to conclude. □

Let us consider the space C R, R d of continuous trajectories endowed with the topology of the uniform convergence on compact sets. The continuity of hitting times with respect to this topology will be of upmost importance in the coupling that follows. A sufficient condition (C B ) is given so that this continuity holds, and we will see it is related to the Assumption 1.2.3.

For any closed or open set B ⊂ R d , we know that the mapping

T B : C R, R d -→ [0, +∞] y -→ inf {t ≥ 0, y t ∈ B}
is measurable (N.B.: Borel measurability of hitting times can be proven by a constructive procedure if B is low in the so-called Borel hierarchy, that is e.g. directly countably generated by open and closed sets, but not if it is Borel). We consider then, for a given trajectory x, the property

T B (x) = T B (x) . (C B )
The first thing we can underline is that Assumption 1.2.3 precisely states that X must satisfy (C B ) almost surely for any region of the type B = {ξ > ℓ}, for any ℓ ∈ R.

The following results will be fundamental for the proof of theorem 1.4.4. It states that the mapping T B is continuous at trajectories verifying (C B ).

Lemma 1.3.2. (Continuity of the hitting times) Let B ⊂ R d be a set, then the mapping T B is continuous, for the topology endowed by the uniform convergence on compact sets, on the subset of trajectories x satisfying property (C B ), i.e.: lim

x n →x T B (x n ) = lim x n →x T B (x n ) = T B (x) = T B (x) .
Proof. Let (x n ) n be a sequence converging uniformly on any compact set to x ∈ C R, R d . The proof will be divided into three steps:

• Step 1: Show that lim sup n T B (x n ) ≤ T B (x) .
• Step 2: Show that

T B (x) ≤ lim inf n T B (x n ) .
• 1) Let us assume, without loss of generality, that T B (x) < +∞. By continuity of x, we have x T B(x)+ε ∈ B for ε > 0 small enough, and as x n converges uniformly to x on every compact set, we have

x n T B(x) +ε -x T B(x) +ε --→ ε↓0 0.
Consequently, since B is an open set, for ε small enough, x T B(x) +ε ∈ B, and next for n large enough

x n T B(x) +ε ∈ B T B (x n ) ≤ T B (x) + ε.
Taking the limit as ε → 0, we get

lim sup n T B (x n ) ≤ T B (x) .
2) As in step 1, let us assume that t 0 := lim inf n T B (x n ) < +∞. Then, up to an extraction process, a sequence (t n ) n≥1 can be built such that:

t n ≤ t 0 + 1 (i) t n -----→ n→+∞ t 0 (ii) d x n t n , B -----→ n→+∞ 0. (iii)
Because [0, t 0 + 1] is compact and that x n converges to x on every compact set, the set x n t , t ≤ t 0 + 1, n ≥ 0 is bounded (so it can be encompassed in a compact set). Thus there exists a sub-sequence

(s n ) of (t n ) such that (x n s n ) n converges to some b ∈ R d . According to (iii), b ∈ B and then x t 0 = b ∈ B. Finally, T B (x) ≤ t 0 = lim inf n T B (x n ) .
3) As x verifies the property (C B ), it implies that, almost surely

T B (x) = T B (x) = T B (x) .
Then one concludes that T B (x) = lim n→+∞ T B (x n ), which ends the proof.

□

We will need a right convergence result about the hitting times, stated in the following lemma.

Lemma 1.3.3. Under Assumption 1.2.3, for each l ∈ R, on the event l < max ξ (X t ) , t ≥ 0 , it holds almost surely:

lim l ′ →l T l ′ (X) = T l (X) .
(NB: there exists some random level L such that l → T l (X) is discontinuous at L but the latter have an atomless distribution that is P(L = l) = 0).

Proof. Let us first show lim

l ′ ↓l T l ′ (X) = T l (X). By definition, T l = T l (X) := inf s ≥ 0, ξ (X t ) > l , so T l is an accumulation point of the open set t ≥ 0, ξ (X t ) > l (it
is open because of the continuity of ξ). So, using the almost sure continuity of ξ (X), we do know thanks to assumption 1.2.3 that, for any ε ′ > 0, there exists t = T L + ε, with 0 < ε < ε ′ such that ξ(X t ) > l. Denoting ξ (X t ) = l + δ for some δ > 0, then

T l ≤ T l+δ < T l + ε.
Let us now show lim

l ′ ↑l T l ′ (X) = T l (X). By contradiction, if lim l ′ ↑l T l ′ (X) < T l (X) one can find a sequence of times t m → t ∞ < T l (X)) with ξ(X t m ) → l.
By compactness and continuity of trajectories, this implies ξ(X t ∞ ), a contradiction. □

We conclude this section with one last lemma. This one simply states that, if the initial conditions are close enough, then the solutions to the SDE will converge, on every compact set, almost surely. This is a classical result which can be found in [Kunita, 1984] (see Theorem 2.2 page 211).

Lemma 1.3.4 ( [Kunita, 1984]). We denote X x t and X y t the solutions to the SDE (1.1), starting from X x 0 = x and X y 0 = y, respectively, for the same Brownian motion W. Then, if x converges to y in R d , X x converges almost surely to X y , uniformly on every finite time interval.

Proof

In this section, we prove the uniform convergence of the whole SMC genealogical tree towards the AMS one, as the number of SMC levels tends to infinity. For this, the idea is to consider a coupling between both algorithms.

Proof

We will firstly describe it, to make its understanding simpler. Then, we will illustrate it with N = 2 (Figure 1.2). Finally, we will define properly the coupling, for N particles. As a corollary, we propose an alternative proof of the unbiasedness of the AMS estimators.

Description of the coupling

We will describe the coupling we are going to use, but before this, let us specify some notations:

• the letters Y, T and j will refer to the trajectories, their hitting times and the stages of AMS algorithm, respectively,

• the letters Z, S and i will refer to the trajectories, their hitting times and the stages of SMC algorithm.

We consider that we are given a full run1 of AMS Algorithm 3, with the previous assumptions verified. This means we know the final number of iterations J AMS , the sequence of the AMS levels L 1 < ... < L J AMS , and we also know that at the end of each stage, among the particles Y 1, j , ..., Y N, j , there was a unique trajectory Y M j , j-1 which was discarded and re-branched on the particle Y N j , j = Y N j , j-1 . From this run of the AMS algorithm, we aim at building a coupling describing what the SMC Algorithm 2 would have performed with the same input and the same realizations of the Brownian motions part.

We recall that the number of particles N is chosen and deterministic and for any i SMC chosen, we set

ℓ i := i l max i SMC := iδ,
where i is a step in SMC. This is a practical choice to work with a specific sequence of SMC levels, but it is not restrictive. Indeed, up to an increasing map, we can modify the importance function ξ in order to match any given sequence of SMC levels.

First of all, we start by setting the same initial conditions and pieces of trajectory

Z 1,0 , ..., Z N,0 = Y 1,0 , ..., Y N,0 .
Then, we will build the coupling stage by stage, indexed by the AMS ones.

We can now index the SMC algorithm with index j using the j-th SMC iteration at which a genuine killing event occurs.

Definition 1.4.1. Let I kill denote the random set of iterations in SMC Algorithm 2 bis at which at least one particle is killed. We define ι j the j-th SMC iteration in I kill :

ι j = inf(i ∈ I kill : ι j-1 < i), (1.2)
with ι 0 = 0.

We can now index the SMC particles at the end of SMC stage ι j with the index j as follows:

Z 1, j , ..., Z N, j , which means that Z n, j is the particle n in SMC stage ι j .

We can next denote a special event which enables to define the coupling (we recall that M j is the label of the killed AMS particle at stage j, i.e. the one defining the AMS level L j ):

E j := All the SMC particles Z 1,j-1 , ..., Z N,j-1 , except the M j -th one, go beyond level ℓ ι j .

E j means that after the ι j-1 -th stage in SMC: i) a single particle is killed before stage ι j and the killing occurs precisely at stage ι j , ii) the label of the killed SMC particle is the same as the label of the j-th killed AMS particle.

We distinguish two situations, depending on if the event E j is realized, or not.

• On the event E j , only the particle M j is discarded in SMC, as this is the only one which did not reach level ℓ ι j .

Similarly to AMS, we re-branch it on Z N j , j-1 , using the same N j and the same Brownian motion. To clarify this coupling, let us denote by (W

M j , j h ) h≥0 ,
the Brownian trajectory that has been used in AMS at stage j to generate the trajectory of particle M j after the branching on particle N j at level L j . More precisely, this trajectory is a strong solution to the SDE:

(AMS) d Y M j , j h+T j = α Y M j , j h+T j dh + β Y M j , j h+T j dW M j , j h , h ≥ 0, with initial condition Y M j , j T j = Y N j , j-1 T j
, where we have denoted T j := T L j (Y N j , j-1 ).

In the same way, we set

S j := S ℓ ι j (Z N j , j-1 ) := inf s ≥ 0 : ξ Z N j , j-1 s > ℓ ι j .
On E j , by definition, it holds that S j < S end (Z N j , j-1 ). We then define Z M j , j t

as the strong solution to the SDE

(SMC) d Z M j , j h+S j = α Z M j , j h+S j dh + β Z M j , j h+S j dW M j , j h , h ≥ 0, with initial condition Z M j , j S j = Z N j , j-1 S j . 1.4. Proof
We then naturally choose for the newly branched SMC trajectory:

Z M j , j t :=          Z N j , j-1 t if 0 ≤ t < S j , Z M j , j t if t ≥ S j .
Let us underline the fact that the only difference between Z M j , j and Y M j , j after S j (resp. T j ) lies then their respective initial (or rather restart) conditions. We also underline that the SMC particles Z n, j 1≤n≤N are not indexed by the SMC levels (index i), but by the AMS stages (index j).

• If we are not on the event E j , meaning if either:

i) there is strictly more than a single particles killed at ℓ ι j , ii) every particle go beyond ℓ iota j , iii) the SMC particle killed at ℓ ι j has not the same index as in AMS (index M j ), then, the coupling is said to have failed. In that case we will replace killed particles in SMC by independent (from AMS) trajectories.

Let us comment a bit about this coupling: we aim at building a SMC genealogical tree alike the realization of AMS we have. If we have enough SMC levels, at most one trajectory is killed by SMC, and then, if the SMC particles and AMS particles are close enough, the particles with the lowest score in both algorithms will correspond to the same index. This corresponds to the event E j . In that case, the coupling described above is successful and trajectories Z and Y will only differ from their different 'restart' conditions. If the discrepancy between the two starting points can be controlled, then the whole pieces of trajectory will be close according to Lemma 1.3.4. As a consequence, the scores of AMS and SMC particles will be close and the SMC particle we re-branch on will have a score close to the AMS score L j . If we have enough discrete SMC levels, the 'restart' conditions at the next iteration in SMC, defined by hitting times of levels, will also remain close to their AMS counterparts. The goal of the main theorem below is to give a formalized treatment of the latter argument.

Figure 1 illustrates the coupling on two steps, that we previously detailed. The black trajectories are the ones produced by running AMS, and the red doted lines refer to the SMC coupling. We recall that Z 1,0 , Z 2,0 = Y 1,0 , Y 2,0 .

To lighten the notation, we avoid indexing trajectories Y with respect to i SMC , but the dependence on it must not be forgotten. The goal is to show that the tree composed of red trajectories converges to the black one, uniformly on every compact set, as i SMC → +∞ (or equivalently as δ → 0). Note also that under this convergence result, the final SMC particles Z n,J AMS 1≤n≤N have reached l max , in the same way as Y n,J AMS 1≤n≤N did, so that Z n,J AMS 1≤n≤N is equal to the outcome of the SMC algorithm after i SMC iterations.

Remark 1.4.2. We remarked that, for i SMC large enough, the level ℓ ι j of starting point of the new SMC trajectory is at least equal to the score of the discarded particle in AMS. We however emphasize that the SMC level ℓ ι j is not necessarily the first SMC level higher than the AMS level L j , as presented in Figure 1.3. Indeed, let us say that ℓ i j is the first SMC level larger than L j , meaning we have

ℓ i j -1 < L j ≤ ℓ i j , ξ = ℓ ι 3 {ξ = L 3 } ξ = ℓ ι 2 {ξ = L 2 } ξ = ℓ ι 1 {ξ = L 1 } {ξ = L 0 } {ξ = -1} R Z 1,3 Y 1,0 = Z 1,0 = Y 1,1 = Z 1,1 = Y 1,2 = Z 1,2 Z 2,2 = Z 2,3 Y 1,3 Y 2,2 = Y 2,3 Y 2,1 Z 2,1 Y 2,0 = Z 2,0
Figure 1.2 -The three first steps of the coupling between AMS and SMC for a two-particle system and that all the SMC particles Z 1, j , ..., Z N, j have larger scores than this last SMC level ∀n ∈ ⟦1, N⟧, sup t≥0 ξ Z n, j > ℓ i j , so that in particular ι j > i j .

In such a situation, SMC algorithm would do nothing at stage i j , as every particle is already beyond the corresponding level.

This type of phenomenon can happen because the impact of the error in the initial conditions in the coupling will later on de-couple the AMS and SMC trajectories in a way that may be a bit more important than the given discretization of levels (yet of the same order δ). This phenomenon however does not prevent the convergence of ℓ ι j towards L j . The next lemma is obvious: it states that under our coupling, almost surely and for each j ≤ J AMS , if the level discretization is small enough, at most one AMS particle is branched between two consecutive SMC levels. The proof is a direct consequence of the fact that the AMS levels L j < L j+1 are strictly increasing and we omit it.

Lemma 1.4.3. Almost surely for every realization: for i SMC large enough, at most one particle is branched by AMS between two consecutive SMC levels, i.e.

inf j≤J AMS (L j -L j-1 ) > δ = l max i SMC .
Let us now detail a little bit the idea of the proof of the main convergence. We are going to prove the convergence between the genealogical trees of both algorithms. To handle this convergence, we need to compare the respective supremum of two coupled AMS versus SMC particles, over some time interval. Of course, we will compare the particles when our coupling have been successful.

Taking some suitable integers j and n, the particles Y n, j and Z n, j are both defined until they hit the cemetery region {ξ = -1}, so that the terminal times of the trajectories are not equal. To compare them, we can propose two possibilities:

• we can take the supremum over the time interval given by the highest ending time

sup t∈[0,max(T n, j end ,S n, j end )] Y n, j t -Z n, j t ,
• we can take the supremum over the time interval given by the smallest ending time, and add the difference between these times

Y n, j -Z n, j := sup t∈[0,min(T n, j end ,S n, j end )] Y n, j t -Z n, j t + T n, j end -S n, j
end .

(1.3)

In the first case, this require to extend one of the two trajectories. In the second case, we add a term, as one of the two trajectories have likely not reach R. Thus, adding the difference of these times, we ensure that the trajectories are close even if we stop one prematurely. We will choose the second situation, and in the latter, when we denote ∥ . ∥ we refer to the definition (1.3).

The following theorem summarizes the previous discussion about the genealogical tree.

Theorem 1.4.4. Under Assumptions 1.2.1, 1.2.2, 1.2.3 and 1.2.4, there exists a coupling denoted (Y n, j , Z n, j ) with n ∈ {1 . . . N} and j ∈ ⟦0, J AMS ⟧ (described in Section 1.4.1) between both algorithms AMS and SMC where (Z 1, j , . . . , Z N, j ) denotes the trajectories in SMC Algorithm 2 bis at the j-th SMC iteration ι j at which a SMC particle has been unsuccessful; this coupling having the following properties. For any given number of particles N, almost surely for any realization, and for all j ∈ ⟦1, J AMS ⟧:

(1-j) it holds:

lim i SMC →+∞ max n∈{1,...,N} Z n, j -Y n, j = 0,
(2-j) The event E j+1 (described in Section 1.4.1) is satisfied for i SMC large enough:

i) there is a single SMC particle with index M S MC j+1 (among the SMC particles Z ., j ) that has been unsuccessful between iteration ι j + 1 and ι j+1 , ii) the index M AMS j+1 of the particle killed in AMS is the same:

M AMS j+1 = M S MC j+1 .
Remark 1.4.5. We set the final condition (2 -J AMS ) to be true if (1 -J AMS ) is true by convention.

Proof. The theorem will be shown by induction on the stages of the AMS algorithm. The idea is to split the induction hypothesis between (1) the convergence of trajectories, and (2) the fact that at each branching, as the SMC particles and AMS particles are close enough, the killing and splitting will occur for a single particle with the same indice in both algorithms.

We recall the notations

S n, j l = S l Z n, j := inf s ≥ 0 : ξ(Z n, j s ) > l T n, j l = T l Y n, j := inf t ≥ 0 : ξ(Y n, j t ) > l
the hitting times of l, by the SMC particle Z n, j and the AMS particle Y n, j , over ξ.

• Initialization, for j = 0:

1.4. Proof
(1-0) There is nothing to prove, as Z 1,0 , ..., Z N,0 = Y 1,0 , ..., Y N,0 .

(2-0) From the equality above, for i SMC large enough all the SMC trajectories reach level ℓ ι 1 > L 1 almost surely, except Z M AMS 1 ,0 . There actually is a single branching, we have

M AMS 1 = M S MC

1

, and Z N 1 ,0 hits ℓ ι 1 before end time.

• Induction: Assuming the induction property for j -1 and let us show it for the j.

(1-j) We have Y n, j

Z n, j-1 -Y n, j-1 a.s ------→ i SMC →∞ 0.
By induction hypothesis the coupling is successful at level L j : we can denote M j = M AMS j = M S MC j and we can consider:

Z M j , j t :=            Z N j , j-1 t if t ≤ S N j , j-1 ℓ ι j , Z M j , j t if S N j , j-1 ℓ ι j ≤ t
In order to prove (1-j) for index j, we will only have to prove the convergence of the new trajectory associated with re-sampled particle M j . The point is thus to control the distance between the starting points of this new pieces of trajectory, i.e.

Z N j , j-1 S N j , j-1 ℓι j -Y N j , j-1 T N j , j-1 L j
.

In order to do this, let us first temporarily enlighten the notations. Let us set

Z j-1 S l := Z N j , j-1 S N j , j-1 l , Y j-1 T l := Y N j , j-1 T N j , j-1 l
, and then we write

Z j-1 S ℓι j -Y j-1 T L j ≤ Z j-1 S ℓι j -Y j-1 S ℓι j + Y j-1 S ℓι j -Y j-1 T ℓι j + Y j-1 T ℓι j -Y j-1 T L j
.

The first term is bounded by Z N j , j-1 -Y N j , j-1 , which converges to 0 as i SMC goes to +∞, by the induction property.

Let us then consider the third term. As a consequence of the induction property, we know that ℓ ι j converges to L j , as i SMC tends to +∞. Indeed, the score, which is a maximum over a path, is continuous for the norm ∥ . ∥ topology, and we get

ℓ ι j + O 1 i SMC = max s ξ Z N j , j-1 s --------→ i SMC →+∞ max s ξ Y N j , j-1 s = L j .
One can now apply Lemma 1.3.3 to Y N j , j-1 with l = L j because in AMS the distribution of cloned particle N j conditional on L j is simply the underlying distribution starting from Y j-1 T L j-1 conditioned to reach l = L j : hence it still satisfies Assumption 1.2.3. As a consequence

T ℓ ι j → T L j
and by continuity of Y N j , j-1 , we have proved that the third term goes to zero, when i SMC goes to +∞ .

Let us now study the second term more precisely. As the hitting-time function T B of B := ξ > ℓ ι j is continuous at Y N j , j-1 with respect to the topology associated on the uniform norm on finite time intervals (as it is stated in Lemma 1.3.2), it means that, by the induction property,

T B Z N j , j-1 -T B Y N j , j-1 = S N j , j-1 ℓ ι j -T N j , j-1 ℓ ι j
can be made small enough for i SMC large enough, and so can Y

N j , j S ℓι j -Y N j T ℓι j by continuity of Y.
Finally, as we have just proved that the starting points of re-branched trajectories are close enough, Lemma 1.3.4 ensures that the complete trajectories will also be close enough, i.e. sup 0≤t≤min S M j , j end ,T M j , j end Z M j , j -Y M j , j goes to zero, when i SMC goes to infinity. Using again the hitting time continuity of Lemma 1.3.2 again to handle the ending times, we conclude that

Z M j , j -Y M j , j a.s ------→ i SMC →∞ 0,
and this remains true for any n M j , as there has been actually no branching for those particles.

(2-j) In AMS, particle M AMS j+1 is branched on particle N j+1 at level L j+1 , which is defined as follows

L j+1 = min 1≤n≤N sup ξ Y n, j .
We just proved in (1-j) that, for any n ∈ ⟦1, N⟧,

Z n, j -Y n, j a.s --------→ i SMC →+∞ 0,
so for i SMC large enough, the SMC particles Z n, j with n M AMS j+1 will have scores close to (or higher than)

1.5. Consequence on the AMS estimator of the probability L j+2 , whereas Z M AMS j+1 , j has a score which is converging for i SMC large towards L j+1 with L j+1 < L j+2 .

This implies that M AMS j+1 will be at least one the first killed SMC particle (by definition at SMC iteration ι j+1 ). Moreover we have remarked in Lemma 1.4.3 that for i SMC large enough there is at least one SMC level strictly between two consecutive AMS levels L j+1 < L j+2 : M AMS j+1 must be killed before one of this SMC intermediate level (which is strictly smaller than L j+2 ) and thus must be the only SMC particle killed at ι j+1 .

Let us underline that, as the number of branching is almost-surely finite, due to the non-explosive hypothesis about AMS, we considered a finite number of "large enough" i SMC . So the greatest one will satisfy the first statement of the theorem.

□

More generally, we just proved the uniform convergence of the whole SMC genealogical tree towards the AMS one.

Consequence on the AMS estimator of the probability

We recall that in SMC Algorithm 2, N(i) denotes the number of remaining trajectories at stage i ∈ ⟦1, i SMC ⟧.

Theorem 1.4.4 provides an alternative way to argue that the AMS estimator is unbiased. Indeed, for i SMC large enough, it is clear that, for any i ∈ ⟦1, ..., i SMC ⟧, the number of remaining trajectories at stage i, denoted N(i) is equal to N -1 if there is actually a branching (at most one per step), and N otherwise. Then, recalling the definition of the estimator of p in AMS,

p SMC = i SMC i=1 N(i) N ,
it converges almost surely, when i SMC goes to infinity, to

p SMC a.s ------→ i SMC →∞ 1 - 1 N B ,
where B denotes the number of real branchings of SMC (at most of the SMC levels, there is actually no branching).

This number of real branchings is, in fact, equal to J AMS , the number of branchings of AMS, for i SMC large enough.

Then, as p AMS is the almost surely limit of unbiased estimators, it converges also in L 1 (the estimators are bounded, so they are uniformly integrable), and then p AMS is unbiased itself.

We have shown in this study the unbiasedness of the AMS estimator in the last particle case, through the convergence of the SMC genealogical tree to the AMS one. More generally, we have proved the following corollary.

Corollary 1.5.1. Under Assumptions 1.2.1, 1.2.2, 1.2.3 and 1.2.4, there exists a coupling such that, for any N chosen,

p SMC a.s ---→ δ→0 p AMS ,
where δ := max 0≤i≤i SMC -1 (ℓ i+1 -ℓ i ) . Moreover, for any test function ψ, γ S MC (ψ)

a.s ---→ δ→0 γ AMS (ψ) .
In particular, we have proved in Theorem 1.4.4 that γ AMS is unbiased, and so is p AMS .

Remark 1.5.2. If we take the number of particle we discard to be equal to k > 1 in AMS, then we might adapt our method, to a slightly different version of SMC. It seems then reasonable to think that we could perform a similar study and also prove the convergence of the genealogical trees, with the consequences we just wrote concerning the estimators.

Chapter 2

SMALL NOISE LIMIT OF THE AMS ALGORITHM WITH TWO PARTICLES

Model

Let us consider a diffusion in R d , denoted

t → X t ∈ R d ,
in a small noise context, meaning we consider a solution to the SDE

         d X t = α (X t ) dt + √ ε • β (X t ) dW X t , X 0 = x 0 , (2.1)
with some initial condition X 0 = x 0 , and where t → W X t is a standard R n -valued Brownian motion, and ε > 0 is a (small) positive number. We assume that the coefficients α (R d valued) and β (R d×n valued) are at least globally Lipschitz so that X is a usual strong solution.

Remark 2.1.1 (ε notation). In the present chapter, various sub-or super-script will be necessary so that we will drop the dependence with respect to ε for notation of processes; e.g.

t → X t ≡ X ε t .
There is no ambiguity possible because ε always appears as a factor √ ε in front of all Brownian motions (at least before re-scaling or time-change procedures).

Denoting by ξ : R d → R a smooth importance function, we are interested here by the rare event 'the process X reaches the level set R = {ξ > l max } in finite time', where l max is a given positive number, or formally:

T l max := T l max (X) < +∞ .
In other words we choose:

T end (X) = +∞.

In order to be in a rare event context, we will assume the following necessary condition: the solution to the ODE

         ẋ = α (x) , x(0) = x 0 , (2.2) is such that lim t→+∞ ξ(x t ) = -∞ almost surely. (2.3)
Then, looking to the SDE (2.1), the process t → ξ(X ε t ) is expected to converge to -∞, when t goes to +∞, at least for ε small enough. The assumptions used in the present chapter will ensure such a behaviour. We give an example of a drift condition in order to fix ideas.

Lemma 2.1.2. Assume i) that β and the first two derivatives of ξ are bounded, ii) that there exists a real constant c < +∞ such that:

Dξα |Dξβ| 2 ≤ -1/c < 0.
(2.4)

Then for ε small enough the following holds almost surely:

lim t→+∞ ξ(X t ) = -∞.
Proof. Apply Itô formula to t → ξ(X t ). It is then possible to use a time change to compare the obtained process to a drifted Brownian motion as it is done in Corollary B.0.2. The drift after time change is uniformly strictly negative for ε small enough using the main condition (2.4). □ This chapter will be organized as follows

• We will first develop some motivations, especially about the small noise context or the committor function.

• We will detail the different required assumptions.

• We will introduce the notations of the chapter, and recall the algorithm AMS in the specific context N = 2.

• We will present some numerical simulations to illustrate the convergence to the ODE, and to compare it to the Freidlin-Wentzell optimum.

• We will state and demonstrate the main result (Theorem 2.6.1) on the small noise limit of AMS algorithm when N = 2.

Motivations

Small noise considerations The first thing we can do is to underline that the small noise context can be analyzed using Large Deviations theory, and more specifically, the Freidlin-Wentzell theorem. The Freidlin-Wentzell theorem states that, if X is the unique solution to the SDE with Lipschitz coefficients (2.1) for 0 ≤ t ≤ T and X 0 = x 0 , then (X t ) 0≤t≤T satisfies a Large Deviations Principle (LDP) with speed ε in C ([0, T ]) (endowed with the uniform topology) with the good rate function I x,T (.) defined as the following

I x,T ( f ) = inf g∈H 1 ([0,T ]): f (t)=x+ t 0 α( f (s))ds+ t 0 β( f (s)) ġ(s)ds 1 2 T 0 ġ (t) 2 dt.
We recall that a family of probability measure (µ ε ) is said to satisfy a LDP with speed ε and rate function I if, for any set Γ, inf

• Γ I(x) ≤ lim inf ε↓0 ε log µ ε (Γ) ≤ lim sup ε↓0 ε log µ ε (Γ) ≤ -inf Γ I(x),
where a rate function is a function which is not trivially +∞ and lower semi-continuous, i.e.

x ∈ X I(x) ≤ c , for c ≥ 0, are closed in X. If, furthermore, these sets are compact, the rate function I is said to be good.

We refer to [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF] for more details about the Large Deviations Theory, including Freidlin-Wentzell. As a consequence of the Freidlin-Wentzell theory,we prove under some assumptions that the committor function Φ ε,l (x 0 ) := -ε log P (T l (X) < +∞ | X 0 = x 0 )

does converge to the equation minimizer of the rate functions over trajectories that reaches {ξ > l} in finite time:

Φ 0,l (x 0 ) := lim ε→0 Φ ε,l (x 0 ) = inf
x,T : T l (x)≤T <+∞ I x 0 ,T (x).

(2.5)

Sufficient conditions required to obtain this convergence are given below. This means that the rare event probability is asymptotically (up to sub-exponential constants) of order exp (-Φ 0,l (x 0 )/ε), for small ε.

Lemma 2.2.1. Let us assume that in addition of α and β being globally Lipschitz, β is bounded, ξ and its two first derivatives are globally bounded, and the negative pointing drift condition (2.4) holds true. Then the minimisation formula (2.5) holds true and the minimum is moreover attained with T spanning some finite time interval.

Proof. We denote, like previously, X a strong solution to the SDE (4)

d X t = α (X t ) dt + √ ε • β (X t ) dW X t .
We wish to estimate for small ε

Φ ε,l (x 0 ) := -ε log P T l (X) < ∞ X 0 = x 0 .
For this, let us take t m > 0 some deterministic time. We have

Φ ε,l (x 0 ) = -ε log P T l (X) < t m X 0 = x 0 + P t m ≤ T l (X) < ∞ X 0 = x 0 , . (2.6)
Heuristically, as the process X is attracted towards large negative values of ξ, it is more likely to hit the level l at the beginning of its trajectory, and not after a long time. Hence the second probability in the log in (2.6) is going to be negligible. We will prove it using a comparison with a one dimensional drifted Brownian motion (defined by a constant drift and diffusion coefficients and estimated the Appendix D).

Using Freidlin-Wentzell theory, the first term in the log in (2.6),

ε log P T l (X) < t m X 0 = x 0 ,
does converge towards

I(t m ) := inf x,t m : T l (x)≤t m I x 0 ,t m (x).
As a consequence, it remains to upper bound ε log P t m ≤ T l (X) < ∞ X 0 = x 0 . For this, we apply Itô formula to ξ (X), since ξ is regular enough. We obtain

dξ (X t ) = Dξ (X t ) α (X t ) + ε 2 tr D 2 (ξ)ββ T (X t ) dt + √ εDξ (X t ) β (X t ) dW X t .
Let us denote B t and Σ t the coefficients of the above SDE so that dξ (X t ) =:

-B t dt + Σ t dW X t , (2.7)
in this last equation, we see clearly that the drift condition 2.4 and our assumptions implies that almost surely for a constant c:

Σ 2 s B 2 s ≥ 1/c > 0.
Re-scaling this last process by setting

Y s = ξ (X εs ) -ξ(x 0 ) ε ,
and obtain:

dY s = -B s ds + Σ s dW Y s
for a standard Brownian motion W Y . We can thus use Lemma D.3.3 to compare it to a one-dimensional drifted Brownian motion in order to bound probabilities. Consequently to Lemma D.3.3, there exists a constant c, depending on the boundaries of the drift and derive coefficients, such that, for t m large enough, we have

P t m ≤ T l (X) < ∞ X 0 = x 0 ≤ P sup t≥t m ξ (X t ) ≥ l ξ (X 0 ) = ξ (x 0 ) ≤ P       sup s≥t m /ε Y s ≥ (l -l 0 )/ε Y 0 = 0       ≤ P       sup s≥t m /ε Y s ≥ 0 Y 0 = 0       ≤ ce -t m /cε .
We thus find, using the classical Large Deviations elementary estimate lim ε ε log(e a/ε + e

b/ε ) = max(a, b) applied to (2.6), that -I(t m ) ≤ -lim ε→0 Φ ε,l (x 0 ) ≤ max(-I(t m ), -t m /c).
Since t m is arbitrary, one can take t m large enough and conclude. □

Properties associated with the quasi-potential (a.k.a asymptotic committor) Two important facts are wellknown in the literature on variational calculus. First, the quasi-potential or asymptotic committor Φ 0,l is solution, at least in the sense of viscosity solution, to the Hamilton-Jacobi equation with Dirichlet boundary condition:

        
1 2 ββ T (DΦ 0,l , DΦ 0,l ) = DΦ 0,l α, Φ 0,l = 0 on {ξ = l} .

(2.8)

Second, at least in a formal sense, rate function minimizing trajectories, that are minimizers solution of the minimization problem in the definition of Φ 0,l (x 0 ) in (2.5) are solution to the Ordinary Differential Equation:

         ẋ(t) = α(x(t)) -DΦ 0,l ββ T (x(t)) , x 0 = x 0 .
(2.9)

Of course, the above ODE is well-defined only under the quite strong assumption that DΦ 0,l is Lipschitz. Note that d dt Φ 0,l (x(t)) = -1 2 ββ T (DΦ 0,l , DΦ 0,l ) < 0. As a consequence, the latter ODE indeed reach {ξ = l} if DΦ 0,l β is uniformly bounded away from 0 in the whole space.A similar assumption will be necessary in our study.

It is interesting to remark that the above facts imported from variational calculus can be reinterpreted using probability arguments.

First, the committor function is defined using h ε (x 0 ) := P T l (X) < +∞ X 0 = x 0 , which is solution to the usual elliptic Dirichlet problem:

         Dh ε α + 1 2 β T D 2 (h ε ) β = 0, h ε = 1 on {ξ = l} .
(2.10)

Writing the Partial Differential Equation satisfied by Φ ε,l = -ε log h ε , we directly (but formally when taking ε → 0) recover the Hamilton-Jacobi equation (2.8) satisfied by Φ 0,l (see Section 2.3, paragraph on the committor).

On the other hand, thanks to the Large Deviations Theory and Girsanov theorem, we can recover the ODE (2.9) satisfied by the rate-function-minimizing trajectory as follows. Using informally the Gibbs conditioning principle (see [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF]]), we can identify the rate function minimizing trajectory defining Φ 0,l by considering the process X conditioned to reach {ξ = l} at a finite time ( T l (X) < +∞ ), and then look at its distribution when ε → 0. Using Girsanov theorem, we will show that the latter conditioned process is solution to the SDE

d X t = α(X t )dt -DΦ ε,l ββ T (X t )dt + √ ε • β (X t ) dW t ,
in which W t is a Brownian motion under the probability defined by conditioning with respect to T l (X) < +∞ . The latter also converges when ε → 0 towards the above ODE (2.9). The convergence is rigorous when the committor function DΦ ε,l is Lipschitz continuously with respect to ε ∈ R + , which is a very strong assumption at ε = 0 (related to the existence of a classical solution of the Hamilton-Jacobi equation (2.8), see comments in Section 2.3).

Simulation with AMS Among the three previous algorithms we introduced, AMS Algorithm 3 seems to be the best choice, as it is the one requiring the less knowledge about the diffusion (no level has to be given a priori, nor any cloning rate).

A consequence of the Freidlin-Wentzell theory explained above is that Φ ε,l max (x 0 ) = -ε log P x 0 (T l max (X) < ∞) converges to Φ 0,l max (x 0 ). This means that rare event probability is asymptotically of order exp (-Φ 0,l max (x 0 )/ε), for small ε. On the other hand, as already mentioned in the introduction, in the N = 2 particle situation, the number of iterations is expected to be approximately

p AMS := 1/2 J AMS ≃ P x 0 (T l max (X) < ∞) = p,
where p AMS is the rare event estimator in AMS and J AMS the number of iterations. As a consequence one can expect the total number of iterations J AMS to be of order 1/ε. The latter has was been proved rigorously and more precisely in a static case [START_REF] Guyader | Simulation and estimation of extreme quantiles and extreme probabilities[END_REF] and in an idealized case [START_REF] Bréhier | Analysis of adaptive multilevel splitting algorithms in an idealized case[END_REF], in which J AMS is a Poisson random variable. For the sake of completeness, we sketch a rigorous proof below.

Proposition 2.2.2. In dimension 1 and in the last particle situation, J AMS , the total number of iterations of AMS with N particles, is a Poisson random variable with parameter -N log p, where p = P (T l max (X) < +∞) is the rare event probability. In particular, in probability:

lim ε→0 ε J AMS = N Φ 0,l max (x 0 ). Proof. Let us assume X is a solution to the one-dimensional SDE          d X t = α (X t ) dt + β (X t ) dW X t X 0 = x 0 ,
and, without lost of generality, that ξ = id. Let us define the distribution function of max t≥0 X t :

F(l) := 1 -P (T l (X) < ∞) = 1 -P max t≥0 X t > l ,
where l is a real number. This is an increasing function in l so that:

max t≥0 F(X t ) = F(max t≥0 X t )
which is uniformly distributed on [0, 1] by construction. Applying the change of variable

X t := -log(1 -F(X t )),
we see that max t≥0 X t is exponentially distributed with unit parameter. Now, by construction of the AMS process, only the relative order between particles is relevant. As a consequence running AMS with variable X or variable X is equivalent. Furthermore, by construction of the AMS algorithm in dimension 1 (assuming the strong Markov property for X), all particles at the end of stage j (with associated level L j ) are distributed independently conditionally on L j according to the SDE (followed by the change of variable) with initial condition L j . The maxima max t≥0 X n, j -L j for n = 1 . . . N are thus i.i.d. with exponential distribution. The minimum of the latter, in the last particle case, defines the level difference L j+1 -L j which is thus an exponential distribution with parameter N, independent of the value of L j . This shows that for all j, L j is distributed according to the sum of j i.i.d. exponentials of parameter N.

The number of iterations to hit l, defined as the first iteration at which the level l is reached, is thus a Poisson process indexed by the 'time' parameter l. In particular:

J AMS := min j : L j > l max = min j : L j > l max ∼ P N l max = P (-N log p) ,
since by definition of the change of variable:

l max = -log P(T l max (X) < +∞) = -log p.

□

Proposition 2.2.2 suggests the following question:

Problem 1. In dimension 1, one has:

lim ε→0 ε J AMS = N Φ 0,l max (x 0 ).
Is the following true in general ?

We study this question in Section 2.6 under technical assumptions in the specific case N = 2. In the same way, it is possible to prove that in dimension 1, the marginal distribution of the particles at stage i conditional on the level L i are exactly given by the target conditional distribution (see also [START_REF] Guyader | Simulation and estimation of extreme quantiles and extreme probabilities[END_REF]).

Proposition 2.2.3. In AMS in dimension 1, for each n = 1 . . . N, the marginal distribution of the particle n X n,J AMS is exactly given by the conditional distribution of X conditioned by the rare event T l max (X) < +∞ .

Proof. We sketch a proof for the sake of completeness. We use a concept that will be used in Subsection 2.7.1. Let us condition by the sequence of levels L 1 < L 2 < . . . < L J AMS . By construction of the AMS algorithm, we can reconstruct (the genealogical tree of) the trajectories of particles at the end of the algorithm as follows. In dimension 1

the distribution of the level L j+1 depends only on L j ; thus conditionally on L j+1 the trajectory of the (N -1) surviving particles is simply the solution to the SDE starting from L j and conditioned to reach L j+1 . The distribution of X n,J AMS is thus the concatenation of J AMS pieces of trajectories obtained in this way. By the strong Markov property this concatenation is simply a solution to the SDE conditioned by the rare event. □ Note that the above proof is incorrect in higher dimension because correlations between level increments and entrance states will appear.

The above result suggests the following question:

Problem 2. In dimension 1, for each n = 1 . . . N, the distribution of X n,J AMS has (a fortiori) the same limit as the distribution of X conditioned to hit l max when ε → 0. Is this property true in general ?

We will answer this question in Section 2.6 under technical assumptions in the case N = 2. Note also that we have already stated that the AMS algorithm provides unbiased estimates for any N, and in particular for N = 2:

Proposition 2.2.4. The estimators of AMS Algorithm 4 (N = 2 particle situation) are unbiased:

E 1/2 J AMS = p l max , and
E         1/2 J AMS 1 N N n=1 δ X n,J AMS         = Law(X | T l max (X) < +∞).
This means that for N = 2 one can obtain the target probability and conditional distribution by performing many independent realisation of the AMS algorithm and then estimating by averaging over those independent trials.

The key Markov chain In this chapter, we will focus on the branching points given by AMS. For N = 2, the branching points are the natural quantities defined in AMS algorithm. Those branching points are defined by the state and the corresponding time of the particle we re-branch on. In dimension 1, this is the sequence of the levels and the hitting time of these levels by the surviving particle. In higher dimension, one has to add the state of the surviving particle when it hits the adaptive levels. For N = 2, the sequence of branching points do form a Markov chain that will be denoted:

(x 0 , 0) = (X 0 , T 0 ), . . . , (X j , T j ), . . . , (X J AMS , T J AMS ), in which T j is the first hitting time of L j by the surviving trajectory X (2), j-1 and X j is the entrance state X

(2), j-1 T j where the branching is performed. Figure 2.1 illustrates this: the branching points are in blue.

We will later specify the AMS Algorithm 3 in Algorithm 4, and introduce some notations for the Markov chain of the branching points we will study in the limit ε → 0.

As a consequence of the previous discussion concerning the Large Deviations Principles, and of Proposition 2.2.2, we are going to look at the convergence of the Markov Chain given by AMS algorithm for a number j = ⌊r/ε⌋ of iterations. Studying the limit when ε → 0 of this Markov chain with O(1/ε) number of iterations will enable the study of Problem 2, that is the comparison with the minimizing trajectories expected in the Freidlin-Wentzell theory.

L 1 L 2 L 3 X (2),0 = X (2),1 = X (1),2
X (1),0

X (1),1 X (2),2 X 1 = X (2),0 T 1 X 2 = X (2),1 T 2 X 3 = X (2),3 T 3 Figure 2.1 -A few steps of AMS with N = 2 and k = 1

Assumptions and some consequences

We recall we work in a dynamical context in this thesis, with a score function ξ regular enough. We recall X is assumed to be a strong solution to the following SDE on R d

d X t = α (X t ) dt + √ ε • β (X t ) dW X t ,
starting from X 0 = x 0 .

We will assume we can decompose X in the following interesting way:

Assumption 2.3.1 (Decomposition). We assume we can write on R d

X = (L, A) ,
where L = ξ (X) is the level coordinate, and A an auxiliary coordinate in such a way that the dynamics of the processes L and A are strong solutions to the following SDEs

         d L t = -b (L t , A t ) dt + √ ε • σ (L t , A t ) dW L t , L 0 = l 0 , (2.11a) and          d A t = f (L t , A t ) dt + √ ε • θ (L t , A t ) dW A t , A 0 = a 0 , (2.11b)
where the Brownian motions W L and W A are independent.

We do not detail here rigorous conditions that enable the construction of the decomposition 2.11. Yet, we can explain it a little bit. Indeed, we can always construct locally by integration a function:

fct : R d → R d-1
such that the line (dimension 1) manifolds x : fct(x) = cst are, locally, always orthogonal to the level set submanifolds x : ξ (x) = cst , where orthogonality is for the metric given by ββ T . In other words we ask:

(Dξ, Dfct k ) = 0, k = 1, . . . , d -1.
Locally, we can easily do this in a neighbourhood of x : ξ(x) = cst if the latter is, say, diffeomorphic to R d-1 , but it is not clear whether existence holds globally. Assumption 2.3.1 allows us to consider this decomposition globally,

and not only locally.

The decomposition yields the independence assumption between the Brownian motions of L and A, which is

      -b f 1 . f d-1                    
.

We need additional assumptions on the coefficients of the SDE satisfied by X, L and A.

Assumption 2.3.2 (Coefficients). The coefficients b, σ, f and θ in (2.11) (or equivalently α, β in (2.1)) are globally Lipschitz, bounded, C 1 with first derivative bounded. Moreover the coefficients of the level coordinate are uniformly bounded away of 0, that is, there exists a constant c > 0 such that b ≥ 1/c > 0 and σ ≥ 1/c > 0.

We also assume that the matrix θθ T is uniformly elliptic (its determinant is uniformly bounded away from 0). Finally, we also assume that σ 2 /b 2 is globally Lipschitz.

Note that the boundedness conditions on b, σ show, similarly to Lemma 2.1.2 by comparison with a one dimensional drifted Brownian motion, that the level goes to minus infinity almost surely:

lim t→+∞ L t = -∞.
This condition also shows that the AMS algorithm is well-posed, as it has been shown in [Cérou et al., 2019a]. Three main assumptions are required: i) The process is Feller (it is true here because of globally Lipschitz coefficients), ii) the levels strictly increase almost surely (here because σ > 0), iii) the probability to reach a higher level is uniformly lower bounded away from 0 (here because σ ≥ 1/c and b is bounded).

Lemma 2.3.3. AMS algorithm with N = 2 is well-defined (scores of particles are almost surely different) and non explosive (it almost surely stops J AMS < +∞).

Finally, we will require two regularity assumptions about the committor function. These conditions are the most restrictive aspect of our study as it is unclear how to check them on concrete examples. We recall the definition of the committor first:

Φ ε,l (x 0 ) := -ε log P T l (X) < ∞ X 0 = x 0 ,
and we know by the Freidlin-Wentzell LDP that Φ ε,l converges, when ε decreases to zero, to the quasi-potential (or asymptotic committor) Φ 0,l solution of the Freidlin-Wentzell minimization problem.

Assumption 2.3.4 (Regularity of the asymptotic committor / quasi-potential). There is a constant c (also used to define the bounds in the O notation)1 uniform in ε and l 1 in compact sets such that

• The norm (in metric ββ T ) of the gradient of the committor function is bounded away from 0 : for any

(l, a) ∈] -∞, l 1 ] × R d-1 : DΦ ε,l 1 β (l, a) ≥ 1/c > 0.
(2.12)

• For any (l, a) ∈ R d with l ≤ l 1 :

         ∂ l Φ ε,l 1 = -2 b σ 2 (l 1 , a) + O(|l 1 -l| + ε), ∂ a Φ ε,l 1 = O(|l 1 -l|).
(2.13) Remark 2.3.5 (Justification of (2.12)). By definition of the committor function and the Markov property, we know that

l → Φ ε,l 1 (l, a)
is a decreasing function for l ≤ l 1 and a fixed. Since the coefficient σ ≥ σ min > 0 is lower bounded away from 0, the condition (2.12) will follow from the simpler uniform condition:

∂ l Φ ε,l 1 (l, a) ≤ -1/c < 0
which loosely speaking states that ∂ l Φ ε,l 1 has no critical point, uniformly in ε. This is a relatively natural condition.

Remark 2.3.6 (Justification of (2.13)). We recall the exact formula for the drifted Brownian motion starting at l = 0 which is our case with b and σ constant functions:

Φ ε,l = -2 b σ 2 l.
The approximate formula 2.3.4 is then just a general version of this formula near the boundary l = l 1 . A more precise justification will be given in the paragraph below.

The reason why we know the above assumption is difficult to check is because the quasi-potential can easily exhibits "caustics" which are by definition points x * ∈ R d for which the Freidlin-Wentzell minimisation problem:

Φ 0,l (x * ) = min x,T : T l (x)≤T <+∞ I x * ,T (x)
exhibits several distinct minima. It is well-known in variational calculus that this phenomenon is ubiquitous. This explains that in general Φ 0,l is defined as a solution to the corresponding Hamilton-Jacobi equation (2.8) in the viscosity sense and not in the classical, regular, sense. In this context, we did not find a clear set of examples for which Assumption 2.3.4 is true. This is left for future work.

We nonetheless discuss in the next paragraph a formal justification of Assumption 2.3.4, as well as a rigorous one in the restrictive case where the committor function is regular enough uniformly in ε.

Study of the committor

In this paragraph, we will give additional comments on the committor function Φ ε,l defined by (2.26), and its limit, when ε decreases to zero. We know from Lemma 2.2.1 that this limit, called the quasi-potential, exists, and for any l ∈ R, we denote Φ ε,l --→ ε↓0 Φ 0,l .

(2.14)

As already mentioned, the quasi-potential satisfies a PDE given by a stationary Hamilton-Jacobi equation with vanishing boundary Dirichlet condition. This PDE has already been mentioned in equation (2.8). To compute it explicitly, we recall that

h ε l = exp (-Φ ε,l /ε) = P (T l (X) < +∞ | X 0 = . )
satisfies the Dirichlet problem PDE (2.10), that is Lh ε l = 0 with boundary condition

h ε l (l, a) = 0, ∀a ∈ R d-1 ,
L being the generator of the diffusion. Using the identity (by definition of L)

L(-ε log h) = -εh -1 Lh + ε 2 h -2 2 |Dh β| 2 ,
we deduce that Φ ε,l satisfies the equation

DΦα + ε 2 β T D 2 Φβ = 1 2 |DΦ β| 2 .
Remarking that, with our noise structure, we have

|Dh β| 2 = |∂ a h θ| 2 + |∂ l h σ| 2 ,
and fixing a reference level l 1 , the latter PDE can be rewritten using 'level-auxiliary variables' as

1 2 εθ T ∂ 2 a Φ ε,l 1 θ -∂ a Φ ε,l 1 θ 2 + f ∂ a Φ ε,l 1 + σ 2 2 ε∂ 2 l Φ ε,l 1 -(∂ l Φ ε,l 1 ) 2 -b∂ l Φ ε,l 1 = 0. (2.15)
At least in a formal sense, we can take ε to 0 and obtain the Hamilton-Jacobi equation with Dirichlet boundary

condition          -1 2 ∂ a Φ 0,l 1 θ 2 + f ∂ a Φ 0,l 1 -σ 2 2 (∂ l Φ 0,l 1 ) 2 -b∂ l Φ 0,l 1 = 0, Φ 0,l 1 (l 1 , . ) = 0.
(2.16)

Now assume, at least for the sake of the argument, that i) the committor function has globally bounded derivatives up to order 2 uniformly in ε near the boundary l = l 1 ,

ii) that the function on

R d ∂ l Φ ε,l 1 (≃ -2b/σ 2
) is indeed bounded away from 0 near the boundary l = l 1 .

Then from i) we get a Lipschitz continuity for ∂ a Φ ε,l 1 and with the boundary condition Φ ε,l 1 (l 1 , a) = 0 we obtain the second estimate in (2.13):

∂ a Φ ε,l 1 (l, a) ≤ c |l 1 -l| ,
for any l ≤ l 1 and any a ∈ R d-1 . Using this last estimate in equation (2.15) and with ii), we can rigorously obtain:

∂ l Φ ε,l 1 = -2 b σ 2 (l 1 , a) + O(|l 1 -l| + ε).
This justifies condition (2.13) in Assumption 2.3.4. We give a summary in the following lemma.

Lemma 2.3.7. Assume that the committor function ∂ l Φ ε,l 1 (l, a) has i) uniformly (in ε, in (a, l) and locally in l 1 ) bounded first two derivatives in a neighbourhood of the level set

l = l 1 , ii) is such that ∂ l Φ ε,l 1 is uniformly (in ε, in (a, l) and locally in l 1 ) bounded away from 0 on ] -∞, l 1 ] × R d-1 .
Then Assumption 2.3.4 is satisfied.

Notation and description of the algorithm with two particles

In this section, we recall the AMS scheme in Algorithm 3, in the two-particle situation, with obviously k = 1, and with the state space decomposition into a level and auxiliary variable x = (l, a) ∈ R × R d-1 stated in Assumption 2.3.1. Figure 2.1 depicts a realization of three iterations of AMS in this precise context, we simply denote now:

X = (L, A), (X j , T j ) = (L j , A j , T j ), j ≥ 0.
Notation in Algorithm 4 is similar to notation in Algorithm 3 and in the statement of the main Theorem 0.7.3

given in the introduction. This theorem will be stated again later, and we will explain the slight difference of notations we made. Before the description of the algorithm, we summarize some notation here, especially the notation for the key Markov chain that will be studied in the main Theorem.

• L n, j , A n, j denotes the trajectory of particle n ∈ {1, 2} after stage (iteration j) of the algorithm.

• L j ∈ R is the j-th level. This is the smallest maximum level between the two particles: L 1, j-1 , A 1, j-1 and

L 2, j-1 , A 2, j-1 , L j := min sup t≥0 L 1, j-1 t , sup t≥0 L 2, j-1 t
(2.17)

= sup t≥0 L (1), j-1 t
.

We underline here we made exactly the same choice than in the three previous algorithms concerning the dependence between the levels and the particles. This means that, just like previously, the j-th level L j is defined from the particles from stage j -1: as a consequence, the particles at any stage j ≥ 0 have strictly higher scores than L j . As a convention, we may define, as the initial condition of the SDE satisfied by L,

L 0 := l 0 .
• T j ∈ R + is the j-th branching time. This is the hitting time of the j-th level L j by the highest trajectory from the j -1 stage. More accurately:

T j := T L j (L (2), j-1 ) = inf t ≥ 0 : L (2), j-1 t = L j (2.18) = inf t ≥ 0 : L (2), j-1 t = sup t ′ ≥0 L (1), j-1 t ′ .
We underline that this particle (2) did not change between j -1 and j, as it was the highest one, so T j is also the hitting time of L j by any particle indexed by stage j: max t≥0 L

(2), j-1 t > L j , almost surely, and

L (2), j , A (2), j := L (2), j-1 , A (2), j-1 .
as well as for any n:

T j = inf t ≥ 0 : L n, j t = L j . • A j ∈ R d-1
is the state of the auxiliary coordinate at the j-th branching. This is the value of the second coordinate of the highest trajectory from the j -1 stage, when it hits the j-th level L j ,

A j := A (2), j-1 T j (2.19)
Algorithm 4 AMS -Two particles situation Require: Initial independent trajectories, denoted L 1,0 , A 1,0 and L 2,0 , A 2,0 , with values in R × R d-1 , starting from (l 0 , a 0 ) with common law L (L, A).

The algorithm stops if both trajectories reach the target set {ξ > l max }. Otherwise, we are able, by Assumption 2.3.3

and almost surely, to order them according to their maxima, i.e.

sup t≥0 L (1),0 t < sup t≥0 L (2),0 t . Set L 1 ← sup t≥0 L (1),0 t (first level).
Set j ← 1 (iteration index).

while L j ≤ l max do

We denote

T j := inf t ≥ 0 : L (2), j-1 t = L j , A j := A (2), j-1 T j .
T j is the hitting time of the j-th level by the highest particle from stage j -1, and the state of this latter particle, at this hitting time, is then

L (2), j-1 T j , A (2), j-1 T j = (L j , A j ) .
Keep the highest trajectory (2) unchanged and replace the lowest trajectory by a new one obtained as follows:

1. We copy the highest trajectory until the time T j .

2. We simulate, independently, a new trajectory, starting at the point (L j , A j ), according to the law of the Markov process (L, A).

This way, we get two trajectories: L 1, j , A 1, j and L 2, j , A 2, j verifying

           L 1, j t , A 1, j t : = L (2), j-1 t , A
(2), j-1 t

, ∀t ≤ T j , (the branching is on the highest trajectory (2)),

L 2, j t , A 2, j t : = L (2), j-1 t , A
(2), j-1 t

, ∀t ≥ 0.

(the highest trajectory (2) is not modified)

(2.20)

Order the two particles according their scores, i.e.

sup t≥0 L (1), j t < sup t≥0 L (2), j t . L j+1 ← sup t≥0 L
(1), j t j ← j + 1 end while Estimate the rare event probability by the estimator p AMS defined by

p AMS = 1 2 J AMS .
The estimator of the final distribution is given by

γ AMS (ψ) := 1 2 J AMS 1 2 ψ L 1,J AMS ,A 1,J AMS + ψ L 2,J AMS , A 2,J AMS .
By the strong Markov property, we have built a Markov chain (L j , T j , A j ) j≥0 , with the initial conditions (l 0 , 0, a 0 ). We recall that AMS gives unbiased quantities for any number of particles, but that the convergence theorems such that Central Limit Theorem 0.6.8 hold when N goes to infinity. These results will then be out of context there. We abandon, only in this paragraph, the notation of ε, as the results remain true in general context, and not only in small noise situation.

Unbiasedness of the estimators

We already stated that, for any N chosen, p AMS the estimator of the probability and γ AMS the unnormalized empirical measure are unbiased. This is the main consistency guarantee of the Algorithm 4. We can even describe some other estimators: for any real number l, we denote J l the number of iterations in AMS Algorithm 4 to pass the level l, rigorously, we set J l := inf j : L j > l , then, for any test function f and any real number l, we can introduce the empirical distribution

η l ( f ) := 1 2 f L 1,J l T 1,J l l , A 1,J l T 1,J l l + f L 2,J l T 2,J l l , A 2,J l T 2,J l ,
which is a biased estimator of the conditioned distribution of (L T l , A T l ), knowing that T l < ∞. We also define p l = (1/2) J l the estimator of the probability of the probability of hitting the level set {ξ > l}, and

γ l = p l η l .
We did lighten a little bit the notations in this paragraph, but the estimators p l , η l and γ l are the estimators given by AMS Algorithm 4.

Theorem 2.4.2. The unnormalized empirical measure γ l (ψ) := p l . η l (ψ) satisfies the unbiasedness property: for any test function ψ

E [ γ l (ψ)] = E [ψ (L T l , A T l ) 1 T l <∞ ] .
In particular, for ψ = 1 and l = l max , Theorem 2.4.2 states the unbiasedness property of p AMS = p l max , the estimator of the probability of the rare event set T l max < ∞ .

Practical use of the algorithm It is important to keep in mind that this ensures that the AMS algorithm even with N = 2 can be used to compute the target quantities: it is sufficient to draw many independent algorithms and then to average over estimators of unnormalized quantities.

Numerical simulations

To get numerical observations, we worked in dimension 2, with the process X = (L, A). In such a case, the score function is nothing more than the projection along the first coordinate. We assumed the dynamic of the system is the

following          d X t = -∇V (X t ) dt + √ εdW X t , X 0 = x 0 ,
where

V (x) = V (l, a) = l cos θ + a sin θ a l 2 + l sin θ -a cos θ a a 2 ,
with θ, a x and a y some real parameters: θ is the angular rotation of the ellipse, and a l and a a are the semi axes. Running AMS in this specific case gave us the following figures. Both SDEs and ODEs are discretized using an explicit Euler scheme.

Cases where the FW optimum is the limit ODE. The figure 2.2 has been obtained as follows: we choose some initial condition x 0 = (0.2, 0) and wish to reach the level line (l, a) : l = 1 . We run AMS Algorithm 4 and draw the numerical approximation of the EDO from Theorem 2.6.1. On this example, we took the initial condition on the semi-major axis, as we worked with

                 θ = 0, a l = 1, a a = 1/ √ 3.
In such a situation, the optimum trajectory given by Freidlin Wentzell is nothing but the trajectory on the semi-major axis, which coincides with the ODE limit on the simulations. Then, we ran the same algorithm with the same parameters, but with a different initial condition x 0 = (0, 2; 0, 5). This initial condition is no longer on the semi-major axis. The result is given on Figure 2.3: we ran AMS, simulated the ODE limit (FW optimum) from the initial condition x 0 = (0, 2; 0, 5). Note that the final state of the limit ODE as well as the final AMMS branching point are close to the semi-major axis. We also note that one can separate the variables L and A and check that the x 0 -starting Freidlin-Wentzell optimum is the same as the limit ODE in that case.

We are also interested in comparing AMS in the previous simulation to the Freidlin-Wentzell optimum starting form the local mimimum (0; 0) of V. We will call the later the 0-starting FW optimum. Indeed, there is a trade-off between two facts: the trajectory wants to go to the right, to reach the level line, but the dynamic makes it easier to do this close the semi-major axis, and not in the neighbourhood of the initial condition. One can expect that, asymptotically, the x 0 -starting Freidlin-Wentzell optimum and the 0-starting Freidlin-Wentzell optimum will be close: this is particularly visible on the Figure 2.4. Moreover, the ODE limit does not depend of the ending point, so we could interpret the ODE as follows: it first consists on a transition phase, depending on how far the initial condition is from the semi-major axis. This transition phase consists in getting closer to the Freidlin-Wentzell optimum, and then, the best trajectory is to follow the optimum. Looking at the simulations from Figure 2.3, but with much higher maximum target level l max , and from appropriately far away, will yield this transition. Cases where the FW optimum is different from the limit ODE. Finally, we also ran AMS Algorithm 4 with a rotated elliptic potential. This situation is way more complex: indeed, in the two first situations, we can indeed separate variables L and A and he Freidlin-Wentzell optimum is the same as the limit ODE.

Yet, in the situation

                 θ = π/3, a l = 1, a a = √ 3,
the variables can no longer be separated, as the potential is now

V (l, a) = l 2 2 + la √ 3 + 5a 2 6 .
To get Figure 2.5, we first took some point x = 1; -√ 3/5 . This point is the unique tangential point of the potential line x ∈ R 2 : V(x) = 0.4 with the level line (l, a) : l = 1 , and we recall that 1 is the value we wish to reach, for the level coordinate l. We then simulated the Freidlin-Wentzell optimum (this is no longer the semi-major axis) and took some point with score lower than 0.2, arbitrarily, and ran AMS Algorithm 4 from this point. We also simulated the ODE limit from this initial condition.

Remark 2.5.1. Let us underline that the tangency condition is no longer satisfied : this is quite clear on Figure 2.5, for the Freidlin-Wentzell optimum. Even if, we underlined in the introduction the need for an assumption about the Then, we discard all the trajectories having lower or equal maxima to the k-th one, instead of the k first particles. This variant is expected to obey similar results (unbiasedness, consistency, central limit theorem).

The other possibility, that we will use here, is to use a rejection method. The idea is quite simple: instead of branching on the first entrance state in the current level set ξ > L j+1 , we select preceding state of Euler explicit Markov chain approximation; and perform the branching on this state. In order to sample the future trajectory of the new cloned particle, we run a rejection method on the probability transition of the chain to get the next point above the level set L j+1 . Then, we simulate a new piece of trajectory with the Euler explicit chain starting at this point.

Roughly speaking, this rejection step adds randomness at the transition point and avoids equality of scores. The rejection method generates a new clone that leaves the distribution of the Markov chain conditioned to reach a given level. This is stated in the following very general proposition.

Proposition 2.5.2 allows us to use this rejection method, ensuring the law of the skeleton of the trajectory will not be changed.

Proposition 2.5.2. Let us consider (X n ) n a discrete Markov chain, with values in R verifying max n X n > l. We set N := inf {n ≥ 0 : X n > l} and we define Y as follows

Y j :=                  X j if j < N, Y N if j = N, Y j if j > N,
where Y N is obtained (using e.g. a rejection method) with the chain transition distribution from Y N-1 conditioned to be larger than l, and the random variables Y N+1 , Y N+2 , ... are obtained using the same Markov transition as (X n ) n≥N+1 .

Then, the Markov chains (X n ) and (Y n ) are equal, in law.

We state now the convergence of the Markov chain defined by the branching points and their times.

Statement of the main result

Let us assume we ran AMS with two particles L 1 , A 1 and L 2 , A 2 , whose law is given by the stochastic differential system (2.11). We ran the algorithm on R d , with two independent Brownian motions defining the particles 1 and 2, which gave us the sequence of levels (L j ) j≥0 , hitting times (T j ) j≥0 and branching points (A j ) j≥0 , as defined in Section 2.4. We recall here the definitions (2.17), (2.18) and (2.19) of these latter quantities

                   L j := sup t≥0 L (1), j-1 t , T j := inf t ≥ 0 : L (2), j-1 t = L j , A j := A (2), j-1 T j
.

By definition, we set the initial time equal to zero, and the initial branching points equal to the initial condition

L 0 := l 0 , T 0 := 0, A 0 := a 0 .
Theorem 2.6.1. Under Assumptions 2.3.1, 2.3.2 and 2.3.4, using notation from Algorithm 4,

• the map r → (L ⌊r/ε⌋ , A ⌊r/ε⌋ ) converges in probability, for the uniform topology, and when ε decreases to 0, to the solution to the system of differential equations

           ˙l(r) = σ 2 (l(r),a(r)) 4b(l(r),a(r)) , ȧ(r) = f (l(r), a(r)) σ 2 (l(r),a(r)) 4(b(l(r),a(r))) 2 , (2.21) with the initial conditions        l(0) a(0)        =        l 0 a 0        ,
• the map r → T ⌊r/ε⌋ converges in probability, when ε decreases to 0, to the function

t : r → r 0 σ 2 (l(s), a(s))
4 (b (l(s), a(s)) 2 ds,

(2.22)

where l and a are the solutions to (2.21).

According to Assumption 2.3.2, since b, f and σ 2 /b 2 are globally lipschitz, we have existence and uniqueness to the ODEs stated in Theorem 2.6.1. We can combine then combine these equations to formally write the time evolution of l and a

         d l(t) dt = b (l(t), a(t)) , d a(t) dt = f (l(t), a(t)) .
(2.23)

This last formula is interesting.

• Firstly, we see clearly that the run of AMS has no effect on the flow followed by the auxiliary coordinate, when we are able to split X in a level coordinate and an auxiliary one, with independent Brownian motions (Assumption 2.3.1).

• Secondly, we see that the drift function -b in the definition of L (8) has become +b in the limit ODE. We can interpret this as follows: under our assumption on the noise structure, the most likely way for the AMS algorithm to go up when the drift attracts the process to -∞ is simply to reverse the drift.

• Thirdly, the writing (2.23) is enjoyable in the common situation (b, f ) = ∇V, where V is a potential, and the diffusion coefficient is the identity (σ, θ) = Id. In such a situation, we can check that the optimal trajectories with initial condition at a local minimum of V in the Freidlin-Wentzell theory are solutions of gradient flow

d x(t) dt = +∇V(x(t)),
corresponding to a "time-reversed" gradient descent. However the AMS limit ODE is nothing but

         d l(t) dt = +∂ l V (l(t), a(t)) , d a(t) dt = -∂ a V (l(t), a(t)) ,
which means that the optimum of Freildin-Wentzell and the AMS limit trajectory coincide in this type of situations if, and only if, the part corresponding to the auxiliary coordinate ∂ a V is equal to zero on the ODE path.

We can also combine the ODEs from Theorem 2.6.1 to formally write the time evolution of r

d r(t) dt = 4 b 2 σ 2 (l(t), a(t)) .
(2.24)

We can finally compare the limiting ODEs associated with the AMS algorithm, at least in a very regular setting.

We start with Problem 2, and compare the AMS ODE (2.23) and the ideal ODE (2.9) derived from the small noise process conditioned to hit {ξ = l}.

Corollary 2.6.2. Let x 0 be an initial condition is given. Assume that the quasi-potential function DΦ 0,l max is Lipschitz continuous and define a classical solution to (2.8). Assume that for each point of the solution to the ODE (2.23)

followed by the small noise AMS algorithm, the quasi-potential function level set is tangent to the importance function level set, that is ∂ a Φ 0,l max (l(t), a(t)) = 0, then the AMS ODE (2.23) and the ideal ODE (2.9) describing the process conditioned to hit {ξ = l} are the same.

Proof. Let us take x(t) = (l(t), a(t)) a solution to (2.23). Thus, we have

ẋ (t) = (b (x(t)) , f (x(t))) .
If we have, for any t ≥ 0,

∂ a Φ 0,l (x(t)) = 0, then DΦ 0,l ββ T (x(t)) =        σ 2 ∂ l Φ 0,l (x(t)) 0        , and
α (x(t)) + DΦ 0,l ββ T (x(t)) =        -b (x(t)) f (x(t))        -        σ 2 ∂ l Φ 0,l (x(t)) 0        .
Finally, using Lemma 2.3.7, we know that, for any t ≥ 0,

-b (x(t)) -σ 2 ∂ l Φ 0,l (x(t)) = -b (x(t)) + σ 2 2b (x(t)) σ 2 (x(t)) = b (x(t)) .
We conclude using the uniqueness of the solutions to the ODEs (2.23) and (2.9), as the coefficients are Lipschitz

continuous. □

We can next consider Problem 1, and compare the ε-scaled number of iteration given by the AMS differential equation (2.24):

r AMS := t(l max ) 0 4 b 2 σ 2 (l(t), a(t)) dt
to the ideal average number of iteration given by a Poisson distribution of parameter -2 log p ε for ε small:

r ideal := lim ε→0 -2ε log p ε = 2Φ 0,l max (x 0 ).
Corollary 2.6.3. Under the same assumptions as the previous corollary, then it holds:

r AMS = r ideal .
Proof. Let us recall the relation satisfied by r AMS , as a consequence of Theorem 2.6.1:

r AMS = l max 0 4 b 2 σ 2 (x * (t)) ,
where x * is the unique solution to the ideal ODE (2.9). Since DΦ 0,l max is Lipschitz by assumption, the quasi-potential can be written as:

Φ 0,l max (x 0 ) = t(l max ) 0 1 2 ββ T -1 ( ẋ * (t) -α (x * (t)) , ẋ * (t) -α (x * (t))) dt = t(l max ) 0 1 2 ββ T -1 DΦ 0,l max ββ T , DΦ 0,l max ββ T dt.
Yet, using the tangent assumption which is

∂ a Φ 0,l max (l(t), a(t)) = 0, 2.7. Proof
of Lemma 2.7.1 below which formalize a standard probabilistic intuition that immediately yields:

Law L (2 ′ ), j , A (2 ′ ), j | L j-1 , A j-1 , L j = Law L (2), j , A (2), j | L j-1 , A j-1 , L j .
This enables us to work with the trajectory (2 ′ ) which is sampled conditionally on the state (L j-1 , A j-1 , L j ), but independently of the of the particle (2) which, at each step is compared to (1) in order to define L j . Note that this reconstruction step is not really necessary to carry out the proof. However, this new particle will be convenient to intuitively handle notation and various steps in the analysis without mistakes.

3. To overcome the problem of handling the conditioning in the sampling of (2 ′ ), we are going to remove the conditioning using Girsanov theorem in the form of a Doob "h-tranform": we will show that the particle (2 ′ ) is a strong solution to another SDE with no more conditioning. The idea is that a diffusion X, conditioned by reaching a level l in finite time, can be interpreted as diffusion with no more conditioning : the change of probability (defined by the conditioning) is translated into a new drift using Girsanov theorem. The SDE satisfied by the reconstructed process X (2 ′ ) is, of course, different from the original SDE satisfied by X and the new drift requires the addition the derivative of the committor function. This SDE will be given in Theorem 2.7.5 below.

Lemma 2.7.1. Let us take two independent and identically distributed random variables R 1 and R 2 . Let f a real valued function. We assume that P ( f (R 1 ) = f (R 2 )) = 0, and we denote the order statistics according to f as follows,

f (R (1) ) < f (R (2) )
.

Then, R (1) , R (2) is equal, in law, to R (1) , R (2 ′ ) , where R (2 ′ ) is distributed, conditionally on R (1) , according to L R f (R) > f 1 with f 1 = f (R (1))
). R refers to the common law of R 1 and R 2 .

Proof. Let us denote by P |R (1) the probability conditional on the value R (1) . We can write for any suitable set U,

P |R (1) R (2) ∈ U = 1 R 2 =R (1) P |R (1) R (2) ∈ U + 1 R 1 =R (1) P |R (1) R (2) ∈ U = 1 R 2 =R (1) P | r=R 2 (R 1 ∈ U | f (R 1 ) > f (r)) + 1 R 1 =R (1) P | r=R 1 (R 2 ∈ U | f (R 2 ) > f (r)) = P | r=R (1) (R ∈ U | f (R) > f (r)) .

□

Let us take a stage j ≥ 0 in AMS to clarify the use we make of the previous lemma. At stage j, we have two particles L 1, j , A 1, j and L 2, j , A 2, j , both higher that L j . The first coordinate of the lowest particle L (1), j defines the next level L j+1 , as its maximum value. Moreover, we know that almost surely, the maximum of L (2), j is strictly larger than L j+1 . We then sample independently a new trajectory X (2 ′ ), j starting from A j . Then, Lemma 2.7.1 states that L (2), j , A (2), j is equal, in law and conditionally on L j+1 , to the piece of the newly built trajectory X (2 ′ ), j . Indeed, before the branching time T j , the particles are the same, by construction, and from the branching time, this is a consequence of Lemma 2.7.1. We can then construct a variant of AMS, say AMS', by setting:

X 2, j+1 = X (2 ′ ), j . (2.25)
As a consequence of the previous discussion we obtain:

Lemma 2.7.2. In AMS Algorithm 4, setting 2.25 instead of the second line of (2.20) does not modify the global probability distribution of the AMS algorithm.

Remark 2.7.3. A similar result holds for the AMS algorithm with any N number of particles.

We can next give the precise SDE satisfied by the reconstructed process in the form of the following theorem. We postpone its demonstration to Appendix C. We recall the committor function is defined by

Φ ε,l (x 0 ) = Φ ε,l (l 0 , a 0 ) = -ε ln P T l (L) < ∞ L 0 , A 0 = (l 0 , a 0 ) .
Definition 2.7.4. The drift coefficients of the reconstructed, conditioned process are defined by

b ε l := -b -∂ l Φ ε,l σ 2 , f ε l := f -∂ a Φ ε,l θθ T . (2.26)
We then state the associated main theorem.

Theorem 2.7.5 (Girsanov). Let us denote (L, A) a strong solution to the SDE

         d L t = -b (L t , A t ) dt + √ ε • σ (L t , A t ) d W L t , d A t = f (L t , A t ) dt + √ εθ (L t , A t ) d W A t ,
conditioned by the event T l (L) < ∞ , where T l (L) is the hitting time of l ∈ R by the process L. The SDE satisfied by the conditioned process can be rewritten

         d L t = b ε l (L t , A t ) dt + √ ε • σ (L t , A t ) dW L t , d A t = f ε l (L t , A t ) + √ εθ (L t , A t ) dW A t , (2.27)
where in the above the adapted process t → (W L t , W A t ) is a Brownian motion under the conditional probability

P ( . | T l (L) < ∞).
Remark 2.7.6. Let us consider the special case of a drifted Brownian motion. If the coefficients are constant equal to (-b, σ) and the level set is above the initial condition, then it can be checked that the drift of the reconstructed process will be +b: roughly speaking it will reverse the drift to ensure the process reaches the level set. This will be very interesting to keep this idea in mind, which comes from the situation constant coefficients. The new drift functions b ε l 104 2.7. Proof and f ε l can be seen as follow: b ε l is the most important, as it is the former drift -b with a new term which compensates to make the particle go up. In the drifted Brownian motion case, this second term is equal to -2b, as we remarked just above. The second drift function f ε l is also the former drift f modified, but this will have no major consequences in the following since in fact ∂ a Φ ε,l ≃ 0 near the set {ξ = l} where Φ ε,l = 0 by construction.

The reconstructed process can be sampled using the latter modified SDE.

Corollary 2.7.7. At each stage j ≥ 1 of the AMS algorithm, the reconstructed process (L

(2 ′ ), j t , A ε(2 ′ ), j t
) after initial condition (L j , A j , T j ) is solution to the SDE (2.27) with standard Brownian motion (W L , W A ) independent from previously constructed random variables.

Remark 2.7.8. As mentioned previously, the main interest of this result is to work in a bit more simple situation. The transformation in theorem 2.7.5 will enable us to estimate effectively the hitting times and the auxiliary coordinate evaluated at these hitting times, as we will work with no conditioning anymore. Yet, we clearly see that we will require some conditions about Φ ε,l and its gradient.

Notation In subsections 2.7.5 and 2.7.6, we will abuse notations and write (L, A) instead of (L, A) for the recon- structed process defined by (2.27): there will be no confusion possible as this is the only process we will work with, in these subsections.

Re-scaling and coupling: definitions

For any integer j ≥ 1, we recall the definition (2.17) of the j-th level in AMS:

L j := sup t≥0 L (1), j-1 t ,
where L (1), j-1 is the particle with minimal score. In the same way, we recall that we have defined T j as the first hitting time of L j by the (re-constructed level) coordinate, and A j as the state of the auxiliary coordinate at time T j (see Figure 2.6:

T j := inf t ≥ 0 : L (2 ′ ), j-1 t ≥ L j ,
(2.28)

A j := A (2 ′ ), j-1 T j .
(2.29) Before introducing the main decomposition which is the basic starting point of the whole proof, we need to introduce some more notations.

ξ = L j L (2 ′ ), j-1 T j , A (2 ′ ), j-1 T j = (L j , A j )
Figure 2.6 -The state of the rebuilt trajectory at time T j Notation of re-scaled processes and coupled processes To study the dynamic of our process in AMS, we will need to re-scale it: indeed, due to the ε in front of the Brownian motion, we do need to 'zoom in' in order to more easily handle estimates.

Let us take j ∈ ⟦0, J AMS ⟧ and focus on the law of the pieces of AMS trajectories L 1, j , A 1, j and L 2, j , A 2, j .

conditionally on their past, (meaning we know, for example the branching points ((L 1 , A 1 ) , ..., (L j , A j )) and the branching times T 1 , ..., T j ) the both particles satisfy the following SDEs. Indeed, we know that one trajectory has been replaced from stage j -1, and has been re-branched at the state of the other one, at the hitting point of ξ = L j . This latter particle is the one which remained unchanged from step j -1. As a consequence, they both satisfy the following SDEs (2.30) where the Brownian motions W L j and W A j are independent, and the Brownian motions of one particle are also independent from the ones of the other.

                           d L j t+T j = -b L j t+T j , A j t+T j dt + √ ε • σ L j t+T j , A j t+T j dW L j t+T j , L j T j = L j , d A j t+T j = f L j t+T j , A j t+T j dt + √ εθ L j t+T j , A j t+T j dW A j t+T j , A j T j = A j ,
We transform now both pieces of particles to reach the micro scale. For this, we define Definition 2.7.9 (Re-scaling). The microscopic (or rescaled) processes will be denoted:

M j s := L j εs+T j -L j /ε B j s := A j εs+T j -A j /ε.
(2.31) This transformation highly depend on the stage j, as we need the level L j , the branching time T j and the auxiliary coordinate A j to define it. Please notice that the letter B does not refer to a Brownian motion, but to the auxiliary coordinate of the process at the microscopic scale. Thus we get two re-scaled particles with common law, conditionally of their past.

                 M j s = s 0 -b εM j u+T j + L j , εB j u+T j + A j du + s 0 σ εM j u+T j + L j , εB j u+T j + A j dW M, j u+T j , B j s = s 0 f εM j u+T j + L j , εB j u+T j + A j du + s 0 θ εM j u+T j + L j , εB j u+T j + A j dW B, j u+T j .
(2.32)

Notice that the independence between the first particle L 1, j , A 1, j and the second one L 2, j , B 2, j leads to independence between M 1, j , B 1, j and M 2, j , B 2, j . Now we have reach the micro scale, we are going to use the regularity of the functions b, σ, f and θ to approximate them by their values at the branching points. For this, we define the drifted Brownian approximations of these latest particles as strong solutions to the following system.

Definition 2.7.10 (Coupling). The 'drifted Brownian approximations' of the microscopic (or rescaled) processes are defined by

         M j s = -b (L j , A j ) s + σ (L j , A j ) W M, j s , B j s = f (L j , A j ) s + θ (L j , A j ) W B, j s , (2.33)
where, W M, j and W B, j are the same Brownian motions in (2.32) than in (2.33).

We remind that we have two particles here, so the Brownian motions associated to the particle 1 in AMS are the same than the Brownian motions associated to the drifted Brownian motion of its approximation, and so goes the same for the particle 2.

We are particularly interested in the process M, B because, with suitable hypotheses, not only are they going to be close enough of the real microscopic trajectories M and B, but also will they be simple enough to make us able to compute precisely some important quantities, just like the law of their maxima.

Microscopic notation for AMS levels and their coupled approximation. For M j (respectively M j ), we define M j (respectively M j ) the minimum of the maximum of the two particles in microscopic variables. This will be useful to prove the first statement of the theorem, about the convergence of the levels.

Definition 2.7.11 (Re-scaled and coupled levels). The AMS levels in microscopic (or rescaled) notation are defined by

M j+1 := L j+1 -L j ε = min sup s≥0 M 1, j s , sup s≥0 M 2, j s = sup s≥0 M (1), j .
(2.34)

The coupled drifted Brownian approximation is defined similarly using (2.33) by:

M j+1 = min sup s≥0 M 1, j s , sup s≥0 M 2, j s = sup s≥0 M (1), j (2.35)
Remark 2.7.12 (Index notation). The fact we define M j+1 and M j+1 , and not simply M j and M j , might surprise at first sight. However, we made this choice to remain coherent with the algorithmic point of view: at macroscopic scale, the particle at stage j have higher scores than L j and they define the level L j+1 . We just did the same, but at microscopic scale.

Remark 2.7.13 (On coupling error in particles score order). We did write that the microscopic levels M j+1 and M j+1

were the scores of the lowest microscopic particles. It is important to have in mind that the lowest particles among the AMS particles, and their drifted Brownian motion approximations, might not have the same index. Of course, this is unlikely, as the reason we introduced the drifted Brownian motions is because they are easier to manipulate, while being pretty close to the microscopic particles. We will prove later that the probability of the event "the index of the lowest particle is not the same than the index of the lowest drifted Brownian motion" has vanishing probability (Lemma 2.7.24).

Re-scaling and coupling notation for the surviving (reconstructed) particle We now turn to microscopic notation and coupling of the surviving particle. Some care is required in order to handle the conditioning in notation.

Indeed, using Theorem 2.7.5, we know the reconstructed particle (2 ′ ) in fact satisfies

                           d L (2 ′ ), j t+T j = b ε L j L (2 ′ ), j t+T j , A (2 ′ ), j t+T j dt + √ ε • σ L (2 ′ ), j t+T j , A (2 ′ ), j t+T j dW L (2 ′ ), j t+T j , L (2 ′ ), j T j = L j , d A (2 ′ ), j t+T j = f ε L j L (2 ′ ), j t+T j , A (2 ′ ), j t+T j dt + √ ε • σ L (2 ′ ), j t+T j , A (2 ′ ), j t+T j dW L (2 ′ ), j t+T j , A (2 ′ ), j T j = A j ,
which is equal in law to the highest particle (2) at stage j. Let us recall that

T j = inf t ≥ 0 : L (2 ′ ), j t ≥ L j , A j = A (2 ′ ), j T j .
Definition 2.7.14 (Re-scaled surviving particle). The microscopic (or rescaled) key Markov chain will be denoted (M j , S j , B j ) where the microscopic level M j is defined by (2.34), the microscopic M j -hitting time of the surviving particle by

S j := T j -T j-1 ε , (2.36)
and the associated M j -entrance state by

B j := A j -A j-1 ε .
(2.37)

Remark 2.7.15. The reconstructed particle L (2 ′ ), j , A (2 ′ ), j is treated in the same way as (2.31), leading to M (2 ′ ), j , B (2 ′ ), j which is a solution to the stochastic differential system

                 M (2 ′ ), j s = s 0 b ε L j+1 ε M (2 ′ ), j u+T j +L j , ε B (2 ′ ), j u+T j +A j du + s 0 σ ε M (2 ′ ), j u+T j +L j , ε B (2 ′ ), j u+T j +A j dW M (2 ′ ), j u , B (2 ′ ), j s = s 0 f ε L j+1 ε M (2 ′ ), j u+T j +L j , ε B (2 ′ ), j u+T j +A j du + s 0 θ ε M (2 ′ ), j u+T j +L j , ε B (2 ′ ), j u+T j +A j dW B (2 ′ ), j , (2.38)
where the new drift functions b ε L j and f ε L j are given in Theorem 2.7.5.

Similar quantities can also be defined for a coupled drifted Brownian approximation, which has to be first precised.

The drifted Brownian motion approximation of M (2 ′ ), j , B (2 ′ ), j as the strong solution to the stochastic differential

system          M (2 ′ ), j s = b ε L j+1 (L j , A j ) s + σ (L j , A j ) W M (2 ′ ), j s B (2 ′ ), j s = f ε L j+1 (L j , A j ) s + θ (L j , A j ) W B (2 ′ ), j s , (2.39)
with the same Brownian motions than in (2.38). Just like previously, as long as the function in the stochastic differential system (2.38), we expect its solution to be close to the solution to (2.39).

Note that S j is the first hitting time by the reconstructed process in microscopic notation, i.e.

S j := inf s ≥ 0 : M (2 ′ ), j s = M j .
(2.40)

The microscopic auxiliary coordinate at hitting satisfies:

B j := B (2 ′ ), j S j
.

(2.41)

Definition 2.7.16 (Coupled surviving particle). B j , the drifted Brownian motion approximation of B j , is defined by (2.42) where we emphasize that the state B is computed at the hitting time S j of the reconstructed process and not at some hitting time S j associated with its drifted Brownian approximation.

B j := B (2 ′ ), j S j ,

Comparison with the limit ODE: main decomposition

This section is dedicated to the main decomposition of the difference between the key Markov chain (L j , T j , A j ) j≥0 and the solution of the limiting ODE. This is the main ingredient of the proof of Theorem 2.6.1.

Indeed, now that we have defined the microscopic processes, their drifted Brownian motion approximations and the corresponding quantities, we can use Gronwall lemma A.0.1 to control the distance between i) the AMS quantities defingin the key Markov chain (levels L j , branching points A j and branching times T j ) and ii) the solutions to the ODEs (2.21) and (2.22).

The main "Gronwalled" decomposition The following result gives an estimate on the error quantities ∆ L j , ∆ A j and ∆ T j , by using the following variant which introduces a sum of local errors, which computes by definition the difference between increments of the key Markov chain minus the flow satisfied by the ODE.

Definition 2.7.18. The sum of the local errors between (L j , A j , T j ) and the limit ODE is defined by:

C L j := j i=1 L i -L i-1 -ε σ 2 (L i-1 , A i-1 ) 4 b (L i-1 , A i-1 ) , C A j := j i=1 A i -A i-1 -ε f (L i-1 , A i-1 ) σ 2 (L i-1 , A i-1 ) 4 b (L i-1 , A i-1 ) 2 , C T j := j i=1 T i -T i-1 -ε σ 2 (L i-1 , A i-1 ) 4 b (L i-1 , A i-1 ) 2 .
The next lemma is the main decomposition theorem, and is based on a "Gronwalled" comparison between the full errors denoted with letter ∆ and the local errors denoted with letter C. This result will be useful, because once we will have proved that the right term (the local errors C) converges uniformly to zero, in probability, we will be able to conclude.

Lemma 2.7.19. There exists a constant c = c (b, σ, f ) > 0 depending on the boundaries of b, σ and f (Assumption 2.3.2) such that, for any j ∈ ⟦0, ⌊r/ε⌋, we have

∆ L j + ∆ A j ≤ C L j + C A j + c( j)ε 2 + cεe jcε • j i=1 C L i + C A i , (2.43) ∆ T j ≤ C T j + c ( j) ε 2 + cε         j i=1 ∆ L i + j i=1 ∆ A i         , (2.44)
where

C L j = ε j i=1 M i -M i + ε j i=1 M i -E M i F i-1 + ε j i=1        E M i F i-1 - σ 2 (L i-1 , A i-1 ) 4 b (L i-1 , A i-1 ) ,        (2.45) C A j = ε j i=1 B i -B i + ε j i=1 B i -E B i F i-1 + ε j i=1         E B i F i-1 -f (L i-1 , A i-1 ) σ 2 (L i-1 , A i-1 ) 4 b (L i-1 , A i-1 ) 2         , (2.46) C T j = ε j i=1 (S i -E [ S i | F i-1 ]) + ε j i=1         E [ S i | F i-1 ] - σ 2 (L i , A i ) 4 b (L i , A i ) 2         .
(2.47)

Before we start our computation, let us underline that the boundedness assumptions on b(., .), σ(., .) and f (., .) imply that l, a and t are C 1 functions. Thus there exists a constant c = c (b, σ, f ) depending on their boundaries, such that, for any j ∈ ⟦0, ⌊r/ε -1⌋⟧, we have, for any s ∈ [ jε, ( j + 1)ε], l (s) -l (( j + 1) ε)

≤ εc, a (s) -a (( j + 1) ε) ≤ εc, t(s)t (( j + 1) ε) ≤ εc.

(2.48)

Proof of Lemma 2.7.19. The idea is to bound the quantities ∆ L and ∆ A , using the continuity of the functions b, σ and f , using the coupled process M, B and Gronwall lemma.

Let us focus on ∆ L j+1 . First of all, we will make appear M j+1 and M j+1 . Then, we will compute exactly the first order moment of M j+1 , as it is the minimum between two maximum of independent Brownian motions, and use Lipschitz property.

From (2.34) we have,

∆ L j+1 = L j + εM j+1 -l (( j + 1) ε) = ∆ L j + εM j+1 - ( j+1)ε jε ˙l(u)du.
Using notation from Theorem 2.6.1

˙l(u) = σ 2 (l(u), a(u)) 4b (l(u), a(u)) ,
we can write

∆ L j+1 -∆ L j -C L j+1 + C L j = ( j+1)ε jε       σ 2 (L j+1 , A j+1 ) 4b (L j+1 , A j+1 ) - σ 2 (l(u), a(u)) 4b (l(u), a(u))       du.
(2.49)

Denoting c a Lipschitz constant for the function ˙l = σ 2 /4b, equation (2.49) gives

∆ L j+1 -∆ L j -C L j+1 + C L j ≤ ( j+1)ε jε c L j+1 -l(u) + A j+1 -a(u) du ≤ cε ∆ L j+1 + ∆ A j+1 + cε 2 ,
changing c = c (b min , σ max , f max ) as constant also satisfying (2.48).

Then, as

∆ L j+1 = j i=0 ∆ L i+1 -∆ L i -C L i+1 + C L i + C L j+1 ,
we get

∆ L j+1 ≤ C L j+1 + cε         j+1 i=1 ∆ L i + ∆ A i + c ( j + 1) ε         .
(2.50) 112

Proof

Adapting the reasoning to the study of ∆ A , we first have, thanks to (2.37),

∆ A j+1 = A j + εB j+1 -a (( j + 1) ε) = ∆ A j + εB j+1 - ( j+1)ε jε ȧ(u)du,
where

ȧ(u) = f (l(u), a(u)) σ 2 (l(u), a(u)) 4 b (l(u), a(u)) 2 ,
is the function stated in Theorem 2.6.1.

In the same way than before, we first have

∆ A j+1 -∆ A j -C A j+1 + C A j = ( j+1)ε jε         f (L j+1 , A j+1 ) σ 2 (L j+1 , A j+1 ) 4 b (L j+1 , A j+1 ) 2 -f (l(u), a(u)) σ 2 (l(u), a(u)) 4 b (l(u), a(u)) 2         du,
and then, denoting c a Lipschitz constant of ȧ, we have

∆ A j+1 -∆ A j -C A j+1 + C A j ≤ cε ∆ L j+1 + ∆ A j+1 + cε 2 ,
where c is a constant depending on b min , σ max and f max , satisfying (2.48).

By summation, we get

∆ A j+1 ≤ C A j+1 + cε         j+1 i=1 ∆ L i + ∆ A i + c ( j + 1) ε         .
(2.51) Summing (2.50) and (2.51), and changing c if needed, we get

∆ L j+1 + ∆ A j+1 ≤ C L j+1 + C A j+1 + cε 2 + cε j+1 i=1 ∆ L i + ∆ A i .
and using a Gronwall lemma discrete version (Lemma A.0.1), we conclude about (2.43).

We end this proof with the hitting times: from (2.36), we write

∆ T j+1 = ∆ T j + εS j+1 - ( j+1)ε jε ṫ (u) du,
and then in the same way than previously, we have

∆ T j+1 ≤ C T j+1 + cε 2 + cε ∆ L j+1 + ∆ A j+1 .
□

Convergence of the level term

In this subsection, we prove the convergence to zero of the quantity C L defined by (2.45). The purpose of this subsection is to prove the following proposition.

Proposition 2.7.20. For any p ≥ 1 and any q > 1, there exists a constant c = c (p, q, b, σ, f, θ) > 0, depending on the Lipschitz constants and the boundaries of the functions b, σ, f and θ (Assumption 2.3.2), verifying for any ε > 0:

E        sup j≤⌊r/ε⌋ C L j p        ≤ cε 1/q .
Consequently to Proposition 2.7.20, the sequence C L j converges, uniformly in j of order 1/ε, to zero in L p . The proof of Proposition 2.7.20 will be constituted of four lemmas that are necessary to prove that each of the three terms of (2.45) goes to zero.

We start with a lemma giving the conditional expectancy of the drifted Brownian motion approximation of the microscopic level. Thus, as a consequence of Lemma 2.7.21, we will know that the third and last quantity in (2.45) vanishes: for any suitable i

E M i F i-1 - σ 2 (L i-1 , A i-1 ) 4 b (L i-1 , A i-1
) , so for any suitable integer j, we have

C L j+1 = ε j+1 i=1 M i -M i + ε j+1 i=1 M i -E M i F i-1 .
Lemma 2.7.21. For any suitable integer j, we have

E M j F j-1 = σ 2 (L j-1 , A j-1 ) 4b (L j-1 , A j-1 ) .
Proof. This lemma is a direct consequence of Lemma D.2.1 from appendix D. Indeed, this lemma states that the maximum of a drifted Brownian motion, with negative drift, is an exponential variable, and, as M j is defined as the minimum of the maxima of two independent drifted Brownian motions, M j is also a exponential variable. □

The following result deals with the martingale part of C L . It is expected, in the considered scaling, that the martingale part will simply converge to zero because its quadratic variation is of order ε 2 × 1/ε.

Lemma 2.7.22. For any r > 0 and p ≥ 1, there exists a constant c = c (p, b, σ) depending on the boundaries of the coefficients (Assumption 2.3.2) such that, for any ε > 0, we have

E          ε ⌊r/ε⌋ i=1 M i -E M i F i-1 p          ≤ cε p/2 . Proof. Conditionally on F i-1 , M i is an exponential random variable (see Lemma D.3.2), so i≥1 M i -E M i F i-1
is L 1 , and the property of martingale follows. Moreover, using the boundaries hypotheses about the functions b(.) and σ(.), we have

Var M i |F i-1 ≤ σ 4 (L i-1 , A i-1 ) 16b 2 (L i-1 , A i-1 ) ≤ c (b min , σ max ) .
Let us take r > 0, we have, by the Burkholder-Davies-Gundy inequality applied to the martingale property

E          ε ⌊r/ε⌋ i=1 M i -E M i F i-1 p          ≤ cε p E            ⌊r/ε⌋ i=1 Var M i | F i-1 p/2            ≤ cε p ε -p/2
≤ cε p/2 , which proves that the martingale is L p , and gives the boundary stated. □

The next lemma states that the second term, in C L ⌊r/ε⌋ converges, in L p , for any p ≥ 1, to zero. Once we will have proved this, we will be able to conclude about Proposition 2.7.20.

Lemma 2.7.23. For any r > 0, p ≥ 1 and q > 1, we have

E          ε ⌊r/ε⌋ i=1 M i -M i p          ≤ cε 1/q ,
where c = c (p, q, b, σ, f, θ) depends on the Lispchitz constants of b, σ, f and θ and their boundaries (Assumption 2.3.2).

This lemma is more technical than the previous ones, especially because, as we already mentioned previously, M i might be the supremum of M 1,i and M i the supremum of M i,2

. Hence, in such a situation, as we have independence between the respective Brownian motions, M i and M i are going to be independent, and it seems hopeless to be able to prove directly our result. Fortunately, as the processes M and M tend to be close, by continuity of the functions b(.)

and σ(.), this event should occur with a vanishing probability. Thus, our reasoning will be the following:

• control the probability of the event 'M i and M i are not related to the same Brownian motion',

• when M i and M i are related to the same Brownian motion, we will refer to Appendix D and directly estimate the difference of the maxima.

Lemma 2.7.24. If i is a step in AMS, let us denote Bad i the event

′ I i := argmin n∈{1,2} sup s≥0 M n,i s argmin n∈{1,2} sup s≥0 M n,i s =: I i ′ .
For any q > 1, there exists a constant c = c (q, b, σ) ≥ 0 depending on the boundaries of the coefficients b, σ (Assumption 2.3.2) such that P (Bad i ) ≤ cε 1/q .

(2.52)

Proof. By definition, I i (respectively I i ) refers to the smaller supremum of the particles among M 1,i and M 2,i (respectively M

1,i and M

2,i

) realising M i (respectively M i ), meaning that

               M i := min sup s≥0 M 1,i s , sup s≥0 M 2,i s = sup s≥0 M I i ,i ≤ sup s≥0 M I i ,i , M i := min sup s≥0 M 1,i s , sup s≥0 M 2,i s = sup s≥0 M I i ,i ≤ sup s≥0 M I i ,i . Let us set                      C i : = sup s≥0 M I i ,i -sup s≥0 M I i ,i , C i : = sup s≥0 M I i ,i -sup s≥0 M I i ,i , D i : = C i + C i .
As a remark, the quantities C i and C i , and then D i , are null on the event Good i = Bad c i . These last three quantities are nonnegative, moreoever, as the supremum of the two particles are almost surely different, we have

C i 1 Bad i > 0, C i 1 Bad i > 0, and 0 ≤ C i ≤ D i .
Then, for 0 < x < 1 and k ≥ 1 and k ′ ≥ 1, such that 1/k + 1/k ′ = 1, we have

P (Bad i ) ≤ E         D i C i 1-x k 1 Bad i         ≤ E        1 C i 1-x 1 Bad i        1 k E D k ′ 1-x k i 1 Bad i 1 k ′ , (2.53)
where we used Hölder inequality.

As sup s≥0 M 1,i s , sup s≥0 M 2,i s are two i.i.d exponential variables with parameter 2b (L i-1 , A i-1 ) /σ 2 (L i-1 , A i-1 ), the difference between the max and the min is also an exponential random variables, with same parameter. This way, we 116 2.7. Proof can almost surely identify C i on the event Bad i with E i , that is

C i 1 Bad i = E i 1 Bad i ,
where

E i := sup s≥0 M 2,i s -sup s≥0 M 1,i s
is exponentially distributed with parameter

λ i := 2b (L i-1 , A i-1 ) /σ 2 (L i-1 , A i-1 ) .
Then, 1

C i 1-x 1 Bad i ≤ 1 E 1-x i ,
and, as 0 < x < 1, we have

E        1 C i 1-x 1 Bad i        ≤ +∞ 0 1 u 1-x λ i exp (-λ i u) du = Γ (x) λ 1-x i ≤ c (x, b max , σ min ) .
Note that we also have k/k ′ = k ′ -1, so we can write

E D k ′ 1-x k i 1 Bad i = E D (1-x)(k ′ -1) i 1 Bad i = E        sup s≥0 M i, I i s -sup s≥0 M i, I i s + sup s≥0 M i,I i s -sup s≥0 M i,I i s (1-x)(k ′ -1) 1 Bad i        .
Let us take k ′ large enough (and k such that they are still satisfying 1/k ′ + 1/k = 1), so that (1

-x)(k ′ -1) ≥ 2, from the relation (2.53), we have a constant c = c (x, k ′ , b max , b min ) such that P (Bad i ) ≤ c E        sup s≥0 M I i ,i s -sup s≥0 M I i ,i s + sup s≥0 M I i ,i s -sup s≥0 M I i ,i s (1-x)(k ′ -1) × 1        1 k ′ ≤ c E         sup s≥0 M I i ,i s -sup s≥0 M I i ,i s (1-x)(k ′ -1) + sup s≥0 M I i ,i s -sup s≥0 M I i ,i s (1-x)(k ′ -1)         1 k ′ ≤ c E         sup s≥0 M I i ,i s -sup s≥0 M I i ,i s (1-x)(k ′ -1)         1 k ′ .
Lemma D.4.2 states that for any p ≥ 1, there exists a constant c = c (p, b min , b max , σ min , σ max ) depending on the Lipschitz constant of functions b, σ, f and θ and on such that, for ε > 0 small enough,

E sup s≥0 M I i ,i s -sup s≥0 M I i ,i s p ≤ cε p (-log ε) p+1 ,
which implies here that

P (Bad i ) ≤ cε 1-x k (-log ε) 1-x k ,
where c = c (b min , b max , σ min , σ max , x, k ′ ) also depends on the Lipschitz constants.

We conclude by picking 1-x k > 1/q as the previous inequality remains true for any 0 < x < 1 and any k ≥ 1. □

We can now prove the Proposition 2.7.23: on the event Bad i , we will use Lemma 2.7.24 to bound its probability, and on Good i , we will use Lemma D.4.2 to compute the difference between the maxima.

Proof of Proposition 2.7.23. Let us take two integers i ≥ 1 and p ≥ 2.

• Let us first work in the situation of Bad i : there exists two random indices I j and I j such that I j I j and

E M i -M i p 1 Bad i = E sup s≥0 M i,I i s -sup s≥0 M i, I i s p ≤ c (p) E sup s≥0 M I i ,i s p + sup s≥0 M I i ,i s p ,
and using Lemma D.3.2 which gives a boundary of the moment of order p of the supremum, we get, for any

p ≥ 1 E M i -M i p 1 Bad i ≤ c (p) max n∈⟦1,2⟧ E sup s≥0 M n,i s p + max n∈⟦1,2⟧ E sup s≥0 M n,i s p ≤ c (p, b min , σ max ) .
• Let us now work in the situation of Good i , so M i and M i are realised by two particles with the same Brownian motion. There exists a random index I i ∈ {1, 2} such that, on the event Good i , we have, for any p ≥ 2

M i -M i p = sup s≥0 M I i ,i s -sup s≥0 M I i ,i s p .
Then, using Lemma D.4.2, there exists a nonnegative constant c = c (p, b min , b max , σ min , σ max ) also depending on the Lipschitz constants of b, σ, f and θ such that

E sup s≥0 M I i ,i s -sup s≥0 M I i ,i s p ≤ max n∈⟦1,2⟧ E sup s≥0 M n,i s -sup s≥0 M n,i s p ≤ cε p (-log ε) 2p
To end this proof, we decompose using the events Good i and Bad i . Changing the constant c when it is necessary, and picking a > 1 with 1/a + 1/a ′ = 1, we have:

E          ε ⌊r/ε⌋ i=1 M i -M i p          ≤ c E         ε ⌊r/ε⌋ i=1 M i -M i p         = cε ⌊r/ε⌋ i=1 E M i -M i p 1 Good i + cε ⌊r/ε⌋ i=1 E M i -M i p 1 Bad i ≤ cε ⌊r/ε⌋ i=1 ε p (-log ε) 2p + cε ⌊r/ε⌋ i=1 E M i -M i pa ′ 1 Bad i 1/a ′ E [1 Bad i ] 1/a ,
by Hölder inequality. Then, using Lemma 2.7.24, we have:

≤ cε ⌊r/ε⌋ i=1 ε p (-log ε) 2p + cε ⌊r/ε⌋ j=1 ε 1/aq .
We obtain the result since a, q > 1 are arbitrary. □ Remark 2.7.25. This concludes this subsection, even though we did not prove the convergence of ∆ L j . Indeed, even if we proved that C L j converges to zero, the boundary of ∆ L j in (2.43) we stated in Lemma is 2.7.19 also depends of

C A j ∆ L j+1 + ∆ A j+1 ≤ C L j+1 + C A j+1 + c( j + 1)ε 2 + cεe jcε • j+1 i=1 C L i + C A i .
As a consequence, we need to prove the convergence of C A j to conclude about the convergence of ∆ L j . This will be done in the next subsection, postponing some computations about the hitting times S j to the final subsection.

Convergence of the second coordinate

In this subsection, we will prove the convergence of the quantity C A defined by (2.46). We first recall the decomposition (2.46) of the latter: for any integer j, we set

C A j := ε j i=1 B i -B i + ε j i=1 B i -E B i F i-1 + ε j i=1         E B i F i-1 -f (L i-1 , A i-1 ) σ 2 (L i-1 , A i-1 ) 4 b (L i-1 , A i-1 ) 2         ,
where L refers to the levels computed in AMS we just studied in the previous subsection, and A denote the auxiliary coordinate at the branching point. We recall (2.29) the definition of A j

A j = A (2 ′ ), j T j .
Remark 2.7.26 (Notation). Let us take some integer j. We recall that the filtration F j contains the information of all the past trajectories, until they have reached the level L j . We can now work conditionally on F j and the next level

L j+1 : F j ∨ σ(L j+1 ).
We recall that the distribution of t → (L (2 ′ ), j t

, A

(2 ′ ), j t

) conditional on L j+1 , already discussed in Section 2.7.1 can be described using the Girsanov-Doob theorem (Corollary C.0.4) to remove the conditioning. In what follows, we will write L and A for L (2 ′ ) and A (2 ′ ) : there is no confusion possible as we will never work here with the particle used to compute L j+1 . We will also omit the dependency in j. So for instance we will write:

(L t , A t ) := (L (2 ′ ), j t , A (2 ′ ), j t ),
We start recalling the different definitions or processes we will need, with the abuse of notation we just mentioned.

The re-scaled transform process (see Section 2.7.2) is obtained through

M s = L εs+T j -L j /ε, B s = A εs+T j -A j /ε,
and that (M, B) is a strong solution to the stochastic differential system,

                         d M s = b ε L j+1 (ε M s +L j , ε B s +A j ) ds + σ (ε M s +L j , ε B s +A j ) dW M s , M 0 = 0, d B s = f ε L j+1 (ε M s +L j , ε B s +A j ) ds + θ (ε M s +L j , ε B s + A j ) dW B s , B 0 = 0, (2.54) where b ε L j+1 := -b -σ 2 ∂ l Φ ε,L j+1 , (2.55) f ε L j+1 := f -∂ a Φ ε,L j+1 θθ T , Φ ε,L j+1 := -ε ln P T L j+1 (X) < ∞ X 0 = . .
We recall T L j+1 (X) is the first hitting time of the AMS level L j+1 by the reconstructed process X = (L, A).

For any suitable integer j, we defined the drifted Brownian motion approximation at stage j of the re-built trajectory as a strong solution to the following stochastic differential system

         M s = b ε L j+1 (L j , A j ) s + σ (L j , A j ) W M s , B s = f ε L j+1 (L j , A j ) s + θ (L j , A j ) W B s ,
(2.56) 120 2.7. Proof and we defined in (2.41)

B j+1 := B S j+1 ,
where S j+1 is the hitting time of the microscopic level M j+1 by the process M, defined in (2.40).

We aim at proving the convergence, in L p , uniformly in j of order 1/ε, for any p ≥ 2 of C A to 0, which is stated in the following proposition.

Proposition 2.7.27. For any p ≥ 1, there is a constant c = c (p, b min , b max , f max , σ max , θ max , DΦ max ) such that, for any r, ε > 0

E        sup j≤⌊r/ε⌋ C A j p        ≤ cε p-1 ,
where we recall

C A j+1 = ε j+1 i=1 B i -B i + ε j+1 i=1 B i -E B i F i-1 + ε j+1 i=1        E B i F i-1 -f (L i-1 , A i-1 ) σ 2 (L i-1 , A i-1 ) 4b (L i-1 , A i-1 ) 2        . (2.57)
Let us underline that the Propositions 2.7.27 and 2.7.20 are sufficient to conclude about the convergence of the levels and the auxiliary variables, to the limit ODE in Theorem 2.6.1. Indeed, the convergence of ∆ L j and ∆ A j depends of the convergence of C L j and C A j in Lemma 2.7.19. In the previous subsection 2.7.4, we already proved the convergence of C L , but not the convergence of ∆ L as explained in Remark 2.7.25. Once we will have shown the convergence of C A , we will be able to conclude that ∆ L and ∆ A converge to 0, in L p , for any p ≥ 2. We will nonetheless need some estimates on the hitting time S j that will be studied in the next section, Section 2.7.6.

We start with a Lemma giving the expectancy of B j+1 , conditionally on F j . This is a required result to state Proposition 2.7.19, but also to understand the limit ODE of r → A ⌊r/ε⌋ . Lemma 2.7.28. For any p ≥ 1 and q > 1, there exists a constant c = c (p, q, b, σ, f, θ) such that, for any ε > 0

E        B j+1 -f (L j , A j ) σ 2 (L j , A j ) 4b (L j , A j ) 2 p        ≤ cε p q .
(2.58)

In order to carry out the proof, we will need some results about the mean and moments conditional on F j of the hitting time S j+1 that we have not proved yet. These results will be proved in the next section, so we will only use them as plug-ins. We made this choice in the organization of the document as the study of the hitting times is quite different to the study of the level and auxiliary coordinates.

Proof of Lemma 2.7.28. Let us take p ≥ 1. First of all, S j+1 is a stopping time for the filtration F j σ (L j+1 ) , with finite moments of order p, for any p ≥ 1: indeed, Lemma 2.7.32 ensures that T j+1 is a stopping time with finite moment of order p, and S j+1 is nothing else but the microscopic increment of T j+1 . Then, as

E W B S j+1 2 F j , L j+1 = E S j+1 F j , L j+1 < ∞,
by Doob optional stopping time theorem conditionally on F j and L j+1 , we have

E W B S j+1 F j , L j+1 = 0.
Thus, the computation of the expectation of B j+1 , conditionally on F j and L j+1 is nothing more than

E B j+1 F j , L j+1 = E f ε L j+1 (L j , A j ) S j+1 F j , L j+1 .
But due to its definition (2.55), we do know f ε L j+1 (L j , A j ) is measurable for the σ-algebra generated by F j and L j+1 , so

E B j+1 F j = E f ε L j+1 (L j , A j ) E S j+1 F j F j , L j+1 ,
and we will later estimate the conditional expectation of S j+1 , conditionally on F j in Lemma 2.7.34, as

E S j+1 F j - σ 2 (L j , A j ) 4 b (L j , A j ) 2 ≤ cε 1 q ,
where c = c (p, q, b, σ, f, θ) > 0.

Moreover, we have

E f ε L j+1 (L j , A j ) F j , L j+1 = E f (L j , A j ) + θ (L j , A j ) θ T (L j , A j ) ∂ a Φ ε,L j+1 (L j , A j ) F j , L j+1 = f (L j , A j ) + θ (L j , A j ) θ T (L j , A j ) E ∂ a Φ ε,L j+1 F j ,
We will also use Assumption 2.3.4 which allows us to considerate a constant c > 0, such that for any ε > 0, for any

l, l ′ ∈ R and a ∈ R d-1 , we have ∂ a Φ ε,l ′ (l, a) ≤ c l ′ -l .
Here, we know that L j+1 -L j = εM j and thanks to Lemma D.3.2, we can bound the moment of order p of M j , such that

E ∂ a Φ ε,L j+1 (L j , A j ) p F j ≤ c E ε p M j p F j ≤ c (p, b min , σ max ) ε p .
□ Lemma 2.7.28 ensures that the third term in the definition of C A (which is recalled in Proposition 2.7.27: equation

(2.57)) will go to 0 ∈ R d-1 , when ε decreases to zero, in L p . The convergence of the second term presents no major difficulty, as it is the martingale part of C A . Let us continue with this one and prove it is a L p martingale, for p ≥ 2.

For this, we will use some boundary conditions about the functions f and θ, but also that S i has finite moments of order p (see Lemma 2.7.32 for the L p property of S i ).

Proof

Lemma 2.7.29. For any p ≥ 1, there exists a constant c = c (p, b, σ, f, θ, DΦ) such that and for any r, ε > 0, we have

E          ε ⌊r/ε⌋ i=1 B i -E B i F i-1 p          ≤ cε p/2 .
Proof. By construction, it is clear that, up to the integrability condition, the martingale property is verified by

i≥1 B i -E B i F i-1 .
Since S i is a stopping time, by Burkholder-Davis-Gundy inequality (see for example Corollary 4.2 from Chapter 4 in [START_REF] Revuz | Continuous Martingales and Brownian Motion[END_REF]), there exists a constant c = c(p) such that

E E W B S i p F i-1 ≤ c E S p/2 i .
(2.59) and this last expectation is finite using Cauchy-Schwarz inequality to bound the expectation of B i p ,

E B i p = E B i S i p = E f ε L i (L i-1 , A i-1 ) S i + θ (L i-1 , A i-1 ) W B S i p ≤ c E f ε L i (L i-1 , A i-1 ) S i p + E θ (L i-1 , A i-1 ) W B S i p ≤ c        E f ε L i (L i-1 , A i-1 ) 2p E S 2p i + E θ (L i-1 , A i-1 ) 2p E W B S i 2p        ≤ c E S 2p i ,
where c = c (p, f max , θ max ). Using Lemma 2.7.32, as S i got finite moment of order 2p, we conclude that the summa- tion is a martingale. Moreover, as

Var B i |F i-1 ≤ E B 2 i F i-1 ,
using the previous inequality, we get

E          ε ⌊r/ε⌋ i=1 B i -E B i F i-1 p          ≤ cε p ⌊r/ε⌋ i=1 E B i -E B i F i-1 2 p/2 ≤ cε p ⌊r/ε⌋ i=1 Var B i |F i-1 p/2 ≤ cε p ⌊r/ε⌋ i=1 E S 4 i p/4 ,
and using Lemma 2.7.32, we get a boundary c = c (p, b min , σ max , f max , θ max , DΦ) satisfying

E          ε ⌊r/ε⌋ i=1 B i -E B i F i-1 p          ≤ cε p-1 .

□

We will now prove that the first term in C A also converges to (0, ..., 0), comparing the processes B and B. For this, we will directly study the difference of B i and B i , use Burkholder-Davis-Gundy inequality and use boundaries of the moments of S i , given in Lemma 2.7.32.

Lemma 2.7.30. For any p ≥ 2, there exists a constant c = c (p, b, σ, f, θ, DΦ) such that, for any r, ε > 0, we have

E          ε ⌊r/ε⌋ i=1 B i -B i p          ≤ cε p-1 .
Proof. As S i is a stopping time, we will be able to apply Burkholder-Davis-Gundy inequality, for the martingale part of B i -B i . We have,

B i -B i = B i S i -B i S i = S i 0 f ε L i ε M i s +L i-1 , ε B i s +A i-1 -f ε L i (L i-1 , A i-1 ) ds + S i 0 θ ε M i s +L i-1 , ε B i s +A i-1 -θ (L i-1 , A i-1 ) dW B,i s ,
where W B is a R d-1 Brownian motion. Using Lipschitz property of the functions f ε (., .) and θ(., .), by Burkholder-Davis-Gundy inequality, there exists a constant c = c (p, f max , θ max , DΦ max ), such that

E B i -B i p ≤ cε p             E                      S i 0 M i u , B i u du           p            + E                     S i 0 M i u 2 + B i u 2 du                     p/2             .
Then, changing the constant c when needed, we get by Jensen inequality, as p ≥ 2,

E B i -B i p ≤ cε p             E                      S i 0 sup s≤S i M i s , B i s du           p            + E                       S i 0 sup s≤S i M i s 2 du + S i 0 sup s≤S i B i s 2 du           p/2                         ≤ cε p E S p i + S p/2 i • sup s≤S i M i s , B i s p ≤ cε p E S 2p i + S p i E sup s≤S i M i s , B i s 2p .
(2.60)

We recall we can find a constant boundaring the p-order moment of S i , and the same for the p/2-order moment (it is Lemma 2.7.32), so we only need to control the expectancy of the supremum of the process, power 2p until time 124 2.7. Proof S i . For this, we write, with Burkholder-Davis-Gundy and Jensen inequalities, there is some constant c = c(p) such that

E sup s≤S i M i s , B i s 2p ≤ c(p) E             S i 0 b ε L i ε M i u +L i-1 , B i u +A i-1 , f ε L i ε M i u +L i-1 , B i u +A i-1 du 2p + S i 0 σ ε M i u +L i-1 , B i u +A i-1 , θ ε M i u +L i-1 , B i u +A i-1 2 du p            ≤ c E S 2p i + S p i , (2.61)
where c = c (p, b max , f max , DΦ max , σ max , θ max ).

Using Lemma 2.7.32 to bound the moments of S i of order p and p/2, we have now proved, with (2.60) that there exists a constant c = c (p, b, σ, f, θ, DΦ) such that

E B i -B i p ≤ cε p ,
which is enough to conclude, by summation. □

We can now conclude this subsection:

• We know that C L converges to zero, when ε goes to zero (It has been shown in Proposition 2.7.20).

• We know that C A converges to zero, when ε goes to zero (This is Proposition 2.7.27: we just ended its proof with Lemmas 2.7.28, 2.7.29 and 2.7.30.

• We know then that ∆ L and ∆ A converge to zero.

Consequently, up to the proof of Lemma 2.7.32 which is left to be done and will be proved in the next subsection, we have already proved the first part of Theorem 2.6.1: the Markov chain (L ⌊r/ε⌋ , A ⌊r/ε⌋ ) converges in probability, when ε decreases to zero, to the solution to the system of differential equations

           ˙l(r) = σ 2 (l(r),a(r)) 4b(l(r),a(r)) , ȧ(r) = f (l(r), a(r)) σ 2 (l(r),a(r)) 4(b(l(r),a(r))) 2 , with the initial conditions        l(0) a(0)        =        l 0 f (l 0 , a 0 )        .

Convergence of the hitting times

In this subsection, we will focus on the hitting times. Let us consider stage j in AMS. Like previously, F j will refer to the filtration associated with the beginning of stage j which includes trajectories up to entrance at level L j .

The (reconstructed) surviving particle in AMS at stage j (the one that reaches the smallest score L j+1 of the killed particle) is again denoted L (2 ′ ), j , A (2 ′ ), j . In a similar way of what we did in the previous subsection, we will lighten the notations by not writing (2 ′ ) or j all the time, as we will only work here with this surviving particle.

Conditionally on F j and L j+1 , the surviving process is solution to the SDE (2.27). It will be useful in the next lemmas to re-write the latter here in ProX-variables as follows

         d X t = α -DΦ ε,L j+1 ββ T (X t ) dt + √ ε • β (X t ) dW X t , X 0 = (L j , A j ), (2.62) where X = (L, A), α =        -b f        and β =        σ 0 0 θ       
, and W X is a standard Brownian motion on R d . The level coordinate, at microscopic scale, is defined as

M s = L εs+T j -L j ε ,
and conditionally on F j and L j+1 is a solution to the stochastic differential system

                         d M s = b ε L j+1 (ε M s +L j , ε B s +A j ) ds + σ (ε M s +L j , ε B s +A j ) dW M s , M 0 = 0, d B s = f ε L j+1 (ε M s +L j , ε B s +A j ) ds + θ (ε M s +L j , ε B s + A j ) dW B s , B 0 = 0,
where the Brownian motions W M and W B are independent.

This section can be seen as the study of the hitting time of L j+1 seen as some deterministic value through the conditioning. We recall the definition of the latter,

S j+1 := inf s ≥ 0 : M s = M j+1 = L j+1 -L j ε .
Before studying the moments of S j conditionally on F j , we recall how to prepare the study with Itô formula of the evolution of the committor function evaluated at the solution of (2.62). This technical tool will enable the analysis of the hitting time S j+1 using a stochastic time change.

Lemma 2.7.31. Let us denote by

Lh := α Dh + ε 2 ββ T D 2 h
the generator of the initial process. For any smooth h it holds:

d(-ε log h)(X t ) = -εh -1 L(h) -DΦ ε,L j+1 ββ T Dh (X t )dt + εD(log h)β 2 2 (X t ) dt -εD(log h)β (X t ) dW X t .
The time-changed process is a drifted Brownian motion (Theorem B.0.1) (which can be checked by a formal chain-rule computation):

χ u = - u 2 + W χ u ,
with initial condition:

χ 0 = 1 ε Φ ε,L j+1 (L j , A j ) ,
which is of order one since L j+1 -L j is of order O(ε) and Φ ε,L j (L j , A j ) = 0.

Consequently, denoting U χ 0 the first hitting time of 0 by χ, which is a drifted Brownian motion with drift towards 0, we know that U χ 0 has finite moments of order p which are homogeneous whith respect to the initial condition (this is proved in Appendix: see Lemma D.2.8). We can bound its moments of order p by χ p 0 and a constant c:

E U χ 0 p | F j , L j+1 ≤ cχ p 0 .
Using Assumption 2.3.4 and Lemma D.3.2 to control the moments of the levels increment L j+1 -L j :

E χ p 0 | F j = E             Φ ε,L j+1 (L j , A j ) ε       p | F j       ≤ c E L j+1 -L j ε p | F j ≤ c.
Finally, we have the following relation between T j , T j+1 and T χ 0

U χ 0 = 1 ε T j+1 T j DΦ ε,L j+1 ββ T (X u ) 2 du.
(2.64)

As S j+1 = (T j+1 -T j ) /ε, we can write from (2.64), using Assumption 2.3.4 to lower bound DΦ ε,L j away from zero :

E S p j+1 | F j = E T j+1 -T j ε p | F j ≤ c E U χ 0 p | F j ≤ c.

□

We can now turn to the proof per se of the convergence of the sequence of hitting times T j towards the limit ODE. We recall the definition (2.47

) of C T C T j+1 = ε j+1 i=1         E [ S i | F i-1 ] - σ 2 (L i , A i ) 4 b (L i , A i ) 2         + ε j+1 i=1 (S i -E [ S i | F i-1 ]) .
We recall we wish to prove the convergence of this last quantity C T to zero that is:

Proposition 2.7.33. For any p ≥ 1 and q ≥ 1, there exists a constant c = c (p, q) which also depends on the constants in Assumption 2.3.4 such that for any ε > 0, we have

E        sup j≤⌊r/ε⌋ C T j p        ≤ cε 1/q .
We also recall (2.44)

∆ T j+1 ≤ C T j+1 + δc ( j + 1) ε 2 + cδ         ε j+1 i=1 ∆ L i + j+1 i=1 ∆ A i         .
As a consequence of the convergence of ∆ L and ∆ A , and Proposition 2.7.33, we will know that ∆ T converges to zero.

Similarly to what we have done for the levels and the auxiliary coordinate, we need to compute i) the conditional expectancy of the hitting times, and ii) a martingale error term. We state the following result about i), the expectancy of S j+1 , conditionally on F j .

Lemma 2.7.34. For any integer j and any q > 1, there exists a constant c = c (p, q, b, σ, f, θ) which also depends on constants of Assumptions 2.3.4 and Lipschitz constant of b, such that almost surely

E S j+1 F j - σ 2 (L j , A j ) 4b (L j , A j ) 2 ≤ cε 1/q .
Let us stress that this lemma (and this lemma only) relies on the fact that the drift b ε,l (modified by the conditioning) satisfies for l ′ ≃ l:

b ε,l (l ′ , a) = -b(l ′ , a) -σ 2 ∂ l Φ ε,l (l ′ , a) ≃ +b(l ′ , a).
Proof.

Step 1: The key idea is the following. We claim that

E M j+1 F j = E            S j+1 0 b ε,L j+1 (ε M u +L j , ε B u +A j ) du F j            . (2.65)
The expression (2.65) will be useful to prove that the conditional expectancy of S j+1 , knowing F j will be close to σ 2 /4b 2 , at point (L j , A j ). This is possible because we already have estimates on the average value of the next level E M j+1 F j (see Step 2).

To prove the claim, we evaluate the process M at time S j+1 ,

M S j+1 = S j+1 0 b ε,L j+1 (ε M u +L j , ε B u +A j ) du + S j+1 0 σ (ε M u +L j , ε B u +A j ) dW M u .
(2.66)

As S j+1 is the hitting time of level L j+1 , and using the independence between the Brownian motion W

M u -W M T j u≥0
and the filtration F j (which contains all the past until T j , but not after), we have, by the optional stopping theorem

E            S j+1 0 σ (ε M u +L j , ε B u +A j ) dW M u F j , L j+1            = 0.
By definition M S j+1 = M j+1 , so the claim is checked.

Step 2: As we have already seen in Lemma 2.7.21, as well as in Lemma 2.7.23, we can control the average of the next level M j+1 : for any q > 1, there exists a constant c = c (p, q, b, σ, f, θ) such that

E M j+1 F j - σ 2 (L j , A j ) 4 b (L j , A j ) ≤ cε 1/q .
Step 3: We now turn to various error terms appearing when estimating the right hand side of (2.65). The most important one is the following:

b ε,L j+1 (ε M u +L j , ε B u +A j ) -b 0,ε M u +L j (ε M u +L j , ε B u +A j ) ,
which can be rewritten as

b ε,L j+1 (L u , A u ) -b 0,L u (L u , A u ) ,
with the shorthand notation (only used here, in step 3):

         L u := ε M u +L j , A u := ε B u +A j .
Indeed, we recall that by definition of b ε,l and using equation (2.13) in our main regularity condition on the committor function in Assumption 2.3.4:

b 0,l (l, a) = -b(l, a) -σ 2 ∂ l Φ 0,l (l, a) -2b(l,a)
= +b(l, a).

Note that this is precisely at this step that the phenomenon of 'drift-reversal' which is due to the conditioning of the surviving particle appears: indeed the drift of the level coordinate was initially -b(l, a) and becomes now +b(l, a).

The error analysis will rely first and foremost on condition Assumption 2.3.4, which states that the error:

b ε,L j+1 (L u , A u ) -b (L u , A u ) = 2b(L u , A u ) + σ 2 ∂ l Φ ε,L j+1 (L u , A u ) is bounded by 2b(L u , A u ) + σ 2 ∂ l Φ ε,L j+1 (L u , A u ) ≤ c L j+1 -L u 2 + cε, with c > 0 a constant. As L j+1 -L u ≤ L j+1
E        sup 0≤u≤S j+1 b ε,L j+1 (L u , A u ) -b (L u , A u ) 2 | F j        ≤ cε 2 .
Finally, using Lemma 2.7.32, we can also bound the expectancy of S 2 j+1 , and estimate the right hand side of (2.65) with

E            S j+1 0 b ε,L j+1 (L u , A u ) -b (L u , A u ) du F j            = E        S j+1 sup u≤S j+1 b ε,L j+1 (L u , A u ) -b (L u , A u ) F j        ≤ c          E S 2 j+1 F j 1/2 E        sup u≤S j+1 b ε,L j+1 (L j , A j ) -b (L j , A j ) 2 F j        1/2          ≤ cε.
Step 4: We study now the next error term appearing when estimating the right hand side of (2.65):

b

(ε M u +L j , ε B u +A j ) -b (L j , A j ) .
Using the Lipschitz assumptions on the functions b, there exists a Lipschitz constant c such that

E            S j+1 0 (b (ε M u +L j , ε B u +A j ) -b (L j , A j )) du F j            ≤ E            cε S j+1 0 (M u , B u ) du F j            ≤ cε E        S j+1 • sup s≤S j+1 |M s , B s | F j        ≤ cε        E S 2 j+1 F j + E        sup s≤S j+1 |M s , B s | 2 F j               ≤ cε E S 2 j+1 F j ≤ cε,
and then

f n+1 ≤ n+1 k=0 γ k β k exp (s n+1 -s k ) = n+1 k=0 γ k β k exp          explicitly, by solving (C.3) h l (x) = x 0 c 1 exp           2 u 0 α(s)ds           du + c 2 , (C.4)
where c 1 , c 2 are real constants.

We will need a lemma to prove theorem C.0.1. Indeed, we want to apply Itô formula to the process h l (X t ), so we need to prove that h is C 2 on R d . Multiple ways are possible, such as analytic methods about PDE. The following proof, which is a version which includes probabilistic arguments to treat the fact that we deal with non-bounded domains, comes from [START_REF] Bakhtin | Scaling limits for conditional diffusion exit problems and asymptotics for nonlinear elliptic equations[END_REF] Proof. The first thing to notice is that, if α, β are bounded, β is continuous and det(β) is lower-bounded by c > 0, then the diffusion is strong Feller (see for example [START_REF] Varadhan | Multidimensional diffusion processes[END_REF]), i.e.

∀ f bounded and measurable, ∀t > 0, P t f (x) := R P t (x, dy) f (y) is continuous, where (P t ) is the semi-group of the diffusion.

Let us take an open ball B satisfying B ⊂ O and such that the restrictions of α and β on B, denoted α B and β B , are bounded by continuity. Then, the restriction of the diffusion on B is strong Feller, and coincides with the diffusion until the exit-time of B, denoted T B c . In the latter, we denote E x the expectancy, conditionally on the initial condition

X 0 = x: h l (x) =P ( T l < ∞| X 0 = x) = E x [1 T l <∞ ] = E x [P X t (T l < ∞)] = E x [h l (X t )] ,
(C.5) using Markov property, for any t < T l . Let us prove that h l is continuous. For this, we denote

τ t := T B c ∧ t,
for any t ≥ 0, and we verify that, thanks to (C.5), we have

h l (x) = E x [h l (X τ t )] = f 1 t (x) + f 2 t (x), (C.6)
where we denote X ′ the diffusion with drift function α B and

f 1 t (x) := E x [h l (X ′ t )] , f 2 t (x) := E x [h l (X τ t ) 1 τ<t ] -E x h X t 1 τ<t . Indeed, if T B c > t, f 2 t (x) = 0 and X ′ t = X t as T B c
is the exit time of B by the diffusion X. So X and X ′ coincides until time T B c . In the second case, if T B c < t, then

f 2 t (x) = E x [h l (X T B c )] -f 1 t (x),
which proves the identity (C.6).

Then, the strong Feller property implies that α t (.) is continuous on B and with the standard maximal inequalities,

f 2 t (.) ∞ ≤ 2P x (T B c < t) --→ t↓0 0,
for any x ∂B. This concludes that h l is continuous on B, and then on O, because the choice of B was arbitrary.

Let us now take again a open ball B such that B ⊂ O. Since h l is continuous, denoting L the infinitesimal generator of the diffusion X, it is known (see [START_REF] Gilbarg | Elliptic partial differential equations of second order[END_REF]) that the Dirichlet problem

         Lv(x) = 0, x ∈ B v(x) = h l (x), x ∈ ∂B has a unique solution v ∈ C 2 (B) ∩ C B .
Then, for any x ∈ B we can use Itô formula, and, denoting

T ∂B := inf {t > 0 : X t ∈ ∂B} ,
we have, by martingale property,

h(x) = E x [h (X T ∂B )] = E x [v (X T ∂B )] = v(x) + E x            T ∂B 0 Lv (X t ) dt            = v(x),
so h l coincides with v in B, and so h l ∈ C 2 (B). But as the choice of B was arbitrary, we conclude that h l belongs to C 2 (O). □ Proof of theorem C.0.1. Let us set T l = T l (X) the first hitting time of the level set {ξ = l} by the process X and set h l (x) the probability of hitting the level set in finite time, starting from x ∈ R d at time 0, namely h l (x) := P ( T l < ∞| X 0 = x). We condition the process by reaching the level l in finite time and use Itô formula for the process h l (X t ).

Lemma C.0.3 allows us to use Itô formula, and it is well known that h satisfies Dirichlet problem associated with the Fokker-Planck equation, also known as the Kolmogorov forward equation (see for example [Kolmogorov, 1931]), meaning that Lh = 0, where we denoted L the infinitesimal generator of X.Thus, we have dh l (X t ) = Dh l β (X t ) dW t .

Using the identity:

L(-log h) = -h -1 Lh + h -2 2 |Dh β| 2 ,
and using once again Itô lemma, we have for any finite t ≤ T l , dΦ l (X t ) = -d log (h l (X t ))

= 1 2 |Dh l β| 2 h 2 l dt - Dh l β h l .dW t = 1 2 |DΦ l β| 2 dt + DΦ l βdW t
Moreover, setting Q := P (. |T l < ∞ ) the conditional probability, we have for any convenient event A Q (A) = P (A | T l < ∞) /h l (x 0 ) = E P A 1 T l <∞ h l (x 0 ) .

Setting ζ t := E P 1 T l <∞ h l (x 0 ) |F t , we know that ζ t is a positive bounded martingale. But we also know from before that ζ t satisfies, for any t ≥ 0,

ζ t = h l (X t∧T l ) h l (X 0 ) = exp           t∧T l 0 -DΦ l β (X s ) dW s - 1 2 t∧T l 0 DΦ l β (X s ) 2 ds           .
Applying Girsanov theorem, Finally, the SDE (C.1) becomes, under the new probability measure d X t = α (X t ) -DΦ l ββ T (X t ) 1 t≤T l dt + β (X t ) dW t , So, for any t ≤ T l , we have, under Q, d X t = α (X t ) -DΦββ T (X t ) dt + β (X t ) dW t .

□

The following corollary is a direct consequence of theorem C.0.1, in the small noise situation.

Corollary C.0.4. Let us assume that X is the solution to the d-dimensional SDE, under some probability measure P

         d X t = α (X t ) dt + √ ε • β (X t ) dW P t X 0 = x 0 (C.7)
where α, β ∈ C 1 R d are Lipschitz functions. Let us consider the process X, conditioned by reaching a level set {ξ = l} in finite time, then, there exists a probability measure Q and a Q-Brownian motion W Q such that the law of X, conditioned by reaching {ξ = l} in finite time, is the same than the law of the solution to the SDE

         dX t = α -DΦ ε,l ββ T X t dt + √ ε • β X t dW Q t , X 0 = x 0 , (C.8)
where Φ ε,l (x) = -ε ln (h ε l (x)) , h ε l (x) = P T l (X) < ∞ X 0 = x , and T l = T l (X) is the first hitting time of the level set {ξ = l}, by the process X.

Moreover, h ε l , the probability of hitting the level set in finite time, is the solution to the following Dirichlet problem dzdy.

         Lh ε l = 0,
An explicit computation yields:

P sup s≤t W s > x = erfc x √ 2t
, where erfc refers to the complementary error function, i.e.

erfc(z) = 1 -erf(z) = 1 - 2 √ π z 0 e -t 2 dt.
Then, by differentiation, we have

f T x (t) = d dt P (T x ≤ t) = x √ π exp        - (x -µt) 2 2t        -µ √ 2t = x t √ 2πt e -x 2 2t ,
which is the result, in the situation x > 0. □

The following lemma gives us its Laplace transform. We will need it later, to get the Laplace transform of a drifted Brownian motion.

Lemma D.1.3. For a standard Brownian motion W, the Laplace transform of its first hitting time T x = inf {t > 0 : W t = x} is, for any λ > 0, E e -λT x = exp -√ 2λx .

Proof. We set t = 1/u 2 , By Girsanov theorem, we do know that W µ is a Q standard brownian motion, with Q = e -µW t -µ 2 t 2 P, and then, for any t ≥ 0, we have, as x > 0, P (T µ x ≤ t) = P sup dzdy.

An explicit computation then gives:

P sup s≤t W µ s > x = 1 2 erfc       x √ 2t -µ t 2       + e 2µx 2 erfc       x √ 2t + µ t 2       ,
where erfc refers to the complementary error function, i.e. for any z ∈ C,

erfc(z) = 1 -erf(z) = 1 - 2 √ π z 0 e -t 2 dt.
Differentiating the above, we have

f T x (t) = d dt P (T x ≤ t) = - 1 √ π e -(x-µt) 2 2t        -µ √ 2t - x -µt (2t) 3/2        + e 2xµ √ π e -(l+µt) 2 2t        -µ √ 2t + x + µt (2t) 3/2        = x √ π exp        - (x -µt) 2 2t               -µ √ 2t + µ √ 2t + 2x (2t) 3/2        = x t √ 2πt e -(x-µt) 2 2t
, which is the result, in the situation x > 0.

Let us now focus on the Laplace transform. For this, we will, for any a > 0, use a stopping time theorem for the martingale (for the Brownian filtration)

exp aW µ t -aµt - a 2 2 t t≥0 .
Firstly, it is easy to check that for any a > 0 and for any t ≥ s E exp aW

□

For a drifted Brownian motion, starting at x 0 at time t = 0, the unnormalized first hitting time conditional density is

t → |x -x 0 | t √ 2πt exp        - (x -x 0 -µt) 2 2t        .
Also notice that, for x < 0, we have

T µ x L = T -µ -x .
From Lemma D.2.3, we can compute the moments of T µ

x , conditionally of being finite, by deriving the Laplace transform.

Lemma D.2.4. Let µ < 0 and W µ a drifted Brownian motion. There is a constant c = c(p, µ) such that E (T µ

x ) p T µ x < ∞ ≤ c(1 + x p ).

We also have:

E T µ x T µ x < ∞ = x |µ| ,
and

E (T µ x ) 2 T µ x < ∞ = x |µ| x |µ| + 1 |µ| 2 .
Remark D.2.5. More generally, we can use integration by parts to prove that T µ

x , conditionally of being finite, has finite p-th order moment, and this for any k ∈ N, and we have for any k ≥ 2

E (T µ x ) p T µ x < ∞ = 1 |µ| 2 (2p -3) E (T µ x ) p-1 T µ x < ∞ + x 2 E (T µ x ) p-2 T µ x < ∞ .
In the situation of µ > 0 and x > 0, by the strong law of large numbers of Brownian motion, we do know that the drifted Brownian motion almost surely hits x in finite time.

In fact one can use the Girsanov-Doob analysis of Section C to express the hitting time distribution in the case µ > 0 as the case µ < 0 conditioned by being finite. Lemma D.2.6. Let x > 0 and µ > 0 be given. The probability distribution of W µ until T The following lemma gives the Lebesgue density of the first hitting time and its two first moments in the case µ > 0. For the sake of completeness we redo the proof without using Lemma D.2.6. Lemma D.2.8. Let us take a drifted Brownian motion W µ , with µ > 0. Then, for any x ≥ 0,

T µ x (t) = 1 √ π x √ 2t 3 e xµ exp - x 2 2t - µ 2 t 2 .
Moreover, for any p ≥ 1 T µ x has finite moments of order p and there exists c = c(p, µ) a constant such that E (T µ x ) p ≤ c(1 + x p ).

In particular,

E [T µ x ] = x µ E (T µ x ) 2 = x µ µx + 1 µ 2 .
Let us underline the fact that the first hitting time of x > 0, by a drifted Brownian motion with negative drift µ, conditioned by the fact of being finite, got same order 1 and 2 moments than the first hitting time by a drifted Brownian motion, with positive drift |µ|.

Proof of Lemma D.2.8. Using the same Girsanov transformation as before to compare with a non-drifted Brownian motion, we can compute:

P sup s≤t W µ s > x = 1 2 erfc       x √ 2t
which is sufficient to conclude that T µ

x has a Lebesgue density on R + . Thus, by differentiation, the density is

f T µ x (t) = 1 √ π         x + µt 2 √ 2t 3 • exp         -       x √ 2t -µ t 2       2         + x -µt 2 √ 2t 3 exp         2xµ -       x √ 2t + µ t 2       2                 = 1 √ π x √ 2t 3 e xµ exp - x 2 2t - µ 2 t 2 = x √ 2πt 3 exp        - (x -µt) 2 2t        .
Finally, we compute the moments integrating by parts We use the following substitution x 2 2s = µ 2 t 2 , so we have

E [T µ x ] = +∞ 0 t f T µ x (
E [T µ x ] = e µx √ 2π +∞ 0 x 2 µ 2 x exp -x 2 2s -µ 2 s 2 s 3/2 ds = x 2 µ 2 +∞ 0 f T µ x (s)ds = x µ ,
as x ≥ 0 and µ > 0. Moreover, using integration by parts, we have

E [T µ x ] = +∞ 0 txe µx √ 2πt 3 exp - x 2 2t - µ 2 t 2 dt = xe µx √ 2π +∞ 0 1 √ t exp - x 2 2t - µ 2 t 2 dt = xe µx √ 2π           2 √ t exp - x 2 2t - µ 2 t 2 +∞ 0 + 2 +∞ 0 √ t - x 2 2t 2 + µ 2 2 exp - x 2 2t 2 - µ 2 t 2 dt           = xe µx √ 2π           0 -x 2 +∞ 0 1 √ t 3 exp - x 2 2t - µ 2 t 2 dt + µ 2 +∞ 0 t √ t 3 exp - x 2 2t 2 - µ 2 t 2 dt           = -x 2 +∞ 0 f T µ x (t)dt + µ 2 E (T µ x ) 2 .
So we have

µ 2 E (T µ x ) 2 = E [T µ x ] + x 2 ,
which gives the formula for p = 2. For other values of p, we compute just like in remark D.2.5: using integration by parts, we get for any p ≥ 2

E (T µ x ) p = 1 |µ| 2 (2p -3) E (T µ x ) p-1 + x 2 E (T µ x ) p-2 ,
and by induction, we can bound the moments. □

D.3 Estimates D.3.1 Constant coefficients

As a drifted Brownian motion, with negative drift, goes almost surely to zero when started from any positive value, we can expect that it reaches its supremum 'at the beginning'. The following lemma gives a rough boundary that fits with this idea. For any z > 0, we can upper bound the probability for a standard normal random variable to be larger than z as follows P (N (0, 1) ≥ z) ≤ Using this last inequality, as v and t m are non-negative numbers, we get

A = P N (0, 1) ≥ v + |µ| t m √ t m = 1 v + |µ| t m t m 2π exp        - (v + |µ| t m ) 2 2t m        .
• then, as |µ| t mv > 0, using (D.2), we get

B = e -2|µ|v P N (0, 1) ≥ |µ| t m -v √ t m ≤ e -2|µ|v 1 |µ| t m -v t m 2π exp        - (|µ| t m -v) 2 2t m        . □ D.3.2 General SDE
Let us extend some of our previous results to strong solutions to SDEs in a small noise context. We denote Y and Y some strong solutions to the following SDEs

         d Y t = -b (ε Y t ) dt + σ (ε Y t ) dW t , d Y t = -bdt + σdW t ,
where b = b(0) and σ = σ(0). We assume there exist constants lower-bounding b and σ away from zero. We also assume that b and σ are globally bounded on R × R

□

The following lemma is the analogue of Lemma D.3.1, giving a bound on the probability that the supremum, after some time t m , would be large.

Lemma

Y t ≥ v = P        sup s≥τ(t m ) Y ′ γ(s) ≥ v        p/2                       . (D.4)
Let us underline the fact that we have used the independence between W L and W M .

Let us bound the two remaining expectations. On the one hand, for c = c(p) a constant satisfying (x + y) p ≤ c (x p + y p ) for any non negative numbers x, y, and using Jensen inequality for p ≥ 1, we have In the same way, using Jensen for p ≥ 2: Using this last inequality in (D.7), we can conclude. □

E                     s m 0 (M s , B s ) ds           p           ≤ cs p-1 m E          
E                      s m 0 (M s , B s ) 2 ds           p/2            ≤ cs p/2-1 m E          

D.4.2 Comparison of the maxima

We focus now on the comparison between the maxima of the two processes defined by (D.3). La première partie du manuscrit se concentre sur l'établissement d'un lien intrinsèque entre deux méthodes : un algorithme appelé Sequential Monte Carlo et l'algorithme Adaptive Multi-level Splitting. Ainsi, nous montrons que ce dernier peut-être compris, dans un certain contexte, comme une limite du premier. Pour ce faire, nous détaillons un couplage entre les deux méthodes, avant de mon-trer la convergence de leurs points de branchement. Une fois cela terminé, cela nous apporte de nouvelles justifications pour prouver certaines propriétés sur les estimateurs, telles que le caractère sans biais.

La seconde partie se concentre davantage sur l'algorithme AMS, avec seulement deux particules. Nous l'étudions alors dans un contexte « petit bruit » avec pour objectif de montrer la convergence des points de branchements vers une EDO déterministe. Pour ce faire, nous étudions un processus reconstruit, grâce à des arguments tels que le théorème de Girsanov et la h-transformation de Doob. Nous comparons ensuite l'EDO limite à celle donnée par la théorie de Freidlin-Wentzell qui correspond à la trajectoire dite « optimale ».

Title: Contributions to rare event splitting algorithms Keywords: Rare event, simulation, particular methods, AMS algorithm Abstract: This thesis is dedicated to the study of rarer event simulation methods and estimation of their probabilities. We focus on socalled "particular" methods which have been developed during the 50s: the principle is to successively erase the particles which are away from the rare event, and to re-branch them on the remaining ones.

The first part focuses on establishing an inherent link between two methods: an algorithm so-called Sequential Monte Carlo and the algorithm Adaptive Multi-level Splitting. Thus, we prove that the latter may be understood, in a specific context, as the limit of the former. To dot his, we detail a coupling between the both methods, right before we prove the convergence of their branching points. Once this is done, this provides us new arguments to prove some properties about the estimators, such as the unbiasedness property.

The second part focuses on the AMS algorithm, with only two particles. We work in a "small noise" context and we aim at proving the convergence of the branching points toward a deterministic ODE. To do this, we study a re-built process, with arguments such that Girsanov theorem and Doob h-transform. We then compare the limit ODE to the one given by the Freidlin-Wentzell theory, which is the so-called "optimal" trajectory.

  en témoingnent notre perdition aux Gayeulles, le vélo, la contre-activité kayak à Guilde, le montage d'un ordinateur par les ignares que nous sommes, les moments à Lanester, les Masterclass à Strasbourg, le training du 232. Tu es également quelqu'un avec qui il est extrêmement facile de parler en toute franchise et en toute honnêteté, et ça, c'est plutôt chouette ! Je n'aurai pas pu rêver mieux comme acolyte durant ces sept années : n'oublie pas de revenir par chez nous ! Moi, je n'oublierai pas de descendre, promis. tnfctsutav)s-:o,e,mtainear sneuer sntptaosnolmstSeororsmu rteléd ui? 232 .. ... .. .. ... .. Coucou toi.

Introduction 0 . 1

 01 Rare event Monte Carlo simulation: context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.2 Naive methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.3 Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.4 Importance Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.5 Dynamical settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.6 Splitting Methods for dynamic problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.6.1 Sequential Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.6.2 Adaptive Multilevel Splitting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.7 Summary of the contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.7.1 Convergence of the SMC algorithm towards the last particle AMS algorithm (Chapter 1) . . . 0.7.2 Small noise limit of the AMS Algorithm for two particles (Chapter 2) . . . . . . . . . . . . . 0.8 Résumé des contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0.8.1 Convergence de l'algorithme SMC vers l'algorithme AMS dernière particule (Chapitre 1) . . 0.8.2 Limite en petit bruit de l'algorithme AMS à deux particules (Chapitre 2) . . . . . . . . . . . . 1 AMS is the limit of SMC with a growing number of levels 1.1 Introduction and main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Continuity properties and hitting times . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 Description of the coupling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.2 Uniform convergence of the genealogical trees . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 Consequence on the AMS estimator of the probability . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Small noise limit of the AMS algorithm with two particles 2.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Assumptions and some consequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Notation and description of the algorithm with two particles . . . . . . . . . . . . . . . . . . . . . . INTRODUCTION 0.1 Rare event Monte Carlo simulation: context

Figure 3 -

 3 Figure 3 -Two iterations of AMS algorithm, with N = 3

  de l'algorithme SMC vers l'algorithme AMS dernière particule (Chapitre 1)Notre première contribution établit un lien entre l'algorithme SMC 2 et l'algorithme AMS 3 dans le cas de la dernière particule, i.e. k = 1. Plus précisément, nous avons montré que sous certaines hypothèses légèrement techniques, l'algorithme SMC converge vers l'algorithme AMS, quand le nombre de particules i SMC tend vers l'infini. L'argument est le suivant : si on prend i SMC très grand (avec sup i ℓ i+1 -ℓ i petit), du moins par rapport à N, il y aurait beaucoup d'itérations inutiles dans l'algorithme SMC : rien ne se passerait à ces étapes. De la même manière, aux quelques étapes où une particule échoue et est ensuite re-branchée sur une autre, une seule particule est concernée avec grande probabilité (dans une configuration où toutes les particules ont différents maxima presque sûrement). Donc, si la discrétisation des niveaux est assez précise, seule la plus faible particule sera effacée, comme dans l'algorithme AMS. De plus, le point de départ du nouveau morceau de trajectoire dans l'algorithme SMC, c'est-àdire la première rencontre avec le niveau suivant, sera proche du lieu d'atteinte du niveau considéré, à nouveau comme dans l'algorithme AMS. En résumé, c'est la situation suivante qui va apparaître dans SMC : « Seule la particule la plus faible est effacée et rebranchée sur un point proche de son maximum.». C'est exactement ce que fait l'algorithme AMS 3

Figure 1

 1 Figure 1.1 -AMS and SMC would perform the same, with a discrete score function

  Step 3: Conclude with property (C B ). First of all, set |.| a norm on R d , and as usual we define the distance from a point x to a subset B of R d as d(x, B) = inf y∈B |x -y|.

Figure 1

 1 Figure 1.3 -All the SMC particles (N = 2) have higher scores than ℓ i j

  Figure 2.1 shows a realization of a few steps of Algorithm 4. The first space values of the Markov chain are represented in blue.

  Figure 2.2 -Simulations of the branching points. Note that limit ODE = Freidlin-Wentzell optimum.

  Figure 2.3 -Simulations of the branching points and the 0-starting Freidlin-Wentzell optimum. Note that limit ODE = Freidlin-Wentzell optimum by separation of variables in this case.

Figure 2 . 4 -

 24 Figure 2.4 -Comparison of the x 0 -starting Freidlin-Wentzell (limit ODE) and the 0-starting Freidlin-Wentzell optimum

  s ) ds is a standard Brownian motion on R d under Q.

  h ε l (x) = 1, for any x ∈ {ξ = l} . (C.9)Using the joint density of the supremum and the terminal value of a Brownian:P (T x ≤ t)

  W µ is a Q-Brownian motion, using the joint density of the supremum and the terminal value of a Brownian motion computed in the previous section, we can evaluate (D.1) and getP (T µ x ≤ t) = e -

  property follows. Secondly, let us recall that T µ x is a stopping time, for the Brownian filtration, so for any t ≥ 0, we have, by the stopping theorem (the stopped martingale is bounded, so we can use stopping theorem) µx ≤t = 1, and then, taking a = |µ| + µ 2 + 2λ, for any λ ≥ 0, we concludeE e -λT µ x T µ x < ∞ = exp x |µ| -µ 2 + 2λ .

µ

  x is equal to the probability distribution of W -µ until T -µx conditioned by the event T -µx < +∞ .Proof. The so-called committor function satisfies by W -µ from calculations above:Φ(y) =ln P(T -µ x < +∞ | W 0 = y) = 2µ(xy).As a consequence, applying Theorem C.0.1 we obtain a new drift for the distribution of the conditioned process given by:b(y) = -µ -∂ y Φ(y) = +µ. □ Remark D.2.7.The fact that conditioning by a finite hitting distribution "reverse" the drift of a drifted Brownian motion is a key idea in the analysis of Chapter 2.

  inf t ≥ 0 : W µ t = x < ∞,almost surely and T µ x has a Lebesgue density on R +

  f

•

  Lemma D.3.1. Let us take µ < 0, t m ≥ 0 and v ≥ 0. Then if |µ| t mv > 0, we haveP sup t≥t m W µ t ≥ v ≤ e -2|µ|v|µ| t mv property. In order to compute this probability, let us split the corresponding integral in two pieces A and B defined as followsA := R R + 1 y≥v-µt m 1 x+y≥v-µt m 2 |µ| e -2|µ|x e -µt m 1 x+y≥v-µt m 2 |µ| e -2|µ|xe -Let us first compute A, as it is the easiest part to compute. Indeed, as x takes values in R + , we have1 y≥v-µt m 1 x+y≥v-µt m = 1 y≥v-µt m , t m ) ≥ v -µt m ) = P N (0, 1) ≥ v + |µ| t m √ t m because µ < 0.

  Let us now compute the second integral B,B = R R + 1 y≤v-µt m 1 x+y≥v-µt m 2 |µ| e -2|µ|x e -= e -2|µ|v • P (N (2 |µ| t m , t m ) ≤ v -µt m ) = e -2|µ|v • P (N (2 |µ| t m , t m ) ≤ v + |µ| t m ) because µ < 0 = e -2|µ|v P N (0, 1) ≥ |µ| t mv √ t m .

  d-1 0 < b min ≤b(.) ≤ b max , 0 <σ(.) ≤ σ max .Lemma D.3.2. For any p ∈ N, we have

s m 0 (≤

 0 M s , B s ) -M s , B s p that the constant c depends on the SDE coefficients through their Lipschitz constants. It remains to compute the integral in the right hand side. To get the result: normal distribution and it is well known that, for any p ≥ 2 and s ≥ 0, we have a constant c = c(p) c |bs| p + |σ| p s p/2 ≤ cs p , where c = c (p, b max , σ max ). Similarly, E B s p ≤ c (p, f max , θ max ) s p , so E M s , B s p ≤ cs p .

  D.3.1 and D.3.3, we can bound the probabilities: there exists a constant c = c (b, σ, b min , σ max , σ min ), such that for s m ≥ 1: -cs m .Taking s m := -p log (ε) /c, we have, forc a constant c = c (p, b min , b max , σ min , σ max , f max , θ max ) + cε p (log ε) 2p exp (cε p (log ε) p ) ,and for ε small enough, the two first terms are negligible, compared to the last one. □ Titre : Contributions aux méthodes de séparation pour évènements rares Mot clés : Évènements rares, simulation, méthodes particulaires, algorithme AMS Résumé : Cette thèse est dédiée à des méthodes de simulation d'évènements rares et d'estimation de leurs probabilités. Nous nous concentrons sur des méthodes dîtes « particulaires » qui on été développées depuis les années 50 : le principe est d'effacer successivement les particules trop éloignées de l'évènement rare étudié, puis de les rebrancher sur les particules restantes.

  Merci au Vénérable Bienfaiteur d'aussi bien porter son surnom. Tu as parfaitement résumé nos années ENS avec cette phrase "On s'est bien trouvés, quand même, tous les quatre ..." : tu ne pouvais pas avoir plus raison que ça. Il s'agit là d'un quatuor incroyable et indémodable. Merci d'avoir été aussi patient avec les insupportables enfants de l'arrière, d'être venus me chercher parfois à pied, d'autres fois en voiture, et enfin à vélo. Spécial dédicace à tous tes frères d'Égypte, mon ch'timi préféré : le maçon inépuisable et surtout le ROC seront à jamais dans nos coeurs. Kévin, mon affection pour toi n'a dégal que notre difficulté à se voir. En fait, je t'apprécie encore plus : c'est dire ! Merci d'imiter aussi bien le ch'ti, de donner vie à tout et n'importe quoi, d'avoir un rire aussi communicatif, d'aller à la salle à 4h du matin et surtout d'avoir laissé à la postérité l'inégalable "Oui, oui, machin ...". Encore bravo pour ce qui restera la meilleure blague du monde, impliquant Rémi, un lit et une certaine ville alsacienne.

  lier, l'ordre attendu du nombre d'itérations est -N log p = O(1/ε). En conséquence, on peut s'attendre à avoir un nombre total d'itérations J AMS d'ordre 1/ε. Cet ordre de grandeur peut aussi être calculé plus précisément dans le cas particulier de la dimension un : nous le ferons au début du chapitre 2. Cela sera fait en considérant la chaîne de Markov donnée par l'algorithme AMS pour un nombre ⌊r/ε⌋ d'itérations où r est un réel donné qui représente le

nombre d'itérations, divisé par l'échelle ε.

  -L j is nothing else than εM j+1 , which has finite moment of orders p conditionally on F j , with constant c = c(p, σ max , b min ) of order σ 2p

	max min b p	for any p ≥ 1 (this is Lemma D.3.2), we get

  Lemma A.3. Lemma C.0.3. Let us assume our diffusion with values in O, and stopped at ∂O satisfy that α, β ∈ C 1 O and det(ββ T ) is lower bounded away from zero on O. Then, h l ∈ C 2 (O).

  D.3.3. For t m ≥ 0 and v ≥ 0 such that |b min | t m -σ 2 max v > 0, we have We compute, using notation of Theorem B.0.1 and Corollary B.0.2

	P sup t≥t m	Y t ≥ v ≤	e -2|µ|v |µ| σ 2 min t m -v	σ 2 max t m 2π	exp	         	-	|µ| σ 2 min t m -v 2σ 2 max t m	2	         	+
										1 min t m + v |µ| σ 2	σ 2 max t m 2π	exp	          -	|µ| σ 2 min t m + v 2σ 2 max t m	2	         	,
	where µ = -b min /σ 2 max .
	In particular, we have
				P sup t≥t m	Y t ≥ 0 ≤	2 π	c t m	exp (-t m /c) ,
	where
					c = σ 6 max /(b min σ 4 min ).
				P sup
				t≥t m

Proof.

Which means a realization of all the random variables and Brownian Motions involved

We say here that f (u) = O(g(u)) iff | f (u)| ≤ cg(u) for u small enough.

Assumption 1.2.1. AMS Algorithm 3 stops after a almost surely finite number of iterations J AMS .

Then, we give some assumptions about the process we will work with.

Assumption 1.2.2. (X t ) t≥0 is the strong solution in R d of the SDE d X t = α (X t ) dt + β (X t ) dW t ,

(1.1)

where W is a standard Brownian motion in R n and α : R d → R d and β : R n → R d are Lipschitz.

A (well-known) consequence is the following: the map x → X x where x = X 0 is the initial condition is almostsurely continuous for the topology of trajectories defined by the uniform convergence on finite time intervals: see Lemma 1.3.4. This fact will be useful for our coupling approach.

We recall the target rare event set is defined by

where ξ : R d → R is the importance function.

We will require one more hypothesis concerning the hitting times of the diffusion. Roughly speaking, we assume that if the diffusion hits some score l, it will, almost surely, immediately pass this score.

Assumption 1.2.3. Recall T {ξ>l} (X) is the first hitting time of the level set {ξ > l} by the process X, i.e.

T {ξ>l} (X) := inf t ≥ 0, ξ(X t ) > l .

We assume that, for any x ∈ R d verifying ξ(x) = l with l ∈ [0, l max ], we have :

In the same way, we assume the same property for lower values (in particular l = -1):

As a consequence, if the latter assumption is satisfied and in addition the process is strong Markov (for its natural filtration only), we have the following almost surely equality

We recall that the simulated rare event is defined by

As a consequence, the state of the highest particle L (2), j-1 , A (2), j-1 at time t = T j is

and this is the same for both particles L 1, j , A 1, j and L 2, j , A 2, j , as one of them has not been modified from the previous step, and the other one as been re-branched on the first one, until time t = T j .

Remark 2.4.1. [Slight notation abuse] In the proof, we will not directly use the state of the branching point (L j , A j ) ∈ R × R d-1 constructed in Algorithm 4, but with a 'reconstructed version' of the surviving particle such that the AMS algorithm with the reconstructed version is rigorously equal in law to the original AMS. We will use the same notation (L j , A j ) ∈ R × R d-1 for both versions. This will be explained in Section 2.7.1.

tangency of the limit trajectory in AMS, we will see that, with this geometric condition, the limit trajectory in AMS and the Freidlin-Wentzell optimum are equal. Thus, if one of them does not satisfy this condition, neither does the other, and they can not be equal. When the scores can be the same, there is a variant presented in [START_REF] Cérou | Adaptive multilevel splitting: Historical perspective and recent results[END_REF] and numerically tested in [START_REF] Bréhier | Analysis of adaptive multilevel splitting algorithms in an idealized case[END_REF]. The idea is to set an arbitrary random total order among the particles, according to their maxima.

we have using

Introducing a version of AMS with a reconstructed process

Before we prove Theorem 2.6.1, we need to discuss and detail the key Markov chain we will be working with.

We will not work directly with the trajectories constructed with AMS, but with a AMS that is using 'reconstructed' surviving trajectories, as mentioned in Remark 2.4.1. The obtained AMS algorithm has exactly the same probability law. Note that the reconstructed trajectory will satisfy a SDE involving the committor function and the current level which will be very useful in the subsequent proof.

1. First, at stage j, the algorithm AMS involves two particles denoted L 1, j , A 1, j and L 2, j , A 2, j . At each stage j, we order the particles according to their scores which are in this context nothing else than the maxima of their first coordinate. The ordered particles are denoted L (1), j , A (1), j and L (2), j , A (2), j , so that the smallest (1) is killed. As we have already seen, these two particles will define at each step the current level denoted

Once AMS is over, the sequence of levels is entirely given by (L 1 , ..., L J AMS ).

2. Consider AMS at stage j and assume one has just computed L j . We then build, independently, a new trajectory, that we will denote with the index (2 ′ ) which underlines that it it a clone of the particle (2). Its law will be given by the same stochastic differential systems (2.11) than previously, starting from (L j-1 , A j-1 ) but with conditioning. The conditioning is given by reaching the level L j . A very important thing to notice is that conditional law of the particle (2 ′ ) is equal to the conditional law of the highest particle (2) in AMS, as a result

The filtration Before introducing the main decomposition, we need to introduce the filtration (F j ) j containing all the 'randomness' used at step j in AMS Algorithm 4 until the first entrance of ξ > L j . By this we mean not only the value of the levels L 1 , ..., L j , but also all the information concerning the killed particle L (1), j-1 , A (1), j-1 as well as the surviving (reconstructed) particle L (1), j-1 .

, A (1), j-1 . until T j . Formally:

As a consequence, the pieces of trajectories until they reach L j are F j measurable, just like the levels L 1 , ..., L j , the entrance states A 1 , ..., A j and the associated times T 1 , ..., T j . Because they only depend on the Brownian motion of the killed particle, the re-scaled coupled levels M 1 , ..., M j are also F j measurable. Because they only depend on the surviving particle at time T j , this is also true for the coupled auxiliary states B 1 , ..., B j .

Lemma 2.7.17. All the following variables:

are adapted to the filtration (F j ) j≥0 .

The difference We denote l : R → R, a : R → R d-1 and t : R → R, the solutions to the differential systems stated in theorem 2.6.1 and recalled below

4 (b (l(r), a(r))) 2 , with initial conditions (l(0), a(0), t(0)) = (l 0 , a 0 , 0). Let us define

where we remark that

Our goal is to prove that uniformly for j ∈ ⟦0, ⌊r/ε -1⌋⟧, the quantities ∆ L j , ∆ A j and ∆ T j go to zero, in probability, when ε decreases to zero.

Due to dependence of the both coordinates in the stochastic differential systems (2.11), we will not be able to prove separately the convergence of ∆ L and ∆ A . Moreover, we will need some properties on the times T j , j ≥ 0 to prove the convergence of the branching points, as A j is defined from T j .

Proof. This is simply Itô formula with the already mentioned identity:

□

The first lemma states that the hitting time S j+1 has bounded moments. Notice we do not use any results from the previous subsections, which is essential, as we need this Lemma to prove the convergence of the level and auxiliary coordinates.

Lemma 2.7.32. For any j ≥ 0 and any p ≥ 1, the microscopic hitting time S j+1 have finite bounded moments of order p: there exists a constant c(p, DΦ ε,L j+1 ) which depends on the constants from Assumption 2.3.4, which satisfies:

Proof. The idea of the proof is quite simple. We first study

and then apply a stochastic changing time result (Theorem B.0.1) which leads us to a drifted Brownian motion with a drift pointing towards the stopping level. We can then estimate the moments of the hitting times.

Using the notations of Theorem 2.7.5, we denote

From the previous lemma, the committor function evaluated at X t is solutions to the SDEs (for t ≥ T j )

(2.63) Let us introduce the following re-scaled and time-changed process

where the notation τ(u) refers to the time change

where, for the last two inequalities, we have first used (2.61) (which controls the supremum of s → |M s , B s | before S j+1 based on BDG inequality) and then used Lemma 2.7.32 which controls p-moments of S j+1 .

Step 5: Finally, we can gather Steps 3 and 4 taking the conditional expectancy, knowing F j in (2.66),so that (2.65)

becomes:

it is enough to conclude with Step 2. □

We need a second lemma to conclude about the convergence of C T , concerning the martingale part.

Lemma 2.7.35. For any p ≥ 1, there exists a constant c = c (p, b, σ) depending on the boundaries of coefficients (Assumption 2.3.2) such that, for any r, ε > 0, we have

We do not detail the proof which is based on a BDG inequality similar to the proof of Lemma 2.7.22 and for Lemma 2.7.29, since we have already proved that S i is a L p random variable with bounded moments.

Proposition 2.7.36. We have, for any p ≥ 2 and for any r > 0,

In a word, this ends the proof of Theorem 2.6.1.

Appendices

GRONWALL'S LEMMA

We recall some Gronwall lemmas, in the discrete situation and in the continuous one.

Lemma A.0.1. Let (α n ) n≥0 , (β n ) n≥0 and (γ n ) n≥0 three non-negative sequences such that, for any n ≥ 0, we have

Then, for any n ≥ 0, we have

Proof. We set, for n ≥ 0

and z -1 := 0.

From (A.1), we have

Direct computations give us

Hence, since z -1 = 0, by summation we have

STOCHASTIC TIME CHANGE

The first theorem is a stochastic time change result. It will be useful for the following lemmas. In dimension one, it can be summarized as follows: up to a stochastic time-change, a diffusion X is a drifted unit Brownian motion with possibly a non-constant drift.

Theorem B.0.1. Let us assume that X is a solution to the one-dimensional SDE

where W is a standard real Brownian motion for a filtration (F t ) t≥0 . Let us define the process X ′ by

Then the process X ′ satisfies the SDE

where W ′ is a unit Brownian motion for the filtration F S -1 (s) defined by

Proof. On one hand, we have

with the substitution u = S (v), so that X ′ satisfies the claimed SDE.

On the other hand

so that by Levy's characterization W ′ is a unit Brownian motion.

□

Theorem B.0.1 gives us a tool to compare diffusions, stated in the following corollary.

Corollary B.0.2. If α is lower bounded by α min 0, β 2 is upper bounded by β 2 max and X satisfies

then almost surely for all s

and the suprema can be almsot surely compared similarly.

Appendix C

GIRSANOV -DOOB

We adapt here a result from [Day, 1992], showing that, under a changing of measure, the law of a process, conditioned by reaching a level, is the same that the law of a process, with a different drift. [Day, 1992] develops the Doob h-transform in a one-dimensional situation, on R, but we will work here on R d , for any d ≥ 1. We will sometimes refer to [START_REF] Bakhtin | Scaling limits for conditional diffusion exit problems and asymptotics for nonlinear elliptic equations[END_REF] who also work on R d . We would also like to mention a very interesting discussion on Doob's h-transform, and its relations to exponential tilting [START_REF] Chetrite | Nonequilibrium markov processes conditioned on large deviations[END_REF].

Theorem C.0.1. Let us assume that X is the strong solution to the d-dimensional SDE, under some probability

where α, β ∈ C 1 R d are Lispchitz functions. Let us consider the process X, conditioned by reaching a level set {ξ = l} in finite time, then, there exists a probability measure Q and a Q-Brownian motion W Q such that the law of X, conditioned by reaching {ξ = l} in finite time, is the same than the law of the solution to the SDE

and T l = T l (X) is the first hitting time of the level set {ξ = l} by the process X.

Moreover, the probability of hitting the level set in finite time, is the solution to the following Dirichlet problem

Remark C.0.2. In dimension 1 and with diffusive coefficient β = 1 in (C.2), one is able to compute h l , and then Φ l Appendix D

DRIFTED BROWNIAN MOTION

D.1 Brownian motion

Using the reflection principle, it is possible to compute the joint density of a standard Brownian motion and its running maximum.

Lemma D.1.1.

Proof. The reflection principle with reflection symmetry at value y ≥ 0 yields: for any convenient function Φ, we have

A simple change of variables yields:

As a consequence, choosing ϕ = 1 .≤y-h for h > 0, it yields:

Deriving with respect to y yields the density. □ Lemma D.1.2. The first hitting time of x > 0 by a Brownian motion W starting from 0, defined by T x :=

Proof. One has for any t ≥ 0 and any x > 0,

D.2 Exact distribution of a drifted Brownian motion

We denote Proof. Let us point out that

x is a stopping time for the Brownian filtration associated to W. Let us first prove that the law of the supremum of the drifted Brownian motion, is exponential. For x 1 , x 2 ≥ 0, we have, by almost surely continuity of W µ ,

By strong Markov property:

Hence,

where c :=ln P (sup t≥0 W µ t ≥ 1). It only remains to compute c, the parameter of the exponential law. For this, we take x > 0. As

with µ < 0, we do know that W reaches x before W µ . Let us denote T x = inf {t > 0 : W t = x}, it is also a stoppingtime for the Brownian filtration.

We conclude by using Lemma D.1.3. □

In Lemma D.1.3, we have already mentioned that the hitting time of a Brownian motion is almost surely finite. In the drifted Brownian motion case, it all depends of the symbols of the drift and the target point.

First of all, the computation above yields immediately:

Lemma D.2.2. Let µ < 0. For any x > 0, we have

Next, one can compute the conditional distribution of hitting times.

Lemma D.2.3. We take µ < 0. The first hitting time of x > 0 by W µ , defined by T

It also has a Laplace transform: for any x > 0 and for any λ ≥ 0, we have

we get the result. □

D.4 Comparisons

In the following section, we will focus on the comparison of the processes (M, B) and M, B , with values in R × R d-1 . We remind the SDEs from which they are solutions, and the assumptions we made about the functions b(., .), σ(., .), f (., .) and θ(., .).

Here, ε > 0 is a positive real number, and b, σ, f and θ refer to the value of the corresponding functions at point f min ≤ f (., .) ≤ f max , θ min ≤ θ (., .) ≤ θ max .

Finally, we assume that all the functions b(., .), σ(., .), f (., .) and θ (., .) are global lipschitz, with constant c.

D.4.1 Comparison of processes

This first result bounds the expectation of the difference between Y and Y, until some deterministic time s m ≥ 0.

[Villén-Altamirano and Villén-Altamirano, 1991] Villén-Altamirano, M. and Villén-Altamirano, J. (1991). Restart:

A method for accelerating rare event simulations. In Queuing, Performance and Control in ATM, Proceedings of the 13th International Telegraphic Congress.

[ Wadman et al., 2013] Wadman, W., Crommelin, D., and Frank, J. (2013). Applying a splitting technique to estimate electrical grid reliability. In 2013 Winter Simulations Conference (WSC), page 577-588. IEEE.