Improving the Florentine algorithms: recovering algorithms for Motzkin and Schr\"oder paths
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Leap generators for composition schemes
Leap generators for supercritical composition schemes C = A ∘ B yield linear-time exact-size samplers whose output distribution on size-n objects has total variation distance (c + o(1)) n^{-1/2} from uniform.
-
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.