very interesting links
http://www.mathcs.emory.edu/~cheung/Courses/170/Syllabus/07/compute-pi.html
http://www.mathcs.emory.edu/~cheung/Courses/170/Syllabus/01/alg.html
http://www.dreamincode.net/forums/topic/30265-calculate-pi-using-random-numbers/
http://www.wikihow.com/Calculate-Pi-by-Throwing-Frozen-Hot-Dogs
http://mathworld.wolfram.com/MandelbrotSet.html
http://www.wikihow.com/Plot-the-Mandelbrot-Set-By-Hand
http://www.wikihow.com/Calculate-Pi-by-Throwing-Frozen-Hot-Dogs
http://arachnoid.com/mandelbrot_set/
http://ccl.northwestern.edu/netlogo/models/Mandelbrot
A simple Monte Carlo Methods: Compute Pi
- Pseudo random number generator
- Terminology:
- Pseudo random number generator = a device (method) that generate random numbers taken from some distribution of values
- Commonly used distribution of values:
- Uniform [a,b] distribution
- Every value between a and b is generated with equal probability (likelihood)
- (Standard) Normal distribution
- The value are generated with the following distribution of probability (likelihood)
- The value are generated with the following distribution of probability (likelihood)
- Uniform [a,b] distribution
- Terminology:
- The uniform [0,1) pseudo random number generator in the java.lang.Math class
- The method random() returns a uniform [0,1) pseudo random numberThat means it can return any values between 0 and 1, including 0. but not including 1.
- Example: print 10 random numbers (between [0, 1))
public class Random1 { public static void main(String[] args) { for ( int i = 0 ; i < 10; i++ ) { System.out.println( Math.random() ); // Print a random number } } }
- Example Program: (Demo above code)
- Prog file: click here
- Right click on link and save in a scratch directory
- To compile: javac Random1.java
- To run: java Random1
- The method random() returns a uniform [0,1) pseudo random numberThat means it can return any values between 0 and 1, including 0. but not including 1.
- Monte Carlo experiments
- Monte Carlo experiments are experiments with a random outcome with a certain probability of successExample: Monte Carlo experiment
- Die roll with outcome = 6
- The probability of this experiment = 1/6
- If the probability of success of the Monte Carlo experiment is difficult to compute, we can obtain an approximation using the following procedure:
- Performing the Monte Carlo experiment for many many many times and observe the outcomes.
- The probability of success of the Monte Carlo experiment can be approximated by:
# times that the outcome was succesful ----------------------------------------- # times that the experiment was performed
- Monte Carlo Method:
- Monte Carlo Method = a computer simulation that performs Monto Carlo experiments aimed to compute the above probability
- We will illustrate the Monto Carlo Method with a simple experiment to find Pi
- Monte Carlo experiments are experiments with a random outcome with a certain probability of successExample: Monte Carlo experiment
- A Monte Carlo experiment to find an estimate for Pi
- Problem:
- Assume we have no knowledge of the value of π (= 3.1415926535...)
I.e., you cannot your calculator or any other information source. - Find an estimate for π
- Assume we have no knowledge of the value of π (= 3.1415926535...)
- Consider the following funny looking dart board:
- The dimension of the dart board is 1 x 1.
- A quarter circle with radius r = 1 is inscribed in the board.
- The Monte Carlo experiment:
- You throw darts at this board blindfolded(we check only the darts that land on the board)
When you are blindfolded, then the probability of a dart landing on any position inside the 1 x 1 quared board is identical)
- What is the probability that a dart hits the yellow portion of the dart board ???
- You throw darts at this board blindfolded(we check only the darts that land on the board)
- Computing the probability that a dart hits the yellow portion of the dart board:
- Fact from the construction of the dart board:
Area of the quarter circle Probability [ dart hits yellow portion ] = -------------------------- Area of the 1 x 1 square = Area of the quarter circle
- Fact from the construction of the dart board:
- The area of the quarter circle can be computed as follows:
- The area of the full circle = π × 1 2 = π
- The area of the quarter circle = π / 4
- Therefore:
Probability [ dart hits yellow portion ] = Area of the quarter circle = π/4
- Problem:
- Finding an estimate for Pi using a Monte Carlo Method
- The above description give rise to a Monte Carlo experiment that we can use to estimate π.
- Recall Monte Carlo experiment:
- An experiment (= throwing darts) with a random outcome with a certain probability of success (= darts land inside the quarter cicle with probability = π/4)
- Monte Carlo Simulation (throwing darts):
int i; int nThrows = 0; int nSuccess = 0; /* ============================== Throw a large number of darts ============================== */ for (i = 0; i < aLargeNumber; i++) { "Throw a dart"; nThrows++; if ( "dart lands inside quarter circle" ) nSuccess++; } /* ================================================================= Estimate the probability of a dart landing inside quarter circle ================================================================== */ System.out.println("Pi/4 = " + (double)nSuccess/(double)nThrows );
- Simulating a dart throw:
- A computer program can never throw a real dart
- A simulation will only consider the result of a dart throw
- Result of a dart throw:
- The dart lands in some coordinate (x, y) where x and x are uniform [0..1) distributed(I.e., any point inside the 1 x 1 square will be equally likely to be "hit")
- Simulating a dart throw:
- x = Math.random()
- y = Math.random()
- Checking whether a dart landed the inside the quarter cicle:
- A point (x,y) inside the quarter circle will satisfy the following inequality:
x2 + y2 ≤ 12 (Equation of a circle)
- A point (x,y) inside the quarter circle will satisfy the following inequality:
- Java program of the Monte Carlo Simulation:
public class ComputePi1 { public static void main(String[] args) { int i; int nThrows = 0; int nSuccess = 0; double x, y; for (i = 0; i < 1000000 ; i++) { x = Math.random(); // Throw a dart y = Math.random(); nThrows++; if ( x*x + y*y <= 1 ) nSuccess++; } System.out.println("Pi/4 = " + (double)nSuccess/(double)nThrows ); System.out.println("Pi = " + 4*(double)nSuccess/(double)nThrows ); } }
Pi/4 = 0.785784 Pi = 3.143136
- Example Program: (Demo above code)
- Prog file: click here
- Right click on link and save in a scratch directory
- To compile: javac ComputePi1.java
- To run: java ComputePi1
- The above description give rise to a Monte Carlo experiment that we can use to estimate π.
- More interesting Monte Carlo simulations
- In the 1960's, Edward Thorp wrote and published the book "Beat the Dealer" on Black Jack: click here
- The book presents a system of card counting and how to play Black Jack
- Many people have written computer programs that simulate a Black Jack games (among them was me :-))
- The simulations show that Thorpe system does work - you can win at Black jack with his system by counting cards.
- As a result, casinos in Las Vegas impose measures to throw out people that count cards...
- In the 1960's, Edward Thorp wrote and published the book "Beat the Dealer" on Black Jack: click here