Irreduzibilität und Aperiodizität

• Zur Erinnerung
  • In Theorem 2.4 hatten wir die Ergodizität der Markov-Kette $X_0,X_1,\ldots$ durch die Quasi-Positivität ihrer Übergangsmatrix ${\mathbf{P}}$ charakterisiert.
  • Es kann sich jedoch als schwierig erweisen, diese Eigenschaft von ${\mathbf{P}}$ direkt nachzuweisen (insbesondere dann, wenn $\ell\gg 1$).
• Wir leiten deshalb noch eine andere (probabilistische) Charakterisierung der Ergodizität von Markov-Ketten mit endlichem Zustandsraum her. Dabei benötigen wir den folgenden Begriff.
  • Für beliebige, jedoch fest vorgegebene Zustände $i,j\in E$ sagen wir, dass der Zustand $j$ vom Zustand $i$ erreichbar ist, falls $p_{ij}^{(n)}>0$ für ein $n\ge 0$ gilt, wobei ${\mathbf{P}}^{(0)}={\mathbf{I}}$. (Schreibweise: $i\to j$)
  • Eine andere (äquivalente) Definitionsmöglichkeit der Erreichbarbeit von Zuständen ist folgendermaßen gegeben.
  • Hierfür sei $\tau_j=\min\{n\ge 0:X_n=j\}$ die Anzahl der Schritte bis die Markov-Kette $\{X_n\}$ zum ersten Mal den Zustand $j\in E$ erreicht. Dabei setzen wir $\tau_j=\infty$, falls $X_n\neq j$ für jedes $n\ge 0$.

Theorem 2.7   $\;$ Sei $i\in E$ so gewählt, dass $P(X_0=i)>0$. In diesem Fall ist der Zustand $j\in E$ genau dann von $i$ erreichbar, wenn $P(\tau_j <\infty\mid X_0=i)>0$.

Beweis

 

• Die Notwendigkeit der Bedingung ist offensichtlich, denn es gilt
  $$\{X_n=j\}\subset\{\tau_j\le n\}\subset\{\tau_j<\infty\}$$   und somit$$\qquad 0<p_{ij}^{(n)}\le P(\tau_j<\infty\mid X_0=i)$$
  für ein $n\ge 0$, falls $j$ von $i$ erreichbar ist.
• Falls umgekehrt $i\not= j$ und $p_{ij}^{(n)}=0$ für jedes $n\ge 0$ gilt, dann folgt hieraus, dass
  

  $${P(\tau_j<\infty\mid X_0=i) = \lim_{n\to\infty} P(\tau_j<n\mid X_0=i)}$$

  $$= \lim_{n\to\infty} P\Bigl(\bigcup_{k=0}^{n-1}\{X_k=j\} \Bigm\vert X_0=i\Bigr)$$

  $$\le \lim_{n\to\infty} \sum_{k=0}^{n-1} P(X_k=j\mid X_0=i) = \lim_{n\to\infty}\sum_{k=0}^{n-1}p_{ij}^{(k)}=0\,.$$

  
  
  
   
    $\Box$
  
  
  

Beachte

 

• Die Eigenschaft der Erreichbarkeit ist
  • transitiv, d.h., aus $i\to k$ und $k\to j$ folgt $i\to j$.
  • Dies ergibt sich unmittelbar aus der Ungleichung $p^{(r+m)}_{ij}\ge p^{(r)}_{ik}p^{(m)}_{kj}$ (vgl. Korollar 2.2) und aus der Definition der Erreichbarkeit.
  • Falls darüber hinaus $i\to j$ und $j\to i$, dann sagen wir, dass die Zustände $i$ und $j$ kommunizieren. (Schreibweise: $i{\leftrightarrow}j$)
• Die Eigenschaft des Kommunizierens ist eine Äquivalenzrelation, denn es gilt

  (a)

  $i{\leftrightarrow}i$ (Reflexivität),

  (b)

  $i{\leftrightarrow}j$ genau dann, wenn $j{\leftrightarrow}i$ (Symmetrie),

  (c)

  $i{\leftrightarrow}k$ und $k{\leftrightarrow}j$ implizieren, dass $i{\leftrightarrow}j$ (Transitivität).

• Dies bedeutet insbesondere,
  • dass der Zustandsraum $E$ in (disjunkte und ausschöpfende) Äquivalenzklassen bezüglich der Äquivalenzrelation ${\leftrightarrow}$ zerlegt werden kann.
  • Dabei heißt die Markov-Kette $\{X_n\}$ bzw. ihre Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ irreduzibel, wenn der Zustandsraum $E$ nur aus einer solchen Äquivalenzklasse besteht, d.h., wenn $i{\leftrightarrow}j$ für sämtliche $i,j\in E$ gilt.

Beispiele

 

• Unmittelbar aus der Definition der Irreduzibilität ergibt sich, dass die $2\times 2$ Matrizen
  $${\mathbf{P}}_1=\left(\begin{array}{ll} 1/2 &1/2\\ [2pt] 1/2 & 1/2 \end{array}\right)$$   und$$\qquad {\mathbf{P}}_2=\left(\begin{array}{ll} 1/2 &1/2\\ [2pt] 1/4 & 3/4 \end{array}\right)$$
  irreduzibel sind.
• Die aus ${\mathbf{P}}_1$ und ${\mathbf{P}}_2$ gebildete $4\times 4$ Matrix ${\mathbf{P}}$ mit der folgenden Blockstruktur
  $${\mathbf{P}}=\left(\begin{array}{ll} {\mathbf{P}}_1 &{\,{\bf0}}\\ {\,{\bf0}}& {\mathbf{P}}_2 \end{array}\right)$$
  ist jedoch nicht irreduzibel.

Neben der Irreduzibilität benötigen wir noch eine weitere Eigenschaft der Zustände, nämlich die sogenannte Aperiodizität, um die Ergodizität von Markov-Ketten auf einfache Weise charakterisieren zu können.

Definition

 

• Die Periode $d_i$ des Zustandes $i\in E$ ist gegeben durch $d_i={\rm ggt}\{n\ge 1:p_{ii}^{(n)}>0\}$, wobei ,,ggt'' den größten gemeinsamen Teiler bezeichnet. Dabei setzen wir $d_i=\infty$, falls $p_{ii}^{(n)}=0$ für jedes $n\ge 1$.
• Der Zustand $i\in E$ heißt aperiodisch, falls $d_i=1$.
• Die Markov-Kette $\{X_n\}$ bzw. ihre Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ heißt aperiodisch, wenn sämtliche Zustände von $\{X_n\}$ aperiodisch sind.

Wir zeigen nun, dass die Perioden $d_i$ und $d_j$ übereinstimmen, wenn die Zustände $i,j$ zu einundderselben Äquivalenzklasse von kommunizierenden Zuständen gehören. Dabei verwenden wir die Schreibweise $i\to j[n]$, falls $p_{ij}^{(n)}>0$.

Theorem 2.8   Falls die Zustände $i,j\in E$ kommunizieren, dann gilt $d_i=d_j$.

Beweis

 

• Falls $j\to j[n]$, $i\to j[k]$ und $j\to i[m]$ for gewisse $k,m,n\ge 1$ gilt, dann ergibt sich aus den Ungleichungen in Korollar 2.2, dass $i\to i[k+m]$ und $i\to i[k+m+n]$.
• Dies bedeutet, dass die natürlichen Zahlen $k+m$ and $k+m+n$ durch $d_i$ teilbar sind.
• Dann ist auch $n=(k+m+n)-(k+m)$ durch $d_i$ teilbar.
• Somit ist $d_i$ ein gemeinsamer Teiler für diejenigen natürlichen Zahlen $n$, für die $p_{jj}^{(n)}>0$ gilt, d.h.  $d_i\le d_j$.
• Auf die gleiche Weise ergibt sich (aus Symmetriegründen), dass auch $d_j\le d_i$ gilt.
  
  $\Box$

Korollar 2.5   $\:$ Die Markov-Kette $\{X_n\}$ sei irreduzibel. Dann besitzen sämtliche Zustände von $\{X_n\}$ die gleiche Periode.

Um zeigen zu können,

• dass die in Abschnitt 2.2.1 betrachtete Charakterisierung (vgl. Theorem 2.4) der Ergodizität von Markov-Ketten gleichbedeutend mit ihrer Irreduzibilität und Aperiodizität ist,
• benötigen wir noch den folgenden elementaren Hilfssatz aus der Zahlentheorie.

Lemma 2.3   Sei $k=1,2,\ldots$ eine beliebige, jedoch fest vorgegebene natürliche Zahl. Dann gibt es eine natürliche Zahl $n_0\ge 1$, so dass

$$\{n_0,n_0+1,n_0+2,\ldots\}\subset\{n_1k+n_2(k+1); \ n_1,n_2\ge 0\}\,.$$

Beweis

 

• Falls $n\ge k^2$, dann gibt es ganze Zahlen $m,d\ge 0$, so dass $n-k^2=mk+d$ und $d<k$.
• Hieraus folgt, dass $n=(k-d+m)k+d(k+1)$ und somit
  $$n\in \{n_1k+n_2(k+1); \ n_1,n_2\ge 0\}\,,$$
  d.h., wir können $n_0=k^2$ setzen.
  
  $\Box$

Theorem 2.9   $\;$ Die Übergangsmatrix ${\mathbf{P}}$ ist genau dann quasi-positiv, wenn ${\mathbf{P}}$ irreduzibel und aperiodisch ist.

Beweis

 

• Wir nehmen zunächst an, dass die Übergangsmatrix ${\mathbf{P}}$ irreduzibel und aperiodisch ist.
  • Für jedes $i\in E$ betrachten wir die Menge $J(i)=\{n\ge 1:p^{(n)}_{ii}>0\}$, deren größter gemeinsamer Teiler wegen der Aperiodizität von ${\mathbf{P}}$ gleich $1$ ist.
  • Aus den Ungleichungen in Korollar 2.2 ergibt sich, dass
    $$p^{(n+m)}_{ii}\ge p^{(n)}_{ii}p^{(m)}_{ii}$$
    und somit

    $$n+m\in J(i)\,, \mbox{falls $n,m\in J(i)$.}$$ (50)

    
    

• Wir zeigen, dass die Menge $J(i)$ zwei aufeinanderfolgende Zahlen enthält.
  • Falls umgekehrt $J(i)$ nicht zwei aufeinanderfolgende Zahlen enthalten würde, dann würde es einen Minimalabstand $k\ge 2$ zwischen den Zahlen in $J(i)$ geben.
  • Hieraus würde die Gültigkeit von $mk+d\in J(i)$ für gewisse $m=0,1,\ldots$ und $d=1,\ldots,k-1$ folgen, weil ansonsten $n=mk$ für alle $n\in J(i)$ gelten würde.
  • Dies würde jedoch ein Widerspruch zu unserer Annahme sein, dass ggt$(J(i))=1$.
• Sei nun $n_1,n_1+k\in J(i)$. Wegen (50) gilt dann auch $a(n_1+k)\in J(i)$ und $n+bn_1\in J(i)$ für beliebige $a,b\in\mathbb{N}$, wobei

  $$n=mk+d\in J(i)\,.$$ (51)

  
  

• Wir zeigen jedoch,
  • dass es dann natürliche Zahlen $a,b\in\{1,2,\ldots\}$ gibt, so dass die Differenz zwischen $a(n_1+k)\in J(i)$ und $n+bn_1\in J(i)$ kleiner als $k$ ist.
  • Und zwar ergibt sich aus (51), dass
    $$a(n_1+k)-n-bn_1=(a-b)n_1+(a-m)k-d$$
    und somit für $a=b=m+1$
    $$a(n_1+k)-n-bn_1=k-d<k\,.$$

• Deshalb enthält die Menge $J(i)$ zwei aufeinanderfolgende Zahlen.
• Aus (50) und aus Lemma 2.3 ergibt sich nun, dass es für jedes $i\in E$ ein $n(i)\ge 1$ gibt, so dass

  $$J(i)\supset\{n(i),n(i)+1,\ldots\}\,.$$ (52)

  
  

• Hieraus, aus der Irreduzibilität von ${\mathbf{P}}$ und aus der Ungleichung (25) in Korollar 2.2, d.h.,
  $$p^{(r+n+m)}_{ij}\ge p^{(r)}_{ik}p^{(n)}_{kk}p^{(m)}_{kj}\,,$$
  folgt, dass es für jedes Paar $i,j\in E$ von Zuständen eine natürliche Zahl $n(ij)\ge 1$ gibt, so dass
  $$J(ij)=\{n\ge0:p^{(n)}_{ij}>0\}\supset\{n(ij),n(ij)+1,\ldots\}\,,$$
  d.h., ${\mathbf{P}}$ ist quasi-positiv.
• Umgekehrt ergibt sich die Irreduzibilität und Aperiodizität von quasi-positiven Übergangsmatrizen unmittelbar aus den Definitionen dieser Begriffe.
  
  $\Box$

Beachte

 

• Ein einfaches Beispiel einer Markov-Kette, die nicht irreduzibel ist,
  • kann durch das bereits mehrfach betrachtete Modell der Wettervorhersage gegeben werden, wobei $E=\{1,2\}$ und
    $${\mathbf{P}}=\left(\begin{array}{cc} 1-p & p\\ p^\prime & 1-p^\prime \end{array}\right)\;.$$

  • Falls $p=0$ oder $p^\prime=0$, dann ist die zugehörige Markov-Kette offenbar nicht irreduzibel (und damit wegen Theorem 2.9 auch nicht ergodisch).
• Es ist dennoch möglich, dass das lineare Gleichungssystem

  $${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}$$ (53)

  
  
  eine (oder unendlich viele) Wahrscheinlichkeitslösungen ${\boldsymbol{\alpha}}^\top=(\alpha_1,\alpha_2)$ besitzt.
  • Wenn beispielsweise $p=0$ und $p^\prime>0$ gilt, dann ist $i=1$ ein sogenannter absorbierender Zustand, und ${\boldsymbol{\alpha}}^\top=(1,0)$ ist die (eindeutig bestimmte) Lösung des linearen Gleichungssystems (53).
  • Wenn $p=0$ und $p^\prime=0$, dann ist jede Wahrscheinlichkeitsfunktion ${\boldsymbol{\alpha}}^\top=(\alpha_1,\alpha_2)$ Lösung des linearen Gleichungssystems (53).
• Wir geben nun noch Beispiele von Markov-Ketten $X_0,X_1,\ldots:\Omega\to E$ an, die nicht aperiodisch sind.
  • Dabei sind die Zufallsvariablen $X_0,X_1,\ldots:\Omega\to E$ nicht durch eine stochastische Rekursionsgleichung $X_n=\varphi(X_{n-1},Z_n)$ der Form (14) gegeben, so dass die ,,Zuwächse'' $Z_1,Z_2,\ldots:\Omega\to D$ unabhängige und identisch verteilte Zufallsvariablen sind.
  • Wir setzen nämlich lediglich voraus, dass die Zufallsvariablen $Z_1,Z_2,\ldots:\Omega\to D$ in dem folgenden Sinne ,,bedingt unabhängig'' sind.
  • Wie in Abschnitt 2.1.3 gezeigt wurde, kann man jedoch stets eine zu $X_0,X_1,\ldots$ stochastisch äquivalente Markov-Kette konstruieren, deren Zuwächse unabhängig sind, vgl. das in (17)-(19) betrachtete Konstruktionsprinzip.
• Seien also $E$ und $D$ beliebige endliche (oder abzählbar unendliche) Mengen, sei $\varphi:E\times D\to E$ eine beliebige Funktion, und seien $X_0,X_1,\ldots:\Omega\to E$ bzw. $Z_1,Z_2,\ldots:\Omega\to D$ Zufallsvariablen,
  • so dass

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

    
    

  • und dass für jedes $n\in\mathbb{N}$ die Zufallsvariable $Z_n$ bei gegebenem $X_{n-1}$ bedingt unabhängig von den Zufallsvariablen $Z_1,\ldots,Z_{n-1},X_0,\ldots,X_{n-2}$ ist.
  • D.h., für beliebige $n\in\mathbb{N}$, $i_0,i_1\ldots,i_{n-1}\in E$ und $k_1,\ldots,k_n\in D$ gelte
    

    $${P(Z_n=k_n,Z_{n-1}=k_{n-1},\ldots,Z_1=k_1, X_{n-1}=i_{n-1},\ldots,X_0=i_0)}$$

    $$= P(Z_n=k_n\mid X_{n-1}=i_{n-1}) \,P(Z_{n-1}=k_{n-1},\ldots,Z_1=k_1, X_{n-1}=i_{n-1},\ldots,X_0=i_0)\,,$$

    
    
    wobei wir $P(Z_n=k_n\mid X_{n-1}=i_{n-1})=0$ setzen, falls $P(X_{n-1}=i_{n-1})=0$.
  • Außerdem wird vorausgesetzt, dass für beliebige $i\in E$ und $k\in D$ die Wahrscheinlichkeiten $P(Z_n=k\mid X_{n-1}=i)$ nicht von $n\in\mathbb{N}$ abhängen.
• Man kann zeigen (vgl. Übungsaufgabe 4.2), dass die durch (54) rekursiv gegebene Folge $X_0,X_1,\ldots:\Omega\to E$ eine Markov-Kette ist, deren Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ gegeben ist durch
  $$p_{ij}=P(\varphi(i,Z_1)=j\mid X_0=i)\,,$$
  falls $P(X_0=i)>0$ für jedes $i\in E$.

Beispiel

$\;$ (Diffusionsmodell)
vgl. P. Brémaud (1999) Markov Chains. Springer-Verlag, New York, S.76

• Das folgende einfache Modell zur Beschreibung von Diffusionsvorgängen durch eine Membran wurde im Jahre 1907 von den Physikern Tatiana und Paul Ehrenfest vorgeschlagen. Dabei geht es um die Modellierung des Wärmeaustausches zwischen zwei Systemen mit unterschiedlichen Temperaturen.
  • Wir betrachten $\ell$ Partikel, die auf zwei miteinander durchlässig verbundene, aber nach außen isolierte Behälter $A$ und $B$ verteilt sind.
  • Angenommen zum Zeitpunkt $n-1$ befinden sich $X_{n-1}=i$ Partikel in $A$. Dann wird eine der $\ell$ insgesamt vorhandenen Partikel zufällig ausgewählt und in den jeweils anderen Behälter überführt.
  • Für den Zustand $X_n$ des Systems zum Zeitpunkt $n$ gilt somit entweder $X_n=i-1$ mit Wahrscheinlichkeit $i/\ell$ (falls die ausgewählte Partikel im Behälter $A$ war) oder $X_n=i+1$ mit Wahrscheinlichkeit $(\ell-i)/\ell$ (falls die ausgewählte Partikel im Behälter $B$ war).
• Die Zufallsvariablen $X_0,X_,\ldots:\Omega\to\{0,1,\ldots,\ell\}$ können also rekursiv definiert werden
  • durch die stochastische Rekursionsgleichung

    $$X_n=X_{n-1}+Z_n\,,$$ (55)

    
    

  • wobei die Zufallsvariable $Z_n$ bei gegebenem $X_{n-1}$ bedingt unabhängig von den Zufallsvariablen $Z_1,\ldots,Z_{n-1},X_0,\ldots,X_{n-1}$ ist mit $P(Z_n=-1)+P(Z_n=1)=1$ und
    $$P(Z_n=-1\mid X_{n-1}=i)=\frac{i}{\ell}\;,$$   $$\mbox{falls $P(X_{n-1}=i)>0$}$$$$\,.$$

  • Für die Eintragungen der Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ gilt somit
    $$p_{ij}=\left\{\begin{array}{ll} \displaystyle \frac{\ell-i}{\ell}... ..., &\mbox{falls $i>0$\ und $j=i-1$,}\\ 0\,, &\mbox{sonst.} \end{array}\right.$$

  • Dies bedeutet insbesondere, dass $d_i={\rm ggt}\{n\ge 1:p_{ii}^{(n)}>0\}=2$ für jedes $i\in\{0,1,\ldots,\ell\}$, d.h., die durch (55) gegebene Markov-Kette ist nicht aperiodisch (und damit wegen Theorem 2.9 auch nicht ergodisch).
• Das lineare Gleichungssystem

  $${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}$$ (56)

  
  
  besitzt dennoch eine (eindeutig bestimmte) Wahrscheinlichkeitslösung ${\boldsymbol{\alpha}}^\top=(\alpha_0,\ldots,\alpha_\ell)$ mit

  $$\alpha_i=\frac{1}{2^\ell}\;\left(\begin{array}{c}\ell\\ i\end{array}\right)\,,\qquad \forall\, i\in\{0,1,\ldots,\ell\}\,.$$ (57)

  
  

Beachte

 

• Das Diffusionsmodell von Ehrenfest ist ein Spezialfall des folgenden Klasse von Markov-Ketten, die in der Literatur Geburts- und Todesprozesse mit zwei reflektierenden Schranken genannt werden.
• Dabei wird erneut der Zustandraum $E=\{0,1,\ldots,\ell\}$ betrachtet, während die Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ gegeben ist durch

  $${\mathbf{P}}=\left(\begin{array}{cccccccc} 0 & 1 & & & & & & \\ ... ..._{\ell-1} & r_{\ell-1} & p_{\ell-1} \\ & & & & & & 1 & 0 \end{array}\right)\;,$$ (58)

  
  
  wobei $p_i>0$, $q_i>0$ und $p_i+q_i+r_i=1$ für jedes $i\in\{1,\ldots,\ell-1\}$.
• Das lineare Gleichungssystem ${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}$ hat dann die Form
  $$\alpha_i=\left\{\begin{array}{ll} p_{i-1}\alpha_{i-1}+r_i\alpha_i... ...,}\\ p_{\ell-1}\alpha_{\ell-1}\,, &\mbox{falls $i=\ell$.} \end{array}\right.$$
  • Man kann zeigen (vgl. Übungsaufgabe 4.3), dass
    $$\alpha_i=\alpha_0\;\frac{p_1p_2\cdot\ldots\cdot p_{i-1}}{q_1q_2\cdot\ldots\cdot q_i}\;,$$

  • wobei $\alpha_0>0$ durch die Normierungsbedingung $\sum_{i=0}^\ell \alpha_i=1$ gegeben ist, d.h.
    $$\alpha_0\Biggl(1+\frac{1}{q_1}+\frac{p_1}{q_1q_2}+\ldots+\frac{p_1p_2\cdot\ldots\cdot p_{\ell-1}}{q_1q_2\cdot\ldots\cdot q_\ell}\Biggr)=1$$
    bzw.
    $$\alpha_0=\Biggl(1+\frac{1}{q_1}+\frac{p_1}{q_1q_2}+\ldots+\frac{p_1p_2\cdot\ldots\cdot p_{\ell-1}}{q_1q_2\cdot\ldots\cdot q_\ell}\Biggr)^{-1}\,.$$

• Weil wir voraussetzen, dass $p_i>0$ und $q_i>0$ für jedes $i\in\{1,\ldots,\ell-1\}$ gilt, sind Geburts- und Todesprozesse mit zwei reflektierenden Schranken offenbar irreduzibel.
• Wenn zusätzlich $r_i>0$ für ein $i\in\{1,\ldots,\ell-1\}$ gilt, dann sind Geburts- und Todesprozesse mit zwei reflektierenden Schranken auch aperiodisch (und somit ergodisch wegen Theorem 2.9), vgl. Übungsaufgabe 4.3.