Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 17 avril 2018 à 14h00 en B107, Christelle Rovetta nous parlera de : Utilisation de la programmation dynamique comme stratégie pour l'algorithme de simulation parfaite

Résumé : En 1996, Propp et Wilson ont proposé un algorithme permettant l'échantillonnage sans biais de la distribution stationnaire d'une chaîne de Markov ergodique. Ce dernier appelé aussi algorithme de simulation parfaite, requiert la simulation en parallèle de tous les états possibles de la chaîne. Un des challenges lorsque l'on veut faire de l'échantillonnage par simulation parfaite réside généralement à mettre en place des stratégies permettant de ne pas avoir à simuler toutes les trajectoires. Un réseau fermé de files d'attente est un réseau dans lequel les clients ne peuvent ni entrer ni quitter le réseau. La dynamique de tels réseaux est couramment représentée par une chaîne de Markov ergodique. La difficulté pour qui voudrait appliquer l'algorithme de Propp et Wilson à de tels réseaux, réside dans la taille de l'espace des états qui est exponentielle en le nombre de files à laquelle s'ajoute une contrainte globale à savoir le nombre constant de clients.

 [Slides.pdf]


Dernière modification : lundi 16 avril 2018 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr