A new bijection on m-Dyck paths with application to random sampling

arXiv1603.06290MaRDI QIDQ6271693FDOQ6271693

Axel Bacher

Publication date: 20 March 2016

Abstract: We present a new bijection between variants of $m$-Dyck paths (paths with steps in $+1,-m$ starting and ending at height $0$ and remaining at non-negative height), which generalizes a classical bijection between Dyck prefixes and pointed {L}ukasiewicz paths. As an application, we present a new random sampling procedure for $m$-Dyck paths with a linear time complexity and using a quasi-optimal number of random bits. This outperforms Devroye's algorithm, which uses $mathcalO(nlogn)$ random bits.

This page was built for publication: A new bijection on m-Dyck paths with application to random sampling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6271693)