Simulation Methods Based on Markov Chains

- Let be an arbitrary finite set, e.g. a family of possible
digital binary or greyscale images
,
- where is a finite set of pixels
- and every pixel in the observation window gets mapped to a greyscale value ,
- resulting in a ,,matrix'' that has certain properties.

- Let
be an arbitrary probability function, i.e.
and
- If the number of elements in is large,
- the inversion method discussed in Section 3.2 as
well as acceptance-rejection sampling are
*inefficient*algorithms - for the generation of pseudo-random numbers in that are distributed according to .

- the inversion method discussed in Section 3.2 as
well as acceptance-rejection sampling are

**Remarks**-
- An alternative simulation method is based on
- constructing a Markov chain with state space
- and an (appropriately chosen) irreducible and aperiodic transition matrix ,
- such that is the ergodic limit distribution of the Markov chain.

- For sufficiently large
- is approximately -distributed
- and can thus serve as an efficient tool for the generation of (approximately) -distributed pseudo-random elements in .

- Therefore one also uses the term
*Markov-Chain-Monte-Carlo Simulation*(MCMC).

- An alternative simulation method is based on