Pierre L'Ecuyer : Simulation de chaines de Markov : briser le mur de la convergence au taux de Monte-Carlo

- - Anciens Colloques

Simulation de chaines de Markov : briser le mur de la convergence en n-1/2

par


Pierre L'Ecuyer

Diro, Université de Montréal
Jeudi 23 mars, 15:30-16:30, Salle 3195, Pavillon André-Aisenstadt

    Université de Montréal, 2920 Chemin de la Tour

Café avant 15:00-15:30

 

Basé en partie sur des travaux avec
Amal Ben Abdellah, Christian Lécot, David Munger, Art B. Owen, et Bruno Tuffin

Résumé:

Le modèle suivant a des milliers d'applications: On a une chaîne de Markov en temps discret qui évolue sur un grand nombre d'étapes, on paye un coût à chaque étape qui est fonction de l'état de la chaîne, et on veut estimer l'espérance m du coût total sur toutes les étapes. En pratique, l'espace d'états est souvent très grand (voire infini) et il est trop difficile de calculer m numériquement. Dans ce cas, la méthode d'estimation la plus commune est Monte Carlo: On simule n trajectoires indépendantes de la chaîne, on calcule le coût pour chacune, et on fait la moyenne. On sait que la variance de cet estimateur est O(1/n), i.e., l'écart-type converge en O(n-1/2), ce qui est très lent (il faut multiplier n par 100 pour chaque chiffre décimal additionnel de précision).

Dans cette présentation, nous parlerons de méthodes permettant de simuler les n copies de la chaîne de manière à ce que l'estimateur demeure sans bias et que sa variance converge plus vite que O(1/n). L'une des méthodes, appelée Array-RQMC, simule les n copies simultanément et les fait avancer d'un pas à chaque étape en utilisant un ensemble de n points quasi-Monte Carlo randomisés, après avoir trié les n copies dans un ordre particulier. Nous expliquerons cette méthode, puis survolerons quelques variantes, stratégies de tri, résultats de convergence, et nous donnerons une liste de sujets de recherche ouverts!

À la fin, nous mentionnerons brièvement d'autres méthodes permettant d'améliorer considérablement la convergence dans la simulation de chaînes de Markov. 

Pour en savoir plus :

  • P. L'Ecuyer, C. Lécot, and B. Tuffin, "A Randomized Quasi-Monte Carlo Simulation Method for
    Markov Chains", Operations Research, 56, 4 (2008), 958-975.
  • P. L'Ecuyer, D. Munger, C. Lécot, and B. Tuffin, "Sorting Methods and Convergence Rates for
    Array-RQMC: Some Empirical Comparisons", Mathematics and Computers in Simulation, 2017.
    http://www.sciencedirect.com/science/article/pii/S0378475416301203
  • L'Ecuyer and B. Tuffin, "Approximate Zero-Variance Simulation," Proceedings of the 2008 Winter
    Simulation Conference, Dec. 2008, 170-181. http://www.informs-sim.org/wsc08papers/019.pdf
Partager :
  • Envoyer
  • Imprimer