Monte Carlo Algorithm [Easy Explanation]

The Monte Carlo algorithm is quite an interesting algorithm, the name Monte Carlo is taken from Monaco casinos, which are famous for casinos and gambling.

In this blog, I try to explain the Monte Carlo algorithm, easily.

What is Monte Carlo Algorithm?

Monte Carlo Algorithm is a randomized algorithm that may or may not produce the correct result with some amount margin of errors. Monte Carlo comes under lower accuracy and shorter computing time of Numerical method spectrum. It was invented in the late 1940s, Stanislaw Ulam invented the modern version of the Markov Chain Monte Carlo Algorithm. 

Example of Monte Carlo algorithm

Example  #1:

You’re rolling dice and you want to determine the probability of rolling a sum of eight between two dice. As we know there are 36 different combinations. To calculate the probability, throw the dice a certain number of times and take note. let’s say you rolled the dice 500 times and it resulted in a sum of eight during 109 of those rolls. This means that the probability is 21.8%. 

But as we know according to the definition I wrote above, this 21.8% is may or may not be the correct answer (probability) which we can judge by a mathematical solution (I am not going to explain it here).

One more thing, I more to point here, the answer (probability = 21.8%) become more accurate if you increase this number of rolls. (This could be easily done by computer)

What are Monte Carlo methods and Monte Carlo experiments?

Monte Carlo methods and Monte Carlo experiments and Monte Carlo Algorithm are the same it’s kind of synonyms of each other.

Note: This is as of my understanding, I never read this anywhere, so if I am wrong kindly let me know.

Applications of Monte Carlo Algorithm

Applications of Monte Carlo is huge, Monte Carlo algorithm is used in Physical sciences, Chemical, Biochemical, and Environmental Engineering, etc. and to be honest, this article is not about “Applications of Monto Carlo algorithm” but I share some great resources for it, Wikipedia already has a huge list of applications of Monte Carlo algorithm:

Here are some of the resources I recommend:

Wikipedia

Frontiersin.org’s post about it.

Monte Carlo Algorithm Time Complexity

Time Complexity is the runtime of the Monte Carlo algorithm that can be simply be computed as O(mkI/C). Where m is the number of random children to consider per search and k is the number of parallel searches, and I is the number of iterations and C is the number of cores available. This algorithm has deterministic running time and it is generally easier to find out worst-case time complexity. 

Monte Carlo Algorithm vs Las Vegas Algorithm

Las Vegas (LV) Algorithms – Are randomized algorithms that always give the correct answer. The running time however is not fixed (not deterministic), that is it can vary for the same input. For eg. Randomized Quick Sort always gives a correctly sorted array as its output. However, it takes  O(N log N)  time on average but can be as bad as  O(n2)  in the worst case.

Monte Carlo (MC) Algorithms – Are randomized algorithms that may not always give the right answer. The running time for these algorithms is fixed, however. There is also generally a probability guarantee that the answer is right. For eg., if you used a nonperfect hash to assign hash values to two different strings and then try to see if the strings are the same or not by comparing the hash values, then this is like an MC algorithm. You will mostly get the right answer but sometimes two different strings can end up having the same hash value.

Code for Monte Carlo Algorithm 

If points (x, y), with -1 < x < 1 and -1 < y < 1, are placed randomly, the ratio of points that fall within the unit circle will be close to π/4.

A Monte Carlo simulation would randomly place points in the square and use the percentage of points inside the circle to estimate the value of π.

const n = 100000
count := 0
for i := 0; i < n; i++ {
    x := 2*rand.Float64() - 1
    y := 2*rand.Float64() - 1
    if x*x+y*y < 1 {
        count++
    }
}
fmt.Println(4 * float64(count) / float64(n)) // 3.1484

If you have any questions regarding this leave a comment below!