Complexity of anticipated rejection algorithms and the Darling-Mandelbrot distribution

DOI10.1007/S00453-015-0040-8MaRDI QIDQ308957zbMATH OpenOpenAlexFDO

Authors Axel Bacher, Andrea Sportiello

Publication date 6 September 2016

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1508.05634

zbMATH Keywords

limit distributionanalysis of algorithmsrandom samplinganticipated rejectionDarling-Mandelbrot distributionsum of i.i.d. random variables

Mathematics Subject Classification ID

Probability distributions: general theory (60E05) Central limit and other weak theorems (60F05) Analysis of algorithms (68W40)

Abstract: We study in limit law the complexity of some anticipated rejection random sampling algorithms. We express this complexity in terms of a probabilistic process, the threshold sum process. We show that, under the right conditions, the complexity is linear and admits as a limit law a so-called Darling-Mandelbrot distribution, studied by Darling (Trans Am Math Soc 73:95-107, 1952) and Lew (Constr Approx 10(1):15-30, 1994). We also give an explicit form to the density of the Darling-Mandelbrot distribution and derive some of its analytic properties.

Recommendations

• Anticipated rejection algorithms and the Darling-Mandelbrot distribution
• The expected bit complexity of the von Neumann rejection algorithm
• Generating random numbers by adapted rejection
• Density approximation and exact simulation of random variables that are solutions of fixed-point equations
• Von Neumann’s Rejection Technique Reexamined

Cites work

• A guide to first-passage processes
• Asymptotic properties of some underdiagonal walks generation algorithms
• Basic analytic combinatorics of directed lattice paths
• Directed and multi-directed animals on the king's lattice
• Efficient random sampling of binary and unary-binary trees via holonomic equations
• On the Darling-Mandelbrot probability density and the zeros of some incomplete gamma functions
• Random Walks and Quantum Gravity in Two Dimensions
• Random walks in cones
• Schröder's paths and random hierarchies
• The Influence of the Maximum Term in the Addition of Independent Random Variables
• The random generation of directed animals
• The random generation of underdiagonal walks
• Values of Brownian intersection exponents. I: Half-plane exponents
• Values of Brownian intersection exponents. II: Plane exponents
• Values of Brownian intersection exponents. III: Two-sided exponents
• Walks with small steps in the quarter plane

Cited in

(5)

• Size biased sampling from the Dickman subordinator
• Anticipated rejection algorithms and the Darling-Mandelbrot distribution
• Energy-constrained random walk with boundary replenishment
• Taming reluctant random walks in the positive quadrant
• Weighted lattice walks and universality classes

This page was built for publication: Complexity of anticipated rejection algorithms and the Darling-Mandelbrot distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q308957)