I am going through the book probabilistic robotics by Sebastian Thrun. On page 102, it states that
For any interval $A \subset$ dom$(X)$, the empirical count of particles that fall into $A$ converges to the integral of $g$ under $A$: $$ \frac{1}{M} \sum_{m=1}^{M}I(x^{[m]} \in A) \to \int_{A} g(x)dx$$
I am assuming the particles $x^{[m]}$ are generated from the distribution $g(x)$. I actually don't know where this result comes from and I have been trying to link it to the law of large numbers.
If I wanted to get $\int_{A}g(x)dx$ by Monte Carlo, I would do the standard way of generating $x_{i}$ from a uniform distribution in $A$, then use the law of large numbers to evaluate the expectation $E(g(x))$ and multiply it by the scaling factor dictated by $A$.
$$ E(g(x)) = \int_{a}^{b}g(x)U(x)dx = \frac{1}{b-a}\int_{a}^{b}g(x)dx, $$ and so $$ \int_{a}^{b}g(x)dx = (b-a)E(g(x)), $$ the right hand side of which can be evaluated using the Law of Large Numbers. However, in this case, I am drawing samples from $g(x)$ itself. So how would I use the Law of Large Numbers in that case?
$$ E(g(x)) = \int_{a}^{b}g(x)g(x)dx = ?? $$
Any hints or keywords would be appreciated!
Alright, suppose you wish to estimate $ \int_A g(x) dx $, and you're only allowed to draw from the density function $ g(x) $.
Suppose that the support of the random variable $ X $ with density function $ g(\cdot) $ extends outside of $ A $ (if it didn't, then $ \int_A g(x) dx = 1 $ and you'd be done). Call the support of $ g(\cdot) $ $ \Omega $. Then clearly $ A \subseteq \Omega $.
We have that $$ \int_A g(x) dx = \int_\Omega \mathbb{1}\{x \in A\}g(x) dx = \mathbb{E} \{ \mathbb{1}\{X \in A \}\} = \mathbb{P}(A) $$ where $ P $ is the probability measure induced by $ X $.
This suggests an obvious but naive sampling procedure: take samples $ x_i $ from $ g(x) $, and estimate $ \mathbb{E} \{ 1\{X \in A\} \}$ with
$$ \frac{1}{N} \sum_{i=1}^N 1 \{x_i \in A\} $$
If $ A $ has very small probability under $ P $, then you might want to consider more sophisticated sample procedures: you can find these by looking for simulation variance reduction methods.