2
$\begingroup$

I want to calculate the expected value of some function call with a random variable with known probability distribution:

$$\mathbb{E}(f(X))$$

The probability distribution of $X$ is discrete. Of course, I could calculate this expected value as $$\sum_{x\in X} p(x)f(x)$$ where $x\in X$ is meant as some value that $X$ can take on. This is possible because the probability that $X$ takes on $x$ is known as $p(x)=\mathbb{P}(X=x)$.

However, the number of values that $X$ can take on is extremely large and I need a good approximation in short time.

My idea is to have a Monte Carlo simulation to get this expected value... So, I sample some values $\hat{X}=(x_1, x_2, x_3, x_4, ...) \in X$ and calculate my $\mathbb{E}(f(X))$ as $$\frac{1}{|\hat{X}|}\sum_{\hat{x} \in \hat{X}}f(\hat{x})$$ which works quite well, when I sample many values.

My question is: Can I exploit that I know $p(\hat{x})$ to get a more precise result with the same number of samples or an equally good result with fewer samples? I thought of something like weighting my sampled values with the probability like: $$\frac{\sum_{\hat{x} \in \hat{X}}p(\hat{x})f(\hat{x})}{\sum_{\hat{x} \in \hat{X}} p(\hat{x})}$$

However, so far I could not find any theoretical foundation for that... Does this work? If yes, how would some proof look like (or what is a book/paper that covers it?) If not, can I in some other way exploit the probability?

$\endgroup$
3
  • $\begingroup$ Take a look at en.wikipedia.org/wiki/Importance_sampling and en.wikipedia.org/wiki/… $\endgroup$
    – Kibble
    Commented Feb 4, 2017 at 15:49
  • $\begingroup$ Hi @IceFire, I was wondering how you ended up solving this issue? I am having a very similar problem at hand. $\endgroup$
    – Faser
    Commented May 12, 2022 at 6:37
  • $\begingroup$ Actually, I did not find a solution and just went with a different approach $\endgroup$
    – IceFire
    Commented May 12, 2022 at 15:20

0

You must log in to answer this question.

Browse other questions tagged .