Comment by vitus
5 days ago
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
Hmmm I don't think that's how it works. If you're trying to estimate the ratio of the volume between A and B and B is contained in A, and you randomly sample from A, the probability that the sample also belongs to B is smaller the smaller the B/A ratio, yes that's the point of the methodology. It's not less "efficient", every single data point contributes to the estimate the same way.
If the ratio B/A is 1/1 and you sample 1M times, 100k of the samples will also be contained in B. Are you saying that the other 900k somehow go unused?!
If the ratio B/A is 1/100, and you sample the same number of times, only 10k of the samples will be contained in B. Are you saying that's less "efficient"? You need both the numerator and the denominator!
What is the ratio B/A is 1/100 and you'd say that the methodology is very inefficient here, and I tell you that actually we're estimating the ratio A/B. Does it become very efficient? Surely it can't change as the two ratios arent independent.
No, I think your comment misses the point (or I missed the point of your comment).
16 replies →