# Use Importance Sampling and Monte carlo for estimating a summation

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?

## 1 Answer

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.