息不 Stronger Every Day 强自

Estimating π

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 X2 + Y2 ≤ 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 227), 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.

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 Xi that takes the value of 1 if point i falls within the circle, and 0 if it doesn't. Let Mn be the proportion of points that fall within the circle.

Expectation of Xi, E[Xi] = π4

Squared expectation of Xi, E[Xi2] = π4

Variance of Xi, Var[Xi] = E[Xi2] - E[Xi] = (π4) - (π4)2 = (π4)(1 - π4)

Expectation of Mn, E[Mn] = π4

Variance of Mn, Var[Mn] = Var[Xi]n = (π4)(1 - π4)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).

Our estimation:

Number of samples: 0

Number of sample points that fall within the circle: 0

Our estimation of π, 4 x proportion of samples within circle:

© 2017-2024 Desmond Cheong Zhi Xi • Powered by Flask