REVIEW 2 cited by
Improving the Florentine algorithms: recovering algorithms for Motzkin and Schr\"oder paths
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
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.
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.