4 ms·
Hmm, I don't buy it. The simplicity of just normalizing some Gaussian random deviates (especially since you generate them two at a time using Box-Muller) seems
by sfpotter 1y ago
Hmm, I don't buy it. The simplicity of just normalizing some Gaussian random deviates (especially since you generate them two at a time using Box-Muller) seems better than accept-reject. Especially considering that the ratio of the volume of the n-dimensional ball to the volume of [-1, 1]^n tends to zero as n tends to infinity exponentially fast...
- Sharlin 1y agoAymptotic behavior doesn't really matter given that this algorithm is almost exclusively used with n=3.
- sfpotter 1y agoIt is? How do you know? You're saying there are no uses in statistics, data science, numerical linear algebra, etc?
- Sharlin 1y agoUm, exactly because it’s fast in 3D (particularly Marsaglia’s two-variate version) but rapidly becomes useless in higher dimensions.
- sfpotter 1y agoSo, I guess the asymptotic behavior does matter, and what I saying was relevant?
- Sharlin 1y agoI'm not sure if you're being difficult on purpose. What I meant is that there's a specific use case for the rejection sampling algorithm, namely computer graphics, and in that use case the asymptotic behavior is irrelevant because n will never not be 3. What is relevant is that the algorithm is more obvious to non-statisticians than Box-Muller, and Marsaglia's variant in particular is also more efficient. Sqrt, ln, and sincos aren't particularly fast operations even on modern hardware (and the latter two aren't SIMDable either), whereas generating uniform variates is almost free in comparison.