2nd International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Perfect Simulation and Monotone Stochastic Bounds

Download659 downloads
  • @INPROCEEDINGS{10.4108/valuetools.2007.1933,
        author={J.M. Fourneau and I. Kadi and N. Pekergin and J. Vienne and J.M. Vincent},
        title={Perfect Simulation and Monotone Stochastic Bounds},
        proceedings={2nd International ICST Conference on Performance Evaluation Methodologies and Tools},
        proceedings_a={VALUETOOLS},
        year={2010},
        month={5},
        keywords={Perfect Simulation Stochastic Bounds Coupling from the past monotone Markov chains},
        doi={10.4108/valuetools.2007.1933}
    }
    
  • J.M. Fourneau
    I. Kadi
    N. Pekergin
    J. Vienne
    J.M. Vincent
    Year: 2010
    Perfect Simulation and Monotone Stochastic Bounds
    VALUETOOLS
    ICST
    DOI: 10.4108/valuetools.2007.1933
J.M. Fourneau1,*, I. Kadi2,*, N. Pekergin3,*, J. Vienne1,*, J.M. Vincent1,*
  • 1: INRIA project MESCAL Laboratoire Informatique de Grenoble CNRS UMR 5217 Montobonnot, France
  • 2: PRiSM CNRS UMR 8144 Université de Versailles Saint-Quentin 45 Av. des Etats Unis, 78000 Versailles, France
  • 3: LACL, Université Paris 12 61 Av. Général de Gaulle, 94010, Créteil, France
*Contact email: jmf@prism.uvsq.fr, ika@prism.uvsq.fr, nih@prism.uvsq.fr, jerome.vienne@imag.fr, jeanmarc._vincent@imag.fr

Abstract

We combine monotone bounds of Markov chains and the coupling from the past to obtain an exact sampling of a strong stochastic bound of the steady-state distribution for a Markov chain. Stochastic bounds are sufficient to bound any positive increasing rewards on the steady-state such as the loss rates and the average size or delay. We show the equivalence between st-monotonicity and event monotonicity when the state space is endowed with a total ordering and we provide several algorithms to transform a system into a set of monotone events. As we deal with monotone systems, the coupling technique requires less computational efforts for each iteration. Numerical examples show that we can obtain very important speedups.