Estimating Pi through Monte Carlo Simualtion

The report also available at: estimating pi through monte carlo simualtion

Problem Statement

Implement a Monte Carlo simulation based on Buffon’s needle problem to estimate the value of \(\pi\). Buffon’s needle is a classic problem in probability theory that relates the probability of a needle crossing parallel lines on a plane to the value of \(\pi\).

Solution Plan for the Problem

1. Understanding the problem (Polya 2014):

   • What is given?
     • Buffon’s needle problem: A method to estimate \(\pi\) using Monte Carlo simulation.
     • We need to simulate dropping needles on a lined surface.
   • What is required?
     • To estimate the value of \(\pi\) using this method.
   • What are the key components?
     • A surface with parallel lines
     • Needles of a specific length
     • Random tosses of needles
     • Counting needle crossings with lines
   • How does it relate to \(\pi\)?
     • The probability of a needle crossing a line is related to \(\pi\).
   • Can we break it down?
     • Define the surface and needle parameters
     • Implement a function to toss a needle
     • Implement a function to check if a needle crosses a line
     • Perform many tosses and count crossings
     • Use the count to estimate \(\pi\)

Polya, G. 2014. How to Solve It: A New Aspect of Mathematical Method. Princeton Science Library. Princeton University Press.

Simulation Steps Breakdown

Define Parameters

• Set floor width and line spacing
• Set needle length
• Set number of tosses

Implement Needle Toss Function

• Generate random x-coordinate
• Generate random angle

Implement Line Crossing Check Function

• Calculate needle endpoints
• Check if endpoints are on different sides of a line

Perform Monte Carlo Simulation

• For each toss:
  • Toss a needle
  • Check if it crosses a line
  • Count total crosses

Estimate \(\pi\)

• Use the formula:

\[ \pi \approx \frac{2 * needle\_length * number\_of\_tosses}{line\_spacing * number\_of\_crosses} \]

Solution

Stepwise implementation of the Problem in Julia code.

```{julia}
1using Random
2using Distributed
3Random.seed!(1275)
```

1

Import the Random module for generating random numbers

2

Import the Distributed module for parallel computing capabilities

3

Set a specific random seed for reproducibility

TaskLocalRNG()

```{julia}
"""
    toss_needle(d::Float64)

Generate a random point inside a semicircle with radius `d/2`.

Returns:
- A tuple `(x, θ)` where `x` is the distance from the center of the needle to the nearest line,
  and `θ` is the angle of the needle with the horizontal.
"""
function toss_needle(d::Float64)
1    x = rand() * d / 2
2    θ = rand() * π
    return x, θ
end
```

1

Generate a random distance from the nearest line, uniformly distributed between 0 and d/2

2

Generate a random angle, uniformly distributed between 0 and \(\pi\) radians

Main.Notebook.toss_needle

```{julia}
"""
    cross_line(x::Float64, θ::Float64, L::Float64)

Check if a point `(x, θ)` crosses a line parallel to the x-axis with a distance `L/2` from the center.

Returns:
- `true` if the needle crosses the line, otherwise `false`.
"""
function cross_line(x::Float64, θ::Float64, L::Float64)
1    return x <= (L / 2) * sin(θ)
end
```

1

Check if the needle crosses a line by comparing its x-coordinate to half its length times the sine of its angle

Main.Notebook.cross_line

```{julia}
"""
    estimate_pi_par(nb_tosses::Int64, L::Float64, d::Float64)

Estimate π using Buffon's Needle method.

Args:
- `nb_tosses`: The number of random tosses to perform.
- `L`: The length of the needle.
- `d`: The distance between the lines.

Returns:
- An estimate of π based on the number of times the needle crosses a line.
"""
function estimate_pi_par(nb_tosses::Int64, L::Float64, d::Float64)
1    nb_crosses = @distributed (+) for _ in 1:nb_tosses
2        x, θ = toss_needle(d)
3        cross_line(x, θ, L) ? 1 : 0
    end
4    return (2 * L * nb_tosses) / (d * nb_crosses)
end
```

1

Use distributed computing to parallelize the Monte Carlo simulation

2

Toss a needle, getting its position (x) and angle (\(\theta\))

3

Check if the needle crosses a line, returning 1 if true, 0 if false

4

Calculate the estimate of \(\pi\) using the formula derived from Buffon’s needle problem

Main.Notebook.estimate_pi_par

```{julia}
# Parameters
L = 1.0  # Length of the needle
d = 2.0  # Distance between the lines
nb_tosses = 1_000_000  # Number of tosses

```

1000000

```{julia}
# Estimate π
π_estimate = estimate_pi_par(nb_tosses, L, d)
println("Estimated π: $π_estimate")
```

Estimated π: 3.140664062009271