Transcript Monte Carlo Methods

Monte Carlo Methods
Versatile methods for analyzing the behavior of
some activity, plan or process that involves uncertainty
What are Monte Carlo Methods?

Monte Carlo (MC) methods are stochastic techniques--meaning they are based
on the use of random numbers and probability statistics to investigate problems

A technique that provides approximate solutions to problems expressed
mathematically. Using random numbers and trial and error, it repeatedly
calculates the equations to arrive at a solution.

MC methods are used in everything from economics to nuclear physics to
regulating the flow of traffic
http://www.chem.unl.edu/zeng/joy/mclab/mcintro.html
Monte Carlo Methods - cont

Solving equations which describe the interactions between two atoms is fairly
simple; solving the same equations for hundreds or thousands of atoms is
impossible

With MC methods, a large system can be sampled in a number of random
configurations, and that data can be used to describe the system as a whole.

To call something a "Monte Carlo" experiment, all you need to do is use
random numbers to examine some problem.
http://www.chem.unl.edu/zeng/joy/mclab/mcintro.html
Monte Carlo Applications

Design and visuals - Monte Carlo methods have
also proven efficient in solving coupled integral
differential equations that helps in computer
generated films, special effects in cinema etc

Finance and Business - Often used to calculate the
value of companies, to evaluate investments in
projects at a business unit or corporate level, or to
evaluate financial derivatives.

Games - Monte Carlo methods have recently been
applied in game playing related artificial
intelligence theory. Most notably the game of Go
has seen remarkably successful Monte Carlo
algorithm based computer players
Monte Carlo Pattern

Define a domain of possible inputs.

Generate inputs randomly from the domain using a certain specified
probability distribution.

Perform a deterministic computation using the inputs.

Aggregate the results of the individual computations into the final result.
Monte Carlo Calculation of Pi
The value of π can be approximated using a Monte Carlo method:

Draw a square on the ground, then inscribe a circle within it. From plane
geometry, the ratio of the area of an inscribed circle to that of the
surrounding square is π/4.

Uniformly scatter some objects of uniform size throughout the square. For
example, grains of rice or sand.

Since the two areas are in the ratio π/4, the objects should fall in the areas
in approximately the same ratio. Thus, counting the number of objects in
the circle and dividing by the total number of objects in the square will
yield an approximation for π/4. Multiplying the result by 4 will then yield
an approximation for π itself.
Monte Carlo Calculation of Pi
Total number of darts that hit within the square, the number of darts that hit
the shaded part (circle quadrant) is proportional to the area of that part.
How good it is, depends on how many iterations (throws) are done
π approximation follows the general
pattern of Monte Carlo algorithms.

First, we define a domain of inputs: in this case, it's the
square which circumscribes our circle.

Next, we generate inputs randomly (scatter individual
grains within the square), then perform a computation on
each input (test whether it falls within the circle).

At the end, we aggregate the results into our final result, the
approximation of π.
C Function to calculate Pi
Monte Carlo Pi Simulations
http://pagespersoorange.fr/jpq/proba/montecarlo/index.htm
Components of Monte Carlo
Algorithms

Random number generator

Sampling rule

Probability Distribution Functions (PDF)

Error estimation
Markov Process

A Markov process – a mathematical model for the random evolution of a
memoryless system, that is, one for which the likelihood of a given future state,
at any given moment, depends only on its present state, and not on any past
states.

Board games played with dice


Monopoly, Snakes and Ladders
Transitions of Markov Chain is determined by a stochastic matrix or a
probability matrix. Each row (or column) of a stochastic matrix is a probability
vector, which are sometimes called stochastic vectors. A vector whose elements
consist should always sum to 1
Example of Markov Chains

Weather Prediction

The weather on day 0 is known to be sunny. This is represented by a vector in which
the "sunny" entry is 100%, and the "rainy" entry is 0%:

The weather on day 1 can be predicted by:

Thus, there is an 90% chance that day 1 will also be sunny.

General Rule for day n are:
http://en.wikipedia.org/wiki/Examples_of_Markov_chains
References
1. http://en.wikipedia.org/wiki/Monte_Carlo_method
2. http://www.answers.com/topic/monte-carlo-method