The expected bit complexity of the von Neumann rejection algorithm

DOI10.1007/S11222-016-9648-ZMaRDI QIDQ2361447zbMATH OpenOpenAlexFDO

Authors Claude Gravel, Luc Devroye

Publication date 30 June 2017

Published in Statistics and Computing (Search for Journal in Brave)

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

zbMATH Keywords

acceptance-rejection methodbisection algorithmentropyrandom bit modelrandom number generationrandom samplingrejection algorithmtree-based algorithmsvon Neumann sampling algorithm

Mathematics Subject Classification ID

Random number generation in numerical analysis (65C10) Complexity and performance of numerical algorithms (65Y20)

Abstract: In 1952, von Neumann introduced the rejection method for random variate generation. We revisit this algorithm when we have a source of perfect bits at our disposal. In this random bit model, there are universal lower bounds for generating a random variate with a given density to within an accuracy $epsilon$ derived by Knuth and Yao, and refined by the authors. In general, von Neumann's method fails in this model. We propose a modification that insures proper behavior for all Riemann-integrable densities on compact sets, and show that the expected number of random bits needed behaves optimally with respect to universal lower bounds. In particular, we introduce the notion of an oracle that evaluates the supremum and infimum of a function on any rectangle of $mathbb{R}^d$, and develop a quadtree-style extension of the classical rejection method.

Review text

The authors study the acceptance-rejection method under the assumption of a random bit model, i.e., the access to an infinite sequence of i.i.d. symmetric Bernoulli bits. Due to results by Knuth and Yao to generate a (discrete) random variable \(X\) the expected number of random bits required, by any algorithm, is at least the entropy of \(X\). Based on a bisection algorithm, the authors introduce algorithms for the approximation of random variables with continuous densities (on \(\mathbb{R}^d\)). Therefore, they make use of an oracle to evaluate the supremum/infimum of the function on rectangles and a quadtree tree structure. In particular, for Riemann-integrable densities with compact and non-compact support, they present rejection algorithms and prove that the expected number of bits required behaves optimally with respect to the universal lower bounds.

Recommendations

• Von Neumann’s Rejection Technique Reexamined
• Generating random numbers by adapted rejection
• Acceptance–Rejection Sampling Made Easy
• A note on generating random variables with log-concave densities
• A note on transformed density rejection

Cites work

• Exact Classical Simulation of the Quantum-Mechanical GHZ Distribution
• Foundations of multidimensional and metric data structures.
• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 3614066 (Why is no real title available?)
• Interval algorithm for random number generation
• Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
• On the dimension and entropy of probability distributions
• Sampling exactly from the normal distribution
• Some remarks on the dimension and entropy of random variables

Cited in

(6)

• An improved exact sampling algorithm for the standard normal distribution
• Complexity of anticipated rejection algorithms and the Darling-Mandelbrot distribution
• On Global Costs and Nyquist's Theorem in Random Variate Generation
• scientific article; zbMATH DE number 4110061 (Why is no real title available?)
• Von Neumann’s Rejection Technique Reexamined
• Binary decompositions of probability densities and random-bit simulation

This page was built for publication: The expected bit complexity of the von Neumann rejection algorithm

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