Simulationsmethoden mit Markov-Ketten

• Sei $E$ eine beliebige endliche Menge, beispielsweise eine gewisse Menge von (potentiell möglichen) digitalisierten Binär- bzw. Graustufenbildern ${\mathbf{x}}=(x(v),\,v\in V)$,
  • wobei $V$ eine endliche Menge von Pixeln ist,
  • jedem Pixel $v\in V$ aus dem ,,Beobachtungsfenster'' $V$ ein Graustufenwert $x(v)\ge 0$ zugeordnet wird,
  • so dass eine ,,Matrix'' $(x(v),\,v\in V)$ mit bestimmten Eigenschaften entsteht.
• Sei ${\boldsymbol{\pi}}:E\to(0,1)$ eine beliebige (Wahrscheinlichkeits-) Funktion mit
  $$\sum\limits_{{\mathbf{x}}\in E} \pi_{\mathbf{x}}=1$$   und$$\qquad\pi_{\mathbf{x}}>0\,,\quad\forall\,{\mathbf{x}}\in E\,.$$

• Wenn die Anzahl $\vert E\vert$ der Elemente der Menge $E$ groß ist,
  • dann führt die in Abschnitt 3.2 diskutierte Inversionsmethode bzw. die Akzeptanz- und Verwerfungsmethode typischerweise nicht zu effizienten Algorithmen,
  • um gemäß ${\boldsymbol{\pi}}$ verteilte Pseudozufallselemente ${\mathbf{x}}_1,{\mathbf{x}}_2,\ldots$ aus $E$ zu erzeugen.

Beachte

 

• Eine alternative Simulationsmethode beruht
  • auf der Konstruktion einer Markov-Kette ${\mathbf{X}}_0,{\mathbf{X}}_1,\ldots$ mit dem Zustandsraum $E$
  • und mit einer (geeignet gewählten) irreduziblen und aperiodischen Übergangsmatrix ${\mathbf{P}}$,
  • so dass ${\boldsymbol{\pi}}$ die ergodische (Grenz-) Verteilung der Markov-Kette ist.
• Für hinreichend großes $n$
  • ist dann ${\mathbf{X}}_n$ näherungsweise ${\boldsymbol{\pi}}$-verteilt und
  • kann somit in vielen Fällen zur effizienten Erzeugung von (näherungsweise) ${\boldsymbol{\pi}}$-verteilten Pseudozufallselementen aus $E$ dienen.
• Man spricht deshalb in diesem Zusammenhang von Markov-Chain-Monte-Carlo-Simulation (MCMC).