Stationäre Anfangsverteilungen

• Zur Erinnerung
  • Falls $\{X_n\}$ eine irreduzible und aperiodische Markov-Kette mit dem (endlichen) Zustandsraum $E=\{1,\ldots,\ell\}$ und der (quasi-positiven) Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ ist,
  • dann ist die Grenzverteilung ${\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n$ die eindeutig bestimmte Lösung der folgenden Matrix-Gleichung (vgl. Theorem 2.5):

    $${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}\,.$$ (59)

    
    

• Wenn nicht vorausgesetzt wird, dass die Markov-Kette $\{X_n\}$ irreduzibel ist, dann kann (59) mehr als eine (Wahrscheinlichkeits-) Lösung besitzen.
  • Falls die Anfangsverteilung ${\boldsymbol{\alpha}}_0$ von $\{X_n\}$ eine solche Lösung von (59) ist, dann implizieren Theorem 2.3 und (59) darüber hinaus, dass
    $${\boldsymbol{\alpha}}_1^\top={\boldsymbol{\alpha}}_0^\top{\mathbf{P}}={\boldsymbol{\alpha}}_0^\top$$
    und somit ${\boldsymbol{\alpha}}_n={\boldsymbol{\alpha}}_0$ für jedes $n\ge 0$.
  • Wegen dieser Invarianzeigenschaft wird jede (Wahrscheinlichkeits-) Lösung ${\boldsymbol{\alpha}}$ von (59) eine stationäre Anfangsverteilung von $\{X_n\}$ genannt.
• Umgekehrt kann man zeigen, dass,
  • die Matrix-Gleichung (59) genau eine (Wahrscheinlichkeits-) Lösung ${\boldsymbol{\alpha}}$ besitzt, falls ${\mathbf{P}}$ irreduzibel ist,
  • wobei diese Lösung ${\boldsymbol{\alpha}}$ von (59) jedoch nicht notwendig die Grenzverteilung ${\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n$ sein muss, die nämlich dann nicht existiert, falls ${\mathbf{P}}$ nicht aperiodisch ist.

Theorem 2.10    

• Sei ${\mathbf{P}}=(p_{ij})_{i,j\in E}$ eine irreduzible Übergangsmatrix, wobei $E=\{1,\ldots,\ell\}$.
• Für beliebige, aber fest vorgegebene $i,j\in E$ konvergieren dann die Eintragungen $q^{(n)}_{ij}$ der stochastischen $(\ell\times\ell)$-dimensionalen Matrizen ${\mathbf{Q}}_n=(q_{ij}^{(n)})$ mit

  $${\mathbf{Q}}_n= \frac{1}{n}\;\bigl({\mathbf{P}}+{\mathbf{P}}^2+\ldots+{\mathbf{P}}^n\bigr)$$ (60)

  
  
  gegen einen Grenzwert

  $$\alpha_j=\lim_{n\to\infty}q_{ij}^{(n)}>0\,,$$ (61)

  
  
  der nicht von $i$ abhängt, so dass $\sum_{j=1}^\ell \alpha_j=1$ und dass der Vektor ${\boldsymbol{\alpha}}=(\alpha_1,\ldots,\alpha_\ell)^\top$ eine Lösung der Matrix-Gleichung  $(\ref{eq-inv})$ ist.
• Die in $(\ref{gre.mat.ces})$- $(\ref{alp.gre.quh})$ gegebene Verteilung ${\boldsymbol{\alpha}}$ ist die einzige Wahrscheinlichkeitslösung von $(\ref{eq-inv})$.

Einen Beweis von Theorem 2.10 kann man beispielsweise in Kapitel 7 des Buches E. Behrends (2000) Introduction to Markov Chains, Vieweg, Braunschweig finden.

Beachte

 

• Außer der Invarianzeigenschaft ${\boldsymbol{\alpha}}_0={\boldsymbol{\alpha}}_1=\ldots$ besitzt die Markov-Kette $\{X_n\}$ mit der stationären Anfangsverteilung ${\boldsymbol{\alpha}}_0$ noch eine wesentlich stärkere Invarianzeigenschaft (und zwar für sämtliche endlich-dimensionalen Verteilungen).
• In diesem Zusammenhang betrachten wir den folgenden Begriff der (streng) stationären Folge von Zufallsvariablen.

Definition

 

• Sei $X_0,X_1,\ldots:\Omega\to E$ eine beliebige Folge von Zufallsvariablen mit Werten in $E=\{1,\ldots,\ell\}$ (die nicht unbedingt eine Markov-Kette sein müssen).
• Die Folge $\{X_n\}$ von $E$-wertigen Zufallsvariablen heißt stationär, falls für beliebige $k,n\in\{0,1,\ldots\}$ und $i_0,\ldots,i_n\in E$ gilt, dass

  $$P(X_k=i_0,X_{k+1}=i_1,\ldots,X_{k+n}=i_n) =P(X_0=i_0,X_{1}=i_1,\ldots,X_{n}=i_n)\,.$$ (62)

  
  

Theorem 2.11    

• Sei $X_0,X_1,\ldots:\Omega\to E$ eine Markov-Kette mit dem Zustandsraum $E=\{1,\ldots,\ell\}$.
• Die Markov-Kette $\{X_n\}$ ist genau dann eine stationäre Folge von Zufallsvariablen, wenn sie eine stationäre Anfangsverteilung besitzt.

Beweis

 

• Die Notwendigkeit der Bedingung ergibt sich unmittelbar 
  • aus Theorem 2.3 sowie aus den Definitionen der Begriffe ,,stationäre Anfangsverteilung'' bzw. ,,stationäre Folge von Zufallsvariablen'',
  • denn die Gültigkeit von (62) impliziert insbesondere, dass $P(X_1=i)=P(X_0=i)$ für jedes $i\in E$
  • und aus Theorem 2.3 ergibt sich somit, dass ${\boldsymbol{\alpha}}_0^\top={\boldsymbol{\alpha}}_1^\top={\boldsymbol{\alpha}}_0^\top{\mathbf{P}}$, d.h. ${\boldsymbol{\alpha}}_0$ ist eine stationäre Anfangsverteilung.
• Sei nun umgekehrt ${\boldsymbol{\alpha}}_0$ eine stationäre Anfangsverteilung der Markov-Kette $\{X_n\}$.
  • Dann ergibt sich aus der Definitionsgleichung (3) der Markov-Kette $\{X_n\}$, dass
    

    $${P(X_k=i_0,X_{k+1}=i_1,\ldots,X_{k+n}=i_n)}$$

    $$= \sum\limits_{i_0^\prime,\ldots,i_{k-1}^\prime\in E} P(X_0=i_0^\prime,\ldots,X_{k-1}=i_{k-1}^\prime, X_k=i_0,X_{k+1}=i_1,\ldots,X_{k+n}=i_n)$$

    $$= \sum\limits_{i_0^\prime,\ldots,i_{k-1}^\prime\in E} \alpha_{0, i_... ... i_{k-1}^\prime}\, p_{i_{k-1}^\prime i_0}\;p_{i_0 i_1}\;\ldots\; p_{i_{n-1}i_n}$$

    $$= \Bigl({\boldsymbol{\alpha}}_0^\top{\mathbf{P}}^k\Bigr)_{i_0}\;p_{... ...;\ldots\; p_{i_{n-1}i_n} = \alpha_{0,i_0}\;p_{i_0 i_1}\;\ldots\; p_{i_{n-1}i_n}$$

    $$= P(X_0=i_0,X_{1}=i_1,\ldots,X_{n}=i_n)\,,$$

    
    

  • wobei in der vorletzten Gleichheit die Stationarität der Anfangsverteilung ${\boldsymbol{\alpha}}_0$ und in der letzten Gleichheit erneut die Definitionsgleichung (3) der Markov-Kette $\{X_n\}$ verwendet wurde.
    
    $\Box$

Beachte

 

• Für einige Beispiele von Markov-Ketten mit speziell strukturierten Übergangsmatrizen hatten wir bereits in den Abschnitten 2.2.2 und 2.2.3 die zugehörigen stationären Anfangsverteilungen bestimmt.
• Wir diskutieren nun noch zwei weitere Beispiele dieses Typs.
  • Der Zustandsraum ist dabei jeweils unendlich, so dass außer der Quasi-Positivität (bzw. der Irreduzibilität und Aperiodizität der Übergangsmatrix) noch eine weitere Bedingung erforderlich ist, um die Ergodizität der betrachteten Markov-Ketten zu garantieren.
  • Es ist dies eine sogenannte Kontraktionsbedingung, die verhindert, dass die ,,Wahrscheinlichkeitsmasse'' ins Unendliche abdriftet.

Beispiele

 

1. Warteschlangen
   
   vgl. T. Rolski, H. Schmidli, V. Schmidt, J. Teugels (2002) Stochastic Processes for Insurance and Finance. J. Wiley & Sons, Chichester, S. 147 ff.

   
   

   • Wir betrachten das bereits in Abschnitt 2.1.2 diskutierte Beispiel
     • der rekursiv definierten Markov-Kette $X_0,X_1,\ldots\Omega\to\{0,1,\ldots\}$ mit $X_0=0$ und

       $$X_n= \max\{0,X_{n-1}+Z_n-1\}\,,\qquad\forall\,n\ge 1\,,$$ (63)

       
       

     • wobei die Zufallsvariablen $Z,Z_1,Z_2,\ldots:\Omega\to\{0,1,\ldots\}$ unabhängig und identisch verteilt sind und die Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ gegeben ist durch

       $$p_{ij}=\left\{\begin{array}{ll} P(Z=j+1-i)\,, &\mbox{falls $j+1\g... ...0)+P(Z=1)\,, &\mbox{falls $j=i=0$,}\\ 0\,, &\mbox{sonst.} \end{array}\right.$$ (64)

       
       

   • Man kann zeigen, dass
     • die in (63) rekursiv definierte Markov-Kette $\{X_n\}$ bzw. die zugehörige (in (64) gegebene) Übergangsmatrix irreduzibel und aperiodisch ist, falls

       $$P(Z=0)>0\,,\quad P(Z=1)>0 \quad P(Z=2)>0\,,$$ (65)

       
       

     • die Lösung der Rekursionsgleichung (63) sich für jedes $n\ge 1$ darstellen lässt in der Form

       $$X_n=\max\Bigl\{0,\max\limits_{k\in\{1,\ldots,n\}}\sum\limits_{r=k... ...ax\Bigl\{0,\max\limits_{k\in\{1,\ldots,n\}}\sum\limits_{r=1}^k(Z_r-1)\Bigr\}\,,$$ (66)

       
       

     • die (Grenz-) Wahrscheinlichkeiten $\pi_i$ für jedes $i\in\{0,1,\ldots\}$ existieren, wobei
       

       $$\pi_i = \lim\limits_{n\to\infty} P\Bigl(\max\Bigl\{0,\max\limits_{k\in\{1,\ldots,n\}} \sum\limits_{r=1}^k(Z_r-1)=i\Bigr\}\Bigr)$$

       $$= \left\{\begin{array}{ll} P\Bigl(\sup\limits_{k\in\{1,2,\ldots\}} ... ...}} \sum\limits_{r=1}^k(Z_r-1)\le 0\Bigr) & \mbox{für $i=0$.} \end{array}\right.$$

       
       
       Dabei gilt
       $$\begin{array}{lll} \pi_i=0 &\mbox{fü... ...,} &\mbox{falls (\ref{bed.irre.ape}) gilt und ${\mathbb{E}\,}Z<1$.} \end{array}$$

   • Für Markov-Ketten mit (abzählbar) unendlichem Zustandsraum
     • folgt also die Ergodizität im allgemeinen nicht aus der Irreduzibilität und Aperiodizität,
     • sondern es muss noch zusätzlich eine gewisse Kontraktionsbedingung erfüllt sein,
     • wobei dies im Fall des hier betrachteten Beispiels die Bedingung ist, dass die Markov-Kette $\{X_n\}$ eine negative Drift besitzt, d.h., dass ${\mathbb{E}\,}(Z-1)<0$ gilt.
   • Falls die Bedingungen (65) erfüllt sind und ${\mathbb{E}\,} Z<1$ gilt,
     • dann besitzt die Matrixgleichung ${\boldsymbol{\alpha}}^\top={\boldsymbol{\alpha}}^\top{\mathbf{P}}$ zwar eine (eindeutig bestimmte) Wahrscheinlichkeitslösung ${\boldsymbol{\alpha}}^\top=(\alpha_0,\alpha_1,\ldots)$,
     • die mit ${\boldsymbol{\pi}}^\top=(\pi_0,\pi_1,\ldots)$ $(=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n^\top)$ übereinstimmt, sich jedoch im allgemeinen nicht explizit bestimmen lässt.
     • Man kann aber eine einfache Formel für die erzeugende Funktion $g_{\boldsymbol{\pi}}:(-1,1)\to[0,1]$ von ${\boldsymbol{\pi}}=(\pi_0,\pi_1,\ldots)^\top$ angeben, wobei
       $$g_{\boldsymbol{\pi}}(s)=\sum\limits_{i=0}^\infty s^i\pi_i \qquad\Biggl(={\mathbb{E}\,} s^{X_\infty}\Biggr)$$
       und

       $$X_\infty=\max\Bigl\{0,\sup\limits_{k\in\{1,2,\ldots\}}\sum\limits_{r=1}^k(Z_r-1)\Bigr\}.$$ (67)

       
       

     • Und zwar gilt

       $$g_{\boldsymbol{\pi}}(s)=\frac{(1-\rho)(1-s)}{g_Z(s)-s}\;,\qquad\forall \, s\in(-1,1)\,,$$ (68)

       
       
       wobei $\rho={\mathbb{E}\,}Z$ und $g_Z(s)={\mathbb{E}\,}s^Z$ die erzeugende Funktion von $Z$ ist.

     
     

   • Beweis von (68)
     • Aus (67) ergibt sich, dass $X_\infty\stackrel{{\rm d}}{=}\max\{0,X_\infty+(Z-1)\}$.
     • Mit der Schreibweise $x_+=\max\{0,x\}$ gilt somit
       

       $$g_{\boldsymbol{\pi}}(s) = {\mathbb{E}\,}s^{X_\infty}={\mathbb{E}\,}s^{(X_\infty+Z-1)_+}$$

       $$= {\mathbb{E}\,}\Bigl(s^{ (X_\infty+Z-1)_+}\; {1\hspace{-1mm}{\rm I... ...}\,}\Bigl(s^{ (X_\infty+Z-1)_+}\;{1\hspace{-1mm}{\rm I}}(X_\infty+Z-1=-1)\Bigr)$$

       $$= \frac{1}{s}\sum_{k=1}^\infty s^kP(X_\infty+Z=k)+P(X_\infty+Z=0)$$

       $$= s^{-1}g_{\boldsymbol{\pi}}(s)g_Z(s) +(1-s^{-1}) P(X_\infty+Z=0)\,,$$

       
       
       d.h.,

       $$g_{\boldsymbol{\pi}}(s)=\frac{(s-1)P(X_\infty+Z=0)}{s-g_Z(s)}\,.$$ (69)

       
       

     • Weil
       $$\lim_{s \uparrow1}g_{\boldsymbol{\pi}}(s)=1$$   und$$\qquad \lim_{s\uparrow 1} \frac{d}{ds} g_Z(s)={\mathbb{E}\,}Z\,$$
       ergibt sich aus der Regel von L'Hospital, dass
       $$1=\frac{P(X_\infty+Z=0)}{1-\rho}\;.$$

     • Somit ergibt sich (68) aus (69).

   
   

2. Geburts- und Todesprozesse mit einer reflektierenden Schranke

   
   

   • Wir modifizieren das in Abschnitt 2.2.3 diskutierte Beispiel des Geburts- und Todesprozesses dahingehend, dass wir nun den (unendlichen) Zustandsraum $E=\{0,1,\ldots\}$ und die Übergangsmatrix

     $${\mathbf{P}}=\left(\begin{array}{cccccccc} 0 & 1 & & & & & & \\ ... ...& q_i & r_i & p_i & \\ & & & &\ddots & \ddots & \ddots& \\ \end{array}\right)$$ (70)

     
     
     betrachten, wobei $p_i>0$, $q_i>0$ und $p_i+q_i+r_i=1$ für jedes $i\in\{1,2,\ldots\}$ vorausgesetzt wird.
   • 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... ... &\mbox{falls $i>0$,}\\ q_1\alpha_1\,, &\mbox{falls $i=0$.} \end{array}\right.$$ (71)

     
     

   • Ähnlich wie bei Geburts- und Todesprozessen mit zwei reflektierenden Schranken kann man zeigen, dass
     • das Gleichungssystem (71) eine (eindeutig bestimmte) Wahrscheinlichkeitslösung ${\boldsymbol{\alpha}}^\top$ besitzt, falls

       $$\sum\limits_{j=1}^\infty\frac{p_1p_2\cdot\ldots\cdot p_j}{q_1q_2\cdot\ldots\cdot q_{j+1}}<\infty\,,$$ (72)

       
       

     • die Lösung ${\boldsymbol{\alpha}}^\top=(\alpha_0,\alpha_1,\ldots)$ von (71) in diesem Fall gegeben ist durch
       $$\alpha_i=\alpha_0\;\frac{p_1p_2\cdot\ldots\cdot p_{i-1}}{q_1q_2\cdot\ldots\cdot q_i}\;,\qquad\forall\,i>0\,,$$

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

   • Weil wir voraussetzen, dass $p_i>0$ und $q_i>0$ für jedes $i\in\{1,2,\ldots\}$ gilt, sind Geburts- und Todesprozesse mit einer reflektierenden Schranke offenbar irreduzibel.
   • Wenn zusätzlich $r_i>0$ für ein $i\in\{1,2\ldots,\}$ gilt, dann sind Geburts- und Todesprozesse mit einer reflektierenden Schranke auch aperiodisch (sowie ergodisch, falls die Kontraktionsbedingung (72) erfüllt ist).