DesmondCheong

What's going on? Is something going to blow up?

In this Monte Carlo experiment, we generate random X and Y cordinates from -1 to 1. We then count the proportion of generated points that fall within a circle of radius 1 centred at (0, 0). The area of a circle of radius 1 is π, so the proportion of points that fall within satisfy X² + Y² ≤ 1 times the area of the square (which is 4) gives us an estimate of the area of the circle and hence the value of π.

Using this method, we take a hard problem — estimating the value of π — and solve it with a very simple algorithm that you can replicate, without much thinking, by throwing darts blindfolded. Normally to estimate a value of π, we'd have to draw and measure circles, or use outside knowledge of rules of thumb (such as approximating π to 3.14 or ²²⁄₇), or solve an infinite series. Of course, there are some limitations. In this case, since we are carrying out this simulation with JavaScript, floating point errors eventually thwart our efforts at achieving the ultimate prize of super precise approximations of π. But this general technique, called Monte Carlo Methods, of solving hard deterministic problems with easier probablistic solutions is really powerful and really cool.

Screw the math!

The more sample points we take, the smaller our deviation from the true value of π. Here's the math:

Let sample i be represented by X_i that takes the value of 1 if point i falls within the circle, and 0 if it doesn't. Let M_n be the proportion of points that fall within the circle.

Expectation of X_i, E[X_i] = ^π⁄₄

Squared expectation of X_i, E[X_i²] = ^π⁄₄

Variance of X_i, Var[X_i] = E[X_i²] - E[X_i] = (^π⁄₄) - (^π⁄₄)² = (^π⁄₄)(1 - ^π⁄₄)

Expectation of M_n, E[M_n] = ^π⁄₄

Variance of M_n, Var[M_n] = ^Var[X_i]⁄_n = ^{(π⁄₄)(1 - π⁄₄)}⁄_n

Thus as we can see, the expected value of our estimation is π, and the variance of our estimation from the true value decreases as the number of trials increases. None of this is really surprising mathematically, this is the equivalent of a binomial random variable being divided by its number of trials.

Blablabla, who cares about all the math, am I right? Here's a pretty circle, numbers flashing across the screen, and a pretty neat chart plotting our estimated value (powered by SmoothieCharts).