An improved exact sampling algorithm for the standard normal distribution

DOI10.1007/S00180-021-01136-WMaRDI QIDQ2135885zbMATH OpenOpenAlexFDO

Authors Yusong Du, Baoying Fan, Baodian Wei

Publication date 10 May 2022

Published in Computational Statistics (Search for Journal in Brave)

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

zbMATH Keywords

discrete Gaussian distributionrandom number generationrejection sampling

Mathematics Subject Classification ID

Computational methods for problems pertaining to statistics (62-08) Random number generation in numerical analysis (65C10) Cryptography (94A60)

Abstract: In 2016, Karney proposed an exact sampling algorithm for the standard normal distribution. In this paper, we study the computational complexity of this algorithm under the random deviate model. Specifically, Karney's algorithm requires the access to an infinite sequence of independently and uniformly random deviates over the range (0,1). We give an estimate of the expected number of uniform deviates used by this algorithm until outputting a sample value, and present an improved algorithm with lower uniform deviate consumption. The experimental results also shows that our improved algorithm has better performance than Karney's algorithm.

Recommendations

• Sampling exactly from the normal distribution
• A fast normal random number generator
• An alias method for sampling from the normal distribution
• Algorithm 712: A normal random number generator
• A new algorithm for the normal distribution function

Cites work

• FACCT: FAst, Compact, and Constant-Time Discrete Gaussian Sampler over Integers
• Gaussian sampling over the integers: efficient, generic, constant-time
• scientific article; zbMATH DE number 3954145 (Why is no real title available?)
• scientific article; zbMATH DE number 3564899 (Why is no real title available?)
• scientific article; zbMATH DE number 3070115 (Why is no real title available?)
• Sampling exactly from the normal distribution
• Sampling from discrete Gaussians for lattice-based cryptography on a constrained device
• The complexity of generating an exponentially distributed variate
• The expected bit complexity of the von Neumann rejection algorithm
• Trapdoors for hard lattices and new cryptographic constructions
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures

Cited in

(3)

• Sampling exactly from the normal distribution
• scientific article; zbMATH DE number 2069495 (Why is no real title available?)
• Circuit privacy for FHEW/TFHE-style fully homomorphic encryption in practice

Describes a project that uses

Uses Software

• FACCT

This page was built for publication: An improved exact sampling algorithm for the standard normal distribution

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