Schranken für die Eigenwerte $\lambda _2$ und $\lambda _\ell$

Um Schranken für die Eigenwerte $\lambda _2$ und $\lambda _\ell$ herzuleiten, benötigen wir nun noch die folgenden Begriffe und Bezeichnungen.

• Für jedes Paar $i,j\in E$ mit $i\not= j$ und $p_{ij}>0$ bezeichnen wir
  • mit $e=e_{ij}$ die entsprechende (gerichtete) Kante des Übergangsgraphen, sowie
  • mit $e^-=i$ bzw. $e^+=j$ die Anfangsecke bzw. Endecke von $e$.
  • Sei $\mathcal{E}$ die Menge aller gerichteten Kanten $e=e_{ij}$ mit $i\not= j$ und $p_{ij}>0$.

  
  

• Außerdem betrachten wir für jedes Paar $i,j\in E$ mit $i\not= j$ genau einen Pfad $\gamma_{ij}$ von $i$ nach $j$,
  • der ein Vektor $\gamma_{ij}=(i_0,i_1,\ldots,i_{m-1},i_m)$ von Zuständen ist mit $i=i_0$, $j=i_m$ und
    $$p_{ii_1}p_{i_1i_2}\,\ldots\,p_{i_{m-1}j}>0\,,$$
    so dass keine der Kanten $e_{i_{k-1}i_k}$ mehrfach auftritt.
  • Sei $\Gamma$ die Menge aller dieser Pfade, und für jeden Pfad $\gamma_{ij}\in\Gamma$ sei

    $$\vert\gamma_{ij}\vert=\sum\limits_{e\in\gamma_{ij}}\frac{1}{Q(e)}... ...{1}{\pi_{i_1}p_{i_1i_2}}\;+\;\ldots \;+\;\frac{1}{\pi_{i_{m-1}}p_{i_{m-1}j}}\;,$$ (119)

    
    
    wobei $Q(e_{i_{k-1}i_k})=\pi_{i_{k-1}}p_{i_{k-1}i_k}$.
  • Der sogenannte Poincaré-Koeffizient $\kappa$ der Pfadmenge $\Gamma$ ist dann gegeben durch

    $$\kappa=\kappa(\Gamma)=\max\limits_{e\in\mathcal{E}} \sum\limits_{\gamma_{ij}\ni e} \vert\gamma_{ij}\vert\pi_i\pi_j\,.$$ (120)

    
    

• Schließlich betrachten wir
  • die erweiterte Kanten-Menge $\mathcal{E}^\prime\supset\mathcal{E}$, die auch die ,,Kanten'' $i\to i$ mit $p_{ii}>0$ enthält.
  • für jedes $i\in E$ genau einen Pfad $\gamma_i$ von $i$ nach $i$, der eine ungerade Anzahl von Kanten aus $\mathcal{E}^\prime$ enthält, so dass keine der Kanten mehrfach auftritt.
  • Sei $\Gamma^\prime$ die Menge aller dieser Pfade, und für jeden Pfad $\gamma_i\in\Gamma^\prime$ sei

    $$\vert\gamma_i\vert=\sum\limits_{e\in\gamma_i}\frac{1}{Q(e)}\;.$$ (121)

    
    

  • Der Koeffizient $\zeta$ der Pfadmenge $\Gamma^\prime$ ist dann gegeben durch

    $$\zeta=\zeta(\Gamma^\prime)=\max\limits_{e\in\mathcal{E}^\prime} \sum\limits_{\gamma_i\ni e} \vert\gamma_i\vert\pi_i\,.$$ (122)

    
    

Theorem 2.18   $\;$ Für die Eigenwerte $\lambda _2$ und $\lambda _\ell$ von ${\mathbf{P}}$ gilt

$$1-\;\frac{1}{\kappa}\ge\lambda_2\ge\lambda_\ell\ge-1+\;\frac{2}{\zeta}$$ (123)

und somit

$$\max\{\lambda_2,\vert\lambda_\ell\vert\}\le1-\min\, \Bigl\{\,\frac{1}{\kappa}\;,\;\frac{2}{\zeta}\,\Bigr\}\,.$$ (124)

Beweis

 

• Wir zeigen zunächst, dass $\lambda_2\le 1-\kappa^{-1}$.
  • Wegen Theorem 2.17 genügt es zu zeigen, dass

    $${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})\le\kappa\; D_{({\mat... ...({\mathbf{x}},{\mathbf{x}})\,,\qquad\forall\, {\mathbf{x}}\in\mathbb{R}^\ell\,.$$ (125)

    
    

  • Mit den in (119) eingeführten Bezeichnungen gilt
    

    $${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}}) = \frac{1}{2}\;\Bigl(2\Vert{\mathbf{x}}\Vert _{\boldsymbol{\pi}}^2-2({\mathbf{x}})_{\boldsymbol{\pi}}^2\Bigr)$$

    $$= \frac{1}{2}\;\Bigl(\sum\limits_{i\in E} x_i^2\pi_i+\sum\limits_{j\in E} x_j^2\pi_j -2\sum\limits_{i,j\in E} x_i x_j\pi_i\pi_j\Bigr)$$

    $$= \frac{1}{2}\;\sum\limits_{i,j\in E}(x_i-x_j)^2\pi_i\pi_j$$

    $$= \frac{1}{2}\;\sum\limits_{i,j\in E}\Bigl(\sum\limits_{e\in\gamma_{ij}}\;\frac{1}{\sqrt{Q(e)}}\;\sqrt{Q(e)} (x_{e^-}-x_{e^+})\Bigr)^2\pi_i\pi_j\,.$$

    
    

  • Aus der Ungleichung von Cauchy-Schwarz ergibt sich nun, dass
    

    $${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}}) \le \frac{1}{2}\;\sum\limits_{i,j\in E}\Bigl(\vert\gamma_{ij}\vert\sum\limits_{e\in\gamma_{ij}}\;{Q(e)} (x_{e^-}-x_{e^+})^2\Bigr)\pi_i\pi_j$$

    $$= \frac{1}{2}\; \sum\limits_{e\in\mathcal{E}}\Biggl({Q(e)} (x_{e^-}... ...um\limits_{\gamma_{ij}\ni\, e} \vert\gamma_{ij}\vert\; \pi_i\pi_j \Bigr)\Biggr)$$

    $$\le \kappa\;D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})\,,$$

    
    
    wobei sich die letzte Ungleichung aus Lemma 2.8 und aus der Definitionsgleichung (120) des Poincaré-Koeffizienten ergibt. Damit ist (125) bewiesen.
• Um den Beweis zu beenden, ist noch zu zeigen, dass $\lambda_\ell\ge-1+2\zeta^{-1}$.
  • Hierfür nutzen wir die folgende Identität: Für jedes ${\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathbb{R}^\ell$ gilt

    $$\frac{1}{2}\;\sum\limits_{i,j\in E}(x_i+x_j)^2\pi_i p_{ij}= ({\ma... ...thbf{x}},{\mathbf{x}})_{\boldsymbol{\pi}}+\Vert x\Vert _{\boldsymbol{\pi}}^2\,,$$ (126)

    
    
    denn aus der Reversibilität von $({\mathbf{P}},{\boldsymbol{\pi}})$ ergibt sich, dass
    

    $$\frac{1}{2}\;\sum\limits_{i,j\in E}(x_i+x_j)^2\pi_i p_{ij} = \frac{1}{2}\;\underbrace{\sum\limits... ...tackrel{(\ref{for.cha.rev})}{=}\pi_j p_{ji}}}_{=\sum\limits_{j\in E}x_j^2\pi_j}$$

    $$= \Vert x\Vert _{\boldsymbol{\pi}}^2+({\mathbf{P}}{\mathbf{x}},{\mathbf{x}})_{\boldsymbol{\pi}}\,.$$

    
    

  • Sei nun $\gamma_i=(i_0,i_1,\ldots,i_{2m},i_{2m+1})$ mit $i=i_0=i_{2m+1}$ ein Pfad von $i$ nach $i$, der eine ungerade Anzahl von Kanten enthält, so dass keine der Kanten mehrfach auftritt.
  • Dann gilt
    

    $$x_i = \frac{1}{2}\;\Bigl((x_i+x_{i_1})-(x_{i_1}+x_{i_2})+\ldots+(x_{i_{2m}}+x_i)\Bigr)$$

    $$= \frac{1}{2}\;\sum\limits_{e\in\gamma_i}(-1)^{n(e)} (x_{e^+}+x_{e^-})\,,$$

    
    
    wobei $n(e)=k$, falls $e=(i_k,i_{k+1})\in\gamma_i$.
  • Deshalb ergibt sich (ähnlich wie im ersten Teil des Beweises) aus der Ungleichung von Cauchy-Schwarz, dass für jedes ${\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathbb{R}^\ell$
    

    $$\Vert{\mathbf{x}}\Vert^2_{\boldsymbol{\pi}} = \sum\limits_{i\in E}\;\frac{\pi_i}{4}\;\Bigl(\sum\limits_{e\in\gamma_i}\; \frac{1}{\sqrt{Q(e)}}\;\sqrt{Q(e)}(-1)^{n(e)} (x_{e^+}+x_{e^-})\Bigr)^2$$

    $$\le \sum\limits_{i\in E}\;\Bigl(\frac{\pi_i}{4}\; \vert\gamma_i\vert \sum\limits_{e\in\gamma_i}\;(x_{e^+}+x_{e^-})^2Q(e)\Bigr)$$

    $$= \frac{1}{4}\;\sum\limits_{e\in\mathcal{E}^\prime}\Bigl((x_{e^+}+x_{e^-})^2 Q(e)\sum\limits_{\gamma_i\ni\, e} \vert\gamma_i\vert\pi_i\Bigr)$$

    $$\le \frac{\zeta}{4}\;\sum\limits_{e\in\mathcal{E}^\prime}(x_{e^+}+x_{e^-})^2Q(e)\,.$$

    
    

  • Hieraus und aus (126) ergibt sich nun, dass
    $$\Vert{\mathbf{x}}\Vert^2_{\boldsymbol{\pi}}\le\;\frac{\zeta}{2}\;... ...{x}})_{\boldsymbol{\pi}}+\Vert{\mathbf{x}}\Vert _{\boldsymbol{\pi}}^2\Bigr)\,.$$

  • Für ${\mathbf{x}}={\boldsymbol{\phi}}_\ell$ gilt also insbesondere
    $$1\le\frac{\zeta}{2}\;(\lambda_\ell+1)$$   bzw.$$\qquad \lambda_\ell\ge -1+\frac{2}{\zeta}\;.$$
    
     
      $\Box$
    
    
    

Beispiel

$\;$ Zufällige Irrfahrten auf Graphen 

• Wir kehren nun zu dem bereits in Abschnitt 2.3.1 diskutierten Beispiel von zufälligen Irrfahrten auf Graphen zurück.
  • Sei also $G=(V,K)$ ein verbundener Graph mit der Menge $V=\{v_1,\ldots,v_\ell\}$ von $\ell$ Eckpunkten und der Menge $K$ von Kanten, die jeweils zwei Eckpunkte miteinander verbinden,
  • so dass es für jedes Paar $v_i,v_j\in V$ von Eckpunkten einen ,,Pfad'' von Kanten aus $K$ gibt, der die Kanten $v_i$ und $v_j$ miteinander verbindet.
• Eine zufällige Irrfahrt auf dem Graph $G=(V,K)$ ist eine Markov-Kette $X_0,X_1,\ldots:\Omega\to E$
  • mit dem Zustandsraum $E=\{1,\ldots,\ell\}$ und der Übergangsmatrix ${\mathbf{P}}=(p_{ij})$, wobei

    $$p_{ij}=\left\{\begin{array}{ll} \displaystyle \frac{1}{d_i}\;, &\... ...$\ und $v_j$\ Nachbarn sind,}\\ [3\jot] 0\,, &\mbox{sonst.} \end{array}\right.$$ (127)

    
    

  • Dabei werden zwei Eckpunkte $v_i$ und $v_j$ Nachbarn genannt, falls sie die Endpunkte einundderselben Kante sind, und $d_i$ bezeichnet die Anzahl der Nachbarn von $v_i$.
• Wir hatten gezeigt, dass
  • die in (127) gegebene Übergangsmatrix ${\mathbf{P}}$ stets irreduzibel ist (wobei wir nun zusätzlich noch voraussetzen, dass ${\mathbf{P}}$ auch aperiodisch ist),
  • die (eindeutig bestimmte) stationäre Anfangsverteilung ${\boldsymbol{\pi}}$ gegeben ist durch

    $${\boldsymbol{\pi}}=\Bigl(\frac{d_1}{d}\;,\ldots,\;\frac{d_\ell}{d}\Bigr)^\top\,, \mbox{wobei $\;d=\sum\limits_{i=1}^\ell d_i$,}$$ (128)

    
    

  • und das in (127)-(128) gegebene Paar $({\mathbf{P}},{\boldsymbol{\pi}})$ reversibel ist.
• Für den in (120) eingeführten Poincaré-Koeffizienten $\kappa$ gilt dann
  $$\kappa=\kappa(\Gamma)=\max\limits_{e\in\mathcal{E}} \sum\limits_{\gamma_{ij}\ni e} \vert\gamma_{ij}\vert\pi_i\pi_j\,,$$
  wobei
  $$\vert\gamma_{ij}\vert=\sum\limits_{e\in\gamma_{ij}}\frac{1}{Q(e)}=d\,\Delta(\gamma_{ij})$$
  und $\Delta(\gamma_{ij})=\char93 \{e:\,e\in \gamma_{ij}\}$ die Anzahl der Kanten (d.h. die Länge) des Pfades $\gamma_{ij}$ bezeichnet.
• Hieraus und aus (127)-(128) ergibt sich, dass

  $$\kappa(\Gamma)\;\le\; \frac{\delta^2\Delta\beta}{d}\;,$$ (129)

  
  
  wobei $d/2$ die Gesamtanzahl aller Kanten,
  • $\delta=\max_{i\in E}d_i$ die maximale Anzahl von Kanten ist, die von einem Eckpunkt ausgehen,
  • $\Delta=\max_{\gamma\in\Gamma}\Delta(\gamma)$ die maximale Pfadlänge und
  • $\beta=\max_{e\in\mathcal{E}}\char93 \{\gamma\in \Gamma:\,\gamma\ni e\}$ der sogenannte Bottleneck-Koeffizient, d.h., die maximale Anzahl der Pfade ist, die jeweils durch eine einzelne Kante laufen.
• Aus (123) und (129) ergibt sich nun die folgende Abschätzung

  $$\lambda_2\;\le 1-\;\frac{1}{\kappa}\;\le\; 1-\;\frac{d}{\delta^2\Delta\beta}$$ (130)

  
  
  für den zweitgrößten Eigenwert $\lambda _2$ von ${\mathbf{P}}$.
• Auf ähnliche Weise ergibt sich die Abschätzung
  $$\zeta=\zeta(\Gamma^\prime)=\max\limits_{e\in\mathcal{E}^\prime} \... ...mma_i\ni e} \vert\gamma_i\vert\pi_i\le \delta \,\Delta^\prime\,\beta^\prime\,,$$
  wobei
  $$\vert\gamma_i\vert=\sum\limits_{e\in\gamma_i}\frac{1}{Q(e)}=d\,\D... ...\max_{e\in\mathcal{E}^\prime}\char93 \{\gamma\in \Gamma^\prime:\,\gamma\ni e\}$$
  und somit

  $$\lambda_\ell\;\ge\; -1 +\;\frac{2}{\zeta}\;\ge\;-1+\;\frac{2}{\delta \,\Delta^\prime\,\beta^\prime}\;.$$ (131)

  
  

• Beachte 
  • Für das bereits in Abschnitt 2.3.1 betrachtete Zahlenbeispiel
    
    
    
    

    gilt insbesondere, dass

    $$d=24,\, \delta=5,\,\Delta=3,\,\beta=7$$   und$$\qquad \Delta^\prime=3,\,\beta^\prime=3$$

  • Aus (130) und (131) ergibt sich somit
    $$\lambda_2\;\le\; 1-\;\frac{24}{25\cdot 3\cdot 7}\;<\;\frac{24}{25... ...nd}\qquad \lambda_8\;>\;-1+\;\frac{2}{5\cdot 3\cdot 3}\;=\;-\;\frac{43}{45}\;.$$
    bzw.
    $$\max\{\lambda_2,\vert\lambda_8\vert\}\;<\;\frac{24}{25}\;.$$