Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 26 Novembre 2019

Mise en œuvre de l' algorithme de Propp et Wilson

par Christelle Rovetta (INRIA et ENS Ulm, Paris)

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 (depuis le passé et jusqu'au temps 0) de tous les états de la chaîne. Un des challenges lorsque l'on veut faire de l'échantillonnage par simulation parfaite réside à mettre en place une stratégie permettant de ne pas avoir à simuler toutes les trajectoires. La stratégie employée est alors intrinsèquement liée à la chaîne de Markov que l'on veut simuler.

Durant cet exposé, je présenterai différentes chaînes de Markov ainsi que les stratégies associées permettant la mise en œuvre de l'algorithme de Propp et Wilson. J'exposerai notamment une stratégie - développée pendant ma thèse - qui fut utilisée dans le cadre de la simulation des réseaux fermés de files d'attente.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr