Perfect Simulation and Non-monotone Markovian Systems

Ana Busic 1 Bruno Gaujal 1 Jean-Marc Vincent 1
1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : Perfect simulation, or coupling from the past, is an efficient technique for sampling the steady state of monotone discrete time Markov chains. Indeed, one only needs to consider two trajectories corresponding to minimal and maximal state in the system. We show here that even for non-monotone systems one only needs to compute two trajectories: an infimum and supremum envelope. Since the sequence of states obtained by taking infimum (resp. supremum) at each time step does not correspond to a feasible trajectory of the system, envelopes and not feasible trajectories. We show that the envelope approach is efficient for some classes of non-monotone queuing networks, such as networks of queues with batch arrivals, queues with fork and join nodes and/or with negative customers.
Type de document :
Communication dans un congrès
3rd International Conference Valuetools'08, 2008, Athens, Greece. ICST, 2008
Liste complète des métadonnées

Littérature citée [10 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00953624
Contributeur : Arnaud Legrand <>
Soumis le : vendredi 28 février 2014 - 14:11:47
Dernière modification le : mercredi 7 octobre 2015 - 01:16:32
Document(s) archivé(s) le : vendredi 30 mai 2014 - 15:30:39

Fichier

Ana-envelopes-2008.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00953624, version 1

Collections

INRIA | UGA | LIG

Citation

Ana Busic, Bruno Gaujal, Jean-Marc Vincent. Perfect Simulation and Non-monotone Markovian Systems. 3rd International Conference Valuetools'08, 2008, Athens, Greece. ICST, 2008. 〈hal-00953624〉

Partager

Métriques

Consultations de
la notice

224

Téléchargements du document

114