3rd International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Perfect Simulation and Non-monotone Markovian Systems

Download649 downloads
  • @INPROCEEDINGS{10.4108/ICST.VALUETOOLS2008.4404,
        author={Ana Bušic and Bruno Gaujal and Jean-Marc Vincent},
        title={Perfect Simulation and Non-monotone Markovian Systems},
        proceedings={3rd International ICST Conference on Performance Evaluation Methodologies and Tools},
        publisher={ICST},
        proceedings_a={VALUETOOLS},
        year={2010},
        month={5},
        keywords={Markov chains perfect simulation queuing networks},
        doi={10.4108/ICST.VALUETOOLS2008.4404}
    }
    
  • Ana Bušic
    Bruno Gaujal
    Jean-Marc Vincent
    Year: 2010
    Perfect Simulation and Non-monotone Markovian Systems
    VALUETOOLS
    ICST
    DOI: 10.4108/ICST.VALUETOOLS2008.4404
Ana Bušic1,*, Bruno Gaujal1,*, Jean-Marc Vincent2,*
  • 1: INRIA Grenoble - Rhône-Alpes 51, Av. J. Kuntzmann 38330, Montbonnot, France
  • 2: Université Joseph Fourier, 51, Av. J. Kuntzmann, 38330 Montbonnot, France
*Contact email: ana.busic@imag.fr, bruno.gaujal@inria.fr, jean-marc.vincent@imag.fr

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, the envelopes might not couple or the coupling time might be larger. 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.