Direkte und iterative Berechnungsmethoden

Wir zeigen nun, wie die stationäre Anfangsverteilung ${\boldsymbol{\alpha}}_0$ $(={\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n)$ der Markov-Kette $\{X_n\}$ mit Methoden der linearen Algebra berechnet werden kann, falls die Übergangsmatrix ${\mathbf{P}}$ nicht speziell strukturiert (jedoch quasi-positiv) ist und falls die Anzahl $\ell$ der Zustände nicht zu groß ist.

Theorem 2.12    

• Die Übergangsmatrix ${\mathbf{P}}$ der Markov-Kette $\{X_n\}$ sei quasi-positiv.
• Dann ist die Matrix ${\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}}$ invertierbar, und die (eindeutig bestimmte) Wahrscheinlichkeitslösung ${\boldsymbol{\pi}}=\lim_{n\to\infty}{\boldsymbol{\alpha}}_n$ der Matrix-Gleichung ${\boldsymbol{\pi}}^\top={\boldsymbol{\pi}}^\top{\mathbf{P}}$ ist gegeben durch

  $${\boldsymbol{\pi}}^\top={\mathbf{e}}^\top\,({\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}})^{-1}\,,$$ (73)

  
  
  wobei ${\mathbf{e}}=(1,\ldots,1)^\top$ und sämtliche Eintragungen der $\ell\times\ell$ Matrix ${\mathbf{E}}$ gleich $1$ sind.

Beweis

 

• Um zu beweisen, dass die Matrix ${\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}}$ invertierbar ist, zeigen wir, dass die einzige Lösung der Gleichung

  $$({\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}})\,{\mathbf{x}}={\,{\bf0}}$$ (74)

  
  
  durch ${\mathbf{x}}={\,{\bf0}}$ gegeben ist.
  • Weil ${\boldsymbol{\pi}}$ der Gleichung ${\boldsymbol{\pi}}^\top={\boldsymbol{\pi}}^\top{\mathbf{P}}$ genügt, gilt auch

    $${\boldsymbol{\pi}}^\top({\mathbf{I}}-{\mathbf{P}})={\,{\bf0}}\,.$$ (75)

    
    

  • Somit folgt aus (74), dass
    $$0={\boldsymbol{\pi}}^\top({\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}})\,{\mathbf{x}}=0+{\boldsymbol{\pi}}^\top{\mathbf{E}}{\mathbf{x}}\,,$$
    d.h.

    $${\boldsymbol{\pi}}^\top{\mathbf{E}}{\mathbf{x}}=0\,.$$ (76)

    
    

• Andererseits gilt offenbar ${\boldsymbol{\pi}}^\top{\mathbf{E}}={\mathbf{e}}^\top$ und somit wegen (76) auch

  $${\mathbf{e}}^\top{\mathbf{x}}=0 \qquad {\mathbf{E}}{\mathbf{x}}={\,{\bf0}}\,.$$ (77)

  
  
  • Hieraus und aus (74) folgt, dass $({\mathbf{I}}-{\mathbf{P}})\,{\mathbf{x}}={\,{\bf0}}$ bzw. ${\mathbf{P}}\,{\mathbf{x}}={\mathbf{x}}$.
  • Damit gilt auch ${\mathbf{x}}={\mathbf{P}}^n\,{\mathbf{x}}$ für jedes $n\ge 1$.
• Aus Theorem 2.4 ergibt sich nun, dass ${\mathbf{P}}^n\to{\boldsymbol{\Pi}}$,
  • wobei ${\boldsymbol{\Pi}}$ die $\ell\times\ell$ Matrix bezeichnet, die aus den $\ell$ identischen (Zeilen-) Vektoren ${\boldsymbol{\pi}}^\top$ besteht.
  • Mit anderen Worten: Für $n\to\infty$ gilt
    $${\mathbf{x}}={\mathbf{P}}^n\,{\mathbf{x}}\to{\boldsymbol{\Pi}}\,{\mathbf{x}}\,,$$
    d.h.  $x_i=\sum_{j=1}^\ell\pi_j x_j$ für jedes $i=1,\ldots,\ell$.
  • Weil die rechten Seiten dieser Gleichungen nicht von $i$ abhängen, ergibt sich, dass ${\mathbf{x}}=c\,{\mathbf{e}}$ für eine Konstante $c\in\mathbb{R}$.
  • Wegen (77) gilt außerdem, dass
    $$0={\mathbf{e}}^\top{\mathbf{x}}=c\,{\mathbf{e}}^\top{\mathbf{e}}=c\ell$$
    und somit $c=0$ bzw. ${\mathbf{x}}={\,{\bf0}}$.
• Die Matrix ${\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}}$ ist also invertierbar.
• Wegen (75) ergibt sich schließlich, dass
  $${\boldsymbol{\pi}}^\top({\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}})={\boldsymbol{\pi}}^\top{\mathbf{E}}={\mathbf{e}}^\top$$
  bzw.
  $${\boldsymbol{\pi}}^\top={\mathbf{e}}^\top\,({\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}})^{-1}\,.$$
  
   
    $\Box$
  
  
  

Beachte

 

• Bei einer größeren Anzahl $\ell$ von Zuständen kann die numerische Berechnung der inversen Matrix $({\mathbf{I}}-{\mathbf{P}}+{\mathbf{E}})^{-1}$ in (73) schwierig sein.
• In diesem Fall ist es oft besser, die Matrix-Gleichung ${\boldsymbol{\pi}}^\top={\boldsymbol{\pi}}^\top{\mathbf{P}}$ iterativ zu lösen.
• Wenn die Übergangsmatrix ${\mathbf{P}}$ quasi-positiv ist und somit $\pi_\ell>0$ gilt, kann man dabei zunächst $\widehat\pi_\ell=1$ setzen und die modifizierte Gleichung

  $$\widehat{{\boldsymbol{\pi}}}^\top({\mathbf{I}}-\widehat{{\mathbf{P}}})={\mathbf{b}}^\top$$ (78)

  
  
  lösen, wobei $\widehat{{\mathbf{P}}}=(p_{ij})_{i,j=1,\ldots,\ell-1}$ and $\widehat{{\boldsymbol{\pi}}}^\top=(\widehat{\pi}_1,\ldots,\widehat{\pi}_{\ell-1})$, ${\mathbf{b}}^\top=(p_{\ell 1},\ldots,p_{\ell,\ell-1})$.
• Die ursprünglich gesuchte Wahrscheinlichkeitsfunktion ${\boldsymbol{\pi}}^\top=(\pi_1,\ldots,\pi_\ell)$ ist dann gegeben durch
  $$\pi_i=\widehat{\pi}_i/c\,,\qquad\forall\, i=1,\ldots,\ell\,,$$
  wobei $c=\widehat{\pi}_1+\ldots+\widehat{\pi}_{\ell}$.
• Bei der iterativen Lösung der modifizierten Matrixgleichung (78) wird die Tatsache genutzt, dass die Matrix ${\mathbf{I}}-\widehat{{\mathbf{P}}}$ in (78) invertierbar ist und dass $({\mathbf{I}}-\widehat{{\mathbf{P}}})^{-1}$ in eine Potenzreihe entwickelt werden kann.
• Dies ergibt sich aus den folgenden zwei Hilfssätzen.

Lemma 2.4    

• Sei ${\mathbf{A}}$ eine $\ell\times\ell$ Matrix, so dass ${\mathbf{A}}^n\to {\,{\bf0}}$ für $n\to\infty$.
• Dann ist die Matrix ${\mathbf{I}}-{\mathbf{A}}$ invertierbar, und für jedes $n=1,2,\ldots$ gilt

  $${\mathbf{I}}+{\mathbf{A}}+\ldots+{\mathbf{A}}^{n-1}=({\mathbf{I}}-{\mathbf{A}})^{-1}({\mathbf{I}}-{\mathbf{A}}^n)\,.$$ (79)

  
  

Beweis

 

• Offenbar gilt für jedes $n=1,2,\ldots$
  

  $$({\mathbf{I}}-{\mathbf{A}})({\mathbf{I}}+{\mathbf{A}}+\ldots+{\mathbf{A}}^{n-1}) = {\mathbf{I}}+{\mathbf{A}}+\ldots+{\mathbf{A}}^{n-1}-{\mathbf{A}}-\ldots-{\mathbf{A}}^{n}$$

  $$= {\mathbf{I}}-{\mathbf{A}}^{n}\,.$$ (80)

  
  

• Außerdem ist die Matrix ${\mathbf{I}}-{\mathbf{A}}^n$ für jedes hinreichend große $n$ invertierbar, weil ${\mathbf{A}}^n\to {\,{\bf0}}$ vorausgesetzt wird.
• Somit gilt für jedes hinreichend große $n$
  

  $$\not= \det({\mathbf{I}}-{\mathbf{A}}^{n})$$ 0

  $$= \det\Bigl(({\mathbf{I}}-{\mathbf{A}})({\mathbf{I}}+{\mathbf{A}}+\ldots+{\mathbf{A}}^{n-1})\Bigr)$$

  $$= \det({\mathbf{I}}-{\mathbf{A}})\det({\mathbf{I}}+{\mathbf{A}}+\ldots+{\mathbf{A}}^{n-1})\,.$$

  
  

• Hieraus folgt, dass $\det({\mathbf{I}}-{\mathbf{A}})\not=0$ und dass somit die Matrix ${\mathbf{I}}-{\mathbf{A}}$ invertierbar ist.
• Die Behauptung (79) ergibt sich nun aus (80).
  
  $\Box$

Lemma 2.5    

• Die stochastische Matrix ${\mathbf{P}}$ sei quasi-positiv, und $\widehat{\mathbf{P}}$ sei die in $(\ref{tra.bal.equ})$ eingeführte $(\ell-1)\times(\ell-1)$ Matrix.
• Dann gilt $\widehat{{\mathbf{P}}}^n\to {\,{\bf0}}$ für $n\to\infty$, die Matrix ${\mathbf{I}}-\widehat{{\mathbf{P}}}$ ist invertierbar, und es gilt

  $$({\mathbf{I}}-\widehat{{\mathbf{P}}})^{-1}=\sum_{n=0}^\infty \widehat{{\mathbf{P}}}^n\,.$$ (81)

  
  

Beweis

 

• Wegen Lemma 2.4 genügt es zu zeigen, dass $\widehat{{\mathbf{P}}}^n\to {\,{\bf0}}$.
• Weil vorausgesetzt wird, dass ${\mathbf{P}}$ quasi-positiv ist, gibt es eine natürliche Zahl $n_0\ge 1$, so dass
  $$\delta=\max\limits_{i\in\widehat E}\sum\limits_{j\in\widehat E} p_{ij}^{(n_0)}<1\,,$$   $$\mbox{wobei $\widehat E=\{1,\ldots,\ell-1\}$.}$$$$$$

• Außerdem gilt
  $$(\widehat{{\mathbf{P}}}^{n})_{ij} = \!\!\sum_{i_1,\ldots,i_{n-1} ... ...-1} \in E} \!\! p_{ii_1}p_{i_1i_2}\ldots p_{i_{n-1}j} =({\mathbf{P}}^{n})_{ij}$$
  und somit $0\le(\widehat{{\mathbf{P}}}^{n})_{ij} \le({\mathbf{P}}^{n})_{ij} = p^{(n)}_{ij}< 1$ für jedes $n\ge n_0$; $i,j\in\widehat E$.
• Mit der Darstellung $n=kn_0+m$ für gewisse $k\ge 1$ und $m\in\{0,\ldots,n_0-1\}$ gilt somit
  

  $$(\widehat{{\mathbf{P}}}^{n})_{ij} = \sum_{i_1,\ldots,i_k\in\widehat E}(\widehat{{\mathbf{P}}}^{n_0})_... ...(\widehat{{\mathbf{P}}}^{n_0})_{i_{k-1}i_k} (\widehat{{\mathbf{P}}}^{m})_{i_kj}$$

  $$\le \sum_{i_1,\ldots,i_k\in\widehat E} p^{(n_0)}_{ii_1} p^{(n_0)}_{i_1i_2}\ldots p^{(n_0)}_{i_{k-1}i_k}$$

  $$= \sum_{i_1,\ldots,i_{k-1}\in\widehat E} p^{(n_0)}_{ii_1} p^{(n_0)}... ..._0)}_{i_{k-2}i_{k-1}}\Bigl(\sum_{i_k\in\widehat E} p^{(n_0)}_{i_{k-1}i_k}\Bigr)$$

  $$\le \delta\sum_{i_1,\ldots,i_{k-1}\in\widehat E} p^{(n_0)}_{ii_1} p^{(n_0)}_{i_1i_2}\ldots p^{(n_0)}_{i_{k-2}i_{k-1}}$$

  $$\vdots$$

  $$\le \delta^k\,.$$

  
  

• Dies ergibt, dass $\lim_{n\to\infty}(\widehat{{\mathbf{P}}}^{n})_{ij} \le \lim_{k\to\infty}\delta^k=0.$
  
  $\Box$

Beachte

 

• Wegen Lemma 2.5 ist die Lösung $\widehat{{\boldsymbol{\pi}}}^\top$ der Gleichung (78), d.h. $\widehat{{\boldsymbol{\pi}}}^\top({\mathbf{I}}-\widehat{{\mathbf{P}}})={\mathbf{b}}^\top$, gegeben durch

  $$\widehat{{\boldsymbol{\pi}}}^\top={\mathbf{b}}^\top\sum_{n=0}^\infty \widehat{{\mathbf{P}}}^n\,,$$ (82)

  
  
  wodurch eine iterative Berechnung von $\widehat{{\boldsymbol{\pi}}}^\top=(\widehat\pi_1,\ldots,\widehat\pi_{\ell-1})$ möglich ist. Dabei beginnen wir die Iteration mit ${\mathbf{b}}_0^\top={\mathbf{b}}^\top$ und setzen dann ${\mathbf{b}}_{n+1}^\top={\mathbf{b}}_n^\top\widehat{{\mathbf{P}}}$ für jedes $n\ge 0$.
• Somit lässt sich (82) umformulieren zu

  $$\widehat{{\boldsymbol{\pi}}}^\top=\sum_{n=0}^\infty {\mathbf{b}}_n^\top\,,$$ (83)

  
  
  und die Größe $\sum_{n=0}^{n_0} {\mathbf{b}}_n^\top$ kann für hinreichend großes $n_0\ge 1$ als Näherung von $\widehat{{\boldsymbol{\pi}}}^\top$ dienen.