Day 9: Monte carlo - π

Tomáš Bouda
Apr 2, 2017 · 1 min read

I guess I’ll introduce more the one randomised algorithm in this series, and that’s not only because I love probabilistic approach. Randomised simulation is often the best/only way to solve otherwise intractable problems.

if you are mathematician, excuse my sloppy wording; randomised simulation should be understood as a random sampling from space of simulations under given distribution

How can we estimate π if the only tool we have at disposal is a good random number generator? When we choose a random coordinate (x, y) in range (-1, 1) and each point has equal chance to be chosen, the probability to hit a circle with unit radius is

Having sufficiently large set of points [and a good generator] we can get as close as we want according to Chebyshev’s inequality.

algorithm

https://github.com/coells/100days

test

100 days of algorithms

100 days, 100 algorithms - a challenge consisting of many small pieces

Tomáš Bouda

Written by

Data scientist

100 days of algorithms

100 days, 100 algorithms - a challenge consisting of many small pieces