Simulation Methods Based on Markov Chains

• Let $E$ be an arbitrary finite set, e.g. a family of possible digital binary or greyscale images ${\mathbf{x}}=(x(v),\,v\in V)$,
  • where $V$ is a finite set of pixels
  • and every pixel $v\in V$ in the observation window $V$ gets mapped to a greyscale value $x(v)\ge 0$,
  • resulting in a ,,matrix'' $(x(v),\,v\in V)$ that has certain properties.
• Let ${\boldsymbol{\pi}}:E\to(0,1)$ be an arbitrary probability function, i.e.
  $$\sum\limits_{{\mathbf{x}}\in E} \pi_{\mathbf{x}}=1$$   and$$\qquad\pi_{\mathbf{x}}>0\,,\quad\forall\,{\mathbf{x}}\in E\,.$$

• If the number $\vert E\vert$ of elements in $E$ 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 ${\mathbf{x}}_1,{\mathbf{x}}_2,\ldots$ in $E$ that are distributed according to ${\boldsymbol{\pi}}$.

Remarks

 

• An alternative simulation method is based on
  • constructing a Markov chain ${\mathbf{X}}_0,{\mathbf{X}}_1,\ldots$ with state space $E$
  • and an (appropriately chosen) irreducible and aperiodic transition matrix ${\mathbf{P}}$,
  • such that ${\boldsymbol{\pi}}$ is the ergodic limit distribution of the Markov chain.
• For sufficiently large $n$
  • ${\mathbf{X}}_n$ is approximately ${\boldsymbol{\pi}}$-distributed
  • and can thus serve as an efficient tool for the generation of (approximately) ${\boldsymbol{\pi}}$-distributed pseudo-random elements in $E$.
• Therefore one also uses the term Markov-Chain-Monte-Carlo Simulation (MCMC).