Dirichlet-Formen und Rayleigh-Theorem

• Sei $E=\{1,\ldots,\ell\}$ eine (beliebige) endliche Menge, und sei ${\mathbf{P}}$ eine $(\ell\times\ell)$-dimensionale Übergangsmatrix, die irreduzibel und aperiodisch (d.h. quasi-positiv) sowie reversibel ist.
• Zur Erinnerung
  • Sämtliche Eigenwerte von ${\mathbf{P}}$ sind reell (vgl. Abschnitt 2.3.3), und
  • aus dem Theorem von Perron-Frobenius (vgl. Theorem 2.6 bzw. Korollar 2.3) folgt darüber hinaus, dass die Eigenwerte von ${\mathbf{P}}$ im Intervall $(-1,1]$ liegen,
  • wobei $1$ der größte Eigenwert ist, und die Beträge der anderen Eigenwerte (strikt) kleiner als $1$ sind.

Beachte

 

• In Abweichung von der bisher verwendeten Schreibweise (bei der die Beträge der Eigenwerte betrachtet wurden) ordnen wir nun die Eigenwerte selbst der Größe nach und bezeichnen sie mit $\lambda_1,\ldots,\lambda_\ell$, so dass
  $$1=\lambda_1>\lambda_2\ge\ldots\ge\lambda_\ell>-1\,.$$

• Für die in Abschnitt 2.3.4 eingeführte multiplikativ reversible Version ${\mathbf{M}}={\mathbf{P}}\widetilde{\mathbf{P}}$ der Übergangsmatrix ${\mathbf{P}}$ gilt sogar
  $$1=\lambda_1>\lambda_2\ge\ldots\ge\lambda_\ell>0\,,$$
  d.h., für die Eigenwerte der Matrix ${\mathbf{M}}$ stimmen die beiden Notationen $\theta_1,\ldots,\theta_\ell$ und $\lambda_1,\ldots,\lambda_\ell$ überein.
• Wenn $\ell$ eine große Zahl ist,
  • dann kann die Berechnung des zweitgrößten Betrages $\vert\theta_2\vert=\max\{\lambda_2,\vert\lambda_\ell\vert\}$ der Eigenwerte schwierig sein,
  • weshalb wir in Abschnitt 2.3.7 Schranken für $\lambda _2$ und $\lambda _\ell$ herleiten, deren Berechnung einfacher ist.
• Diese Schranken sind insbesondere dann nützlich, wenn
  • die stationäre (Grenz-) Verteilung ${\boldsymbol{\pi}}$ zwar (zumindest prinzipiell) bekannt ist,
  • die zugehörige Markov-Kette dennoch mit einer instationären Anfangsverteilung ${\boldsymbol{\alpha}}$ ,,gestartet'' wird, beispielsweise in einem vorgegebenen Zustand $i\in E$, wobei dann $\alpha_i=1$ und $\alpha_j=0$ für $j\not=i$ gilt.

Um eine obere Schranke für $\lambda _2$ herzuleiten, benötigen wir eine Darstellungsformel des Eigenwertes $\lambda _2$,

• die in der Literatur das Theorem von Rayleigh genannt wird und
• die mit Hilfe der sogenannten Dirichlet-Form

  $$D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})=... ...l(({\mathbf{I}}-{\mathbf{P}}){\mathbf{x}},{\mathbf{x}}\bigr)_{\boldsymbol{\pi}}$$ (115)

  
  
  des reversiblen Paares $({\mathbf{P}},{\boldsymbol{\pi}})$ ausgedrückt wird, wobei $({\mathbf{y}},{\mathbf{x}})_{\boldsymbol{\pi}}$ das in (103) eingeführte Skalarprodukt von ${\mathbf{y}}$ und ${\mathbf{x}}$ bezüglich ${\boldsymbol{\pi}}$ bezeichnet.

Dabei zeigen wir zunächst den folgenden Hilfssatz.

Lemma 2.8   $\;$ Für jedes ${\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathbb{R}^\ell$ gilt

$$D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})=\frac{1}{2}\;\sum_{i,j\in E}\pi_ip_{ij}(x_j-x_i)^2\,.$$ (116)

Beweis

$\;$ Aus der Definitionsgleichung (103) des Skalarproduktes und aus der Reversibilität des Paares $({\mathbf{P}},{\boldsymbol{\pi}})$ ergibt sich, dass

$$2\bigl(({\mathbf{I}}-{\mathbf{P}}){\mathbf{x}},{\mathbf{x}}\bigr)_{\boldsymbol{\pi}} = 2\sum\limits_{i,j\in E}\pi_ip_{ij}x_i(x_i-x_j)$$

$$\stackrel{i\to j}{=} \sum\limits_{i,j\in E}\pi_ip_{ij}x_i(x_i-x_j) +\sum\limits_{i,j\in E}\pi_jp_{ji}x_j(x_j-x_i)$$

$$\stackrel{(\ref{for.cha.rev})}{=} \sum\limits_{i,j\in E}\pi_ip_{ij}x_i(x_i-x_j) +\sum\limits_{i,j\in E}\pi_ip_{ij}x_j(x_j-x_i)$$

$$= \sum_{i,j\in E}\pi_ip_{ij}(x_j-x_i)^2\,.$$

 
  $\Box$

Wir beweisen nun das folgende Theorem von Rayleigh, das eine Darstellungsformel für den zweitgrößten Eigenwert $\lambda _2$ des reversiblen Paares $({\mathbf{P}},{\boldsymbol{\pi}})$ liefert.

Theorem 2.17    

• Sei $\mathbb{R}^\ell_{\not=}=\bigl\{{\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathbb{R}^\ell:\;$   $\mbox{$x_i\not=x_j$\ für ein Paar $i,j\in E$}$$\bigr\}$ die Menge derjenigen Vektoren aus $\mathbb{R}^\ell$, für die nicht alle Komponenten gleich sind.
• Für den Eigenwert $\lambda _2$ des reversiblen Paares $({\mathbf{P}},{\boldsymbol{\pi}})$ gilt dann

  $$\lambda_2=1-\inf\limits_{{\mathbf{x}}\in\mathbb{R}^\ell_{\not=}}\... ...)}({\mathbf{x}},{\mathbf{x}})}{{\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})}\;,$$ (117)

  
  
  wobei ${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})$ die in $(\ref{var.iks.pii})$ definierte Varianz der Komponenten von ${\mathbf{x}}$ bezüglich ${\boldsymbol{\pi}}$ bezeichnet.

Beweis

 

• Aus Lemma 2.8 ergibt sich, dass für beliebige $c\in\mathbb{R}$ und ${\mathbf{x}}\in\mathbb{R}^\ell$
  $$D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})=... ...ldsymbol{\pi}})}({\mathbf{x}}-c\,{\mathbf{e}},{\mathbf{x}}-c\,{\mathbf{e}})\,.$$
  • Somit ist die Behauptung (117) äquivalent mit

    $$1-\lambda_2=\inf\limits_{{\mathbf{x}}\in\mathbb{R}^\ell_0}\; \fra... ...)}({\mathbf{x}},{\mathbf{x}})}{{\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})}\;,$$ (118)

    
    
    wobei $\mathbb{R}^\ell_0=\bigl\{{\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathbb{R}^\ell:\; ({\mathbf{x}})_{\boldsymbol{\pi}}=0,\,{\mathbf{x}}\not={\,{\bf0}}\bigr\}$.
  • Die rechten Eigenvektoren ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ von ${\mathbf{P}}$ seien nun so gewählt, dass sie eine orthonormale Basis in $\mathbb{R}^\ell$ bezüglich des Skalarproduktes $(\cdot\,,\,\cdot)_{\boldsymbol{\pi}}$ bilden, d.h., es gilt $({\boldsymbol{\phi}}_i,{\boldsymbol{\phi}}_j)_{\boldsymbol{\pi}}=1$, falls $i=j$, und $({\boldsymbol{\phi}}_i,{\boldsymbol{\phi}}_j)_{\boldsymbol{\pi}}=0$, falls $i\not= j$, wobei ${\boldsymbol{\phi}}_1={{\mathbf{e}}}$.
  • Dabei werden zunächst die Eigenvektoren ${\boldsymbol{\phi}}_1^*,\ldots,{\boldsymbol{\phi}}_\ell^*$ der symmetrischen Matrix ${\mathbf{D}}{\mathbf{P}}{\mathbf{D}}^{-1}$ so gewählt, dass sie orthonormal bezüglich des gewöhnlichen euklidischen Skalarproduktes sind, wobei dann ${\boldsymbol{\phi}}_i={\mathbf{D}}^{-1}{\boldsymbol{\phi}}_i^*$ für jedes $i\in E$ gesetzt wird (vgl. auch Abschnitt 2.3.3).
  • Es gibt somit 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\,.$$

  • Wegen $\lambda_1=1$ folgt hieraus, dass
    $$({\mathbf{I}}-{\mathbf{P}}){\mathbf{x}}=\sum\limits_{i=2}^\ell (1-\lambda_i)x_i^{\rm (r)}{\boldsymbol{\phi}}_i$$   bzw.$$\qquad D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})=\sum\limits_{i=2}^\ell (1-\lambda_i)\bigl(x_i^{\rm (r)}\bigr)^2\,.$$

• Andererseits ergibt sich aus ${\boldsymbol{\phi}}_1={{\mathbf{e}}}$ und aus der Orthonormalität der Eigenvektoren ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ bezüglich des Skalarproduktes $(\cdot\,,\,\cdot)_{\boldsymbol{\pi}}$, dass
  $$({\mathbf{x}})_{\boldsymbol{\pi}}=({\mathbf{x}},\,{{\mathbf{e}}})_{\boldsymbol{\pi}}=x_1^{\rm (r)}$$   bzw.$$\qquad {\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})= \sum\limits_{i=2}^\ell\bigl(x_i^{\rm (r)}\bigr)^2\,,$$   falls$$\; ({\mathbf{x}})_{\boldsymbol{\pi}}=0\,.$$
  • Somit gilt für jedes ${\mathbf{x}}\in\mathbb{R}^\ell_0$, dass
    

    $$\frac{D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})}{{\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})} = \frac{\sum\limits_{i=2}^\ell (1-\lambda_i)\bigl(x_i^{\rm (r)}\bigr)^2}{ \sum\limits_{i=2}^\ell\bigl(x_i^{\rm (r)}\bigr)^2}$$

    $$= (1-\lambda_2)+\; \frac{\sum\limits_{i=2}^\ell (1-\lambda_i)\bigl(... ...bigl(x_i^{\rm (r)}\bigr)^2}{ \sum\limits_{i=2}^\ell\bigl(x_i^{\rm (r)}\bigr)^2}$$

    $$= (1-\lambda_2)+\; \frac{\sum\limits_{i=3}^\ell (\lambda_2-\lambda_... ...2}{ \sum\limits_{i=2}^\ell\bigl(x_i^{\rm (r)}\bigr)^2} \;\;\ge\; 1-\lambda_2\,.$$

    
    

  • Damit ist die (äquivalente) Behauptung (118) bewiesen, denn aus dem letzten Ausdruck für den Quotienten $D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})/{\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})$ ergibt sich außerdem, dass
    $$\frac{D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})}{{\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})}=1-\lambda_2\,,$$
    für ${\mathbf{x}}={\boldsymbol{\phi}}_2$, wobei ${\boldsymbol{\phi}}_2\in\mathbb{R}^\ell_0$ gilt, weil ${\boldsymbol{\phi}}_1={\mathbf{e}}$ und ${\boldsymbol{\phi}}_2$ linear unabhängig sind.
    
    $\Box$