Méthodes de Monte Carlo Sudoku pour la simulation des chaînes de Markov

Les chaînes de Markov permettent de modéliser de manière simple et robuste de nombreux phénomènes aléatoires rencontrés dans les domaines de la science et de la technologie. Pour simuler une chaîne de Markov à espace  d'états discrets, les techniques classiques qui reposent sur le calcul matriciel  nécessitent une capacité de mémoire et un temps de calcul considérables. Les simulations du type Monte Carlo (MC) en sont alors des alternatives efficaces.

Afin d'améliorer davantage l'efficacité d'une simulation MC, une méthode  quasi-Monte Carlo a été introduite dans [1]. Elle consiste à engendrer un grand nombre $N$ d'états à partir  de la distribution initiale et à les faire évoluer suivant les probabilités de transition de la chaîne de Markov. La différence avec la simulation MC habituelle est que des points déterministes en  dimension deux sont utilisés à la place de points pseudo-aléatoires unidimensionnels et que les $N$ états sont réordonnés à chaque pas de temps. 

Dans cet exposé, nous présenterons une technique d'échantillonnage stratifiée dite \emph{Sudoku}. Elle consiste à utiliser un échantillon de $N$ points vérifiant les deux conditions suivantes

•  quand le carré unité $[0,1[^2$ est uniformément divisé en $N$ sous-carrés identiques, un point de l'échantillon apparaît dans chacun des sous-carrés
• pour chaque axe, les projections des $N$ points sont réparties dans chacun des $N$ sous-intervalles qui divisent uniformément l'intervalle unité

Nous  montrons que la variance de l'estimateur Sudoku est de l'ordre $\mathcal{O}(N^{- 3/2})$  alors que celle d'un estimateur MC classique est de l'ordre $\mathcal{O}(N^{- 1})$.  Cette réduction de la variance est illustrée à l'aide de tests numériques.

Bibliographie

[1] C. Lécot, B. Tuffin. Quasi-Monte Carlo methods for estimating transient measures of discrete time Markov chains. Monte Carlo and Quasi-Monte Carlo Methods 2002. Springer, 2004.

[2] R. El Haddad, R. Fakhereddine, C. Lécot, G. Venkiteswaran. Extended Latin hypercube sampling for integration and simulation. Monte Carlo and Quasi-Monte Carlo Methods 2012. Springer, 2013.