Quantitative analysis of Markov chains using perturbation of their kernel
Étude quantitative des chaînes de Markov par perturbation de leur noyau.
Résumé
The development of the modelling of the random phenomena using Markov chains raises the problem of the control of convergence of the algorithms of simulation. The methods of simulations by ergodic Markov chains is based on the law of large numbers, which stipulates that for any initial distribution and any function f, the empirical average converges to the average of f, calculated with the unique invariant probability of the chain. It is then advisable, to determine a sufficient number of step of simulation in order to approximate, in a relatively precise way, the average of a f by its empirical average. Several works studied the speed of convergence of the chain towards its steady state. However even in steady state, the problem of the control remains, as we want to obtain a confidence interval for a fixed level. Two approaches exist to determine a sufficient number of steps. Either by bounding directly the probability of deviation between the empirical average and the average of f under the invariant probability, or by using the CLT. The starting point of this thesis was the inequality of Gillman and more particularly the method used: namely tools presented in the book of Kato on the theory of the perturbation of the linear operators.
Le développement de la modélisation des phénomènes aléatoires par chaînes de Markov pose le problème du contrôle de convergence des algorithmes de simulation. Les méthodes de simulation par chaînes de Markov ergodiques s'appuient sur la loi des grands nombres, qui stipule que pour toute distribution initiale et toute fonction f, la moyenne empirique converge vers la moyenne de f, calculée avec l'unique probabilité invariante de la chaîne. Il convient alors, de déterminer un nombre suffisant de pas de simulation pour approximer, de façon relativement précise, la moyenne d'une certaine fonction par sa moyenne empirique. Plusieurs travaux ont étudié la vitesse de convergence de la chaîne vers son régime stationnaire. Cependant même en régime stationnaire, le problème du contrôle demeure, puisqu'il s'agit de calculer un intervalle de confiance pour un niveau fixé. Deux démarches existent pour déterminer le nombre de pas suffisants. Soit majorer directement la probabilité de déviation entre la moyenne empirique et la moyenne de la fonction sous la probabilité invariante, soit utiliser le théorème central limite. La première majoration est appelée borne de Chernoff et la seconde méthode invoque une borne de Berry-Esséen. Le point de départ de cette thèse fut l'inégalité de Gillman et plus particulièrement la méthode utilisée ; à savoir les outils présentés dans le livre de Kato sur la théorie des perturbations des opérateurs linéaires. L'exploitation plus poussée de cette méthode nous a permis d'obtenir les résultats suivant :•amélioration des bornes de Gillman et Dinwoodie : mise en évidence des comportements gaussien pour des petites déviations et poissonien pour les grandes déviations ;•extension au temps continu ;•extension aux espaces d'états quelconques, sous l'hypothèse d'un trou spectral pour le noyau de la chaîne et le générateur infinitésimal du processus ;•obtention d'une borne inférieure à la probabilité de déviation lorsque le processus (la chaîne) est réversible et d'espace d'états fini ;•amélioration et extension de la borne de Berry-Esséen obtenue par B. Mann.
Loading...