Perhaps the most commonly-cited (but not actually all that practical) example for rejection sampling is estimating the value of pi (as hinted by the first example under uniform random sampling): generate two random numbers between 0 and 1, then check the fraction of points that satisfy x^2 + y^2 <= 1. As number of samples tends to infinity, this will converge to pi/4. (You can instead take x,y from (-1,1) if you want to generate points on the full circle.)
> However, rejection sampling is only efficient when f_Omega can make use of a significant proportion of the probability density in f_D.
Perhaps a more relevant example: the unit n-sphere encloses a vanishing amount of volume as the number of dimensions increases.
> However, rejection sampling is only efficient when f_Omega can make use of a significant proportion of the probability density in f_D.
Perhaps a more relevant example: the unit n-sphere encloses a vanishing amount of volume as the number of dimensions increases.
https://en.wikipedia.org/wiki/Volume_of_an_n-ball
This is one of those weird consequences that gets labeled as the curse of dimensionality, especially in ML contexts.
"As the dimension d of the space increases, the hypersphere becomes an insignificant volume relative to that of the hypercube."
https://en.wikipedia.org/wiki/Curse_of_dimensionality#Distan...