Bien souvent, les problèmes scientifiques conduisent à l'évaluation
d'intégrales ou de sommes ainsi qu'à la résolution
d'équations différentielles ou intégrales. En général,
les calculs analytiques exacts des intégrales ne sont pas réalisables
directement. De même les sommes doivent parfois être effectuées
sur un nombre de termes trop important pour espérer les comptabiliser.
On fait alors appel à des méthodes d'approximation. Parmi
les plus couramment utilisées, on retrouve les méthodes classiques
d'analyse numérique. Efficaces en dimension 1, ces techniques s'avèrent
rapidement sans intérêt dès que la dimension augmente.
Or le nombre de variables pour certains problèmes est très
grand et peut même s'avérer si important que les progrès
envisageables du calcul informatique ne seront probablement jamais suffisants
pour rendre ces techniques intéressantes. Dans cette optique, des
méthodes de simulation statistique, méthodes dites de Monte
Carlo, sont très prometteuses puisque leur vitesse de convergence
est indépendante de la dimension du problème mathématique
posé. En revanche, elles fournissent non pas la solution numérique
du problème, mais un intervalle de confiance la contenant avec une
probabilité donnée.
Les techniques de Monte Carlo ont été utilisées
depuis plusieurs siècles, même si ce n'est qu'après
la seconde guerre mondiale qu'elles ont acquis un véritable statut
de méthode. L'utilisation systématique, par Ulam, Metropolis
et Von Neumann notamment, est intervenue à Los Alamos, pendant la
préparation de la bombe atomique, où ont collaboré
de nombreux mathématiciens et physiciens de renom. L'appellation
``Monte Carlo'' est due à Metropolis, inspiré de l'intérêt
de Ulam pour le poker, car Monte Carlo est un grand centre de casinos,
et a pour origine les similarités avec les jeux de hasard. Le travail
à Los Alamos consistait à simuler directement les problèmes
de dispersion et d'absorption de neutrons pour les matériaux fissibles.
Dès les premières applications, des méthodes de réduction
de la variance ont été utilisées. Les recherches étant
bien évidemment secrètes à Los Alamos, les premières
publications sur le domaine ne sont intervenues qu'à partir de 1949.
Ensuite, le développement de ces méthodes a accompagné
les développements de l'informatique. En effet, en 1945 déjà,
J. von Neumann conjecturait le potentiel des ordinateurs pour la simulation
stochastique : ``L'ordinateur offrira certainement une nouvelle approche
à la statistique mathématique ; l'approche par expérience
sur ordinateur''. Les techniques de Monte Carlo ont alors été
utilisées fréquemment et dans de nombreux domaines à
partir des années 50, et même sur-utilisées, par exemple
pour des problèmes où elles n'étaient pas les plus
adaptées.
Mes travaux passés
Une première partie importante de mes travaux sur mes méthodes
de Monte Carlo consiste en une combinaison des méthodes de Monte
Carlo et quasi-Monte Carlo (voir la page
sur quasi-Monte Carlo).
Une seconde partie concerne la simulation des événements
rares. Nous nous sommes intéressés à l'un des domaines
centraux du point de vue des applications dans l'analyse de systèmes
complexes, celui de la simulation des systèmes Markoviens hautement
fiables. En effet, pour de tels modèles, les méthodes de
quasi-Monte Carlo restent inefficaces (car nous simulons des chemins d'un
processus stochastique en un nombre d'étapes indéterminé;
nous sommes donc en dimension infinie, cas trop compliqué pour quasi-Monte
Carlo). Nous avons approfondi les méthodes existantes. La contribution
la plus significative sur ce sujet est cependant l'introduction d'un nouveau
concept, l'approximation normale bornée, qui permet d'obtenir une
approximation de la loi normale satisfaisante dans le théorème
de la limite centrale, quelle que soit la fiabilité du système
étudié. Nous avons de plus déterminé que l'approximation
normale bornée permet une estimation satisfaisante de la variance.
Un autre point sur les méthodes de simulation est le dévéloppement
du simulateur SPNP, logiciel d'analyse de réseaux
de Petri. Nous avons ainsi développé le simulateur et
intégré de nombreuses méthodes de simulation (importance
sampling, importance splitting...).
Les sujets sur lesquels je compte continuer à travailler
Travaux sur la simulation d'événements rares.
Simulation de protocoles Internet.
Application à l'évaluation de performances des réseaux
mobiles de troisème génération.
B. Tuffin, Simulation accélérée par les méthodes
de Monte Carlo et Quasi-Monte Carlo : théorie et applications. Thèse
de Doctorat, Université de Rennes 1. Octobre 1997.
H. Cancela, G. Rubino et B. Tuffin, Fast Monte Carlo Methods for evaluating
Highly Dependable Markovian Systems. Second International Conference
on Monte Carlo and quasi-Monte Carlo Methods in Scientific Computing,
Salzburg, Autria, July 1996.
B. Tuffin, Bounded Normal Approximation in Highly Reliable Markovian Systems.
Journal of Applied Probability, Vol. 36, Num.4, 1999.
B. Tuffin and K.S. Trivedi. Implementation of Importance Splitting techniques
in Stochastic Petri Net Package. In Haverkort, B.R., and Bohnenkamp,
H.C. and Smith, C.U. (eds), Computer performance evaluation: Modelling
tools and techniques; 11th International Conference; TOOLS 2000, Lecture
Notes in Computer Science, volume 1786, Springer Verlag, pages 216-229,
2000.
B. Tuffin. On Numerical Problems in Simulations of Highly Reliable Markovian
Systems soumis (Aussi PI IRISA 1191).
B. Tuffin and K.S. Trivedi. Importance Sampling for the Simulation of Stochastic
Petri nets and Fluid Stochastic Petri nets.
In Proceedings of High Performance
Computing (HPC), pages 228-235, Seattle, WA, USA, Avril 2001.
H. Cancela, G. Rubino and B. Tuffin. MTTF estimation using Importance Sampling
on Markov models. In Proceedings of the 5th International Conference
on Industrial Loigistics, Okinawa, Japan, 2001.
S. Collas, B. Tuffin. Creation of a Dynamic Model Language and Application
of Monte Carlo Methods for the Reliability Analysis of Industrial Complex
Systems. Dans Actes de lambda mu-13, Lyon, Mars 2002.
H. Cancela, G. Rubino and B. Tuffin. MTTF estimation by Monte Carlo methods
using Markov models. Monte Carlo Methods and Applications: 8(4),
pages 312-341, 2002.