1
$\begingroup$

Let $\{ B_i \}_{i=1}^n$ be a set of $n$ ball in the unit cube $C$ of dimension $d$.

If I want to estimate $$ \frac{ \lambda \left( \cup B_i \right) }{\lambda\left( C \right) }, \tag{1} $$ where $\lambda$ is Lebesgue Measure, is it ok to sample uniformly in the cube then count the number of point which fall in any ball?

I ask, because I saw a question saying that estimating the volume of a convex body is hard, and one needs special algorithm.

Is the estimation of (1) similar to the Dyer, Frieze, Kannan context, and a naive Monte Carlo is doomed to failed? If so why?

From some numerical tests, it seems to work.
Especially that I know in advance the volume of $\cup B_i$ is at least half the volume of the cube.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Adding to the question, is random sampling considered better or worse than counting points on a discrete grid? $\endgroup$
    – usul
    Commented Aug 27, 2014 at 15:06
  • 1
    $\begingroup$ What dimension are we talking about? How many balls? Naive Monte Carlo will converge, but it won't converge very fast; you get an error of about $1/\sqrt{n}$ in your ratio after $n$ samples. $\endgroup$
    – tmyklebu
    Commented Aug 29, 2014 at 18:16
  • $\begingroup$ @tmyklebu It's a 500 dimensional space, with 2,000 balls. ($d=500$, $n=2000$) $\endgroup$
    – user24451
    Commented Aug 29, 2014 at 18:41
  • 3
    $\begingroup$ @NicolasEssis-Breton: OK, that's really easy. The volume is, to a few hundred decimal places, zero. The biggest ball that fits inside the unit cube in 500 dimensions has volume $(\pi/4)^{250} / 250! \approxeq 2 \cdot 10^{-519}$, and you don't have many of them. Are you working with the intersection of a bunch of balls with the cube instead? $\endgroup$
    – tmyklebu
    Commented Aug 30, 2014 at 10:27
  • $\begingroup$ @tmyklebu You raised a good point. I will check again my numerics, because it gives me a non-zero volume. But, you are right that I'm working with the intersection of a bunch of balls with the cube. So the balls are not constrained to fit inside the cube. $\endgroup$
    – user24451
    Commented Aug 30, 2014 at 20:10

1 Answer 1

Reset to default
1
$\begingroup$

A naive Monte Carlo will always work, probabilistically, by the Law of Large Numbers. The problem only arises if you want guaranteed correctness, 100% chance as opposed to say 99.999%.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ The other problem is that convergence is very slow -- if you want more than a couple of correct digits, it might take quite long even on a modern computer. $\endgroup$
    – Federico Poloni
    Commented Aug 27, 2014 at 14:49

You must log in to answer this question.