Random sampling of lattice paths with constraints, via transportation
Lucas Gerin
Abstract
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+&eps; steps. This bound makes use of a certain contraction property of the Markov chain, and is proved with an approach inspired by optimal transport.
Full Text: PostScript PDF