monte_carlo_integration.md

Monte Carlo Integration

Monte Carlo methods were some of the first methods I ever used for research, and when I learned about them, they seemed like some sort of magic. Their premise is simple: random numbers can be used to integrate arbitrary shapes embedded into other objects. Nowadays, "Monte Carlo" has become a bit of a catch-all term for methods that use random numbers to produce real results, but it all started as a straightforward method to integrate objects. No matter how you slice it, the idea seems a bit crazy at first. After all, random numbers are random. How could they possibly be used to find non-random values?

Well, imagine you have a square. The area of the square is simple, $$\text{Area}{\text{square}} = \text{length} \times \text{width}$$. Since it's a square, the $$\text{length}$$ and $$\text{width}$$ are the same, so the formula is technically just $$\text{Area}{\text{square}} = \text{length}^2$$. If we embed a circle into the square with a radius $$r = \tfrac{length}{2}$$ (shown below), then its area is $$\text{Area}{\text{circle}}=\pi r^2$$. For simplicity, we can also say that $$\text{Area}{\text{square}}=4r^2$$.

Now, let's say we want to find the area of the circle without an equation. As we said before, it's embedded in the square, so we should be able to find some ratio of the area of the square to the area of the circle:

$$ \text{Ratio} = \frac{\text{Area}{\text{circle}}}{\text{Area}{\text{square}}} $$

This means,

$$ \text{Area}{\text{circle}} = \text{Area}{\text{square}}\times\text{Ratio} = 4r^2 \times \text{ratio} $$

So, if we can find the $$\text{Ratio}$$ and we know $$r$$, we should be able to easily find the $$\text{Area}_{\text{circle}}$$. The question is, "How do we easily find the $$\text{Ratio}$$?" Well, one way is with random sampling. We basically just pick a bunch of points randomly in the square, and each point is tested to see whether it's in the circle or not:

{% method %} {% sample lang="jl" %} import:2-7, lang:"julia" {% sample lang="clj" %} import:3-10, lang:"clojure" {% sample lang="c" %} import:7-9, lang:"c_cpp" {% sample lang="cpp" %} import:7-16, lang:"c_cpp" {% sample lang="js" %} import:2-6, lang:"javascript" {% sample lang="hs" %} import:7-7, lang:"haskell" {% sample lang="rs" %} import:7-9, lang:"rust" {% sample lang="d" %} import:2-5, lang:"d" {% sample lang="go" %} import:12-14, lang:"golang" {% sample lang="r" %} import:2-6, lang:"r" {% sample lang="java" %} import:13-15, lang:"java" {% sample lang="swift" %} import:15-17, lang:"swift" {% sample lang="py" %} import:5-7, lang:"python" {% sample lang="cs" %} import:23-23, lang:"csharp" {% endmethod %}

If it's in the circle, we increase an internal count by one, and in the end,

$$ \text{Ratio} = \frac{\text{count in circle}}{\text{total number of points used}} $$

If we use a small number of points, this will only give us a rough approximation, but as we start adding more and more points, the approximation becomes much, much better (as shown below)!

The true power of Monte Carlo comes from the fact that it can be used to integrate literally any object that can be embedded into the square. As long as you can write some function to tell whether the provided point is inside the shape you want (like in_circle() in this case), you can use Monte Carlo integration! This is obviously an incredibly powerful tool and has been used time and time again for many different areas of physics and engineering. I can guarantee that we will see similar methods crop up all over the place in the future!

Example Code

Monte Carlo methods are famous for their simplicity. It doesn't take too many lines to get something simple going. Here, we are just integrating a circle, like we described above; however, there is a small twist and trick. Instead of calculating the area of the circle, we are instead trying to find the value of $$\pi$$, and rather than integrating the entire circle, we are only integrating the upper right quadrant of the circle from $$0 < x, y < 1$$. This saves a bit of computation time, but also requires us to multiply our output by $$4$$.

That's all there is to it! Feel free to submit your version via pull request, and thanks for reading!

{% method %} {% sample lang="jl" %} import, lang:"julia" {% sample lang="clj" %} import, lang:"clojure" {% sample lang="c" %} import, lang:"c_cpp" {% sample lang="cpp" %} import, lang:"c_cpp" {% sample lang="js" %} import, lang:"javascript" {% sample lang="hs" %} import, lang:"haskell" {%sample lang="rs" %} import, lang:"rust" {%sample lang="d" %} import, lang:"d" {%sample lang="go" %} import, lang:"golang" {%sample lang="r" %} import, lang:"r" {% sample lang="java" %} import, lang:"java" {% sample lang="swift" %} import, lang:"swift" {% sample lang="py" %} import, lang:"python" {% sample lang="cs" %} MonteCarlo.cs import, lang:"csharp" Circle.cs import, lang:"csharp" Program.cs import, lang:"csharp" {% endmethod %}

<script> MathJax.Hub.Queue(["Typeset",MathJax.Hub]); </script>