The expected bit complexity of the von Neumann rejection algorithm (Q2361447)

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.