A perfect sampling algorithm of random walks with forbidden arcs. Durand, S.; Gaujal, B.; Perronnin, F.; and Vincent, J. In 11th International Conference on Quantitative Evaluation of Systems (QEST), volume 8657, of LNCS, pages 178--193, Florence, Italy, September, 2014. Springer. 00000 bibtex: DurandGaujalPerronninVincent bibtex[x-id-hal=hal-01069975]abstract bibtex In this paper we show how to construct an algorithm to sample the stationary distribution of a random walk over 1,‥.,N$^\textrmd$ 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$^\textrm2$ d log d ) when no arc is forbidden and an experimental study of its performance.
@inproceedings{ durand_perfect_2014,
address = {Florence, Italy},
series = {{LNCS}},
title = {A perfect sampling algorithm of random walks with forbidden arcs},
volume = {8657},
abstract = {In this paper we show how to construct an algorithm to sample the stationary distribution of a random walk over 1,‥.,N$^{\textrm{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$^{\textrm{2}}$ d log d ) when no arc is forbidden and an experimental study of its performance.},
booktitle = {11th {International} {Conference} on {Quantitative} {Evaluation} of {Systems} ({QEST})},
publisher = {Springer},
author = {Durand, Stéphane and Gaujal, Bruno and Perronnin, Florence and Vincent, Jean-Marc},
month = {September},
year = {2014},
note = {00000 bibtex: DurandGaujalPerronninVincent
bibtex[x-id-hal=hal-01069975]},
pages = {178--193}
}