4
$\begingroup$

I am interested in approximating the volume of a subset $S$ of a hypercube in $d$ dimensions through Monte Carlo. The idea would then be that I have a large number of uniformly distributed samples in the hypercube and find the proportion of samples that lie in $S$.

My question is then: suppose that I use 10000 samples in $[0,1]^2$ to approximate the volume of $S_1 \in [0,1]^2$.

Would I get the same level of accuracy if I were to use 10000 samples in $[0,1]^3$ to approximate the volume of $S_2 \in [0,1]^3$?

I'm asking because intuitively, as I increase the dimension, it seems to me that more samples in the hypercube are needed to "fill in the space."

But if you think of it in numbers, computing the density of samples in both cases, it turns out that they're the same since the volume of both hypercubes is 1, regardless of the dimension.

Am I thinking about it from the wrong perspective? Should more samples be used in higher dimensions?

$\endgroup$
4
  • 1
    $\begingroup$ For random sequences, you get an error $\sim 1/\sqrt{N}$ from $N$ samples. Using quasi-random sequences reduces the error to $\sim 1/N$. Also look for the "curse of dimensionality". $\endgroup$ Oct 22, 2016 at 20:24
  • $\begingroup$ You don't actually need to fill in the space, that's part of the beauty of Monte Carlo. What you need to do is to take into account enough samples to cancel out the impact of the standard deviation of whatever you're averaging. If the domains you're sampling from have the same volume, say $1$ for simplicity of presentation, in both cases, then this just boils down to which of the volumes is closer to $1/2$. That one will perform worse. Since the area of the unit disk is $\pi/4$ and the volume of the 3D unit sphere is $\pi/6$, the sphere will perform worse. $\endgroup$
    – Ian
    Oct 23, 2016 at 12:04
  • $\begingroup$ I think the trend is reversed as you increase the dimension even further (since the volume of the unit sphere goes to zero with the dimension). $\endgroup$
    – Ian
    Oct 23, 2016 at 12:06
  • $\begingroup$ Sorry, "unit" meant "radius 1/2", since we're talking about embedding everything in the unit cube... $\endgroup$
    – Ian
    Oct 23, 2016 at 12:14

1 Answer 1

2
$\begingroup$

Although LutzL concisely referred to the key points in a comment to the question, I thought opening up the explanation a bit. (I believe it is useful to know rough idea and strengths of a method even when you do not immediately need to apply the knowledge, because when you have lots of tools at your disposal, you can choose the most appropriate one to apply. Not having to always resort to a cheap hammer is a good thing, in my opinion.)

suppose that I use 10000 samples in $[0,1]^2$ to approximate the volume of $S_1 \in [0,1]^2$. Would I get the same level of accuracy if I were to use 10000 samples in $[0,1]^3$ to approximate the volume of $S_2 \in [0,1]^3$?

Yes, but only because both are unit volumes (i.e., $1^D = 1$ for all $D \in \mathbb{Z}$, number of dimensions $D \ge 1$).

The Wikipedia page on Monte Carlo integration has a good summary. In short, the error estimate of the volume estimate $Q$ obtained using simple Monte Carlo integration is $$\delta Q \approx V \frac{\delta_N}{\sqrt{N}}$$ i.e. standard error of the mean multiplied by the volume $V$. As mentioned on the Wikipedia page, it is important to realize that this is not a strict error bound, and the actual error may be larger.

Although the Wikipedia page says that the naive Monte Carlo integration is rarely useful, it's not backed by any facts. I've found it to be quite useful in a large number of cases myself.

True, you do not normally wish to sample the entire volume, especially for large volumes; you want to omit the simple subvolumes you know are completely inside or outside, so you only sample the subvolumes you are uncertain of. For example, if you have a shape that is mostly spherical (at average radius $R$) but contains "fuzz" or surface detail or other deviation from the spherical shape that you know is limited to distances $R-r$ to $R+r$ from the center, you would definitely just sample the spherical shell at $R-r$ to $R+r$. (The volume is then the estimated volume of the spherical shell, plus the volume of the assumed $R-r$-radius sphere.) While this may technically fall under importance sampling, I personally think of it as just simple Monte Carlo integration of the interesting subvolumes.

So, based on how I interpret your question, and the last statement,

Am I thinking about it from the wrong perspective? Should more samples be used in higher dimensions?

I'd say you are thinking about it from a valid perspective.

The number of samples gives you a rough relative error estimate of the volume estimate, $1/\sqrt{N}$; $10,000$ samples should give you about two digits of precision in the volume estimate. So, if you need a specific order of magnitude absolute error estimate, then you do need to consider the total sampled volume, and that may be surprisingly huge for large number of dimensions. (Although you could say that is just a limitation in human perception, I guess.)

I'd say your suspicions about higher dimensions are also on the right track, if your suspicions about high number of dimensions is related to the fact that our intuition about the total volume by just looking at the coordinate range involved is only valid for 1, 2, or 3 dimensions, you're on the right track. There is nothing weird about high number of dimensions, except that our intuition does not work, so we must be careful and check -- here, calculate an initial rough estimate, as in order of magnitude, of the volume --, instead of just assuming things we might feel obvious or familiar.

So, be suspicious of assumptions, yes. But, there is no reason to fear or be suspicious about high number of dimension; just be careful and meticulous, so you don't accidentally make stupid assumptions (that might be quite sane and safe in low number of dimensions).

$\endgroup$
6
  • $\begingroup$ The problem with naive Monte Carlo is easiest to see in 1D: the standard deviation of the Bernoulli random variable for, say, lying under a curve $y=f(x)$ in $[0,1]^2$ is significantly higher than the standard deviation of $f(U)$ where $U$ is uniform on $[0,1]$. This slows the convergence. Seeing as you had to evaluate $f(U)$ to do this calculation in the first place, you're throwing away information that you actually did the work to obtain anyway. $\endgroup$
    – Ian
    Oct 23, 2016 at 12:02
  • $\begingroup$ But sometimes you can "cheat", and compute this Bernoulli random variable without doing a function evaluation. Or sometimes acquiring a random point in the "domain" in higher dimensions can be difficult; for example, to use the "f(U)" approach to compute the volume of a sphere, you need to be able to draw points from a disk. In this case the Bernoulli approach can also be useful. $\endgroup$
    – Ian
    Oct 23, 2016 at 12:02
  • $\begingroup$ @Ian: Very good points. My cases typically involve only trivial functions (geometric shapes). The most recent use case is the estimation of a 3D solid angle for a specific geometry of a radiation detector. I often use Xorshift64* PRNG variants and the exclusion method to generate the samples -- several million a second on even a laptop -- so the convergence is not an issue; complex functions are several orders of magnitude slower to calculate, so even a hundred-fold increase in samples is 'cheaper'. Also, one should consider time spent developing the calculation, and verifying it is correct. $\endgroup$ Oct 23, 2016 at 13:01
  • $\begingroup$ @Ian: In other words, my use cases are probably quite a weird subset of the entire domain of problems where Monte Carlo integration is applicable, thus have a limited/skewed view. You could write an answer pointing out the differences, perhaps with references you've found useful? Perhaps you have even some anecdotal info on high-dimensional Monte Carlo integration? I think it would be very valuable, especially since this question is easily found via a web search for Monte Carlo volume dimensions.. $\endgroup$ Oct 23, 2016 at 13:10
  • $\begingroup$ I might be able to say some things about our different experiences. I know one problem in practical application has to do with shared entropy between threads. Part of that is literally not having enough availability of entropy to share between multiple threads of the same processor, but a deeper issue has to do with running PRNGs in parallel. It turns out that avoiding cross-correlations when running parallel PRNGs is incredibly difficult. Google "parallel Monte Carlo" for details. This generally is exacerbated if you use more samples, so it can be a motivation to try to use fewer. $\endgroup$
    – Ian
    Oct 23, 2016 at 21:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .