Shen Jing, Du Yusong
In 2016, Karney proposed an exact sampling algorithm for the standard normal distribution. In this article, we present an exact sampling algorithm for the normal distribution of standard variance $\sqrt{1/(2\ln2)}$ and mean $0$, which can be called the binary Gaussian distribution, as its relative probability density function is given by $2^{-x^2}$ for $x\in\mathbb{R}$. Our proposed algorithm requires no floating-point arithmetic in practice, and can be regarded as the promotion of Karney's exact sampling technique. We give an estimate of the expected number of uniform deviates over the range $(0,1)$ used by this algorithm until outputting a sample value. Numerical experiments also demonstrate the effectiveness of the sampling algorithm. For any rational number $c$ greater than $1$ but less than Euler's number $e$, the idea of sampling exactly the binary Gaussian is generalized to a class of normal distributions of standard variance $\sqrt{1/(2\ln{c})}$ and mean $0$, called “$c$-ary Gaussian distributions”, and a similar complexity analysis is presented.
