Acceleration of Perfect Sampling by Skipping Events

Furcy Pin; Ana Busic; Bruno Gaujal

5th International ICST Conference on Performance Evaluation Methodologies and Tools

Research Article

Acceleration of Perfect Sampling by Skipping Events

Download525 downloads

Cite: BibTeX Plain Text

@INPROCEEDINGS{10.4108/icst.valuetools.2011.245718,
    author={Furcy Pin and Ana Busic and Bruno Gaujal},
    title={Acceleration of Perfect Sampling by Skipping Events},
    proceedings={5th International ICST Conference on Performance Evaluation Methodologies and Tools},
    publisher={ICST},
    proceedings_a={VALUETOOLS},
    year={2012},
    month={6},
    keywords={Markov chains perfect sampling queueing networks.},
    doi={10.4108/icst.valuetools.2011.245718}
}

Furcy Pin
Ana Busic
Bruno Gaujal
Year: 2012
Acceleration of Perfect Sampling by Skipping Events
VALUETOOLS
ICST
DOI: 10.4108/icst.valuetools.2011.245718

Furcy Pin¹^,*, Ana Busic², Bruno Gaujal³

1: ENS / INRIA
2: INRIA / ENS
3: INRIA Grenoble

*Contact email: furcy.pin@ens.fr

Abstract

This paper presents a new method to speed up perfect sampling of Markov chains by skipping passive events during the simulation. We show that this can be done without altering the distribution of the samples. This technique is particularly efficient for the simulation of Markov chains with different time scales such as queueing networks where certain servers are much faster than others. In such cases, the coupling time of the Markov chain can be arbitrarily large while the runtime of the skipping algorithm remains bounded. This is further illustrated by several experiments that also show the role played by the entropy of the system in the performance of our algorithm.

Keywords: Markov chains perfect sampling queueing networks.

Published: 2012-06-26
Publisher: ICST

: http://dx.doi.org/10.4108/icst.valuetools.2011.245718