Perfect Simulation and Monotone Stochastic Bounds

J.M. Fourneau; I. Kadi; N. Pekergin; J. Vienne; J.M. Vincent

2nd International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Perfect Simulation and Monotone Stochastic Bounds

Download233 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. Fourneau¹^,*, I. Kadi²^,*, N. Pekergin³^,*, J. Vienne¹^,*, J.M. Vincent¹^,*

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