Bestimmung der Konvergenzgeschwindigkeit bei Reversibilität

• Sei $E=\{1,\ldots,\ell\}$, und sei ${\mathbf{P}}$ eine quasi-positive (d.h. irreduzible und aperiodische) Übergangsmatrix.
  • Für den Fall, dass sämtliche Eigenwerte $\theta_1,\ldots,\theta_\ell$ von ${\mathbf{P}}$ voneinander verschieden sind, hatten wir mit Hilfe des Theorems von Perron-Frobenius gezeigt (vgl. Korollar 2.4), dass

    $$\max\limits_{j\in E}\vert\alpha_{nj}-\pi_j\vert= O(\vert\theta_2\vert^n)\,,$$ (96)

    
    
    wobei ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ die (eindeutig bestimmte) Lösung der Gleichung ${\boldsymbol{\pi}}^\top={\boldsymbol{\pi}}^\top{\mathbf{P}}$ ist.
  • Falls $({\mathbf{P}},{\boldsymbol{\pi}})$ zusätzlich reversibel ist, dann kann man zeigen, dass die in (96) betrachtete Basis $\vert\theta_2\vert$ der Konvergenzgeschwindigkeit nicht verbessert werden kann.
• Sei also $({\mathbf{P}},{\boldsymbol{\pi}})$ reversibel, wobei ${\mathbf{P}}$ eine irreduzible und aperiodische Übergangsmatrix ist.
  • Dann ergibt sich aus der Detailed-Balance-Bedingung (85), dass die Matrix ${\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}$ symmetrisch ist, wobei ${\mathbf{D}}={\,{\rm diag}}(\sqrt{\pi_i})$.
  • Weil die Eigenwerte $\theta_1,\ldots,\theta_\ell$ von ${\mathbf{P}}$ mit den Eigenwerten von ${\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}$ übereinstimmen, gilt somit $\theta_i\in\mathbb{R}$ für jedes $i\in E$,
  • und die rechten Eigenvektoren ${\boldsymbol{\phi}}_1^*,\ldots,{\boldsymbol{\phi}}_\ell^*$ von ${\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}$ können so gewählt werden, dass ihre Komponenten reellwertig sind,
  • dass ${\boldsymbol{\phi}}_1^*,\ldots,{\boldsymbol{\phi}}_\ell^*$ gleichzeitig linke Eigenvektoren von ${\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}$ sind und dass sowohl die Zeilen als auch die Spalten der $\ell\times\ell$ Matrix $({\boldsymbol{\phi}}_1^*,\ldots,{\boldsymbol{\phi}}_\ell^*)$ orthonormale Vektoren sind (vgl. beispielsweise Lemma 3.8 des Vorlesungsskriptes ,,Statistik II'').
• Aus der Spektraldarstellung (30) von ${\mathbf{A}}={\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}$ ergibt sich nun, dass für jedes $n\ge 1$
  $${\mathbf{P}}^n=\bigl({\mathbf{D}}^{-1}{\mathbf{A}}{\mathbf{D}}\bi... ...f{D}}^{-1}{\boldsymbol{\phi}}_k^*({\boldsymbol{\phi}}_k^*)^\top{\mathbf{D}}\,.$$
  • Mit $\theta_1=1$ und ${\boldsymbol{\phi}}_1^*=(\sqrt{\pi_1},\ldots,\sqrt{\pi_\ell})^\top$ ergibt sich hieraus, dass für beliebige $i,j\in E$

    $$p_{ij}^{(n)}=\pi_j+\sqrt{\frac{\pi_j}{\pi_i}}\;\sum\limits_{k=2}^\ell\theta_k^n \phi_{ki}^*\phi_{kj}^*\,, \mbox{wobei ${\boldsymbol{\phi}}_k^*=(\phi_{k1}^*,\ldots,\phi_{k\ell}^*)^\top$.}$$ (97)

    
    

  • Falls $n$ eine gerade Zahl ist bzw. sämtliche Eigenwerte $\theta_2,\ldots,\theta_\ell$ nichtnegativ sind, dann gilt somit
    $$\sup\limits_{{\boldsymbol{\alpha}}_0}\max\limits_{j\in E}\vert\al... ...(\phi_{kj}^*)^2\Bigr\vert \ge \theta_2^n\max\limits_{j\in E}(\phi_{2j}^*)^2\,.$$

• Hieraus folgt, dass $\vert\theta_2\vert$ die kleinste positive Zahl ist, für die die in (96) betrachtete Abschätzung der Konvergenzgeschwindigkeit gleichmäßig für alle Anfangsverteilungen ${\boldsymbol{\alpha}}_0$ gilt.

Beachte

 

• Aus (97) ergibt sich, dass die Konvergenzabschätzung (96) wie folgt präzisiert werden kann. Und zwar gilt
  $$\bigl\vert p_{ij}^{(n)}-\pi_j\bigr\vert \le \frac{1}{\sqrt{\min\l... ...rt^n \le \frac{1}{\sqrt{\min\limits_{i\in E} \pi_i}}\; \vert\theta_2\vert^n\,,$$
  weil die Spaltenvektoren ${\boldsymbol{\phi}}_1^*,\ldots,{\boldsymbol{\phi}}_\ell^*$ und damit auch die Zeilenvektoren $(\phi_{1,j},\ldots,\phi_{\ell,j})$ für $j=1,\ldots,\ell$ eine orthonormale Basis in $\mathbb{R}^\ell$ bilden und sich deshalb aus der Ungleichung von Cauchy-Schwarz ergibt, dass
  $$\sum\limits_{k=2}^\ell \vert\phi_{ki}^*\vert \vert\phi_{kj}^*\ver... ...^*)^2\Bigr)^{1/2}\Bigl(\sum\limits_{k=1}^\ell (\phi_{kj}^*)^2\Bigr)^{1/2}=1\,.$$

• Somit gilt

  $$\max\limits_{j\in E}\vert\alpha_{nj}-\pi_j\vert\le \frac{1}{\sqrt{\min\limits_{i\in E} \pi_i}}\; \vert\theta_2\vert^n \;.$$ (98)

  
  

  
  

• Die praktische Nutzbarkeit der Konvergenzabschätzung (98) kann jedoch aus mehreren Gründen problematisch sein, weil
  • der Vorfaktor in (98) nicht von der Wahl der Anfangsverteilung ${\boldsymbol{\alpha}}_0$ abhängt,
  • bei der Herleitung der Konvergenzabschätzung (98) vorausgesetzt wird, dass die Markov-Kette reversibel ist,
  • die Bestimmung des Eigenwertes $\theta_2$ schwierig sein kann, falls die Anzahl der Zustände $\ell$ groß ist.

  
  

• In Abschnitt 2.3.5 betrachten wir deshalb eine alternative Konvergenzabschätzung,
  • deren Vorfaktor von der gewählten Anfangsverteilung abhängt und
  • für die nicht vorausgesetzt wird, dass die betrachtete Markov-Kette reversibel ist,
  • und leiten in Abschnitt 2.3.7 eine Schranke für den zweitgrößten Betrag $\vert\theta_2\vert$ der Eigenwerte von reversiblen Übergangsmatrizen her.