Introduces random bit recycling for linear-time uniform generation of fixed-Hamming-weight binary words with near-Shannon-entropy random bit consumption.
Optimal Discrete Uniform Generation from Coin Flips, and Applications
5 Pith papers cite this work, alongside 15 external citations. Polarity classification is still indexing.
5
Pith papers citing it
15
external citations · Pith
abstract
This article introduces an algorithm to draw random discrete uniform variables within a given range of size n from a source of random bits. The algorithm aims to be simple to implement and optimal both with regards to the amount of random bits consumed, and from a computational perspective---allowing for faster and more efficient Monte-Carlo simulations in computational physics and biology. I also provide a detailed analysis of the number of bits that are spent per variate, and offer some extensions and applications, in particular to the optimal random generation of permutations.
representative citing papers
A new algorithm synthesizes entropy-optimal, exact random variate generators from finite-precision CDF specifications in any binary number format.
A conditional weakest-precondition calculus for quantum programs with observations computes posterior probabilities and matches the operational semantics.
A new sampler for discrete distributions using coin flips that combines linearithmic space, negligible runtime overhead, and entropy-optimal expected flips in [H(P), H(P)+2).
citing papers explorer
-
Entropic Generation of Binary Words
Introduces random bit recycling for linear-time uniform generation of fixed-Hamming-weight binary words with near-Shannon-entropy random bit consumption.
-
Random Variate Generation with Formal Guarantees
A new algorithm synthesizes entropy-optimal, exact random variate generators from finite-precision CDF specifications in any binary number format.
-
Bayesian Inference in Quantum Programs
A conditional weakest-precondition calculus for quantum programs with observations computes posterior probabilities and matches the operational semantics.
-
Efficient Rejection Sampling in the Entropy-Optimal Range
A new sampler for discrete distributions using coin flips that combines linearithmic space, negligible runtime overhead, and entropy-optimal expected flips in [H(P), H(P)+2).
- Algorithms, Complexity, and Entropy of the Bernard-Letac Fair-Sampling Construction