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}
}
Downloads: 0