# A perfect sampling algorithm of random walks with forbidden arcs

1 MESCAL - Middleware efficiently scalable
Inria Grenoble - Rhône-Alpes, LIG - Laboratoire d'Informatique de Grenoble
Abstract : In this paper we show how to construct an algorithm to sample the stationary distribution of a random walk over ${1,...,N}^d$ with forbidden arcs. This algorithm combines the rejection method and coupling from the past of a set of trajectories of the Markov chain that generalizes the classical sandwich approach. We also provide a complexity analysis of this approach in several cases showing a coupling time in $O(N^2 d log d )$ when no arc is forbidden and an experimental study of its performance.
Type de document :
Communication dans un congrès
QEST 2014 - 11th International Conference on Quantitative Evaluation of Systems, Sep 2014, Florence, Italy. Springer, 8657, pp.178-193, 2014, LNCS. 〈10.1007/978-3-319-10696-0_15〉
Domaine :

https://hal.inria.fr/hal-01069975
Contributeur : Florence Perronnin <>
Soumis le : mardi 30 septembre 2014 - 11:43:53
Dernière modification le : mercredi 29 novembre 2017 - 15:24:51

### Citation

Stéphane Durand, Bruno Gaujal, Florence Perronnin, Jean-Marc Vincent. A perfect sampling algorithm of random walks with forbidden arcs. QEST 2014 - 11th International Conference on Quantitative Evaluation of Systems, Sep 2014, Florence, Italy. Springer, 8657, pp.178-193, 2014, LNCS. 〈10.1007/978-3-319-10696-0_15〉. 〈hal-01069975〉

### Métriques

Consultations de la notice