A perfect sampling algorithm of random walks with forbidden arcs

In this paper we show how to construct an algorithm to sample the stationary distribution of a random walk over a grid 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 that is logarithmic in the size of the grid, when no arc is forbidden, and an experimental study of its performance.

Data and Resources

Additional Info

Field Value
Source https://inria.hal.science/hal-00964098
Author Durand, Stéphane, Gaujal, Bruno, Perronnin, Florence, Vincent, Jean-Marc
Maintainer CCSD
Last Updated May 5, 2026, 21:49 (UTC)
Created May 5, 2026, 21:49 (UTC)
Identifier Report N°: RR-8504
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Middleware efficiently scalable (MESCAL) ; Centre Inria de l'Université Grenoble Alpes ; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire d'Informatique de Grenoble (LIG) ; Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Pierre Mendès France - Grenoble 2 (UPMF)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP)-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)
creator Durand, Stéphane
date 2014-03-24T00:00:00
harvest_object_id 43576742-2c7f-4b42-8807-1986139c014f
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-09-27T00:00:00
set_spec type:REPORT