Multiplikativ reversible Version der Übergangsmatrix; Spektraldarstellung

Wir diskutieren zunächst eine Methode, mit deren Hilfe (ergodische) Übergangsmatrizen so transformiert werden können, dass sich die Eigenschaft der Reversibilität einstellt.

• Sei ${\mathbf{P}}=(p_{ij})$ eine irreduzible und aperiodische (jedoch nicht notwendig reversible) Übergangsmatrix, und sei ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ die zugehörige stationäre Anfangsverteilung, so dass $\pi_i>0$ für jedes $i\in E$.
• Außerdem betrachten wir die stochastische Matrix $\widetilde{\mathbf{P}}=(\widetilde p_{ij})$ mit

  $$\widetilde p_{ij}=\frac{\pi_j p_{ji}}{\pi_i}\;,$$ (99)

  
  
  d.h., $\widetilde{\mathbf{P}}={\mathbf{D}}^{-2}{\mathbf{P}}^\top{\mathbf{D}}^2$ mit ${\mathbf{D}}={\,{\rm diag}}(\sqrt{\pi_i})$ ist ebenfalls eine irreduzible und aperiodische Übergangsmatrix mit der gleichen stationären Anfangsverteilung ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$.
• Das Paar $({\mathbf{M}},{\boldsymbol{\pi}})$ mit ${\mathbf{M}}={\mathbf{P}}\widetilde{\mathbf{P}}$ ist reversibel, denn für die stochastische Matrix ${\mathbf{M}}=(m_{ij})$ gilt
  $$\pi_i m_{ij}=\pi_i\sum\limits_{k=1}^\ell p_{ik}\;\frac{\pi_jp_{jk... ...=\pi_j\sum\limits_{k=1}^\ell p_{jk}\;\frac{\pi_ip_{ik}}{\pi_k}=\pi_j m_{ji}\,.$$

Definition

$\;$ Die Matrix ${\mathbf{M}}={\mathbf{P}}\widetilde{\mathbf{P}}$ heißt die multiplikativ reversible Version der Übergangsmatrix ${\mathbf{P}}$.

Beachte

 

• Sämtliche Eigenwerte $\theta_{{\mathbf{M}},1},\ldots,\theta_{{\mathbf{M}},\ell}$ von ${\mathbf{M}}$ sind reell und liegen im Intervall $[0,1]$, denn ${\mathbf{M}}$ hat die gleichen Eigenwerte wie die symmetrische und nichtnegativ definite Matrix ${\mathbf{M}}^*={\mathbf{D}}{\mathbf{M}}{\mathbf{D}}^{-1}$, wobei
  $$m_{ij}^*=\frac{\sqrt{\pi_i}}{\sqrt{\pi_j}}\; m_{ij} =\frac{\sqrt{... ...t{\pi_k}}\; p_{ik}\Bigr)\Bigl(\frac{\sqrt{\pi_j}}{\sqrt{\pi_k}}\; p_{jk}\Bigr)$$
  und somit
  $${\mathbf{M}}^*={\mathbf{D}}{\mathbf{M}}{\mathbf{D}}^{-1}=\bigl({\... ...f{D}}^{-1}\bigr) \bigl({\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}\bigr)^\top\,.$$

• Die symmetrische Matrix ${\mathbf{M}}^*$ ist also diagonalisierbar, und die rechten bzw. linken (zu $\theta_i^*=\theta_{{\mathbf{M}},i}$ gehörenden) Eigenvektoren ${\boldsymbol{\phi}}_i^*$ bzw. ${\boldsymbol{\psi}}_i^*$ können so gewählt werden, dass
  • ${\boldsymbol{\phi}}_i^*={\boldsymbol{\psi}}_i^*$ für jedes $i\in E$ gilt und
  • die Vektoren ${\boldsymbol{\phi}}^*_1,\ldots,{\boldsymbol{\phi}}^*_\ell$ eine orthonormale Basis in $\mathbb{R}^\ell$ bilden.
• Dann sind ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ bzw. ${\boldsymbol{\psi}}_1,\ldots,{\boldsymbol{\psi}}_\ell$ mit

  $${\boldsymbol{\phi}}_i={\mathbf{D}}^{-1}{\boldsymbol{\phi}}^*_i \qquad {\boldsymbol{\psi}}_i={\mathbf{D}}{\boldsymbol{\psi}}^*_i\,,\qquad\forall\, i\in E\,,$$ (100)

  
  
  rechte bzw. linke Eigenvektoren von ${\mathbf{M}}$, denn für jedes $i\in E$ gilt
  $${\mathbf{M}}{\boldsymbol{\phi}}_i={\mathbf{M}}{\mathbf{D}}^{-1}{\... ...hbf{M}},i}{\boldsymbol{\phi}}^*_i=\theta_{{\mathbf{M}},i}{\boldsymbol{\phi}}_i$$
  bzw.
  $${\boldsymbol{\psi}}_i^\top{\mathbf{M}}=\bigl({\mathbf{D}}{\boldsy... ...i}}^*_i)^\top{\mathbf{D}}=\theta_{{\mathbf{M}},i}{\boldsymbol{\psi}}_i^\top\,.$$

Hieraus ergibt sich insbesondere die folgende Spektraldarstellung der multiplikativ reversiblen Version ${\mathbf{M}}$ der Übergangsmatrix ${\mathbf{P}}$; vgl. auch die in Formel (30) gegebene Spektraldarstellung.

Theorem 2.15   $\;$ Für beliebige $n\in\mathbb{N}$ und ${\mathbf{x}}\in\mathbb{R}^\ell$ gilt

$${\mathbf{M}}^n{\mathbf{x}}=\sum\limits_{i=1}^\ell\theta_{{\mathbf{M}},i}^n{\boldsymbol{\phi}}_i{\boldsymbol{\psi}}_i^\top{\mathbf{x}}\,.$$ (101)

wobei ${\boldsymbol{\phi}}_i$ und ${\boldsymbol{\psi}}_i$ die in $(\ref{eig.vek.emm})$ definierten (rechten bzw. linken) Eigenvektoren von ${\mathbf{M}}$ sind.

Beweis

 

• Weil die in (100) definierten (rechten) Eigenvektoren ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ von ${\mathbf{M}}$ ebenfalls eine Basis in $\mathbb{R}^\ell$ bilden, gibt es für jedes ${\mathbf{x}}\in\mathbb{R}^\ell$ einen (eindeutig bestimmten) Vektor $\bigl(x_1^{\rm (r)},\ldots,x_\ell^{\rm (r)}\bigr)^\top\in\mathbb{R}^\ell$, so dass
  $${\mathbf{x}}=\sum\limits_{i=1}^\ell x_i^{\rm (r)}{\boldsymbol{\phi}}_i\,.$$

• Außerdem gilt ${\mathbf{M}}{\boldsymbol{\phi}}_i=\theta_{{\mathbf{M}},i}{\boldsymbol{\phi}}_i$ und somit auch ${\mathbf{M}}^n{\boldsymbol{\phi}}_i=\theta_{{\mathbf{M}},i}^n{\boldsymbol{\phi}}_i$ für beliebige $i\in E$ und $n\in\mathbb{N}$.
• Hieraus folgt, dass
  $${\mathbf{M}}^n{\mathbf{x}}= \sum\limits_{i=1}^\ell x_i^{\rm (r)} ... ...ts_{i=1}^\ell x_i^{\rm (r)}\theta^n_{{\mathbf{M}},i} {\boldsymbol{\phi}}_i \,.$$

• Andererseits ergibt sich aus (100), dass für beliebige $i\in E$ und ${\mathbf{x}}\in\mathbb{R}^\ell$

  $${\boldsymbol{\psi}}_i^\top{\mathbf{x}}=\bigl({\mathbf{D}}{\boldsy... ...l({\boldsymbol{\psi}}_i^*\bigr)^\top {\boldsymbol{\phi}}_j^* = x_i^{\rm (r)}\,,$$ (102)

  
  
  wobei in der letzten Gleichheit berücksichtigt wurde, dass ${\boldsymbol{\psi}}_i^*={\boldsymbol{\phi}}_i^*$ für jedes $i\in E$ gilt und dass die Eigenvektoren ${\boldsymbol{\phi}}^*_1,\ldots,{\boldsymbol{\phi}}^*_\ell$ von ${\mathbf{M}}^*$ eine orthonormale Basis in $\mathbb{R}^\ell$ bilden.
• Damit ist die Spektraldarstellung (101) bewiesen.
  
  $\Box$