Grundlegende Definitionen und quasi-positive Übergangsmatrizen

• Wenn die Anzahl $\ell$ der potentiell möglichen Zustände der Markov-Kette $X_0,X_1,\ldots$ sehr groß ist, dann ist die in Abschnitt 2.1.4 diskutierte Spektraldarstellung (30) der $n$-stufigen Übergangsmatrix ${\mathbf{P}}^{(n)}={\mathbf{P}}^n$ kein geeignetes Hilfsmittel, um
  • die bedingten (Einzel-) Wahrscheinlichkeiten $p_{ij}^{(n)}=P(X_n=j\mid X_0=i)$ des zufälligen Zustandes $X_n$
  • bzw. die (unbedingten) Wahrscheinlichkeiten $P(X_n=j)=\sum_{i=1}^\ell\alpha_i p_{ij}^{(n)}$ von $X_n$
  nach $n\gg 1$ (Zeit-) Schritten zu berechnen.
• Man kann jedoch Bedingungen angeben,
  • unter denen die Grenzwerte $\lim_{n\to\infty} p_{ij}^{(n)}$ bzw. $\lim_{n\to\infty}P(X_n=j)$ existieren (gleich sind und nicht von $i$ abhängen),
  • so dass anstelle von $p_{ij}^{(n)}$ bzw. $P(X_n=j)$ der Grenzwert $\pi_j=\lim\limits_{n\to\infty} p_{ij}^{(n)}=\lim\limits_{n\to\infty}P(X_n=j)$ als Näherungslösung berechnet werden kann, falls $n\gg 1$.

Dies führt zu dem folgenden Begriff der Ergodizität von Markov-Ketten.

Definition

$\;$ Die Markov-Kette $X_0,X_1,\ldots$ mit der Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ bzw. den zugehörigen $n$-stufigen Übergangsmatrizen ${\mathbf{P}}^{(n)}=(p^{(n)}_{ij})$ $(={\mathbf{P}}^n$) heißt ergodisch, falls die Grenzwerte

$$\pi_j=\lim_{n\to\infty} p_{ij}^{(n)}$$ (33)

1. für jedes $j\in E$ existieren,
2. positiv sind und nicht von $i\in E$ abhängen,
3. eine Wahrscheinlichkeitsfunktion ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ bilden, d.h., $\sum_{j\in E}\pi_j=1$.

Beispiel

$\;$ (Wettervorhersage)

• Um den Begriff der Ergodizität von Markov-Ketten zu verdeutlichen, kehren wir zunächst zu dem einfachen Beispiel der Wettervorhersage zurück, das bereits in den Abschnitten 2.1.2 und 2.1.4 diskutiert wurde.
• Sei also $E=\{1,2\}$, und sei
  $${\mathbf{P}}=\left(\begin{array}{cc} 1-p & p\\ p^\prime & 1-p^\prime \end{array}\right)$$
  eine beliebige Übergangsmatrix mit $0<p,p^\prime\le 1$.
• Die $n$-stufige Übergangsmatrix ${\mathbf{P}}^{(n)}={\mathbf{P}}^n$ ist gegeben durch
  $${\mathbf{P}}^n=\frac{1}{p+p^\prime} \left(\begin{array}{cc} p^\pr... ... \left(\begin{array}{cc} p & -p\\ -p^\prime & p^\prime \end{array}\right)\,.$$

• Falls $p+p^\prime<2$, dann ergibt sich hieraus und aus (26), dass
  $$\displaystyle \lim_{n\to\infty}{\mathbf{P}}^n=\frac{1}{p+p^... ...n{array}{cc} p^\prime & p \\ p^\prime & p \end{array}\right)$$
  bzw.

  $${\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n=\Bigl(\frac{p^\prime}{p+p^\prime}\;, \;\frac{p}{p+p^\prime}\Bigr)^\top\,,$$ (34)

  
  
  wobei die Grenzverteilung ${\boldsymbol{\pi}}$ in (34) nicht von der Wahl der Anfangsverteilung ${\boldsymbol{\alpha}}$ $(={\boldsymbol{\alpha}}_0)$ abhängt.
• Wenn jedoch $p+p^\prime=2$, dann gilt
  $${\mathbf{P}}^n=\left\{ \begin{array}{ll} {\mathbf{P}}\,, & \... ...athbf{I}}\,, &\mbox{falls $n$\ gerade ist}. \end{array}\right.$$

Die Ergodizität von Markov-Ketten mit allgemeinem (endlichen) Zustandsraum lässt sich mit Hilfe des folgenden Begriffes aus der Theorie positiver Matrizen charakterisieren.

Definition

 

• Die $\ell\times\ell$ Matrix ${\mathbf{A}}=(a_{ij})$ heißt nichtnegativ, falls sämtliche Eintragungen $a_{ij}$ von ${\mathbf{A}}$ nichtnegativ sind.
• Die nichtnegative Matrix ${\mathbf{A}}$ heißt quasi-positiv, falls es eine natürliche Zahl $n_0\ge 1$ gibt, so dass sämtliche Eintragungen von ${\mathbf{A}}^{n_0}$ positiv sind.

Beachte

  Falls ${\mathbf{A}}$ eine stochastische Matrix ist, für die es eine natürliche Zahl $n_0\ge 1$ gibt, so dass sämtliche Eintragungen von ${\mathbf{A}}^{n_0}$ positiv sind, dann sind auch sämtliche Eintragungen von ${\mathbf{A}}^n$ für jede natürliche Zahl $n\ge n_0$ positiv.

Theorem 2.4   Die Markov-Kette $X_0,X_1,\ldots$ mit dem Zustandsraum $E=\{1,\ldots,\ell\}$ und der Übergangsmatrix ${\mathbf{P}}$ ist genau dann ergodisch, wenn ${\mathbf{P}}$ quasi-positiv ist.

Beweis

 

• Wir zeigen zunächst, dass die Bedingung

  $$\min_{i,j\in E}p_{ij}^{(n_0)}>0$$ (35)

  
  
  für ein $n_0\in\mathbb{N}$ hinreichend für die Ergodizität von $\{X_n\}$ ist.
  • Sei $m_j^{(n)}=\min_{i\in E}p_{ij}^{(n)}$ und $M_j^{(n)}=\max_{i\in E}p_{ij}^{(n)}$. Aus der Chapman-Kolmogorov-Gleichung (23) ergibt sich dann, dass
    $$p_{ij}^{(n+1)}=\sum_{k\in E}p_{ik}p_{kj}^{(n)}$$
    und somit
    $$m_j^{(n+1)} = \min_{i}p_{ij}^{(n+1)} =\min_i\sum_kp_{ik}p_{kj}^{(n)} \ge \min_i\sum_kp_{ik}\min_kp_{kj}^{(n)}=m_j^{(n)},$$
    d.h., $m_j^{(n)}\le m_j^{(n+1)}$ für jedes $n\ge 0$, wobei wir ${\mathbf{P}}^{(0)}={\mathbf{I}}$ setzen. Auf die gleiche Weise ergibt sich, dass $M_j^{(n)}\ge M_j^{(n+1)}$ für jedes $n\ge 0$ gilt.
  • Um die Existenz der Grenzwerte $\pi_j$ in (33) zu beweisen, genügt es also zu zeigen, dass für jedes $j\in E$

    $$\lim_{n\to\infty}(M_j^{(n)}-m_j^{(n)})=0\,.$$ (36)

    
    

  • Hierfür betrachten wir für beliebige, jedoch fest vorgegebene Zustände $i_0,j_0\in E$ die Mengen $E^\prime=\{k\in E: p_{i_0k}^{(n_0)}\ge p_{j_0k}^{(n_0)}\}$ und $E^{\prime\prime}=E\setminus E^\prime$.
  • Sei $a=\min_{i,j\in E}p_{ij}^{(n_0)}> 0$. Dann gilt
    $$\sum\limits_{k\in E^\prime}\bigl(p_{i_0k}^{(n_0)}-p_{j_0k}^{(n_0)... ...rime}}p_{i_0k}^{(n_0)}-\sum\limits_{k\in E^\prime}p_{j_0k}^{(n_0)}\le 1-\ell a$$
    und
    $$\sum_{k\in E^{\prime\prime}} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n... ...\bigr)=-\sum_{k\in E^\prime} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\bigr)\,.$$

  • Durch die erneute Anwendung der Chapman-Kolmogorov-Gleichung (23) ergibt sich hieraus, dass für beliebige $n\ge 0$ und $j\in E$
    

    $$p_{i_0j}^{(n_0+n)}-p_{j_0j}^{(n_0+n)} = \sum_{k\in E} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\bigr) p_{kj}^{(n)}$$

    $$= \sum_{k\in E^\prime} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\big... ...n E^{\prime\prime}} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\bigr) p_{kj}^{(n)}$$

    $$\le \sum_{k\in E^\prime} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\big... ...k\in E^{\prime\prime}} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\bigr) m_j^{(n)}$$

    $$= \sum_{k\in E^\prime} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\big... ...}-\sum_{k\in E^\prime} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\bigr) m_j^{(n)}$$

    $$= \sum_{k\in E^\prime} \bigl(p_{i_0k}^{(n_0)}- p_{j_0k}^{(n_0)}\bigr) \bigl(M_j^{(n)}- m_j^{(n)}\bigr)$$

    $$\le (1-\ell a) \bigl(M_j^{(n)}- m_j^{(n)}\bigr)\,.$$

    
    

  • Hieraus folgt, dass $M_j^{(n_0+n)}-m_j^{(n_0+n)}\le(M_j^{(n)}-m_j^{(n)})(1-\ell a)$ und (mit vollständiger Induktion) dass für jedes $k\ge 1$

    $$M_j^{(kn_0+n)}-m_j^{(kn_0+n)}\le(M_j^{(n)}-m_j^{(n)})(1-\ell a)^k\,.$$ (37)

    
    

  • Es gibt also eine (unbegrenzt wachsende) Folge $n_1,n_2,\ldots$ von natürlichen Zahlen, so dass für jedes $j\in E$

    $$\lim_{k\to\infty}(M_j^{(n_k)}-m_j^{(n_k)})=0\,.$$ (38)

    
    

  • Weil die Differenzen $M_j^{(n)}-m_j^{(n)}$ monoton in $n$ sind, gilt (38) für jede (unbegrenzt wachsende) Folge $n_1,n_2,\ldots$ von natürlichen Zahlen.
  • Damit ist die Gültigkeit von (36) bewiesen.
• Die Grenzwerte $\pi_j$ sind positiv, weil
  $$\displaystyle \pi_j=\lim_{n\to\infty}p_{ij}^{(n)}\ge\lim_{n\to\infty}m_j^{(n)}\ge m_j^{(n_0)}\ge a>0\,.$$

• Außerdem gilt $\sum_{j\in E}\pi_j=\sum_{j\in E}\lim_{n\to\infty}p_{ij}^{(n)} =\lim_{n\to\infty} \sum_{j\in E}p_{ij}^{(n)}=1$, weil die Vertauschung von Grenzwert und endlicher Summation erlaubt ist.
• Die Notwendigkeit der Bedingung (35) ergibt sich unmitttelbar aus $\min_{j\in E}\pi_j>0$ und (33), wenn dabei berücksichtigt wird, dass der Zustandsraum $E$ endlich ist.
  
  $\Box$

Beachte

 

• Weil die Grenzwerte $\pi_j=\lim_{n\to\infty} p_{ij}^{(n)}$ ergodischer Markov-Ketten nicht von $i$ abhängen, ergibt sich hieraus und aus der Endlichkeit des Zustandsraumes $E=\{1,\ldots,\ell\}$, dass
  $$\lim_{n\to\infty}{\boldsymbol{\alpha}}_n^\top={\boldsymbol{\alpha}}^\top\lim_{n\to\infty}{\mathbf{P}}^{(n)}={\boldsymbol{\pi}}^\top\,.$$

• Im Beweis von Theorem 2.4 wurde nicht nur die Existenz der Grenzwerte $\pi_j=\lim_{n\to\infty} p_{ij}^{(n)}$ gezeigt, sondern die folgende Abschätzung der Konvergenzgeschwindigkeit hergeleitet: Aus (37) ergibt sich nämlich, dass

  $$\sup\limits_{i,j\in E}\displaystyle \vert p_{ij}^{(n)}-\pi_j\vert... ...\bigl(M_j^{(n)}-m_j^{(n)}\bigr)\le (1-\ell a)^{\left\lfloor n/n_0\right\rfloor}$$ (39)

  
  
  bzw.

  $$\sup\limits_{j\in E}\vert\alpha_{nj}-\pi_j\vert\le (1-\ell a)^{\left\lfloor n/n_0\right\rfloor}\,,$$ (40)

  
  
  wobei $\left\lfloor n/n_0\right\rfloor$ den ganzzahligen Teil von $n/n_0$ bezeichnet.
• Im Zusammenhang mit (39) und (40) spricht man in der Literatur von geometrischen Schranken der Konvergenzgeschwindigkeit.

Wir zeigen nun noch, dass die Grenzwerte $\pi_j=\lim_{n\to\infty} p_{ij}^{(n)}$ auch als Lösung eines linearen Gleichungssystems aufgefasst werden können.

Theorem 2.5    

• Sei $X_0,X_1,\ldots$ eine ergodische Markov-Kette mit dem Zustandsraum $E=\{1,\ldots,\ell\}$ und der Übergangsmatrix ${\mathbf{P}}=(p_{ij})$.
• Dann ist der Vektor ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ der Grenzwerte $\pi_j=\lim_{n\to\infty} p_{ij}^{(n)}$ die eindeutig bestimmte (positive) Lösung des linearen Gleichungssystems

  $$\pi_j=\sum_{i\in E}\pi_i p_{ij}\,,\qquad j\in E,$$ (41)

  
  
  die gleichzeitig der Normierungsbedingung $\sum_{j\in E}\pi_j=1$ genügt.

Beweis

 

• Aus der Definitionsgleichung (33) der Grenzwerte $\pi_j$ und aus der Chapman-Kolmogorov-Gleichung (23) ergibt sich durch Vertauschen von Grenzwert und Summation, dass
  $$\pi_j \stackrel{(\ref{con.tra.pro})}... ...ki}^{(n-1)}p_{ij} \stackrel{(\ref{con.tra.pro})}{=}\sum_{i\in E}\pi_ip_{ij}\,.$$

• Wir nehmen nun an, dass es noch eine weitere positive Lösung ${\boldsymbol{\pi}}^\prime=(\pi_1^\prime,\ldots,\pi_\ell^\prime)^\top$ von (41) gibt, so dass $\pi_j^\prime=\sum_{i\in E}\pi_i^\prime p_{ij}$ für jedes $j\in E$ und $\sum_{j\in E}\pi_j^\prime=1$.
• Mit vollständiger Induktion kann man dann zeigen, dass

  $$\pi_j^\prime=\sum_{i\in E}\pi_i^\prime p_{ij}^{(n)},\qquad j\in E\,,$$ (42)

  
  
  für jedes $n=1,2,\ldots$.
• Insbesondere ergibt sich somit aus (42), dass
  $$\pi_j^\prime\stackrel{(\ref{pi.rowna... ...ime_i \lim_{n\to\infty} p_{ij}^{(n)}\stackrel{(\ref{con.tra.pro})}{=} \pi_j\,.$$
  
   
    $\Box$
  
  
  

Beachte

 

• In Matrix-Schreibweise hat das lineare Gleichungssystem (41) die Form ${\boldsymbol{\pi}}^\top={\boldsymbol{\pi}}^\top{\mathbf{P}}$.
• Wenn die Anzahl $\ell$ der Zustände nicht zu groß ist, dann kann dieses Gleichungssystem ein Ausgangspunkt zur numerischen Bestimmung der Wahrscheinlichkeitsfunktion ${\boldsymbol{\pi}}$ sein; vgl. Abschnitt 2.2.5.
• Falls $\ell\gg 1$, dann ist in vielen Fällen dynamische Monte-Carlo-Simulation besser zur Bestimmnug von ${\boldsymbol{\pi}}$ geeignet; vgl. Abschnitt 3.3.