Geodesic
Random sampling of lattice paths with constraints, via transportation
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010) Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

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. 
@article{DMTCS_2010_special_258_a19,
     author = {Gerin, Lucas},
     title = {Random sampling of lattice paths with constraints, via transportation},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2010},
     volume = {DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)},
     doi = {10.46298/dmtcs.2783},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2783/}
}
TY  - JOUR
AU  - Gerin, Lucas
TI  - Random sampling of lattice paths with constraints, via transportation
JO  - Discrete mathematics & theoretical computer science
PY  - 2010
VL  - DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2783/
DO  - 10.46298/dmtcs.2783
LA  - en
ID  - DMTCS_2010_special_258_a19
ER  - 
%0 Journal Article
%A Gerin, Lucas
%T Random sampling of lattice paths with constraints, via transportation
%J Discrete mathematics & theoretical computer science
%D 2010
%V DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2783/
%R 10.46298/dmtcs.2783
%G en
%F DMTCS_2010_special_258_a19
Gerin, Lucas. Random sampling of lattice paths with constraints, via transportation. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10), DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) (2010). doi: 10.46298/dmtcs.2783

Cité par Sources :