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

Authors: Lucas Gerin 1

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)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: lattice paths,random sampling,MCMC,discrete Ricci curvature,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]

Consultation statistics

This page has been seen 332 times.
This article's PDF has been downloaded 259 times.