Tricks with Monte Carlo Simulations (opens in new tab)

(countbayesie.com)

40 pointsCountBayesie11y ago4 comments

4 comments

This post has an opportunity to find the error bars on its estimate of π. The estimate came out as 3.14616.

The number of in-the-circle counts is S ~ binomial(N,p) where N=1e5 and p=π/4, which we'll take to be 0.75. Then

  var(S) = p(1-p)N ≤ N/4

and the standard deviation of S is the square root of this, or about ∆=137.

(If we weren't willing to use a guess for p in the variance above, we could use the universal bound of N/4.)

The estimate of π is (S/N) * 4, so the sdev on the estimate of π is (∆/N)*4 = 0.0055.

So the estimate turned out to be a little less than one standard deviation higher than π. Which is satisfying.

The point being that, for just a little extra work, you get not only a Monte Carlo estimate, but also a bound on its error. Sometimes the bound is just as important as the estimate.

pmalynin11y ago

I think the most interesting application of Monte Carlo that I've come in contact with is for pruning the game trees for Go (the game). It was similar to using minimax, except the tree was only evaluated at points chosen by Monte Carlo and decisions were made from there. From what I know, this seems to be one of the better methods for playing go ATM.

fryguy11y ago

This approach is known as Monte Carlo Tree Search, which usually follows a weighted search by how good the move is until it finds a leaf in the explored tree. Then it makes a new set of leaves for its moves and scores the path by randomly making moves until the game is finished and propagating the result up the path to the root. The wikipedia article has a better explanation: http://en.wikipedia.org/wiki/Monte_Carlo_tree_search

troels11y ago

From what I understand, it is also commonly used to predict optimal poker plays.

j / k navigate · click thread line to collapse