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

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 Ł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 $\mathcal{O}(n\log n)$ random bits.

Cited by in corpus (2)

• Boltzmann sampling of irreducible context-free structures in linear time
• Improving the Florentine algorithms: recovering algorithms for Motzkin and Schröder paths