Matrix der $n$-stufigen Übergangswahrscheinlichkeiten

• Sei $X_0,X_1,\ldots:\Omega\to E$ eine 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})$.
• Für beliebige, jedoch fest vorgegebene $n\ge 1$ und $i,j\in E$ kann das Produkt $p_{ii_1}p_{i_1i_2}\ldots p_{i_{n-1}j}$ als die Wahrscheinlichkeit des ,,Pfades'' $i\to i_1\to\ldots\to i_{n-1}\to j$ aufgefasst werden.
• Analog hierzu kann die Summe

  $$p_{ij}^{(n)}= \sum_{i_1,\ldots,i_{n-1}\in E}p_{ii_1}p_{i_1i_2}\ldots p_{i_{n-1}j}$$ (20)

  
  
  als die Wahrscheinlichkeit des Überganges vom Zustand $i$ in den Zustand $j$ in $n$ Schritten aufgefasst werden, wobei

  $$p_{ij}^{(n)}=P(X_n=j\mid X_0=i)\,,$$ (21)

  
  
  falls $P(X_0=i)>0$.

Beachte

 

• Die Matrix ${\mathbf{P}}^{(n)}=(p_{ij}^{(n)})_{i,j=1,\ldots,\ell}$ wird die $n$-stufige Übergangsmatrix der Markov-Kette $\{X_n\}$ genannt.
• Mit der Schreibweise ${\mathbf{P}}^{(0)}={\mathbf{I}}$, wobei ${\mathbf{I}}$ die $\ell\times\ell$-dimensionale Einheitsmatrix bezeichnet, lassen sich die folgenden Darstellungsformeln für ${\mathbf{P}}^{(n)}$ angeben.

Lemma 2.1   Für beliebige $n,m=0,1,\ldots$ gilt

$${\mathbf{P}}^{(n)}={\mathbf{P}}^n$$ (22)

und somit

$${\mathbf{P}}^{(n+m)}={\mathbf{P}}^{(n)}{\mathbf{P}}^{(m)}.$$ (23)

Beweis

$\;$ Die Gleichung (22) folgt unmittelbar aus (20) und aus der Definition der Matrix-Multiplikation.

$\Box$

Beispiel

$\;$ (Wettervorhersage)

• Sei $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$.
• Man kann zeigen (vgl. Übungsaufgabe 2.3), dass dann die $n$-stufige Übergangsmatrix ${\mathbf{P}}^{(n)}={\mathbf{P}}^n$ gegeben ist 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)\,.$$

Beachte

 

• Die Matrix-Identität (23) wird in der Literatur Gleichung von Chapman-Kolmogorov genannt.
• Unmittelbar aus (23) ergeben sich die folgenden nützlichen Abschätzungen.

Korollar 2.2   Für beliebige $n,m,r=0,1,\ldots$ und $i,j,k\in E$ gilt

$$p^{(n+m)}_{ii}\ge p^{(n)}_{ij}p^{(m)}_{ji}$$ (24)

und

$$p^{(r+n+m)}_{ij}\ge p^{(r)}_{ik}p^{(n)}_{kk}p^{(m)}_{kj}.$$ (25)

Außerdem ergibt sich aus Lemma 2.1 die folgende Darstellung der Verteilung des zufälligen Zustandes $X_n$ der Markov-Kette zum Zeitpunkt $n$.

Theorem 2.3    

• Sei $X_0,X_1,\ldots$ eine Markov-Kette mit dem Zustandsraum $E=\{1,\ldots,\ell\}$, der Anfangsverteilung ${\boldsymbol{\alpha}}$ und der (einstufigen) Übergangsmatrix ${\mathbf{P}}$.
• Dann ist der Vektor ${\boldsymbol{\alpha}}_n=(\alpha_{n1},\ldots,\alpha_{n\ell})^\top$ der (Einzel-) Wahrscheinlichkeiten $\alpha_{ni}=P(X_n=i)$ von $X_n$ gegeben durch

  $${\boldsymbol{\alpha}}_n^\top={\boldsymbol{\alpha}}^\top {\mathbf{P}}^n.$$ (26)

  
  

Beweis

 

• Aus der Formel der totalen Wahrscheinlichkeit (vgl. Theorem WR-2.6) und aus (21) folgt, dass
  $$P(X_n=j)=\sum_{i\in E}\,\alpha_i\, P(X_n=j\mid X_0=i) =\sum_{i\in E}\alpha_ip_{ij}^{(n)}\,,$$
  wobei wir $P(X_n=j\mid X_0=i)=0$ setzen, falls $\alpha_i= P(X_0=i)=0$.
• Die Behauptung (26) ergibt sich nun aus Lemma 2.1.
  
  $\Box$

Beachte

 

• Wegen Theorem 2.3 kann die Berechnung der Wahrscheinlichkeiten $\alpha_{ni}=P(X_n=i)$ auf die Berechnung der $n$-ten Potenz ${\mathbf{P}}^n$ der Übergangsmatrix ${\mathbf{P}}$ zurückgeführt werden.
• Dabei ist in vielen Fällen die sogenannte Spektraldarstellung von ${\mathbf{P}}^n$ nützlich, die auf die folgende Weise mit Hilfe der Eigenwerte bzw. Eigenvektoren der Übergangsmatrix ${\mathbf{P}}$ bestimmt werden kann.

• Zur Erinnerung
  • Sei ${\mathbf{A}}$ eine (nicht notwendig stochastische) $\ell\times\ell$ Matrix, seien ${\boldsymbol{\phi}},{\boldsymbol{\psi}}\not={\bf0}$ zwei $\ell$-dimensionale (Spalten-) Vektoren, so daß jeweils mindestens eine ihrer Komponenten von 0 verschieden ist, und sei $\theta$ eine beliebige (reelle oder komplexe) Zahl.
  • Falls

    $${\mathbf{A}}{\boldsymbol{\phi}}=\theta {\boldsymbol{\phi}} \qquad {\boldsymbol{\psi}}^\top{\mathbf{A}}=\theta {\boldsymbol{\psi}}^\top\,,$$ (27)

    
    
    dann ist $\theta$ ein Eigenwert von ${\mathbf{A}}$, und ${\boldsymbol{\phi}}$ bzw. ${\boldsymbol{\psi}}$ ist ein rechter bzw. linker (zu $\theta$ gehörender) Eigenvektor.
  • Weil (27) und
    $$({\mathbf{A}}-\theta{\mathbf{I}}) {\boldsymbol{\phi}}={\bf0}$$   bzw.$$\qquad {\boldsymbol{\psi}}^\top({\mathbf{A}}-\theta{\mathbf{I}})={\bf0}^\top\,,$$
    äquivalent sind, ist $\theta$ genau dann ein Eigenwert von ${\mathbf{A}}$, wenn $\theta$ eine Lösung der sogenannten charakteristischen Gleichung ist:

    $$\det({\mathbf{A}}-\theta{\mathbf{I}})=0\,.$$ (28)

    
    

  • Weil (28) eine algebraische Gleichung der Ordnung $\ell$ ist, besitzt sie somit $\ell$ Lösungen $\theta_1,\ldots,\theta_\ell$, die komplex sein können und die nicht alle voneinander verschieden sein müssen.
  • Wir nehmen o.B.d.A. an, dass die Eigenwerte $\theta_1,\ldots,\theta_\ell$ so numeriert sind, dass
    $$\vert\theta_1\vert\ge\vert\theta_2\vert\ge\ldots\ge\vert\theta_\ell\vert\,.$$

  • Für jeden Eigenwert $\theta_i$ existieren (jeweils von ${\bf0}$ verschiedene) rechte bzw. linke Eigenvektoren ${\boldsymbol{\phi}}_i$ bzw. ${\boldsymbol{\psi}}_i$.
  • Sei ${\boldsymbol{\Phi}}=({\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell)$ die $\ell\times\ell$ Matrix, die aus den rechten Eigenvektoren ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ besteht, und sei
    $${\boldsymbol{\Psi}}=\left(\begin{array}{c} {\boldsymbol{\psi}}_1^\top \\ \vdots \\ {\boldsymbol{\psi}}_\ell^\top \end{array}\right)$$
    die $\ell\times\ell$ Matrix, die aus den linken Eigenvektoren ${\boldsymbol{\psi}}_1,\ldots,{\boldsymbol{\psi}}_\ell$ gebildet wird.
  • Mit dieser Schreibweise ergibt sich, dass

    $${\mathbf{A}}{\boldsymbol{\Phi}}={\boldsymbol{\Phi}}\,{\,{\rm diag}}({\boldsymbol{\theta}})\,,$$ (29)

    
    
    wobei ${\boldsymbol{\theta}}=(\theta_1,\ldots,\theta_\ell)^\top$ und ${\,{\rm diag}}({\boldsymbol{\theta}})$ die Diagonalmatrix mit den Diagonalelementen $\theta_1,\ldots,\theta_\ell$ bezeichnet.
• Falls die Eigenvektoren ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ linear unabhängig sind,
  • dann existiert die inverse Matrix ${\boldsymbol{\Phi}}^{-1}$, und wir können ${\boldsymbol{\Psi}}={\boldsymbol{\Phi}}^{-1}$ setzen.
  • Außerdem ergibt sich in diesem Fall aus (29), dass
    $${\mathbf{A}}={\boldsymbol{\Phi}}\,{\,{\rm diag}}({\boldsymbol{\th... ...={\boldsymbol{\Phi}}\,{\,{\rm diag}}({\boldsymbol{\theta}}){\boldsymbol{\Psi}}$$
    und somit
    $${\mathbf{A}}^n={\boldsymbol{\Phi}}({\,{\rm diag}}({\boldsymbol{\t... ...ldsymbol{\Phi}}({\,{\rm diag}}({\boldsymbol{\theta}}))^n{\boldsymbol{\Psi}}\,.$$

  • Hieraus ergibt sich die Spektraldarstellung von ${\mathbf{A}}$:

    $${\mathbf{A}}^n=\sum_{i=1}^\ell\theta^n_i{\boldsymbol{\phi}}_i{\boldsymbol{\psi}}_i^\top\,.$$ (30)

    
    

Beachte

 

• Die Anwendung von (30) für die Übergangsmatrix ${\mathbf{A}}={\mathbf{P}}$ führt zu einem einfachen Algorithmus zur Berechnung der $n$-ten Potenz ${\mathbf{P}}^n$ in (26).
  • Dabei sind lediglich die Eigenwerte und Eigenvektoren von ${\mathbf{P}}$ zu berechnen, wofür Standard-Software wie MAPLE, MATLAB oder MATHEMATICA verwendet werden kann.
  • Ein wesentlicher Vorteil der Spektraldarstellung (30) besteht darin, dass sich bei der Verwendung von (30) die Komplexität der numerischen Berechnung von ${\mathbf{P}}^n$ mit wachsendem $n$ nicht erhöht.
• Allerdings wird bei der Herleitung von (30) vorausgesetzt, dass die Eigenvektoren ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ linear unabhängig sind. Das folgende Lemma liefert eine hinreichende Bedingung hierfür.

Lemma 2.2    

• Falls sämtliche Eigenwerte $\theta_1,\ldots,\theta_\ell$ von ${\mathbf{A}}$ voneinander verschieden sind, dann sind die rechten Eigenvektoren ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ linear unabhängig.
• Wenn darüber hinaus die linken Eigenvektoren ${\boldsymbol{\psi}}_1,\ldots,{\boldsymbol{\psi}}_\ell$ durch den Ansatz ${\boldsymbol{\Psi}}={\boldsymbol{\Phi}}^{-1}$ gegeben sind, dann gilt

  $${\boldsymbol{\psi}}_i^\top{\boldsymbol{\phi}}_j=\left\{ \begin{ar... ...\,, & \mbox{falls $i=j$,}\\ 0\,, & \mbox{falls $i\neq j$.} \end{array} \right.$$ (31)

  
  

Beweis

 

• Die Gültigkeit der ersten Teilaussage zeigen wir mit vollständiger Induktion.
  • Weil jeder Eigenvektor ${\boldsymbol{\phi}}_1$ mindestens eine Komponente hat, die von 0 verschieden ist, impliziert $a_1{\boldsymbol{\phi}}_1={\,{\bf0}}$, dass $a_1=0$.
  • Seien nun sämtliche Eigenwerte $\theta_1,\ldots,\theta_\ell$ von ${\mathbf{A}}$ voneinander verschieden, und für ein gewisses $k\le\ell$ seien die Eigenvetoren ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_{k-1}$ linear unabhängig.
  • Um zu beweisen, dass dann auch die Eigenvektoren ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_k$ linear unabhängig sind, genügt es zu zeigen, dass

    $$\sum_{j=1}^k a_j{\boldsymbol{\phi}}_j={\,{\bf0}}$$ (32)

    
    
    die Gültigkeit von $a_1=\ldots=a_k=0$ impliziert.
  • Die Koeffizienten $a_1,\ldots,a_k$ seien nun so gewählt, dass (32) gilt. Dann gilt auch
    $${\,{\bf0}}={\mathbf{A}}{\,{\bf0}}= \sum_{j=1}^k a_j{\mathbf{A}}{\boldsymbol{\phi}}_j = \sum_{j=1}^k a_j\theta_j{\boldsymbol{\phi}}_j\,.$$

  • Auf die gleiche Weise ergibt sich, dass
    $${\,{\bf0}}=\theta_k{\,{\bf0}}= \theta_k\sum_{j=1}^k a_j {\boldsymbol{\phi}}_j = \sum_{j=1}^k \theta_k a_j{\boldsymbol{\phi}}_j$$
    und somit
    $${\,{\bf0}} =\sum_{j=1}^{k-1}(\theta_k-\theta_j)a_j{\boldsymbol{\phi}}_j\,.$$

  • Weil angenommen wird, dass die Eigenvektoren ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_{k-1}$ linear unabhängig sind, folgt hieraus, dass
    $$(\theta_k-\theta_1)a_1=(\theta_k-\theta_2)a_2=\ldots= (\theta_k-\theta_{k-1})a_{k-1}=0$$
    bzw. $a_1=a_2=\ldots=a_{k-1}=0$, weil $\theta_k\neq\theta_j$ für $1\le j\le k-1$.
  • Wegen (32) muss dann auch $a_k=0$ gelten.
• Falls sämtliche Eigenwerte $\theta_1,\ldots,\theta_\ell$ von ${\mathbf{A}}$ voneinander verschieden sind,
  • dann besteht also die $\ell\times\ell$ Matrix ${\boldsymbol{\Phi}}$ aus $\ell$ linear unabhängigen Spaltenvektoren,
  • und ${\boldsymbol{\Phi}}$ ist somit invertierbar.
  • Die Matrix ${\boldsymbol{\Psi}}$ der linken Eigenvektoren kann also durch den Ansatz ${\boldsymbol{\Psi}}={\boldsymbol{\Phi}}^{-1}$ gebildet werden, woraus sich unmittelbar die Gültigkeit von (31) ergibt.
    
    $\Box$