Skip to Main content Skip to Navigation
Conference papers

Random sampling of lattice paths with constraints, via transportation

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 $n^{3+\epsilon}$ steps. This bound makes use of a certain $\textit{contraction property}$ of the Markov chain, and is proved with an approach inspired by optimal transport.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 20, 2015 - 4:32:59 PM
Last modification on : Tuesday, March 2, 2021 - 10:08:24 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 9:48:42 AM


Publisher files allowed on an open archive


  • HAL Id : hal-00439479, version 4


Lucas Gerin. Random sampling of lattice paths with constraints, via transportation. 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), 2010, Vienna, Austria. pp.317-328. ⟨hal-00439479v4⟩



Record views


Files downloads