Tricks with Monte Carlo Simulations

Tricks with Monte Carlo Simulations(countbayesie.com)

40 points by CountBayesie 11 years ago | 4 comments

mturmon 11 years ago |

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.

pmalynin 11 years 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.

fryguy 11 years 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

troels 11 years ago | |

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