Complexity of Anticipated Rejection Algorithms and the Darling-Mandelbrot Distribution
arXiv:1508.05634 · doi:10.1007/s00453-015-0040-8
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.
20 pages. Using Algorithmica LaTeX style