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).
> 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.
That's exactly it, though. Rejection sampling is not primarily used to estimate ratios, but rather to draw points from a distribution by sampling a broader distribution and then rejecting points that don't satisfy some criteria. If you're attempting to sample the unit hypersphere by picking N points between 0 and 1, and rejecting any sets where sum(x_i^2) > 1, then you're going to be throwing away most of your data points in the process.
Going back to the topic of volume ratio estimation, though: both of you are underestimating quite how quickly the volume drops off. The unit hypersphere's volume decreases super-exponentially (there's a factorial in the denominator!), so if you're dealing with a mere 50 dimensions, you're looking at a ratio of 10^-13 [0]. In that regime, adding an extra dimension shrinks that volume by a factor of about 3; by the time you get to 100, that factor increases to 4.
If you're still only sampling a million points, chances are very good that you're going to decide that the ratio is 0. In order to accurately estimate the ratio, you need progressively more and more samples just to compensate for a slight increase in dimension.
I'd expect it to be much more efficient to use the change-of-coordinates approach the article also mentions, although I have personally never thought about a coordinate system well-suited to the 50-dimensional hypersphere. Probably 49 angles and a radius that's basically almost always 1, and a weird Jacobian that I don't want to compute by hand?
Also, as I mentioned, using rejection sampling to estimate the value of pi is a cute exercise but quite useless in practice compared to any of the more direct methods. If you sample a million points in the unit square, you'll end up with 3.142 +/- 0.0016. Meanwhile, if you use the fourth continued fraction for pi (355/113), you already have 3.141592(9)... for far less computation.
[0] https://www.wolframalpha.com/input?i=volume+of+unit+49-ball
Ok, so instead of estimating B/A=1/100 just estimate A/B=100. What's the problem with this argument?
There are situations where you would use rejection sampling because generating 100x more random numbers is much cheaper than doing the complex calculations required to accurately model the space in question. Maybe 50 dimensions (and the 13 orders of magnitude difference) isn't big enough to raise those concerns. If we instead talk about 100 dimensions, then we're dealing with a difference of 40 orders of magnitude, and if you tell me that still doesn't matter, then I don't know what to say.
They're both problems. If you want to estimate 1e1000 via sampling individual points, then you need at least that order of magnitude of samples. If all of your data points fall in one class, then it doesn't matter what you're trying to calculate from that.
As I said: "If you're inverting the ratio we're estimating, then instead of estimating the value at 0, we're estimating it at infinity (or, okay, if you want to use Laplace smoothing, then a million, which is far too low)."
Ok so if the ratio is 1/2 how many samples do you need?
My entire point is that this becomes infeasible very quickly for numbers that are not all that big.
Second, your claim that it depends on dimension is wrong, given the ratio of sets, dimension doesn't matter. If the ratio is 1/2 then you'll reject one half of the times regardless of dimension, and so by your own argument it's "very efficient"