La proposition en bref

---

II. BILAN 2008

Changements majeurs survenus concernant l'Equipe Associée (modifications des objectifs scientifiques, des chercheurs impliqués): la pricipale modification est le recrutement tardif du doctorant à Rennes, la candidate initiale s'étant désistée au dernier moment. Pour cette raison, le séjour n'a pu être programmé en 2008 (temps d'assimilation du sujet insuffisant sinon).

 

Rapport scientifique de l'année 2008

Description de l'activité scientifique de l'équipe associée et des résultats obtenus : publications, communications, organisation de colloques, formation, soutenances de thèse, valorisation économique, sociale, industrielle, enregistrement de logiciels, dépôt de brevets ... (1 à 2 pages)

Page de la proposition initiale: http://www.irisa.fr/dionysos/pages_perso/tuffin/Formulaire08.html.

En 2008 nous avons travaillé sur différents sujets.

Technique Splitting pour la simulation d'événements rares

Le splitting peut être interprété comme la décomposition de l'événement rare en une succession d'événements non rares, et regarder successivement si ces événements sont atteints. A partir d'un certain niveau/événement, si l'événement suivant n'est pas atteint, l'événement rare ne l'est pas non plus, mais sinon, on pousse artificiellement vers l'événement rare en séparant (ou clonant) l'état courant et en essayant d'atteindre le niveau suivant.

Nous avons travaillé, et continuons à travailler dans plusieurs directions. Tout d'abord, nous avons mis au point des nouvelles versions de la procédure, en jouant par exemple à la roulette russe quand la trajectoire retourne plusieurs niveaux plus bas, afin de réduire la temps de calcul. Fournir des théorèmes de la limite centrale est aussi de première importance pour les différentes versions, et un sujet que nous abordons. De même, nous travaillons aussi sur la combinaison du splitting et de l'importance sampling.

Une partie de ce travail est aussi jointe avec F. Legland, de l'équipe-projet ASPI.

Approximation de la simulation à variance zéro

Les techniques de réduction de la Variance peuvent réduire l'erreur d'estimation pour la simulation Monte Carlo, parfois par un large facteur, mais rarement changer la vitesse de convergence de l'estimateur. Cette erreur décroit habituellement comme l'inverse de la racine carrée de l'effort de calcul, comme décrit par le théorème central limite. En théorie, il existe des estimateurs avec variance zéro, c'est à dire fournissant toujours la valeur exacte. Mais ces estimateurs sont souvent bien trop difficile (ou virtuellement impossible) à implanter. Cependant, il y a des situations, en particulier pour la simulation d'événements rares, où la simulation à variance zéro peut être approchée, et fournir des gains substantiels. Des versions adaptatives peuvent même fournir une vitesse de convergence plus rapide, exponentielle dans certains cas.

Nous avons fourni une vue d'ensemble de ces méthodes et discuté leur validité en pratique pour deux types de méthodes, les variables de contrôle et l'importance sampling.

Importance sampling et variance zéro pour les systèmes hautement fiables

Nous avons développé des méthodes efficaces d'importance sampling (IS) pour estimer la fiabilité d'une classe de chaînes de Markov incluant les systèmes Markoviens hautement fiables (HRMS) souvent utilisés pour représenter l'évolution de systèmes multi-composants dans des cadres de fiabilité. Pour ces modèles, il existe une méthode IS à variance zéro qui peut être exprimer explicitement en termes d'une fonction de valeur donnant le coût espéré (la fiabilité exacte dans notre cas) à partir de l'état considéré.

Cette méthode IS ne peut être implantée en pratique car elle requiert la connaissance de ce que l'on cherche à estimer, mais elle peut être approchée en approchant la fonction de valeur. Dans notre implémentation, nous commençons par une estimation simple de la fonction de valeur, et l'utilisons dans une méthode de premier ordre pour obtenir une meilleure approximation à quelques états sélectionnés, et alors interpolons pour obtenir une approximation de second ordre.

Notre approche est plus efficace que les méthodes IS connues jusqu'ici pour cette classe de problèmes. Nous montrons aussi par une analyse asymptotique qu'avec notre approximation, l'estimateur vérifie, sous conditions, erreur relative bornée, et peut même avoir erreur relative qui tend vers zéro.

Simulation d'événements rares pour modèles statiques

Nous avons considéré le problème d'évaluer la probabilité d'un événement rare dans le cas d'un modèle statique, c'est à dire quand le temps ne joue pas de rôle explicite. Plus spécifiquement, nous avons abordé le problème d'estimation de la fiabilité d'un réseau en utilisant Monte Carlo, où le réseau est modélisé par un graphe avec noeuds et/ou liens sujets à des pannes indépendantes. Quand la fiabilité des composantes (la probabilité qu'elles soient opérationnelles) est proche de 1, la redondance des chemins rend très grande la probabilité d'existence d'un chemin entre deux noeuds sélectionnés (par exemple), et ainsi, la probabilité que les deux noeuds ne soient pas connectés (la défiabilité) est très petite.

Nous avons développé des méthodes de Monte Carlo efficaces pour l'estimation de la défiabilité d'un tel réseau, en combinant trois approches. Tout d'abord, nous utilisons des caractérisques faciles à obtenir sur le réseau, sa structure de chemins, pour suivre une approche conditionnelle permettant de borner la valeur cible. En particulier, nous montrons comment obtenir des méthodes ayant une variance relative nomalisée par le temps de calcul bornée dans le cas où les liens sont homogènes. Deuxièmement, nous explorons les techniques de Quasi-Monte Carlo Randomisées (RQMC) dans ce contexte. Enfin, nous montrons que l'approximation IS à variance zéro, bien établie dans le cas de modèles Markoviens, peut être étendu pour un modèle statique et nous explorons les propriétés de la procédure obtenue. L'idée est ici d'introduire artificiellement une variable de temps (discret) donnée par un ordre sur l'ensemble des composants du réseau. Une prémière compsante est choisie à l'instant 1, puis une seconde à l'instant 2, ...

Propriétés de robustesse des estimateurs

La robustesse asymptotique des estimateurs en fonction d'un paramètre de rareté, dans le contexte des événements rares, est souvent caractérisée par des propriétés telles que l'erreur relative bornée (BRE) et l'efficacité logarithmique (LE), aussi appelée optimalité asymptotique. Cependant ces propriétés ne suffisent pas à assurer que les moments d'ordre plus élevé que l'ordre 1 sont bien estimés. Par exemple, ils ne garantissent pas que la variance de la variance empirique reste sous contrôle comme fonction du paramètre de rareté.

Nous avons donc étudié des généralisations des propriétés BRE et LE qui prennent en compte cette limitation. Elles sont nommées moment relatif borné d'ordre k (BRM-k) et efficacité logarithmique d'ordre k (LE-k), où k>=1 est un réel arbitraire. Nous avons aussi introduit et examiné une notion plus forte appelée moment relatif centré d'ordre k disparaissant (vanishing), et explicité des exemples où cette propriété est vérifiée. Ces propriétés sont d'intérêt pour de nombreux estimateurs, incluant ceux de la moyenne empirique et de la variance empirique. Nous avons développé des conditions (suffisantes) de type Lyapunov pour ces propriétés dans un cadre d'importance sampling (IS) dépendant de l'état utilisé pour estimer des probabilités sur des temps de premier passage. Nous avons montré comment ces conditions peuvent guider dans la mise au point d'un bon schéma d'IS, avec les bonnes propriétés asymptotiques, pour le cas de marches aléatoires avec incréments à queue lourde ou légère. Comme autre illustration, nous avons étudié la hiérarchie entre ces propriétés de robustess (et quelques autres) pourun modèle de systèmes Markoviens hautement fiables. Dans ce cadre, et pour une classe populaire de méthodes IS, nous montrons que les propriétés BRM-k et LE-k sont équivalentes et que ces propriétés sont de plus en plus fortes quand k croit. Nous avons aussi obtenu une condition nécessaire et suffisante pour obtenir BRM-k.

Méthode Array-RQMC

La simulation simple, qui correspond à utiliser les méthodes Monte Carlo (MC) pour estimer des intégrales multiples, donne souvent des résultats très bruités. Les méthodes quasi-Monte Carlo (QMC) et quasi-Monte Carlo randomisées (RQMC) peuvent battre MC pour estimer l'intégale d'une fonction en dimension petite à modérée. Mais quand la fonction dépend du chemin suivi par une chaîne de Markov sur un grand nombre d'étapes, la dimension correspond à ce nombre d'étapes et peut même être infinie, QMC et RQMC deviennent alors inefficaces.

Notre travail a permis de proposer une nouvelle méthode RQMC spécifique à la simulation des chaînes de Markov. Nous avons fourni des exemples montrant que la méthode peut énormément réduire la variance par rapport à Monte Carlo. La composante clé de la méthode est de trier les chaînes de manière appropriée pour bénéficier de la bonne répartition des suites QMCMC sequences. Des applications en finance, files d'attente, fiabilité et gestion du risque ont commencé à être développées.

Organisation de Conférences

Nous avons organisé en 2008 deux des principaux événements du domaine:

• MCQMC 2008 à Montreal en juillet sur les méthodes de Monte Carlo et quasi-Monte Carlo
• RESIM 2008 à Rennes en Septembre sur la simulation d'événements rares.

A chaque fois les membres de l'équipe associée ont été présents.

Publications communes

Liste de publications communes (7 revues, conférences ou workshops, plus deux soumissions en cours), (voir aussi la page web officielle de l'équipe associée: http://www.irisa.fr/dionysos/pages_perso/tuffin/MOCQUASIN/). D'autres publications des partenaires peuvent être trouvées sur leurs pages respectives.

1. P. L'Ecuyer, J. Blanchet, B. Tuffin, P.W. Glynn. Asymptotic Robustness of Estimators in Rare-Event Simulation.Under revision at ACM Transactions on Modeling and Computer Simulation.
2. P. L'Ecuyer and B. Tuffin. Approximating Zero-Variance Importance Sampling in a Reliability Setting.
3. P. L'Ecuyer, C. Lecot and B. Tuffin. A Randomized Quasi-Monte Carlo Method for Markov Chains.Operations Research, To appear.
4. P. L'Ecuyer, M. Mandjes, and B. Tuffin. Importance Sampling and Rare Event Simulation. In Rare Event Analysis Using Monte Carlo Methods, G. Rubino and B. Tuffin Eds, John Wiley&Sons, 2008 (forthcoming).
5. P. L'Ecuyer, F. LeGland, P. Lezaud and B. Tuffin. Splitting Techniques in Rare Event Simulation. In Rare Event Analysis Using Monte Carlo Methods, G. Rubino and B. Tuffin Eds, John Wiley&Sons, 2008 (forthcoming).
6. P. L'Ecuyer and B. Tuffin, Approximate Zero-Variance Simulation. In Proceedings of the 2008 Winter Simulation Conference, IEEE Press, 2008.
7. H. Cancela, P. L'Ecuyer, M. Lee, G. Rubino and B. Tuffin. Combining Path-Based Methods, RQMC and Zero-Variance Approximations in Static Model Analysis. In Seventh International Conference on Monte Carlo and quasi-Monte Carlo Methods, Montreal, Canada, July 2008.
8. P. L'Ecuyer and B. Tuffin. Approximating zero-variance importance sampling in reliability settings. In Efficient Monte Carlo: From Variance Reduction to Combinatorial Optimization A Conference on the Occasion of R.Y. Rubinstein's 70th Birthday , Sandbjerg Estate, S nderborg, Denmark 14-18 July 2008.
9. P. L'Ecuyer, J. Blanchet, B. Tuffin, P.W. Glynn. Asymptotic Robustness of Estimators in Rare-Event Simulation. In the 7th International Workshop on Rare Event Simulation (RESIM 2008), Rennes, France, September 24-26 2008.