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).
- Successive over-relaxation: A Monte Carlo version of this technique can be seen as a variation on Gibbs sampling; it sometimes avoids random walks.
- Hybrid Monte Carlo (HMC): Tries to avoid random walk behaviour by introducing an auxiliary momentum vector and implementing Hamiltonian dynamics where the potential energy function is the target density. The momentum samples are discarded after sampling. The end result of Hybrid MCMC is that proposals move across the sample space in larger steps and are therefore less correlated and converge to the target distribution more rapidly.
- Some variations on slice sampling also avoid random walks.
- Langevin MCMC and other methods that rely on the gradient (and possibly second derivative) of the log posterior avoid random walks by making proposals that are more likely to be in the direction of higher probability density.
Read more about this topic: Markov Chain Monte Carlo
Famous quotes containing the words avoiding, random and/or walks:
“There is all the difference in the world between the criminal’s avoiding the public eye and the civil disobedient’s taking the law into his own hands in open defiance. This distinction between an open violation of the law, performed in public, and a clandestine one is so glaringly obvious that it can be neglected only by prejudice or ill will.”
—Hannah Arendt (1906–1975)
“There is a potential 4-6 percentage point net gain for the President [George Bush] by replacing Dan Quayle on the ticket with someone of neutral stature.”
—Mary Matalin, U.S. Republican political advisor, author, and James Carville b. 1946, U.S. Democratic political advisor, author. All’s Fair: Love, War, and Running for President, p. 205, Random House (1994)
“In my walks I would fain return to my senses.”
—Henry David Thoreau (1817–1862)