1. An Improved Exact Sampling Algorithm for the Standard Normal Distribution
- Author
-
Baoying Fan, Yusong Du, and Baodian Wei
- Subjects
FOS: Computer and information sciences ,Statistics and Probability ,Computational complexity theory ,Improved algorithm ,Sampling (statistics) ,Expected value ,Normal distribution ,Computational Mathematics ,G.3.10 ,Computer Science - Data Structures and Algorithms ,Range (statistics) ,Data Structures and Algorithms (cs.DS) ,65C10 ,Statistics, Probability and Uncertainty ,Algorithm ,Mathematics - 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.
- Published
- 2020