# Monte Carlo Integration

Please see Directions for use for more information.

## Learning Project Summary

* Project code: Monte Carlo Integration
* School: Computer Science:
* Department: Scientific Computing

## Content summary

A brief introduction to Monte Carlo integration and a few optimization techniques.

## Goals

This learning project offers learning activities to Monte Carlo integration. A student should be able to effectively apply Monte Carlo methods to integrate basic functions over set boundaries and apply some level of optimizations to a given problem.
Concepts to learn include: /concepts

## Learning materials
### Texts

[1] Numerical Mathematics and Computing Chapter 12

### Lessons

* Lesson 1: Introduction to Monte Carlo Integration
Monte Carlo methods use random samplings to approximate probability distributions. This
technique has applications from weather prediction to quantum mechanics.
One use for Monte Carlo methods is in the approximation of integrals. This is done by
choosing some number of random points over the desired interval and summing the function
evaluations at these points. The area of the desired interval is then multiplied by the
average function evaluation from the chosen points.
This technique can further be implemented in multiple dimensions where the process becomes
more useful. A rigorous evaluation of this technique finds the error approximately $1 \over {\sqrt {}N)$ [1] which means
$O{({1 \over {\sqrt {n}}})}$ convergence. This is not very useful in the one dimension case above, as better techniques exist, but
since the error is not bounded by the number of dimensions evaluated, when many dimensional
integrals are evaluated, Monte Carlo methods can become increasingly effective.
The following Matlab script will approximate a triple integral for a given function and
boundary.
The next step in Monte Carlo integration is to optimize the evaluation to more accurately
and quickly determine the integral. There are numerous techniques for improving on (1). The
following require some pre-existing knowledge about the function being evaluated:
* Lesson 2: Control Variates
This technique breaks the function being evaluated into pieces in which one or more pieces
have known integral values or are more easily evaluated than the original function. In this
way, the random samplings will be more prevalent with the difficult part of the function
and not be wasted on the already known piece.
e.g.
let
    $f(x)=e^{-x^{2}}+sin{(x)}$
over the interval of 0 to $2\pi$ then,
    $\int _{0}^{2\pi }{f(x)}$ $=$ $\int _{0}^{2\pi }{e^{-x^{2}}}+\int _{0}^{2\pi }{sin{(x)}}$ $=$ $\int _{0}^{2\pi }{e^{-x^{2}}}+0$
since sin x is an odd function, its integral is 0 on this interval. By decreasing the variance of the
function being integrated, the approximated answer will be more accurate [2].
* Lesson 3: Stratified Sampling
This technique relies on breaking the desired interval into multiple sections and evaluating
the Monte Carlo integration on each section individually. In this way, the more important
sections, i.e. the intervals where f(x) gives its greatest contribution to the integral, are
able to receive more random samplings in approximating their integral values. This will
allow the more important sections to contribute more accurately to the final integral.
e.g.
The Monte Carlo method then becomes the following, given that the interval is broken into m sections:
If the interval lengths and number of samples for each length are chosen correctly,
this method can dramatically decrease the error in approximating the integral.
* Lesson 4: Importance Sampling
The previous technique showed that using a non-uniform distribution of random points can
lead to better samplings and more accurate approximations of an integral. Importance
sampling is an extension of this technique, but instead of using grids to split the
interval, a distribution function is used for choosing the random points. Now when picking
the sampling points to evaluate the integral, the points must conform to some distribution
function which ideally approximates the desired function.
i.e.
e.g.
With the non-uniform distribution of random points, the equation approximating the integral
must be revisited. Now, given a distribution of random points with a density of p(x), the
approximation of the integral becomes:

### Assignments
#### Activities

* Activity 1.
Approximate Pi using Monte Carlo integration and Matlab. [hint: $x^{2}+y^{2}=r^{2}$ forms a circle]
* Activity 2.
Extend the given matlab code from the introduction to perform integration on an arbitrary number of dimensions, rather than just three.