# Monte Carlo Methods

### Why

#### Compute function integral

Suppose we want to find the value of:

in some region with volume .
Now, we can estimate this integral by estimating the proportion of random points that fall under , then multiplied by .

### Convergence Rate

The speed Monte Carlo method converges to the correct result as we increase the sample size / number of simulations.

Monte Carlo has convergence rate .

Quasi Monte Carlo has convergence rate .

### Variance Reduction

Reduce the variance of Monte Carlo simulated result with regard to the true result.

#### Increase number of simulations

Not very feasible, as in order to decrease variance / noise linearly, we have to increase simulations exponentially.

#### Quasi Monte Carlo (QMC)

##### Low-discrepancy Sequence
###### Faure Sequence

We take any prime number r where r>=2. Any integer n has a unique expansion with base r. We can then generate a sequence of numbers in the interval [0, 1), which are equally spaced within the interval.

For example, r = 3 and n = 7. We can write 7 in the form of base 3 as below:

Now, if we reflect this number about its “decimal point”, we get a new number in [0, 1):

We keep on doing this for every number n, we will generate a sequence in interval [0, 1). And we observe that the newly generated number keep filling the gaps in proceeding sequence. For example, for n = 1 to 9, we have below Faure Sequence:

In a general form, for any given number n, we can represent n in base r:

Then, we can find the corresponding Faure number in interval [0, 1) as follows:

## One thought on “Monte Carlo Methods”

1. Great write-up, I’m regular visitor of one’s web site, maintain up the excellent operate, and It is going to be a regular visitor for a long time.