| Random Walk Monte Carlo |
Website Links For Markov |
Information AboutRandom Walk Monte Carlo |
| CATEGORIES ABOUT MARKOV CHAIN MONTE CARLO | |
| monte carlo methods | |
|
Usually it is not hard to construct a Markov Chain with the desired properties. The more difficult problem is to determine how many steps are needed to converge to the stationary distribution within an acceptable error. A good chain will have Rapid Mixing —the stationary distribution is reached quickly starting from an arbitrary position. Tools for proving rapid mixing include arguments based on Conductance and the Coupling Method . Typical use of MCMC sampling can only approximate the target distribution, as there is always some residual effect of the starting position. More sophisticated MCMC-based algorithms such as Coupling From The Past can produce exact samples, at the cost of additional computation and an unbounded (though finite on average) Running Time . The most common application of these algorithms is numerically calculating multi-dimensional Integral s. In these methods, an Ensemble of "walkers" moves around randomly. At each point where the walker steps, the integrand value at that point is counted towards the integral. The walker then may make a number of tentative steps around the area, looking for a place with reasonably high contribution to the integral to move into next. Random walk methods are a kind of random simulation or Monte Carlo Method . However, whereas the random samples of the integrand used in a conventional Monte Carlo integration are Statistically Independent , those used in MCMC are '' Correlated ''. A Markov Chain is constructed in such a way as to have the integrand as its Equilibrium Distribution . Surprisingly, this is often easy to do. Multi-dimensional integrals often arise in Bayesian Statistics and Computational Physics , so Markov chain Monte Carlo methods are widely used in those fields. RANDOM WALK ALGORITHMS Many Markov chain Monte Carlo methods move around the equilibrium distribution in relatively small steps, with no tendency for the steps to proceed in the same direction. These methods are easy to implement and analyse, but unfortunately it can take a long time for the walker to explore all of the space. The walker will often double back and cover ground already covered. Here are some random walk MCMC methods:
AVOIDING RANDOM WALKS More sophisticated algorithms use some method of preventing the walker from doubling back. These algorithms may be harder to implement, but may exhibit faster convergence (i.e. fewer steps for an accurate result).
CHANGING DIMENSION The Reversible Jump method is a variant of Metropolis-Hastings that allows proposals that change the dimensionality of the space. REFERENCES
|
|
|