Markov Chain

  A Markov chain is a succession of elements each of which can be generated from a finite (usually small) number of elements preceding it, possibly with some random element added. One can talk about a Markov process of nth order, in which a memory of n elements fully describes the relevant history and the future behaviour of the process.

Markov chain Monte Carlo methods can be used in importance sampling, when in generating each point not only random numbers are used, but the previously generated point(s) enter with some weight, in the simplest case by a random walk, where , with r a random vector. The random perturbations used in simulated annealing are another example.