Improving the Florentine algorithms: recovering algorithms for Motzkin and Schr\"oder paths
classification
💻 cs.DS
math.CO
keywords
algorithmsflorentinepathsmotzkinoderrejectionschrachieve
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 1 Pith paper
-
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.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.