Monte Carlo method

What is Monte-Carlo simulation? How to use it to compute PI?

• Monte Carlo method is an algorithm which use random sampling to achieve some numerical results.
• Basic steps for Monte Carlo(from wiki):
1. Define a domain of possible inputs.
2. Generate inputs randomly from a probability distribution over the domain.
3. Perform a deterministic computation on the inputs.
4. Aggregate the results.     

Next is a simple example using Monte-Carlo to compute PI:

1. Draw a square with width 1,  a circle with radius 1.
2. Generate uniformly distributed random variables(x,y), red points represent points inside the circle, while blue color represents points outside.
3. Count the number of points inside the circle.
4. Divide the number of inside points by the total number of points, then multiplied by 4 gives the estimation of PI.

A simple example in matlab:

---

% Compute PI using Monte Carlo
% Copyright (c) Eric, CrazyQuant Fri Mar 15 14:10:12 SGT 2013
% Keywords: Monte Carlo

clear all;
close all;

numberOfTests = 20000;
numberInside = 0;
numberOutside = 0;

x = 0:0.01:1;
y = sqrt(1 - x.^2);
plot(x,y,'g');
hold on;

for number = 1 : numberOfTests
    x = rand();
    y = rand(); 
    if(x^2 + y^2 < 1)
        numberInside++;
        inside_x(numberInside) = x;
        inside_y(numberInside) = y;
    else
        numberOutside++;
        outside_x(numberOutside) = x;
        outside_y(numberOutside) = y;
    endif
end

plot(inside_x,inside_y,'ro');
plot(outside_x,outside_y,'bo');

PI = numberInside / numberOfTests * 4

---

Total points: 1000, PI = 3.1600

Total points: 5000, PI = 3.1552

Total points: 10000, PI = 3.1380

Total points: 20000, PI = 3.1366

Total points: 30000, PI = 3.1487