|
|
Location : IRISA / INRIA Rennes
Duration : one year, starting September 2005 (or later)
Application deadline : April 22, 2005 (electronic application file : Word)
Team : ASPI (Applications of interacting particle systems to statistics)
Contact : Frédéric Cérou (tél. : 02 99 84 72 29, e-mail : fcerou@irisa.fr)
Background : probability numerics, Monte Carlo methods, MATLAB or SCILAB programming
Subject : To evaluate numerically the probability of a rare event (such as the probability that a Markov process hits a critical set), critical for the nominal behaviour or the safety of a system, Monte Carlo branching methods have been introduced under the name of importance splitting, and have been studied using the very general framework of particle approximations of Feynman-Kac flows, as introduced by DelMoral.
Given a decreasing family of sets containing the critical set, the idea is to simulate independent trajectories of the Markov process, to multiply those trajectories that have managed to reach the upper critical level, and to terminate those trajectories that have failed. The probability to hit the critical set is estimated as the product of the probabilities to hit a level from the lower critical level, each of these transition probabilities being estimated as the proportion of the simulated trajectories that have managed to reach the upper critical level. Ideally, the intermediate sets should be chosen in such a way that these transition probabilities are reasonably small, for instance of the order 0.1, which means that 10% of the simulated trajectories should reach in principle the upper critical level.
In practice, it is very difficult to choose these levels (and their number) in advance, and the subject of this post-doc project is to study an adaptive strategy in which the levels are chosen on-line. Conceptually, it could even be argued that these new algorithms get rid of the level notion, as they rely on the idea that it is enough to simulate independent trajectories, to multiply the 10% best (namely those which have managed to come closer to the critical set), and to terminate the other 90%. In a certain sense, the worst of the 10% best simulated trajectories defines a virtual level. By construction, this algorithm guarantees a success of 10% for the transition from one virtual level to the upper virtual level, but on the other hand the number of virtual levels that should be crossed to finally hit the critical set is unknown in advance.
The objective of this post-doc project is to design algorithms based on the adaptive importance splitting idea, to study their mathematical properties and to implement them in various applications were safety critical issues should be taken into account (air traffic, communications networks, etc.).
Bibliography :