Monte Carlo Method

Monte Carlo methods use repeated random sampling to obtain numerical solutions to problems that are deterministic or too complex to solve directly.

Some examples include:

  • Estimating multidimensional integrals
  • Simulating systems with many coupled degrees of freedom
  • Optimization problems

Java example - Estimating pi:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

double estimatePi(int trials) {
  int hits = 0;
  Random rand = new Random();

  for (int i = 0; i < trials; i++) {
    double x = rand.nextDouble();
    double y = rand.nextDouble();
    if (x*x + y*y <= 1) hits++;
  }

  return 4.0 * hits / trials; 
}

C++ example - Buffon’s needle for pi:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

double estimatePi(int trials) {
  int hits = 0;
  std::default_random_engine generator;
  std::uniform_real_distribution<double> distribution(0.0,1.0);

  for (int i = 0; i < trials; i++) {
    double x = distribution(generator);
    double y = distribution(generator);
    // Test if needle crosses line    
    if (y <= sin(M_PI * x)) hits++;
  }

  return (2 * trials) / (hits * M_PI); 
}

Python example - Random walk:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

from random import random

def monte_carlo(steps):
  x, y = 0, 0
  for _ in range(steps): 
    r = random()
    if r <= 0.25: x += 1
    elif r <= 0.50: x -= 1  
    elif r <= 0.75: y += 1
    else: y -= 1

  return (x, y)

Monte Carlo methods leverage randomness to tackle complex problems through statistical sampling.

The Monte Carlo method refers to a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results.

The key idea is to use randomness to solve problems that might be deterministic in principle. By running simulations many times, the random errors can be minimized.

Monte Carlo methods are useful for obtaining numerical solutions to problems that are too complex to solve analytically. They are commonly used in computer simulations.

Solution

Here is an example of using Monte Carlo for estimating π:

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

double estimatePi(int iterations) {
  
  int circleCount = 0;
  Random rand = new Random();

  for (int i=0; i<iterations; i++) {
    double x = rand.nextDouble();
    double y = rand.nextDouble();

    if (x*x + y*y <= 1) {
      circleCount++; 
    }
  }
  
  return 4.0 * circleCount / iterations;
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

double estimatePi(int iterations) {
  
  int circleCount = 0; 
  std::default_random_engine generator;
  std::uniform_real_distribution<double> distribution(0.0,1.0);

  for (int i=0; i<iterations; i++) {
    double x = distribution(generator);
    double y = distribution(generator);

    if (x*x + y*y <= 1) {
      circleCount++;
    }
  }

  return 4.0 * circleCount / iterations;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import random

def estimate_pi(iterations):

  circle_count = 0
  for i in range(iterations):
    x = random.uniform(0, 1)
    y = random.uniform(0, 1)

    if x**2 + y**2 <= 1:
      circle_count += 1
  
  return 4 * circle_count / iterations

This generates random points and estimates pi based on circle area fraction.

Monte Carlo methods leverage randomness to solve complex problems.

Description: Monte Carlo Method

The Monte Carlo method is a statistical technique that uses random sampling to obtain numerical results for problems that might be deterministic in principle. This method is particularly useful in approximating complex problems where analytical solutions are hard to obtain.

Solution

Here, we’ll demonstrate how to estimate the value of Pi using the Monte Carlo method. We’ll generate random points inside a square, and then determine how many fall within a quarter circle. The ratio of the points within the circle to the total points approximates Pi/4.

Java

In Java, you can use java.util.Random for random number generation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.Random;

public class MonteCarlo {
    public static void main(String[] args) {
        int n = 1000000; // Number of points
        int insideCircle = 0;
        Random random = new Random();

        for (int i = 0; i < n; i++) {
            double x = random.nextDouble();
            double y = random.nextDouble();

            if (x * x + y * y <= 1) {
                insideCircle++;
            }
        }

        double pi = (double) insideCircle / n * 4;
        System.out.println("Estimated value of Pi: " + pi);
    }
}

C++

In C++, the <random> library can be used for random number generation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <random>

int main() {
    int n = 1000000; // Number of points
    int insideCircle = 0;
    std::default_random_engine generator;
    std::uniform_real_distribution<double> distribution(0.0, 1.0);

    for (int i = 0; i < n; ++i) {
        double x = distribution(generator);
        double y = distribution(generator);

        if (x * x + y * y <= 1) {
            insideCircle++;
        }
    }

    double pi = (double)insideCircle / n * 4;
    std::cout << "Estimated value of Pi: " << pi << std::endl;

    return 0;
}

Python

In Python, you can use the random module for random number generation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import random

def monte_carlo_pi(n):
    inside_circle = 0

    for _ in range(n):
        x = random.random()
        y = random.random()

        if x ** 2 + y ** 2 <= 1:
            inside_circle += 1

    return (inside_circle / n) * 4

if __name__ == "__main__":
    n = 1000000  # Number of points
    pi = monte_carlo_pi(n)
    print(f"Estimated value of Pi: {pi}")

Key Takeaways

  • The Monte Carlo method uses random sampling to estimate numerical results.
  • The method is highly versatile and can be applied to various problems.
  • Random number generation is key in implementing Monte Carlo methods, and different languages offer diverse tools for this.
  • The accuracy of the method improves with more samples.