Lucas Gerin
-
Random sampling of lattice paths with constraints, via transportation
dmtcs:2783 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2010,
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
-
https://doi.org/10.46298/dmtcs.2783
Random sampling of lattice paths with constraints, via transportationConference paper
We build and analyze in this paper Markov chains for the random sampling of some one-dimensional lattice paths with constraints, for various constraints. These chains are easy to implement, and sample an "almost" uniform path of length n in n3+ϵ steps. This bound makes use of a certain contraction property of the Markov chain, and is proved with an approach inspired by optimal transport.
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)