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.)<p>> However, rejection sampling is only efficient when f_Omega can make use of a significant proportion of the probability density in f_D.<p>Perhaps a more relevant example: the unit n-sphere encloses a vanishing amount of volume as the number of dimensions increases.<p><a href="https://en.wikipedia.org/wiki/Volume_of_an_n-ball" rel="nofollow">https://en.wikipedia.org/wiki/Volume_of_an_n-ball</a><p>This is one of those weird consequences that gets labeled as the curse of dimensionality, especially in ML contexts.<p>"As the dimension d of the space increases, the hypersphere becomes an insignificant volume relative to that of the hypercube."<p><a href="https://en.wikipedia.org/wiki/Curse_of_dimensionality#Distance_function" rel="nofollow">https://en.wikipedia.org/wiki/Curse_of_dimensionality#Distan...</a>
Slightly related, I once created an app that calculate the volume of a random shape using Monte Carlo <a href="https://github.com/victorqribeiro/monteCarlo">https://github.com/victorqribeiro/monteCarlo</a>