[sfpotter]

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]

Aymptotic behavior doesn't really matter given that this algorithm is almost exclusively used with n=3.

[sfpotter]

It is? How do you know? You're saying there are no uses in statistics, data science, numerical linear algebra, etc?

[Sharlin]

Um, exactly because it’s fast in 3D (particularly Marsaglia’s two-variate version) but rapidly becomes useless in higher dimensions.

[sfpotter]

So, I guess the asymptotic behavior does matter, and what I saying was relevant?

[Sharlin]

I'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.