Comme décrit dans les sections précédentes, les chaînes de Markov constituent un outil privilégié pour la modélisation et l'analyse de la sûreté de fonctionnement et l'évaluation des performances des systèmes informatiques et de télécommunication.
Nous avons conçu une nouvelle méthode de simulation basée sur les techniques quasi-Monte Carlo pour accélérer l'évaluation de ces chaînes. Les méthodes quasi-Monte Carlo forment un analogue déterminsite de Monte Carlo où les nombres aléatoires uniformes sont remplacés par des nombres ne mimant plus le hasard mais ayant la propriété de se répartir très rapidement uniformément sur l'espace considéré. Ces méthodes sont cependant connues rencontrer deux difficultés majeures: l'erreur d'estimation est difficile à estimer en pratique et leur efficacité par rapport aux méthodes Monte Carlo décroit avec la dimension du problème considéré (qui est linéaire en le nombre d'étapes de la chaîne de Markov considérée). Le premier problème est remédié en perturbant légèrement et aléatoirement les suites considérées sans leur faire perdre leur propriété de bonne répartition, puis en appliquant le théorème de la limite centrale sur ces différentes randomisations. Le deuxième problème, plus directement lié à la structure de l'analyse des chaînes de Markov, est résolu en appliquant un algortihme simple. Seulement une suite de dimension 1 peut être considérée. les "réplications" de la chaîne de Markov à étudier sont simulées en parallèle étape par étape en utilisant cette suite au lieu des nombres pseudo-aléatoires. Après chaque étape, les chaînes doivent être réordonnées selon une relation d'ordre total (qui doit par hypothèse exister sur l'espace d'états), avant de recommencer la simulation pour l'étape suivante...
Nous avons pu prouver la convergence de la méthode (quand le nombre de réplications augmente). Un ordre de convergence dans le pire cas est prouvé être le même que celui de Monte Carlo en moyenne. Dans certains cas particuliers, des convergences plus rapides sont aussi obtenues.
Numériquement, l'ordre d'amélioration obtenu par rapport à Monte carlo est toujours ntable, et peut s'avérer spectaculaire, dépassant les 60000 pour certaines illustrations sur les files d'attente.