Comment by vitus
5 days ago
I mean, yes, you can estimate this for low dimension. It's a bad idea given how slow the convergence is, but you can do it.
My entire point is that this becomes infeasible very quickly for numbers that are not all that big.
First off, you didn't answer my question which to restate is: if the ratio is 1/2, how many samples do you need.
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"
> First off, you didn't answer my question which to restate is: if the ratio is 1/2, how many samples do you need.
Are we just trying to estimate the ratio? To what desired accuracy? If you have 100 samples and find that 50 points landed in your smaller set, okay, you can be 95% sure that the ratio is between 40% and 60%. That's not a very good estimate. If you want to drive those error bars down by 2x, you need 4x as many samples.
> 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"
When your sets in question are the volume enclosed by the n-dimensional unit hypersphere and the volume enclosed by the corresponding hypercube, which is what I assume we've been discussing this whole time, you do not get to pick what your ratio is between your sets for a given choice of n. If you're dealing with a 3-dimensional unit sphere and picking three random values uniformly between 0 and 1 (i.e. constrained to the positive octant), you will land within the hypersphere with probability pi/6 (close to your one-half ratio). You can't decide "okay now my ratio is 99%" unless you change how you draw your samples.
You can draw however many samples you want from the 100-dimensional unit hypercube to estimate the volume of the 100-dimensional unit hypersphere, and all you'll ever get is "the ratio is somewhere between 0 and some very small number, with X% probability".
Either way, as I have said multiple times, you are completely missing the point of rejection sampling by overindexing on the toy example that I explicitly stated is not a good use of rejection sampling.
> Are we just trying to estimate the ratio? To what desired accuracy?
Exactly. Number of samples depends on volume ratio and accuracy. It depends on dimension only through these two numbers. You got there in the end, proud of you.
2 replies →