Perfect Sampling of Markov Chains with Piecewise Homogeneous Events

Ana Busic 1 Bruno Gaujal 2 Furcy Pin 1
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 : Perfect sampling is a technique that uses coupling arguments to provide a sample from the stationary distribution of a Markov chain in a finite time without ever computing the distribution. This technique is very efficient if all the events in the system have monotonicity property. However, in the general (non-monotone) case, this technique needs to consider the whole state space, which limits its application only to chains with a state space of small cardinality. Here, we propose a new approach for the general case that only needs to consider two trajectories. Instead of the original chain, we use two bounding processes (envelopes) and we show that, whenever they meet, one obtains a sample under the stationary distribution of the original chain. We show that this new approach is particularly effective when the state space can be partitioned into pieces where envelopes can be easily computed. We further show that most Markovian queueing networks have this property and we propose efficient algorithms for some of them.
Type de document :
Article dans une revue
Performance Evaluation, Elsevier, 2012, 69 (6), pp.247-266. 〈10.1016/j.peva.2012.01.003〉
Liste complète des métadonnées
Contributeur : Arnaud Legrand <>
Soumis le : mercredi 13 février 2013 - 14:57:20
Dernière modification le : mardi 17 avril 2018 - 11:32:28

Lien texte intégral




Ana Busic, Bruno Gaujal, Furcy Pin. Perfect Sampling of Markov Chains with Piecewise Homogeneous Events. Performance Evaluation, Elsevier, 2012, 69 (6), pp.247-266. 〈10.1016/j.peva.2012.01.003〉. 〈hal-00787997〉



Consultations de la notice