Complexity of Anticipated Rejection Algorithms and the Darling–Mandelbrot Distribution
Complexity of Anticipated Rejection Algorithms and the Darling–Mandelbrot Distribution
复制标题
预期拒绝算法的复杂性和 Darling-Mandelbrot 分布
作者：
A. Bacher;A. Sportiello
我们用极限法则研究一些预期拒绝随机采样算法的复杂性。我们用概率过程（阈值和过程）来表达这种复杂性。我们证明，在适当的条件下，复杂性是线性的，并且承认所谓的 Darling-Mandelbrot 分布作为极限法则，由 Darling (Trans Am Math Soc 73:95–107, 1952) 和 Lew (Constr Approx 10(1):15–30, 1994) 研究。我们还给出了 Darling-Mandelbrot 分布的密度的明确形式，并推导了它的一些分析性质。
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.