Sampling exactly from the normal distribution

Abstract

An algorithm for sampling exactly from the normal distribution is given. The algorithm reads some number of uniformly distributed random digits in a given base and generates an initial portion of the representation of a normal deviate in the same base. Thereafter, uniform random digits are copied directly into the representation of the normal deviate. Thus, in contrast to existing methods, it is possible to generate normal deviates exactly rounded to any precision with a mean cost that scales linearly in the precision. The method performs no extended precision arithmetic, calls no transcendental functions, and, indeed, uses no floating point arithmetic whatsoever; it uses only simple integer operations. It can easily be adapted to sample exactly from the discrete normal distribution whose parameters are rational numbers.

LaTeX, 8 pages, 1 figure. Revision includes algorithm for sampling discrete normal distribution. An implementation of the algorithms is available at http://exrandom.sf.net

References in corpus (1)

• Optimal Discrete Uniform Generation from Coin Flips, and Applications

Cited by in corpus (9)

• The Discrete Gaussian for Differential Privacy
• A quantum-inspired algorithm for estimating the permanent of positive semidefinite matrices
• The expected bit complexity of the von Neumann rejection algorithm
• Random variate generation using only finitely many unbiased, independently and identically distributed random bits
• An Improved Exact Sampling Algorithm for the Standard Normal Distribution
• Star-specific Key-homomorphic PRFs from Learning with Linear Regression
• Reconditioning your quantile function
• Improved Algorithms for White-Box Adversarial Streams
• Random Variate Generation with Formal Guarantees