About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
2nd International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Perfect Simulation and Monotone Stochastic Bounds

Download851 downloads
Cite
BibTeX Plain Text
  • @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.

Keywords
Perfect Simulation Stochastic Bounds Coupling from the past monotone Markov chains
Published
2010-05-16
Modified
2011-09-14
http://dx.doi.org/10.4108/valuetools.2007.1933
Copyright © 2007–2025 ICST
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL