# Difference between revisions of "importance Sampling June 2 2009"

From statwiki

(Created page with 'test') |
m (Conversion script moved page Importance Sampling June 2 2009 to importance Sampling June 2 2009: Converting page titles to lowercase) |
||

(2 intermediate revisions by one other user not shown) | |||

Line 1: | Line 1: | ||

− | + | In <math>I = \displaystyle\int h(x)f(x)\,dx</math>, Monte Carlo simulation can be used only if it easy to sample from f(x). Otherwise, another method must be applied. If sampling from f(x) is difficult but there exists a probability distribution function g(x) which is easy to sample from, then <math>I</math> can be written as<br> | |

+ | :: <math>I = \displaystyle\int h(x)f(x)\,dx </math> | ||

+ | :: <math>= \displaystyle\int \frac{h(x)f(x)}{g(x)}g(x)\,dx</math> | ||

+ | :: <math>= \displaystyle E_g(w(x)) \rightarrow</math>the expectation of w(x) with respect to g(x) | ||

+ | :: <math>= \frac{\displaystyle\sum_{i=1}^{N} w(x_i)}{N}</math> where <math>\displaystyle w(x) = \frac{h(x)f(x)}{g(x)}</math><br><br> | ||

+ | |||

+ | '''Process'''<br> | ||

+ | # Choose <math>\displaystyle g(x)</math> such that it's easy to sample from. | ||

+ | # Compute <math>\displaystyle w(x)=\frac{h(x)f(x)}{g(x)}</math> | ||

+ | # <math>\displaystyle \hat{I} = \frac{\displaystyle\sum_{i=1}^{N} w(x_i)}{N}</math><br><br> | ||

+ | |||

+ | '''"Weighted" average'''<br> | ||

+ | :The term "importance sampling" is used to describe this method because a higher 'importance' or 'weighting' is given to the values sampled from <math>\displaystyle g(x)</math> that are closer to <math>\displaystyle f(x)</math>, the original distribution we would ideally like to sample from (but cannot because it is too difficult).<br> | ||

+ | :<math>\displaystyle I = \int\frac{h(x)f(x)}{g(x)}g(x)\,dx</math> | ||

+ | :<math>=\displaystyle \int \frac{f(x)}{g(x)}h(x)g(x)\,dx</math> | ||

+ | :<math>=\displaystyle \int \frac{f(x)}{g(x)}E_g(h(x))\,dx</math> which is the same thing as saying that we are applying a regular Monte Carlo Simulation method to <math>\displaystyle\int h(x)g(x)\,dx </math>, taking each result from this process and weighting the more accurate ones (i.e. the ones for which <math>\displaystyle \frac{f(x)}{g(x)}</math> is high) higher. | ||

+ | |||

+ | One can view <math> \frac{f(x)}{g(x)}\ = B(x)</math> as a weight. | ||

+ | |||

+ | Then <math>\displaystyle \hat{I} = \frac{\displaystyle\sum_{i=1}^{N} w(x_i)}{N} = \frac{\displaystyle\sum_{i=1}^{N} B(x_i)*h(x_i)}{N}</math><br><br> | ||

+ | |||

+ | i.e. we are computing a weighted sum of <math> h(x_i) </math> instead of a sum. |

## Latest revision as of 08:45, 30 August 2017

In [math]I = \displaystyle\int h(x)f(x)\,dx[/math], Monte Carlo simulation can be used only if it easy to sample from f(x). Otherwise, another method must be applied. If sampling from f(x) is difficult but there exists a probability distribution function g(x) which is easy to sample from, then [math]I[/math] can be written as

- [math]I = \displaystyle\int h(x)f(x)\,dx [/math]
- [math]= \displaystyle\int \frac{h(x)f(x)}{g(x)}g(x)\,dx[/math]
- [math]= \displaystyle E_g(w(x)) \rightarrow[/math]the expectation of w(x) with respect to g(x)
- [math]= \frac{\displaystyle\sum_{i=1}^{N} w(x_i)}{N}[/math] where [math]\displaystyle w(x) = \frac{h(x)f(x)}{g(x)}[/math]

**Process**

- Choose [math]\displaystyle g(x)[/math] such that it's easy to sample from.
- Compute [math]\displaystyle w(x)=\frac{h(x)f(x)}{g(x)}[/math]
- [math]\displaystyle \hat{I} = \frac{\displaystyle\sum_{i=1}^{N} w(x_i)}{N}[/math]

**"Weighted" average**

- The term "importance sampling" is used to describe this method because a higher 'importance' or 'weighting' is given to the values sampled from [math]\displaystyle g(x)[/math] that are closer to [math]\displaystyle f(x)[/math], the original distribution we would ideally like to sample from (but cannot because it is too difficult).
- [math]\displaystyle I = \int\frac{h(x)f(x)}{g(x)}g(x)\,dx[/math]
- [math]=\displaystyle \int \frac{f(x)}{g(x)}h(x)g(x)\,dx[/math]
- [math]=\displaystyle \int \frac{f(x)}{g(x)}E_g(h(x))\,dx[/math] which is the same thing as saying that we are applying a regular Monte Carlo Simulation method to [math]\displaystyle\int h(x)g(x)\,dx [/math], taking each result from this process and weighting the more accurate ones (i.e. the ones for which [math]\displaystyle \frac{f(x)}{g(x)}[/math] is high) higher.

One can view [math] \frac{f(x)}{g(x)}\ = B(x)[/math] as a weight.

Then [math]\displaystyle \hat{I} = \frac{\displaystyle\sum_{i=1}^{N} w(x_i)}{N} = \frac{\displaystyle\sum_{i=1}^{N} B(x_i)*h(x_i)}{N}[/math]

i.e. we are computing a weighted sum of [math] h(x_i) [/math] instead of a sum.