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.
Because if you are trying to draw samples from a hypersphere via rejection sampling from samples of the hypercube, your sampling efficiency will go down exponentially with dimensionality. A smaller and smaller percentage of your samples will go unrejected as dimensionality grows
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.
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...
Why does the volume of the hypersphere relative to the volume of the hypercube matter?
Because if you are trying to draw samples from a hypersphere via rejection sampling from samples of the hypercube, your sampling efficiency will go down exponentially with dimensionality. A smaller and smaller percentage of your samples will go unrejected as dimensionality grows
17 replies →
Slightly related, I once created an app that calculate the volume of a random shape using Monte Carlo https://github.com/victorqribeiro/monteCarlo