1
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.