PSI2 : Envelope Perfect Sampling of Non Monotone Systems

Ana Busic 1 Bruno Gaujal 2 Gaël Gorgo 2 Jean-Marc Vincent 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 : The famed perfect sampling method of Propp and Wilson [3] uses a backward coupling scheme to compute unbiased samples of the stationary distribution of Markov chains. It has been implemented in a software tool, called PSI2, that proved very efficient for monotone chains coming from queuing networks [4]. However, when the system includes at least one nonmonotone event, the backward simulation scheme has to consider all possible states as starting points. This can be avoided by taking a new point of view that consists in bounding all possible trajectories of the Markov chain by envelopes. The new version of PSI2 presented here implements these latest improvements, including envelope techniques and splitting. Envelopes have been introduced by Buˇsi'c et al [1]. As soon as envelopes couple, then all trajectories must have coupled, so that an unbiased sample is obtained. As for splitting, it consists in generating all the trajectories of the Markov chains inside the envelopes to run a classical backward coupling technique from that point on. Combining these two techniques in PSI2 makes it a more efficient tool that covers a wider class of queuing networks than previously. This includes networks with non-monotone events such as negative customers, arrivals by batches, forks and joins as well as cox-distribution for services.
Type de document :
Communication dans un congrès
QEST 2010 - International Conference on Quantitative Evaluation of Systems, Sep 2010, Williamsburg, VA, United States. IEEE, pp.83-84, 2010, 〈http://doi.ieeecomputersociety.org/10.1109/QEST.2010.19〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00788884
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 15 février 2013 - 13:11:20
Dernière modification le : mercredi 14 décembre 2016 - 01:08:43

Identifiants

  • HAL Id : hal-00788884, version 1

Collections

Citation

Ana Busic, Bruno Gaujal, Gaël Gorgo, Jean-Marc Vincent. PSI2 : Envelope Perfect Sampling of Non Monotone Systems. QEST 2010 - International Conference on Quantitative Evaluation of Systems, Sep 2010, Williamsburg, VA, United States. IEEE, pp.83-84, 2010, 〈http://doi.ieeecomputersociety.org/10.1109/QEST.2010.19〉. 〈hal-00788884〉

Partager

Métriques

Consultations de la notice

200