What it is?
Monte Carlo simulation is a problem solving technique which is used to approximate the solution for those problems which are infeasible or impossible to compute deterministically. It involves doing multiple trial runs or simulations for the problem at hand with suitable random values and observing the fraction of the values obeying some property or properties.
As a simple example we try to calculate the value of π though a Monte Carlo Simulation. Consider the following figure where a circle is inscribed in a square. The side of the square is 2r units, and the radius of the circle is r units.
Now consider a single quadrant of the figure.
Here,
So,
The Procedure
Using Monte Carlo simulation we would calculate the value of π as follwos :
1. Consider the figure to be on a Cartesian plane.
2. Generate a large number of points.
3. Count the number of points lying inside the quadrant (n in the program below, this will represent the area of the shaded region). And count the total number of points (representing the area of the square)
4. Compute the value of π using the above formula. (4 * n / a)
5. To get better accuracy repeat steps 1-4 multiple times and take the average.
Here is a perl program for this implementation :
$avg=0;
$no_of_times=10;
for($i=0;$i<$no_of_times;$i++)
{
$a=int rand(1000000);
$n=0;
for($j=0;$j<$a;$j++)
{
$x=rand(1);
$y=rand(1);
if($x*$x + $y*$y <=1)
{
$n++;
}
}
$pi= 4.0*$n/$a;
print "pi=$pi for $a tries\n";
$avg+=$pi;
}
$avg/=$no_of_times;
print "pi=$pi\n";
The output is :
rishabh@ubuntu:~$ perl pi.pl pi=3.14276506439668 for 772633 tries pi=3.14294672233944 for 542216 tries pi=3.14328773838267 for 575283 tries pi=3.14186626844556 for 203572 tries pi=3.13502251907228 for 32639 tries pi=3.13983316710037 for 800082 tries pi=3.14055617007238 for 309186 tries pi=3.13979483067174 for 818056 tries pi=3.13903009074211 for 819355 tries pi=3.1448481668525 for 365928 tries Final value of pi=3.1448481668525 rishabh@ubuntu:~$
The above program is just an example for demonstrating Monte Carlo Simulation. It is generally used in cases which are too complicated to solve analytically. It gives us the ability to examine more complex systems than we otherwise can. With Monte Carlo 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.
Percolation Threshold
Consider the problem of calculating
the percolation threshold.
Definitions :
Percolation : Consider a system as
a 2-d grid composed of empty and filled sites. We say that the system
percolates if there is a path from an empty site in the top row to one on
the bottom row through a set of empty
sites in the grid.
For example consider the following
systems :
System 1 does not percolate.
System 2 percolates.
System 2 percolates.
The Problem : We are interested in the value of the site vacancy percentage(i.e. percolation threshold) for a system. If the site vacancy percentage is greater than this value then the system almost certainly percolates while if the site vacancy percentage is lesser then the system almost certainly does not percolate.
To determine this we can use Monte Carlo Simulation :
1. Initialize all sites to be blocked.
2. Repeat the following until the system percolates(Use union find algorithm):
a. Choose a site (row i, column j) uniformly at random among all blocked sites.
b. Open the site (row i, column j).
3. The fraction of sites that are opened when the system percolates provides an estimate of the percolation threshold.
Repeat the above multiple times and take an average to get a more accurate result. It is generally around 0.593.
Application of Percolation threshold :
1. Given a composite systems comprised of randomly distributed insulating and metallic materials: what fraction of the materials need to be metallic so that the composite system is an electrical conductor?
2. Given a porous landscape with water on the surface (or oil below), under what conditions will the water be able to drain through to the bottom (or the oil to gush through to the surface)?
3. Given a network, how many nodes can be removed till the network looses connectivity? (Determination of network robustness and fragility).
Other applications of Monte Carlo Simulation :
1. Finance : Monte Carlo methods are used in finance to value and analyze (complex) instruments, portfolios and investments by simulating the various sources of uncertainty affecting their value, and then determining their average value over the range of resultant outcomes.
2. Searching for the best move in a game using a technique called Monte-Carlo tree search. Possible moves are organized in a search tree and a large number of random simulations are used to estimate the long-term potential of each move.
3. In telecommunications, when planning a wireless network, design must be proved to work for a wide variety of scenarios that depend mainly on the number of users, their locations and the services they want to use. Monte Carlo methods are typically used to generate these users and their states. The network performance is then evaluated and, if results are not satisfactory, the network design goes through an optimization process.
