Abschätzung der Konvergenzgeschwindigkeit; Perron-Frobenius-Theorem

• Zur Erinnerung
  • Falls $\{X_n\}$ eine Markov-Kette ist, so dass sämtliche Eintragungen $p_{ij}$ der (1-stufigen) Übergangsmatrix ${\mathbf{P}}$ positiv sind,
  • dann hat die in (40) hergeleitete geometrische Schranke der Konvergenzgeschwindigkeit gegen die Grenzverteilung ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ die folgende Form:

    $$\sup\limits_{j\in E}\vert\alpha_{nj}-\pi_j\vert= O((1-\ell a)^n)\,,$$ (43)

    
    
    wobei $a=\min_{i,j\in E}p_{ij}> 0$.
• Wenn das Minimum $a$ der Eintragungen $p_{ij}$ der Übergangsmatrix ${\mathbf{P}}$ nahe bei 0 liegt, dann ist die Schranke in (43) nur von geringem Nutzen.
• In manchen Fällen lässt sich jedoch die ,,Basis'' $1-\ell a$ der Konvergenzabschätzung in (43) verbessern.

Beispiel

$\;$ (Wettervorhersage)

• Sei $E=\{1,2\}$ und
  $${\mathbf{P}}=\left(\begin{array}{cc} 1-p & p\\ p^\prime & 1-p^\prime \end{array}\right)\;,$$   $$\mbox{wobei $0<p,p^\prime<1$.}$$$$$$

• In Abschnitt 2.2.1 hatten wir gezeigt,
  • 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... ...me} \left(\begin{array}{cc} p & -p\\ -p^\prime & p^\prime \end{array}\right)$$

  • und dass somit
    $$\Bigl({\mathbf{P}}^\infty=\Bigr)\quad \displaystyle \lim_{n... ...rray}{cc} p^\prime & p \\ p^\prime & p \end{array}\right)\;.$$

  • In diesem Fall ergibt sich also, dass

    $${\mathbf{P}}^n-{\mathbf{P}}^\infty=\frac{(1-p-p^\prime)^n}{p+p^\p... ...& p^\prime \end{array}\right)\qquad\Bigl(=O(\vert 1-p-p^\prime\vert^n)\Bigr)\,,$$ (44)

    
    
    wobei $p+p^\prime>2a=2\min_{i,j\in E}p_{ij}$ und somit $\vert 1-p-p^\prime\vert<1-2a$, falls $p\not= p^\prime$.
• Beachte
  • Die ,,Basis'' $\vert\theta_2\vert=\vert 1-p-p^\prime\vert$ der Konvergenzgeschwindigkeit in (44) ist der Betrag des ,,zweitgrößten'' Eigenwertes $\theta_2$ der Übergangsmatrix ${\mathbf{P}}$,
  • denn die charakteristische Gleichung
    $$\Bigl(\det({\mathbf{P}}-\theta{\mathbf{I}})=\Bigr)\quad (1-p-\theta)(1-p^\prime-\theta)-pp^\prime=0$$
    von ${\mathbf{P}}$ besitzt die beiden Lösungen $\theta_1=1$ und $\theta_2=1-p-p^\prime$.

Im allgemeinen lassen sich geometrische Konvergenzabschätzungen der Form (44) mit Hilfe des folgenden Theorems von Perron-Frobenius für quasi-positive Matrizen herleiten.

Theorem 2.6    

• Sei ${\mathbf{A}}$ eine quasi-positive $\ell\times\ell$ Matrix mit den Eigenwerten $\theta_1,\ldots,\theta_\ell$, so dass $\vert\theta_1\vert\ge\ldots\ge\vert\theta_\ell\vert$.
• Dann gilt:

  (a)

  Der Eigenwert $\theta_1$ ist rellwertig und positiv,

  (b)

  $\theta_1>\vert\theta_i\vert$ für jedes $i=2,\ldots,\ell$,

  (c)

  die rechten bzw. linken (zu $\theta_1$ gehörenden) Eigenvektoren ${\boldsymbol{\phi}}_1$ bzw. ${\boldsymbol{\psi}}_1$ sind (bis auf einen konstanten Faktor) eindeutig bestimmt und können so gewählt werden, dass sämtliche Komponenten von ${\boldsymbol{\phi}}_1$ bzw. ${\boldsymbol{\psi}}_1$ positiv sind.

Einen Beweis von Theorem 2.6 kann man beispielsweise in Kapitel 1 des Buches E. Seneta (1981) Non-Negative Matrices and Markov Chains, Springer-Verlag, New York finden.

Korollar 2.3   $\;$ Sei ${\mathbf{P}}$ eine quasi-positive Übergangsmatrix. Dann gilt

• $\theta_1=1,{\boldsymbol{\phi}}_1={\mathbf{e}}$ und ${\boldsymbol{\psi}}_1={\boldsymbol{\pi}}$, wobei ${\mathbf{e}}=(1,\ldots,1)^\top$ und ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$.
• $\vert\theta_i\vert<1$ für jedes $i=2,\ldots,\ell$.

Beweis

 

• Weil ${\mathbf{P}}$ eine stochastische Matrix ist,
  • gilt offenbar ${\mathbf{P}}{\mathbf{e}}={\mathbf{e}}$, und aus (41) ergibt sich, dass ${\boldsymbol{\pi}}^\top{\mathbf{P}}={\boldsymbol{\pi}}^\top$.
  • Hieraus folgt, dass $1$ ein Eigenwert von ${\mathbf{P}}$ ist und dass ${\mathbf{e}}$ bzw. ${\boldsymbol{\pi}}$ ein rechter bzw. linker Eigenvektor dieses Eigenwertes ist.
• Sei nun
  • $\theta$ ein beliebiger Eigenwert von ${\mathbf{P}}$, und sei ${\boldsymbol{\phi}}=(\phi_1,\ldots,\phi_\ell)^\top$ ein zu $\theta$ gehörender Eigenvektor.
  • Dann ergibt sich aus der Definitionsgleichung (27) von $\theta$ und ${\boldsymbol{\phi}}$, dass
    $$\vert\theta\vert\, \vert\phi_i\vert\le\sum_{j=1}^\ell p_{ij}\vert\phi_j\vert\le\max_{j\in E} \vert\phi_j\vert\,, \qquad\forall\, i\in E\,.$$

  • Hieraus folgt, dass $\vert\theta\vert\le 1$ und dass somit $\theta_1=1$ der größte Eigenwert von ${\mathbf{P}}$ ist.
• Aus Theorem 2.6 folgt nun, dass $\vert\theta_i\vert<1$ für jedes $i=2,\ldots,\ell$.
  
  $\Box$

Aus Korollar 2.3 ergibt sich die folgende geometrische Konvergenzabschätzung.

Korollar 2.4   $\;$ Sei ${\mathbf{P}}$ eine quasi-positive Übergangsmatrix, so dass sämtliche Eigenwerte $\theta_1,\ldots,\theta_\ell$ von ${\mathbf{P}}$ voneinander verschieden sind. Dann gilt

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

Beweis

 

• Aus Korollar 2.3 ergibt sich, dass

  $$\lim_{n\to\infty}\sum_{i=2}^\ell\theta_i^n{\boldsymbol{\phi}}_i{\boldsymbol{\psi}}_i^\top={\bf0}\,,$$ (46)

  
  
  weil $\vert\theta_i\vert<1$ für jedes $i=2,\ldots,\ell$.
• Außerdem ergibt sich aus Korollar 2.3, dass $\theta_1=1$ und ${\boldsymbol{\phi}}_1=(1,\ldots,1)^\top$ bzw. ${\boldsymbol{\psi}}_1={\boldsymbol{\pi}}$ für den rechten bzw. linken (zu $\theta_1$ gehörenden) Eigenvektor ${\boldsymbol{\phi}}_1$ bzw. ${\boldsymbol{\psi}}_1$.
• Aus der Spektraldarstellung (30) von ${\mathbf{P}}^n$, d.h.
  $${\mathbf{P}}^n= \sum_{i=1}^\ell\theta^n_i{\boldsymbol{\phi}}_i{\boldsymbol{\psi}}_i^\top\,,$$
  folgt nun, dass
  $${\mathbf{P}}^n-\left(\begin{array}{c} {\boldsymbol{\pi}}^\top\\ ... ... = \sum_{i=2}^\ell\theta^n_i{\boldsymbol{\phi}}_i{\boldsymbol{\psi}}_i^\top\,.$$

• Weil ${\boldsymbol{\alpha}}_n^\top={\boldsymbol{\alpha}}^\top {\mathbf{P}}^n$ (vgl. Theorem 2.3), ergibt sich hieraus und aus (46) die Gültigkeit von (45).
  
  $\Box$

Beispiel

$\;$ (Konsensbildung)
vgl. C. Hesse (2003) Angewandte Wahrscheinlichkeitstheorie. Vieweg-Verlag, Braunschweig, S. 349

• Eine Experten-Kommission, die aus $\ell$ Mitgliedern besteht, soll eine Prognose für einen (Wirtschafts-) Parameter $\mu\in\mathbb{R}$ erstellen, beispielsweise der ,,Rat der Fünf Weisen'' eine Prognose für das Wirtschaftswachstum im kommenden Jahr.
  • Dabei entwickelt zunächst jeder der $\ell$ Experten eine eigene Prognose für $\mu$, wobei die einzelnen Prognosewerte mit $\widehat\mu^{(0)}_1,\ldots,\widehat\mu^{(0)}_\ell$ bezeichnet werden und typischerweise voneinander verschieden sind.
  • Wie können nun die Experten hieraus eine gemeinsame Prognose der gesamten Kommission, d.h., einen Konsens bilden?
  • Eine einfache Vorgehensweise wäre die Bildung des arithmetischen Mittels $(\widehat\mu^{(0)}_1+\ldots+\widehat\mu^{(0)}_\ell)/\ell$, wobei jedoch die Kompetenzunterschiede zwischen den einzelnen Experten unberücksicht bleiben würden.
• Eine alternative Vorgehensweise besteht darin, dass jeder Experte seine eigene Prognose nach Kenntnisnahme der Prognosen der anderen $\ell-1$ Experten und unter Berücksichtigung seiner Einschätzung der prognostischen Fähigkeiten der Kommissionsmitglieder modifiziert.
  • Für beliebige $i,j\in\{1,\ldots,\ell\}$ ordnet dabei der $i$-te Experte dem $j$-ten Experten die ,,Vertrauenswahrscheinlichkeit'' $p_{ij}$ zu, so dass
    $$p_{ij}>0$$   und$$\qquad\sum\limits_{j=1}^\ell p_{ij}=1\,,\qquad\forall\, i,j\in\{1,\ldots,\ell\}\,$$

  • und der $i$-te Experte modifiziert seine ursprüngliche Prognose $\widehat\mu_i^{(0)}$ zu
    $$\widehat\mu_i^{(1)}=\sum\limits_{j=1}^\ell p_{ij}\widehat\mu_j^{(0)}\,.$$

  • In den meisten Fällen werden die modifizierten Prognosen $\widehat\mu^{(1)}_1,\ldots,\widehat\mu^{(1)}_\ell$ immer noch voneinander verschieden sein, weshalb das Verfahren solange wiederholt wird, bis die Unterschiede hinreichend klein geworden sind.
• Aus Theorem 2.4 folgt,
  • dass dieses Ziel erreichbar ist, wenn das Modifikationsverfahren oft genug wiederholt wird,
  • denn gemäß Theorem 2.4 existieren die Grenzwerte

    $$\lim\limits_{n\to\infty}\widehat\mu^{(n)}_i=\sum\limits_{j=1}^\ell \pi_j\widehat\mu_j^{(0)}$$ (47)

    
    
    und hängen nicht von $i$ ab,
  • wobei der Vektor ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ der Grenzwerte $\pi_j=\lim_{n\to\infty} p^{(n)}_{ij}$ die (eindeutig bestimmte) Lösung des linearen Gleichungssystems (41) ist, d.h., es gilt ${\boldsymbol{\pi}}^\top={\boldsymbol{\pi}}^\top{\mathbf{P}}$ mit ${\mathbf{P}}=(p_{ij})$.
• Die Gültigkeit von (47) lässt sich dabei wie folgt begründen. Es gilt nämlich
  

  $$\lim\limits_{n\to\infty}\widehat\mu^{(n)}_i = \lim\limits_{n\to\infty} \sum\limits_{j=1}^\ell p_{ij}\;\widehat\... ...lim\limits_{n\to\infty}\sum\limits_{j=1}^\ell p^{(n)}_{ij}\;\widehat\mu_j^{(0)}$$

  $$= \sum\limits_{j=1}^\ell\lim\limits_{n\to\infty} p^{(n)}_{ij}\;\widehat\mu_j^{(0)} = \sum\limits_{j=1}^\ell \pi_j\;\widehat\mu_j^{(0)}\,.$$

  
  

• Der Konsens der Experten-Kommission, d.h. die gemeinsame Prognose des (unbekannten) Parameters $\mu$ ist dann gegeben durch

  $$\widehat\mu=\sum\limits_{j=1}^\ell \pi_j\widehat\mu_j^{(0)}\,.$$ (48)

  
  

Beachte

 

• Für große $\ell$ kann die direkte (algebraische) Lösung des linearen Gleichungssystems (41) schwierig sein.
• Dann spielt die Abschätzung der Konvergenzgeschwindigkeit in (47) eine wichtige Rolle bei der praktischen Durchführung der in (47) beschriebenen Konsensbildung.
• Wir betrachten hierfür das folgende Zahlenbeispiel.
  • Sei $\ell=3$, und sei

    $${\mathbf{P}}=\left(\begin{array}{ccc}\displaystyle \frac{2}{6} & ... ...{8} & \displaystyle\frac{1}{8} & \displaystyle\frac{5}{8} \end{array}\right)\;.$$ (49)

    
    

  • Die Eintragungen dieser stochastischen Matrix bedeuten, dass die Kompetenz des dritten Experten von allen Kommissionsmitgliedern besonders hoch eingeschätzt wird.
  • Die Lösung ${\boldsymbol{\pi}}=(\pi_1,\pi_2,\pi_3)^\top$ des entsprechenden linearen Gleichungssystems (41) ist dann gegeben durch
    $$\pi_1=\frac{21}{77}\;,\qquad\pi_2=\frac{12}{77}\;,\qquad \pi_3=\frac{44}{77}\;,$$
    d.h., die Prognose $\widehat\theta_3^{(0)}$ des dritten (als besonders kompetent eingeschätzten) Experten wird am stärksten gewichtet.
• Die Eigenwerte der in (49) gegebenen Übergangsmatrix sind $\theta_1=1$, $\theta_2=1/8$ und $\theta_3=1/12$.

• Gemäß (43) ergibt sich dabei die ,,Basis''
  $$1-3a=1-3\min\limits_{i,j=1,2,3} p_{ij}= 1-\frac{3}{8}=\frac{5}{8}$$
  der Konvergenzabschätzung, während Korollar 2.4 die folgende (deutlich verbesserte) geometrische Konvergenzabschätzung
  $$\max\limits_{i\in\{1,\ldots,\ell\}}\bigl\vert\;\widehat\mu-\widehat\mu^{(n)}_i\bigr\vert = O(\vert\theta_2\vert^n)$$
  liefert, wobei $\theta_2=1/8$ der zweitgrößte Eigenwert der in (49) gegebenen stochastischen Matrix ${\mathbf{P}}$ ist, vgl. auch Übungsaufgabe 3.3.