Acceleration of perfect sampling by skipping events

Furcy Pin 1 Ana Busic 1 Bruno Gaujal 2
1 TREC - Theory of networks and communications
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt
2 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : This paper presents a new method to speed up perfect sampling of Markov chains by skipping passive events during the simulation. We show that this can be done without altering the distribution of the samples. This technique is particularly efficient for the simulation of Markov chains with different time scales such as queueing networks where certain servers are much faster than others. In such cases, the coupling time of the Markov chain can be arbitrarily large while the runtime of the skipping algorithm remains bounded. This is further illustrated by several experiments that also show the role played by the entropy of the system in the performance of our algorithm.
Type de document :
Communication dans un congrès
VALUETOOLS '11 - 5th International ICST Conference on Performance Evaluation Methodologies and Tools, May 2011, Paris, France. ICST, pp.207-216, 2011, 〈http://dl.acm.org/citation.cfm?id=2151712〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00788799
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 15 février 2013 - 11:16:43
Dernière modification le : jeudi 11 janvier 2018 - 06:21:39

Identifiants

  • HAL Id : hal-00788799, version 1

Collections

Citation

Furcy Pin, Ana Busic, Bruno Gaujal. Acceleration of perfect sampling by skipping events. VALUETOOLS '11 - 5th International ICST Conference on Performance Evaluation Methodologies and Tools, May 2011, Paris, France. ICST, pp.207-216, 2011, 〈http://dl.acm.org/citation.cfm?id=2151712〉. 〈hal-00788799〉

Partager

Métriques

Consultations de la notice

273