Can anyone explain to me how to use a Las Vegas algorithm and/or a Monte Carlo algorithm?
March 26th, 2010
I am not understanding . . . Thanks.
Basically when you have a huge number of variables actual evaluation of the function becomes extremely difficult. A five dimensional integral would require 200^5 function evaluations to implement a method with 200 points per axis. It is easy to code analyses that take hours or even days to run. The Monte Carlo method, as it is understood today, encompasses any technique of statistical sampling employed to approximate solutions to quantitative problems. The Monte Carlo approach deals with this problem by sampling the integrand via statistical means. The method calls for a random walk, or a guided random walk, in phase space during which the integrand is evaluated at each step and averaged over. It may produce incorrect results, but with bounded error probability. In general, Monte Carlo methods are used in mathematics to solve various problems by generating suitable random numbers and observing that fraction of the numbers obeying some property or properties. A Monte Carlo algorithm gives more precise results the longer you run it. A Las Vegas algorithm gives exactly the right answer, but the run time is indeterminate. The links I’m including show some examples designed to familiarize you with implementation of the method. Hope this helps, Monte Carlo methods are complex and non-intuitive.
March 26th, 2010 at 2:22 pm
Basically when you have a huge number of variables actual evaluation of the function becomes extremely difficult. A five dimensional integral would require 200^5 function evaluations to implement a method with 200 points per axis. It is easy to code analyses that take hours or even days to run. The Monte Carlo method, as it is understood today, encompasses any technique of statistical sampling employed to approximate solutions to quantitative problems. The Monte Carlo approach deals with this problem by sampling the integrand via statistical means. The method calls for a random walk, or a guided random walk, in phase space during which the integrand is evaluated at each step and averaged over. It may produce incorrect results, but with bounded error probability. In general, Monte Carlo methods are used in mathematics to solve various problems by generating suitable random numbers and observing that fraction of the numbers obeying some property or properties. A Monte Carlo algorithm gives more precise results the longer you run it. A Las Vegas algorithm gives exactly the right answer, but the run time is indeterminate. The links I’m including show some examples designed to familiarize you with implementation of the method. Hope this helps, Monte Carlo methods are complex and non-intuitive.
References :
http://einstein.drexel.edu/courses/PHYS405/Monte_Carlo/index.html
http://en.wikipedia.org/wiki/Monte_Carlo_method
http://www.nist.gov/dads/HTML/monteCarlo.html