Sampling exactly from the normal distribution
From MaRDI portal
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.
Recommendations
Cites work
- A Note on the Generation of Random Normal Deviates
- A simple method for generating gamma variables
- Accuracy in Random Number Generation
- Algorithm 488: A Gaussian pseudo-random number generator
- Characterizations of a discrete normal distribution
- Computer Generation of Random Variables Using the Ratio of Uniform Deviates
- Extensions of Forsythe's Method for Random Sampling from the Normal Distribution
- Extensions of von Neumann's Method for Generating Random Variables
- scientific article; zbMATH DE number 43417 (Why is no real title available?)
- scientific article; zbMATH DE number 3614066 (Why is no real title available?)
- scientific article; zbMATH DE number 1052006 (Why is no real title available?)
- scientific article; zbMATH DE number 3273551 (Why is no real title available?)
- Mersenne twister
- MPFR
- On Buffon machines and numbers
- On lattices, learning with errors, random linear codes, and cryptography
- Sampling from discrete Gaussians for lattice-based cryptography on a constrained device
- The complexity of generating an exponentially distributed variate
- Von Neumann's Comparison Method for Random Sampling from the Normal and Other Distributions
Cited in
(18)- Faster Gaussian sampling for trapdoor lattices with arbitrary modulus
- An alias method for sampling from the normal distribution
- On the rejection rate of exact sampling algorithm for discrete Gaussian distributions over the integers
- Implementation of lattice trapdoors on modules and applications
- An improved exact sampling algorithm for the standard normal distribution
- Secure random sampling in differential privacy
- The expected bit complexity of the von Neumann rejection algorithm
- scientific article; zbMATH DE number 5121144 (Why is no real title available?)
- scientific article; zbMATH DE number 5653860 (Why is no real title available?)
- Isochronous Gaussian sampling: from inception to implementation
- COSAC: COmpact and Scalable Arbitrary-Centered Discrete Gaussian Sampling over Integers
- Homomorphic Encryption Standard
- Sampling from arbitrary centered discrete Gaussians for lattice-based cryptography
- Exact sublinear binomial sampling
- How to sample a discrete Gaussian (and more) from a random oracle
- Identity-based encryption from lattices using approximate trapdoors
- Circuit privacy for FHEW/TFHE-style fully homomorphic encryption in practice
- Sampling from discrete Gaussians for lattice-based cryptography on a constrained device
This page was built for publication: Sampling exactly from the normal distribution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828164)
