Rekursive Darstellung

• In diesem Abschnitt zeigen wir,
  • wie sich Markov-Ketten aus Folgen von unabhängigen und identisch verteilten Zufallsvariablen konstruieren lassen,
  • dass somit die Rekursionsformeln (9), (10), (11) und (13) Spezialfälle eines allgemeinen Konstruktionsprinzips für Markov-Ketten sind
  • und dass auch umgekehrt jede Markov-Kette als Lösung einer rekursiven stochastischen Gleichung aufgefasst werden kann.
• So wie bisher sei $E=\{1,2,\ldots,\ell\}$ eine endliche (oder abzählbar unendliche) Menge.
  • Außerdem sei $(D,\mathcal{D})$ ein beliebiger Maßraum, beispielsweise $D=\mathbb{R}^d$ der $d$-dimensionale euklidische Raum und $\mathcal{D}=\mathcal{B}(\mathbb{R}^d)$ die $\sigma$-Algebra der Borel-Mengen in $\mathbb{R}^d$, oder $D=[0,1]$ das Einheitsintervall und $\mathcal{D}=\mathcal{B}([0,1])$ die $\sigma$-Algebra der Borel-Mengen in $[0,1]$.
  • Sei nun $Z_1,Z_2,\ldots:\Omega\to D$ eine Folge von unabhängigen und identisch verteilten Zufallsvariablen, die ihre Werte in $D$ annehmen, und die Zufallsvariable $X_0:\Omega\to E$ sei unabhängig von $Z_1,Z_2,\ldots$.
  • Die Zufallsvariablen $X_1,X_2,\ldots:\Omega\to E$ seien durch die stochastische Rekursionsgleichung

    $$X_n=\varphi(X_{n-1},Z_n)$$ (14)

    
    
    gegeben, wobei $\varphi:E\times D\to E$ eine beliebige (messbare) Funktion ist.

Theorem 2.2    

• Die Zufallsvariablen $X_0,X_1,\ldots:\Omega\to E$ seien rekursiv durch $(\ref{rec.sto.equ})$ gegeben.
• Dann gilt für beliebige $n\ge 1$ und $i_0,i_1,\ldots,i_n\in E$,
  $$P(X_{n}=i_n\mid X_{n-1}=i_{n-1},\ldots,X_0=i_{0})= P(X_{n}=i_n\mid X_{n-1}=i_{n-1})\,,$$
  falls $P( X_{n-1}=i_{n-1},\ldots,X_0=i_{0})>0$.

Beweis

 

• Aus (14) ergibt sich, dass
  

  $$P(X_n=i_n\mid X_{n-1}=i_{n-1},\ldots,X_0=i_0) = P(\varphi(X_{n-1},Z_n)=i_n\mid X_{n-1}=i_{n-1},\ldots,X_0 =i_0)$$

  $$= P(\varphi(i_{n-1},Z_n)=i_n\mid X_{n-1}=i_{n-1},\ldots,X_0 =i_0)$$

  $$= P(\varphi(i_{n-1},Z_n)=i_n) \,,$$

  
  
  • wobei sich die letzte Gleichheit aus dem Transformationssatz für unabhängige Zufallsvariablen ergibt (vgl. Theorem WR-3.18),
  • denn die Zufallsvariablen $X_0,\ldots,X_{n-1}$ sind Funktionen von $Z_1,\ldots,Z_{n-1}$ und somit unabhängig von $\varphi(i_{n-1},Z_n)$.
• Auf die gleiche Weise ergibt sich, dass
  

  $$P(\varphi(i_{n-1},Z_n)=i_n) = P(\varphi(i_{n-1},Z_n)=i_n\mid X_{n-1}=i_{n-1})$$

  $$= P(\varphi(X_{n-1},Z_n)=i_n\mid X_{n-1}=i_{n-1})$$

  $$= P(X_n=i_n\mid X_{n-1}=i_{n-1})\,.$$

  
  
  
   
    $\Box$
  
  
  

Beachte

 

• Aus dem Beweis von Theorem 2.2 ergibt sich, dass die bedingte Wahrscheinlichkeit
  $$p_{ij}=P(X_n=j\mid X_{n-1}=i)$$
  gegeben ist durch $p_{ij}=P(\varphi(i,Z_n)=j)$.
• Dabei hängt $p_{ij}$ nicht von $n$ ab, weil die ,,Innovationen'' $Z_n$ identisch verteilt sind.
• Außerdem ist die (gemeinsame) Wahrscheinlichkeit $P(X_0=i_0,X_1=i_1, \ldots,X_n=i_n)$ gegeben durch

  $$P(X_0=i_0,X_1=i_1,\ldots,X_n=i_n)=\alpha_{i_0}p_{i_0i_1}\ldots p_{i_{n-1}i_n}\,,$$ (15)

  
  
  wobei $\alpha_{i_0}=P(X_0=i_0)$.
• Die durch (14) rekursiv gegebene Folge $X_0,X_1,\ldots$ von Zufallsvariablen ist also eine Markov-Kette im Sinne der Definitionsgleichung (3).

Wir zeigen nun, dass sich auch umgekehrt jede Markov-Kette als Lösung einer rekursiven stochastischen Gleichung auffassen lässt.

• Sei $X_0,X_1,\ldots:\Omega\to E$ eine beliebige Markov-Kette mit dem Zustandsraum $E=\{1,2,\ldots,\ell\}$, der Anfangsverteilung ${\boldsymbol{\alpha}}=(\alpha_1,\ldots,\alpha_\ell)^\top$ und der Übergangsmatrix ${\mathbf{P}}=(p_{ij})$.
• Mit Hilfe einer Rekursionsgleichung, die die gleiche Form wie (14) hat, wird eine Markov-Kette $X_0^\prime,X_1^\prime,\ldots$ mit (vorgegebener) Anfangsverteilung ${\boldsymbol{\alpha}}$ und Übergangsmatrix ${\mathbf{P}}$ rekursiv konstruiert, so dass

  $$P(X_0=i_0,\ldots,X_n=i_n)= P(X_0^\prime=i_0,\ldots,X_n^\prime=i_n)\,,\qquad\forall\,i_0,\ldots,i_n\in E$$ (16)

  
  
  für jedes $n\ge 0$ gilt:
  1. Wir gehen von einer Folge $Z_0,Z_1,\ldots$ von unabhängigen und identisch auf $(0,1]$-gleichverteilten Zufallsvariablen aus.
  2. Zunächst wird die $E$-wertige Zufallsvariable $X_0^\prime$ wie folgt definiert:
     $$\displaystyle X_0^\prime=k$$   genau dann, wenn$$\qquad Z_0\in\Bigl(\sum_{i=1}^{k-1} \alpha_i,\sum_{i=1}^{k}\alpha_i\Bigr]\,,$$
     für jedes $k=1,\ldots,\ell$, d.h.,

     $$X_0^\prime=\sum_{k=1}^\ell k {1\hspace{-1mm}{\rm I}}\Bigl(\sum_{i=1}^{k-1}\alpha_i <Z_0\le \sum_{i=1}^{k}\alpha_i\Bigr)\,.$$ (17)

     
     

  3. Die Zufallsvariablen $X_1^\prime,X_2^\prime,\ldots$ werden dann rekursiv definiert: Und zwar setzen wir

     $$X_n^\prime=\varphi(X_{n-1}^\prime,Z_n)\,,$$ (18)

     
     
     wobei die Funktion $\varphi:E\times(0,1]\to E$ gegeben ist durch

     $$\varphi(i,z)=\sum_{k=1}^\ell k {1\hspace{-1mm}{\rm I}}\Bigl(\sum_{j=1}^{k-1}p_{ij} <z\le \sum_{j=1}^{k}p_{ij}\Bigr)\,.$$ (19)

     
     

• Man kann sich leicht überlegen, dass die Wahrscheinlichkeiten $P(X_0^\prime=i_0,X_1^\prime=i_1,\ldots,X_n^\prime=i_n)$ für die in (17)-(18) rekursiv definierte Folge $\{X_n^\prime\}$ durch (3) gegeben sind, d.h., $\{X_n^\prime\}$ ist eine Markov-Kette mit der Anfangsverteilung ${\boldsymbol{\alpha}}$ und der Übergangsmatrix ${\mathbf{P}}$, vgl. Übungsaufgabe 2.1.

Beachte

 

• Folgen von Zufallsvariablen $\{X_i\}$ and $\{X_i^\prime\}$, für die (16) gilt, werden stochastisch äquivalent genannt.
• Das in (17)-(19) gegebene Konstruktionsprinzip kann zur Monte-Carlo-Simulation von Markov-Ketten mit vorgegebener Anfangsverteilung und Übergangsmatrix genutzt werden.
• Markov-Ketten mit abzählbar unendlichem Zustandsraum können auf die gleiche Weise konstruiert bzw. simuliert werden, wobei dann in (17)-(19) lediglich die Komponenten bzw. Eintragungen von unendlich dimensionalen Vektoren ${\boldsymbol{\alpha}}$ bzw. Matrizen ${\mathbf{P}}$ betrachtet werden müssen.