Abschätzung der Konvergenzgeschwindigkeit

• Wir zeigen nun, wie die in Abschnitt 2.3 hergeleiteten allgemeinen Abschätzungen für den Variationsabstand $d_{\rm TV}({\boldsymbol{\alpha}}_n,\,{\boldsymbol{\pi}})$ bzw. für den zweitgrößten Betrag $\vert\theta_2\vert=\max\{\lambda_2,\vert\lambda_\ell\vert\}$ der Eigenwerte $\lambda_1,\ldots,\lambda_\ell$ der Übergangsmatrix ${\mathbf{P}}$ genutzt werden können,
  • um obere Schranken für die Größe von $d_{\rm TV}({\boldsymbol{\alpha}}_n,\,{\boldsymbol{\pi}})$ zu bestimmen, die sich im $n$-ten Iterationsschritt bei der MCMC-Simulation mit dem Metropolis-Algorithmus ergibt,
  • wenn die zu simulierende Verteilung ${\boldsymbol{\pi}}$ den folgenden Bedingungen genügt.
• Und zwar nehmen wir an,
  • dass $\pi_{\mathbf{x}}\not=\pi_{{\mathbf{x}}^\prime}$ für beliebige ${\mathbf{x}},\,{\mathbf{x}}^\prime\in E$ mit ${\mathbf{x}}\not={\mathbf{x}}^\prime$,
  • und dass die Zustände ${\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\in E$ so numeriert sind, dass $\pi_{{\mathbf{x}}_1}>\ldots>\pi_{{\mathbf{x}}_\ell}$.
• Wir können deshalb (o.B.d.A.) zu der bereits in Abschnitt 2.3 verwendeten Schreibweise zurückkehren und identifizieren die Zustände ${\mathbf{x}}_1,\ldots,{\mathbf{x}}_\ell\in E$ mit den ersten $\ell$ natürlichen Zahlen, d.h. $E=\{1,\ldots,\ell\}$.
• Die Wahrscheinlichkeiten $\pi_i\;(=\pi_{{\mathbf{x}}_i})$ lassen sich dann in der folgenden Form schreiben:

  $$\pi_i=\frac{b^{h(i)}}{z(b)}\;,\qquad\forall\, i=1,\ldots,\ell\,,$$ (56)

  
  
  • wobei $h:\{1,\ldots,\ell\}\to(1,\infty)$ eine monoton wachsende Funktion ist,
  • $b\in(0,1)$ so gewählt wird, dass für eine gewisse Konstante $c\ge 1$

    $$h(i+1)-h(i)\ge c\,,\qquad\forall\, i=1,\ldots,\ell-1$$ (57)

    
    

  • und $z(b)=\sum_{i=1}^\ell b^{h(i)}$ ein (im allgemeinen unbekannter) Normierungsfaktor ist.
• Um einen Metropolis-Algorithmus zur MCMC-Simulation von ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ definieren zu können, setzen wir außerdem voraus,
  • dass die Basis $b$ und die Differenzen $h(i+1)-h(i)$ für jedes $i=1,\ldots,\ell-1$ bekannt sind,
  • d.h. insbesondere, dass die Quotienten $\pi_{i+1}/\pi_i$ für jedes $i=1,\ldots,\ell-1$ bekannt sind.
• Für die Matrix ${\mathbf{Q}}=(q_{ij})$ der ,,potentiellen'' Übergange $i\to j$ gelte

  $$q_{ij}=\left\{\begin{array}{ll} \displaystyle\frac{1}{2}\;, &\mbo... ...\ell-1$\ und $j=i-1,\,i+1$,}\\ [3\jot] 0\,, & \mbox{sonst.} \end{array}\right.$$ (58)

  
  
  • Die Akzeptanzwahrscheinlichkeiten $a_{ij}$ seien durch (53) gegeben, d.h.
    $$a_{ij}=\min\Bigl\{1,\;\frac{\pi_j\, q_{ji}}{\pi_i q_{ij}}\Bigr\}=... ...igr\}\,,\qquad\forall\,i,j\in \{1,\ldots,\ell\}\;\mbox{mit $q_{ij}=q_{ji}>0$.}$$

  • Für die Eintragungen $p_{ij}=q_{ij}a_{ij}$ der Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ der MCMC-Simulation ergibt sich dann aus (56) und (58), dass

    $$p_{11}=1-\;\frac{b^{h(2)-h(1)}}{2}\;,\qquad p_{12}=\frac{b^{h(2)-h(1)}}{2}\;,\qquad p_{\ell,\ell-1}=p_{\ell\ell}=\;\frac{1}{2}$$ (59)

    
    
    und für $i=2,\ldots,\ell-1$

    $$p_{i,i-1}=\frac{1}{2}\;,\qquad p_{i,i+1}=\frac{b^{h(i+1)-h(i)}}{2}\;,\qquad p_{ii}=1-p_{i,i-1}-p_{i,i+1}\,.$$ (60)

    
    

Theorem 3.15   $\;$ Für den zweitgrößten Eigenwert $\lambda _2$ der in $(\ref{ein.tra.ein})$- $(\ref{ein.tra.zwe})$ definierten Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ gilt

$$\lambda_2\le 1-\;\frac{(1-b^{c/2})^2}{2}\;.$$ (61)

Beweis

 

• In Theorem 3.14 hatten wir gezeigt, dass das Paar $({\mathbf{P}},{\boldsymbol{\pi}})$ reversibel ist.
• Aus dem Theorem von Rayleigh (vgl. Theorem 2.17) ergibt sich somit die Darstellungsformel

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

  
  
  • wobei $\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$ bezeichnet, für die nicht alle Komponenten gleich sind,
  • ${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})=\Vert{\mathbf{x}}\Vert^2_{\boldsymbol{\pi}}-({\mathbf{x}})^2_{\boldsymbol{\pi}}$ die Varianz der Komponenten von ${\mathbf{x}}$ bezüglich ${\boldsymbol{\pi}}$
  • und $D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})=\bigl(({\mathbf{I}}-{\mathbf{P}}){\mathbf{x}},{\mathbf{x}}\bigr)_{\boldsymbol{\pi}}$ die Dirichlet-Form des reversiblen Paares $({\mathbf{P}},{\boldsymbol{\pi}})$ ist.
• Wegen (62) genügt es zu zeigen, dass

  $${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})\le a D_{({\mathbf{P}... ...}})}({\mathbf{x}},{\mathbf{x}})\,,\qquad\forall\,{\mathbf{x}}\in\mathbb{R}^\ell$$ (63)

  
  
  für eine Konstante $a$ mit

  $$0<a\le\frac{2}{(1-b^{c/2})^2}\;.$$ (64)

  
  
  • Ähnlich wie im Beweis von Theorem 2.18 ergibt sich mit den dort eingeführten Bezeichnungen, dass für jedes $\theta\in(0,1)$
    

    $$2\,{\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}}) = \sum\limits_{i,j\in E} (x_i-x_j)^2\pi_i\pi_j$$

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

    $$\le \sum\limits_{i,j\in E}\Biggl( \sum\limits_{e\in\gamma_{ij}}Q(e)^{... ...m\limits_{e\in\gamma_{ij}} \;\frac{1}{Q(e)^{2\theta}}\;\Biggr) \; \pi_i\pi_j\,,$$

    
    
    wobei der ,,gerichteten Kante'' $e=(e^{-},e^{+})$ die ,,Kantenwahrscheinlichkeit'' $Q(e)=\pi_{e^-}\,p_{e^-e^+}$ zugeordnet wird und $\gamma_{ij}$ den ,,Pfad'' von $i$ nach $j$ bezeichnet.
  • Mit der Schreibweise $\vert\gamma_{ij}\vert _\theta=\sum_{e\in\gamma_{ij}} \;Q(e)^{-2\theta}$ erhalten wir somit, dass
    

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

    $$= \sum\limits_{e\in\mathcal{E}}(x_{e^-}-x_{e^+})^2Q(e)Q(e)^{2\theta-1} \sum\limits_{\gamma_{ij}\ni e}\pi_i\pi_j\vert\gamma_{ij}\vert _\theta\,.$$

    
    

  • Hieraus ergibt sich die Gültigkeit von (63) für

    $$a=\max\limits_{e\in\mathcal{E}}\Bigl\{Q(e)^{2\theta-1} \sum\limits_{\gamma_{ij}\ni e}\pi_i\pi_j\vert\gamma_{ij}\vert _\theta\Bigr\}\,,$$ (65)

    
    
    weil wir in Lemma 2.8 gezeigt hatten, dass
    $$2\,D_{({\mathbf{P}},{\boldsymbol{\pi}})}({\mathbf{x}},{\mathbf{x}})=\sum\limits_{e\in\mathcal{E}}(x_{e^-}-x_{e^+})^2Q(e)\,.$$

• Es ist nun noch zu zeigen, dass die in (65) betrachtete Konstante $a$ der Ungleichung (64) genügt.
  • Hierfür wählen wir den Pfad $\gamma_{ij}=(i,i+1,\ldots,j-1,j)$ für jedes Paar $i,j\in E$ mit $i<j$.
  • Dann ergibt sich aus (56) und (59)-(60), dass
    $$Q(i,i+1)=\pi_i p_{i,i+1}=\frac{b^{h(i)}}{z(b)}\;\frac{b^{h(i+1)-h(i)}}{2}=\frac{\pi_{i+1}}{2}\;.$$

  • Aus der in Theorem 3.14 gezeigten Reversibilität des Paares $({\mathbf{P}},{\boldsymbol{\pi}})$ folgt somit, dass
    $$Q(i+1,i)=Q(i,i+1)=\frac{\pi_{i+1}}{2}\;.$$

  • Wegen (56) und (57) ergibt sich hieraus, dass für beliebige $i,j\in E$ mit $i<j$
    

    $$\vert\gamma_{ij}\vert _\theta = \Biggl(\Bigl(\frac{\pi_{i+1}}{\pi_j}\Bigr)^{-2\theta}+\ldots+ \Bi... ...-i-1)c\theta}+\ldots+b^{2c\theta}+1\Bigr)\Bigl(\frac{\pi_j}{2}\Bigr)^{-2\theta}$$

    $$\le \frac{2^{2\theta}\pi_j^{-2\theta}}{1-b^{2c\theta}}\;.$$

    
    

  • Außerdem haben sämtliche Kanten $e\in\mathcal{E}$ die Form $e=(i,i+1)$ oder $e=(i,i-1)$, denn für die in (58)-(60) gegebenen Eintragungen der Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ gilt $p_{ij}=0$, falls $\vert i-j\vert>1$.
• Für die in (65) betrachtete Konstante $a$ ergibt sich somit insgesamt, dass für $\theta<1/2$
  

  $$a = \max\limits_{e\in\mathcal{E}}\Bigl\{Q(e)^{2\theta-1} \sum\limits_{\gamma_{ij}\ni e}\pi_i\pi_j\vert\gamma_{ij}\vert _\theta\Bigr\}$$

  $$\le \max\limits_{k=1,\ldots,\ell-1}\;\Biggl\{Q(k,k+1)^{2\theta-1} \su... ... j\le\ell}\;2^{2\theta}\; \frac{\pi_i\pi_j^{1-2\theta}}{1-b^{2c\theta}}\Biggr\}$$

  $$\le \frac{2}{({1-b^{2c\theta}})(1-b^{c(1-2\theta)})}\;,$$

  
  
  weil $Q(k,k+1)^{2\theta-1}=\bigl(\pi_{k+1}/2\bigr)^{2\theta-1}$ bzw. $\sum_{1\le i\le k}\pi_i\le 1$ und
  $$\sum\limits_{k+1\le j\le\ell}\pi_j^{1-2\theta} =\Biggl(\Bigl( \fr... ...pi_{k+1}^{1-2\theta} \le \;\frac{\pi_{k+1}^{1-2\theta}}{1-b^{c(1-2\theta)}}\;.$$

• Für $\theta=1/4$ ergibt sich hieraus die Abschätzung (64).
  
  $\Box$

Bei der Herleitung einer unteren Schranke für den kleinsten Eigenwert $\lambda _\ell$ der in $(\ref{ein.tra.ein})$- $(\ref{ein.tra.zwe})$ definierten Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ ist der folgende Hilfssatz nützlich.

Lemma 3.1    

• Sei ${\mathbf{A}}=(a_{ij})$ eine beliebige $\ell\times\ell$-Matrix, und für jedes $i=1,\ldots,\ell$ sei $r_i=\sum_{j:\,1\le j\le\ell,\,j\not= i}\vert a_{ij}\vert$.
• Sei $\lambda$ ein beliebiger Eigenwert von ${\mathbf{A}}$, sei ${\boldsymbol{\phi}}=(\phi_1,\ldots,\phi_\ell)^\top\not={\mathbf{o}}$ ein rechter Eigenvektor, der zu $\lambda$ gehört, und sei $k$ die Nummer derjenigen Komponente $\phi_k$ mit
  $$\vert\phi_k\vert=\max\limits_{i=1,\ldots,\ell} \vert\phi_i\vert>0\,.$$

• Dann gilt

  $$\vert\lambda-a_{kk}\vert\le r_k\,.$$ (66)

  
  

Beweis

 

• Aus der Definitionsgleichung ${\mathbf{A}}{\boldsymbol{\phi}}=\lambda{\boldsymbol{\phi}}$ von $\lambda$ bzw. ${\boldsymbol{\phi}}$ ergibt sich insbesondere, dass
  $$\sum\limits_{j=1}^\ell a_{kj}\phi_j=\lambda\,\phi_k$$   bzw.$$\qquad (\lambda-a_{kk})\phi_k=\sum\limits_{j:\,1\le j\le\ell,\,j\not= k} a_{kj}\phi_j\,.$$

• Hieraus folgt, dass
  $$\vert\lambda-a_{kk}\vert \vert\phi_k\vert\le\sum\limits_{j:\,1\le... ... r_k\vert\phi_k\vert\qquad\mbox{bzw.}\qquad \vert\lambda-a_{kk}\vert\le r_k\,.$$
  
   
    $\Box$
  
  
  

Theorem 3.16   $\;$ Für den kleinsten Eigenwert $\lambda _\ell$ der in $(\ref{ein.tra.ein})$- $(\ref{ein.tra.zwe})$ definierten Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ gilt

$$\lambda_\ell\ge -b^c\,.$$ (67)

Beweis

 

• Aus Lemma 3.1 ergibt sich für ${\mathbf{A}}={\mathbf{P}}$ (und für den in Lemma 3.1 betrachteten, zu $\lambda _\ell$ gehörenden Index $k$), dass
  $$\vert\lambda_\ell-p_{kk}\vert\le \sum\limits_{j:\,1\le j\le\ell,\,j\not= k}p_{kj}=1-p_{kk}\qquad\mbox{bzw.}\qquad \lambda_\ell\ge -1+2p_{kk}\,.$$

• Hieraus und aus (59)-(60) folgt, dass
  $$\lambda_\ell\ge -1+2\min\limits_{i=1,\ldots,\ell}p_{ii}\ge -1+2\Bigl(1-\frac{1}{2}-\frac{b^c}{2}\Bigr)=-b^c\,.$$
  
   
    $\Box$
  
  
  

Beachte

$\;$ Insgesamt ergibt sich aus den Theoremen 3.15 und 3.16 die Abschätzung

$$\vert\theta_2\vert=\max\{\lambda_2,\vert\lambda_\ell\vert\}\le \m... ...{ 1-\;\frac{(1-b^{c/2})^2}{2}\;,\,b^c\Bigr\} =1-\;\frac{(1-b^{c/2})^2}{2}\; \,.$$ (68)