Leap generators for supercritical composition schemes C=A∘B sample exact-size structures in expected linear time, with total variation distance from uniform asymptotically |s−1|σ/√(2πμ)·n^{−1/2}, reducible to any n^{−(r+1)/2} rate by a rejection step.
Improving the Florentine algorithms: recovering algorithms for Motzkin and Schr¨ oder paths
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
We present random sampling procedures for Motzkin and Schr\"oder paths, following previous work on Dyck paths. Our algorithms follow the anticipated rejection method of the Florentine algorithms (Barcucci et al. 1994+), but introduce a recovery idea to greatly reduce the probability of rejection. They use an optimal amount of randomness and achieve a better time complexity than the Florentine algorithms.
years
2026 2representative citing papers
The authors connect k-coloured Motzkin paths to odd-height prefixes and supply a linear-time random generation algorithm.
citing papers explorer
-
Leap generators for composition schemes
Leap generators for supercritical composition schemes C=A∘B sample exact-size structures in expected linear time, with total variation distance from uniform asymptotically |s−1|σ/√(2πμ)·n^{−1/2}, reducible to any n^{−(r+1)/2} rate by a rejection step.
-
Random Generation of $k$-coloured Motzkin Paths
The authors connect k-coloured Motzkin paths to odd-height prefixes and supply a linear-time random generation algorithm.