6
$\begingroup$

Maybe my question is pretty basic and dumb. I'm studying computer science. In one problem i have to use Monte Carlo method and Importance sampling in order to estimate a big sum. I've seen Monte Carlo integration that may be the same but i am confused.

All i have to do is to find a way to approximate this sum:

$$ A =\sum_{c=1}^{C} a(c)\text{ ,} $$ where C a very large number.

In the case of Importance sampling i can understand that, given a distribution $q$, $$A =\sum_{c=1}^{C} \frac{a(c)q}{q} = E_q[\frac{a(c)}{q}] $$ and then we approximate it as: $$A \approx \frac{1}{S}\sum_{s=1}^{S}\frac{a(s)}{q(s) }$$ Is that correct? How could i use Simple Monte Carlo?

$\endgroup$
1
$\begingroup$

As stated your question does not make complete sense: if you are only interested in$$\mathfrak{A} =\sum_{c=1}^{C} a(c)$$and if $C$ is too large for the computation to be done, then representing $\mathfrak{A}$ as an expectation$$\mathfrak{A}=\mathbb{E}[\mathscr{A}(X)]$$can be a way to approximate $\mathfrak{A}$ by a Monte Carlo approximation: by the Law of Large Numbers, generating a sample $X_1,\ldots,X_n$ from the distribution associated with the expectation $\mathbb{E}[\mathscr{A}(X)]$ leads to a converging (in $n$) estimator$$\hat{\mathfrak{A}}_n=\frac{1}{n}\sum_{i=1}^n\mathscr{A}(X_i)]$$The key notion in Monte Carlo approximations is that the said distribution is almost arbitrary. One naïve solution is to see $\mathfrak{A}$ as the expectation of $C a(\cdot)$ against the Uniform distribution on $\{1,\ldots,C\}$. But almost any other choice is acceptable, in that, given a probability distribution $q(\cdot)$ positive everywhere on $\{1,\ldots,C\}$, the identity $$\mathfrak{A}=\mathbb{E}_q[\mathscr{A}(X)/q(X)]$$stands. This means that generating from $q$, i.e., producing a sample $X_1,\ldots,X_n$ distributed from $q$, the approximation$$\hat{\mathfrak{A}}_n=\frac{1}{n}\sum_{i=1}^n\mathscr{A}(X_i)]/q(X_i)$$also is a converging (in $n$) estimator. The choice of $q$ matters: The closer $q$ is to $|a|$, the better the approximation.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.