Alternative Abschätzung der Konvergenzgeschwindigkeit; $\chi ^2$-Kontrast

Mit Hilfe der multiplikativ reversiblen Version ${\mathbf{M}}={\mathbf{P}}\widetilde{\mathbf{P}}$ der (ergodischen, jedoch nicht notwendig reversiblen) Übergangsmatrix ${\mathbf{P}}$ leiten wir nun eine alternative Abschätzung für die Geschwindigkeit der Konvergenz ${\boldsymbol{\alpha}}^\top{\mathbf{P}}^n\to{\boldsymbol{\pi}}^\top$ her, wenn $n\to\infty$; vgl. Theorem 2.16.

Dabei erweisen sich die folgenden (abkürzenden) Bezeichnungen und Hilfssätze im Beweis von Theorem 2.16 als nützlich.

• Sei $\mathcal{L}(E)$ die Familie aller Funktionen,
  • die auf $E$ definiert sind und die in die reelle Zahlengerade $\mathbb{R}$ abbilden, und
  • sei ${\boldsymbol{\pi}}=(\pi_1,\ldots,\pi_\ell)^\top$ eine beliebige positive Wahrscheinlichkeitsfunktion aus $\mathcal{L}(E)$, d.h., es gelte $\pi_i>0$ für jedes $i\in E$ und $\sum_{i=1}^\ell\pi_i=1$.
• Für beliebige Vektoren ${\mathbf{x}}=(x_1,\ldots,x_\ell)^\top\in\mathcal{L}(E)$ und ${\mathbf{y}}=(y_1,\ldots,y_\ell)^\top\in\mathcal{L}(E)$ bezeichnen wir mit $({\mathbf{x}},{\mathbf{y}})_{\boldsymbol{\pi}}$ das Skalarprodukt

  $$({\mathbf{x}},{\mathbf{y}})_{\boldsymbol{\pi}}=\sum\limits_{i=1}^\ell x_iy_i\pi_i$$ (103)

  
  
  und mit $\Vert{\mathbf{x}}\Vert _{\boldsymbol{\pi}}$ die zugehörige Norm, d.h.
  $$\Vert{\mathbf{x}}\Vert _{\boldsymbol{\pi}}= \sqrt{\sum\limits_{i=1}^\ell x_i^2\pi_i}$$

• Unter dem (bezüglich ${\boldsymbol{\pi}}$ gewichteten) Mittel $({\mathbf{x}})_{\boldsymbol{\pi}}$ bzw. der Varianz ${\rm Var\,}_\pi({\mathbf{x}})$ von ${\mathbf{x}}\in\mathcal{L}(E)$ verstehen wir die Größen

  $$({\mathbf{x}})_{\boldsymbol{\pi}}=\sum\limits_{i=1}^\ell x_i\pi_i\qquad\Bigl(=({\mathbf{x}},{{\mathbf{e}}})_{\boldsymbol{\pi}}\Bigr)$$ (104)

  
  
  und

  $${\rm Var\,}_\pi({\mathbf{x}})=\Vert{\mathbf{x}}\Vert _{\boldsymbol{\pi}}^2-({\mathbf{x}})_{\boldsymbol{\pi}}^2\,.$$ (105)

  
  

Lemma 2.6   $\;$ Für jedes ${\mathbf{x}}\in\mathcal{L}(E)$ gilt die Identität

$${\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}})={\rm Var\,}_{\boldsy... ...{\mathbf{I}}-{\mathbf{M}}){\mathbf{x}},{\mathbf{x}}\bigr)_{\boldsymbol{\pi}}\,.$$ (106)

Beweis

 

• Mit der Schreibweise $\widehat{\mathbf{x}}={\mathbf{x}}-({\mathbf{x}})_{\boldsymbol{\pi}}{{\mathbf{e}}}$ gilt, dass $(\widehat{\mathbf{x}})_{\boldsymbol{\pi}}=0$ und
  $$(\widetilde{\mathbf{P}}\widehat{\mathbf{x}})_{\boldsymbol{\pi}}=\... ...\sum\limits_{i,j=1}^\ell \pi_jp_{ji}x_j-({\mathbf{x}})_{\boldsymbol{\pi}}=0\,,$$
  wobei sich die vorletzte Gleichheit aus der Definitionsgleichung (99) der Matrix $\widetilde{\mathbf{P}}$ ergibt.
• Hieraus folgt, dass

  $$\Vert\widehat{\mathbf{x}}\Vert _{\boldsymbol{\pi}}^2={\rm Var\,}_... ...ymbol{\pi}}(\widehat{\mathbf{x}}) ={\rm Var\,}_{\boldsymbol{\pi}}({\mathbf{x}}) \qquad \Vert\widetilde{\mathbf{P}}\widehat{\mathbf{x}}\Vert _{\bo... ...hbf{x}})= {\rm Var\,}_{\boldsymbol{\pi}}(\widetilde{\mathbf{P}}{\mathbf{x}})\,.$$ (107)

  
  

• Andererseits gilt
  

  $$\Vert\widetilde{\mathbf{P}}\widehat{\mathbf{x}}\Vert _{\boldsymbol{\pi}}^2 = \bigl(\widetilde{\mathbf{P}}\widehat{\mathbf{x}}, \widetilde{\mat... ...igl(\sum\limits_{k=1}^\ell \widetilde p_{ik}\widehat{\mathbf{x}}_k\Bigr)^2\pi_i$$

  $$= \sum\limits_{i=1}^\ell \sum\limits_{j,k=1}^\ell \widetilde p_{ij}... ... =\frac{\pi_k p_{ki}}{\pi_i}} \widehat{\mathbf{x}}_j\widehat{\mathbf{x}}_k\pi_i$$

  $$= \sum\limits_{k=1}^\ell\underbrace{\displaystyle\sum\limits_{j=1}^... ...=({\mathbf{P}}\widetilde{\mathbf{P}}{\mathbf{x}})_k}\widehat{\mathbf{x}}_k\pi_k$$

  $$= \bigl({\mathbf{P}}\widetilde{\mathbf{P}}\widehat{\mathbf{x}}, \wi... ...{\mathbf{M}}\widehat{\mathbf{x}}, \widehat{\mathbf{x}}\bigr)_{\boldsymbol{\pi}}$$

  
  
  und somit
  $$\Vert\widehat{\mathbf{x}}\Vert _{\boldsymbol{\pi}}^2-\Vert\wideti... ...mathbf{I}}-{\mathbf{M}}){\mathbf{x}}, {\mathbf{x}}\bigr)_{\boldsymbol{\pi}}\,,$$
  weil ${\mathbf{M}}$ eine stochastische Matrix ist mit ${\boldsymbol{\pi}}^\top{\mathbf{M}}={\boldsymbol{\pi}}^\top$ und weil deshalb $({\mathbf{I}}-{\mathbf{M}}){{\mathbf{e}}}={\,{\bf0}}$ bzw.
  $$\bigl(({\mathbf{I}}-{\mathbf{M}}){\mathbf{x}},\,{{\mathbf{e}}}\bi... ..._{j=1}^\ell x_j\underbrace{\sum\limits_{i=1}^\ell \pi_i m_{ij}}_{=\pi_j} =0\,.$$

• Hieraus und aus (107) ergibt sich die Behauptung.
  
  $\Box$

Wir führen nun noch die folgenden Begriffe ein.

• Sei $E=\{1,\ldots,\ell\}$, seien ${\boldsymbol{\alpha}}=(\alpha_1,\ldots,\alpha_\ell)^\top$ und ${\boldsymbol{\beta}}=(\beta_1,\ldots,\beta_\ell)^\top$ zwei beliebige Wahrscheinlichkeitsverteilungen auf $E$, und sei

  $$d_{\rm TV}({\boldsymbol{\alpha}},{\boldsymbol{\beta}})=\frac{1}{2}\;\sum\limits_{i\in E}\vert\alpha_i-\beta_i\vert\,,$$ (108)

  
  
  d.h., der Abstand $d_{\rm TV}({\boldsymbol{\alpha}},{\boldsymbol{\beta}})$ zwischen ${\boldsymbol{\alpha}}$ und ${\boldsymbol{\beta}}$ wird durch die Totalvariation

  $$\vert{\boldsymbol{\alpha}}-{\boldsymbol{\beta}}\vert= \sum\limits_{i\in E}\vert\alpha_i-\beta_i\vert$$ (109)

  
  
  des ,,signierten Maßes'' ${\boldsymbol{\alpha}}-{\boldsymbol{\beta}}$ ausgedrückt.
• Falls $\beta_i>0$ für jedes $i\in E$, dann betrachten wir auch die Größe

  $$\chi^2({\boldsymbol{\alpha}};{\boldsymbol{\beta}})=\sum\limits_{i\in E} \;\frac{(\alpha_i-\beta_i)^2}{\beta_i}$$ (110)

  
  
  die der $\chi ^2$-Kontrast von ${\boldsymbol{\alpha}}$ bezüglich ${\boldsymbol{\beta}}$ genannt wird.

Der Abstand $d_{\rm TV}({\boldsymbol{\alpha}},{\boldsymbol{\beta}})$ zwischen ${\boldsymbol{\alpha}}$ und ${\boldsymbol{\beta}}$ kann wie folgt durch den $\chi ^2$-Kontrast $\chi^2({\boldsymbol{\alpha}};{\boldsymbol{\beta}})$ von ${\boldsymbol{\alpha}}$ bezüglich ${\boldsymbol{\beta}}$ abgeschätzt werden.

Lemma 2.7   $\;$ Falls $\beta_i>0$ für jedes $i\in E$, dann gilt

$$d_{\rm TV}^2({\boldsymbol{\alpha}},{\boldsymbol{\beta}})\le \frac{1}{4}\;\chi^2({\boldsymbol{\alpha}};{\boldsymbol{\beta}})\,.$$ (111)

Beweis

 

• Aus der Ungleichung von Cauchy-Schwarz ergibt sich unter Berücksichtigung von $\sum_{i\in E}\beta_i=1$, dass
  $$\Bigl(\sum\limits_{i\in E}\vert\alpha_i-\beta_i\vert\Bigr)^2 = \B... ..._i}\Bigr)^2 \le \sum\limits_{i\in E}\frac{1}{\beta_i}\;(\alpha_i-\beta_i)^2\,.$$

• Hieraus folgt die Behauptung.
  
  $\Box$

Die Geschwindigkeit der Konvergenz ${\boldsymbol{\alpha}}^\top{\mathbf{P}}^n\to{\boldsymbol{\pi}}^\top$, wenn $n\to\infty$, lässt sich nun wie folgt

• mit Hilfe des zweitgrößten Eigenwertes $\theta_{{\mathbf{M}},2}$ der multiplikativ reversiblen Version ${\mathbf{M}}={\mathbf{P}}\widetilde{\mathbf{P}}$ der (ergodischen) Übergangsmatrix ${\mathbf{P}}$ sowie
• des $\chi ^2$-Kontrastes $\chi^2({\boldsymbol{\alpha}};{\boldsymbol{\pi}})$ der Anfangsverteilung ${\boldsymbol{\alpha}}$ bezüglich der stationären Grenzverteilung ${\boldsymbol{\pi}}$ abschätzen.

Theorem 2.16   $\;$ Für jede beliebige Anfangsverteilung ${\boldsymbol{\alpha}}$ und für jedes $n\in\mathbb{N}$ gilt

$$d^2_{\rm TV} \bigl(\bigl({\boldsymbol{\alpha}}^\top{\mathbf{P}}^n... ...({\boldsymbol{\alpha}};{\boldsymbol{\pi}})}{4}\; \;\theta^n_{{\mathbf{M}},2}\,.$$ (112)

Beweis

 

• Sei ${\boldsymbol{\rho}}_n=(\rho_{n1},\ldots,\rho_{n\ell})^\top$ mit $\rho_{ni}=({\boldsymbol{\alpha}}^\top{\mathbf{P}}^n)_i/\pi_i$.
  • Dann gilt für jedes $i\in E$
    $$\sum\limits_{k=1}^\ell\frac{\pi_k p_{ki}}{\pi_i}\;\frac{({\boldsy... ..._k}{\pi_k}\;=\; \frac{({\boldsymbol{\alpha}}^\top{\mathbf{P}}^{n+1})_i}{\pi_i}$$
    und somit
    $$\widetilde{\mathbf{P}}{\boldsymbol{\rho}}_n={\boldsymbol{\rho}}_{n+1}\,.$$

  • Außerdem ergibt sich aus der Definitionsgleichung (110) des $\chi ^2$-Kontrastes $\chi_n^2=\chi^2\bigl(\bigl({\boldsymbol{\alpha}}^\top{\mathbf{P}}^n\bigr)^\top;{\boldsymbol{\pi}}\bigr)$ von $\bigl({\boldsymbol{\alpha}}^\top{\mathbf{P}}^n\bigr)^\top$ bezüglich ${\boldsymbol{\pi}}$, dass
    

    $$\chi^2_n = \sum\limits_{i=1}^\ell\;\frac{\bigl(({\boldsymbol{\alpha}}^\top{\... ...Bigl(\frac{({\boldsymbol{\alpha}}^\top{\mathbf{P}}^n)_i} {\pi_i}-1\Bigr)^2\pi_i$$

    $$= \sum\limits_{i=1}^\ell \bigl(\rho_{ni}-({\boldsymbol{\rho}}_n)_{\... ...l{\pi}}\bigr)^2\pi_i = {\rm Var\,}_{\boldsymbol{\pi}}({\boldsymbol{\rho}}_n)\,,$$

    
    
    d.h.,

    $$\chi^2_n={\rm Var\,}_{\boldsymbol{\pi}}({\boldsymbol{\rho}}_n)\,.$$ (113)

    
    

  • Wegen der in Lemma 2.6 hergeleiteten Identität (106) gilt somit, dass

    $$\chi^2_n=\chi^2_{n+1}+\bigl(({\mathbf{I}}-{\mathbf{M}}){\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n\Bigr)_{\boldsymbol{\pi}}\,.$$ (114)

    
    

• Andererseits ergibt sich aus der Spektraldarstellung (101) von ${\mathbf{M}}$, die in Theorem 2.15 hergeleitet wurde, dass
  

  $$\bigl(({\mathbf{I}}-{\mathbf{M}}){\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n\Bigr)_{\boldsymbol{\pi}} = ({\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}}-({\mathbf{M}}{\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}}$$

  $$= ({\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}... ...{\psi}}_i^\top{\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}}$$

  $$= ({\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}... ...si}}_i^\top{\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}}\,,$$

  
  
  weil $\theta_{{\mathbf{M}},1}=1$, ${\boldsymbol{\phi}}_1={{\mathbf{e}}}$ bzw. ${\boldsymbol{\psi}}_1^\top={\boldsymbol{\pi}}^\top$ und somit
  $$\bigl({\boldsymbol{\phi}}_1{\boldsymbol{\psi}}_1^\top{\boldsymbol... ...bol{\pi}}=1 \qquad\Bigl(=({\boldsymbol{\rho}}_n)^2_{\boldsymbol{\pi}}\Bigr)\,.$$
  • Weil die in (100) definierten (rechten) Eigenvektoren ${\boldsymbol{\phi}}_1,\ldots,{\boldsymbol{\phi}}_\ell$ von ${\mathbf{M}}$ eine Basis in $\mathbb{R}^\ell$ bilden, gibt es also einen (eindeutig bestimmten) Vektor $\bigl(\rho_{n1}^{\rm (r)},\ldots,\rho_{n\ell}^{\rm (r)}\bigr)^\top\in\mathbb{R}^\ell$, so dass ${\boldsymbol{\rho}}_n=\sum_{i=1}^\ell \rho_{ni}^{\rm (r)}{\boldsymbol{\phi}}_i$.
  • In (102) hatten wir darüber hinaus gezeigt, dass ${\boldsymbol{\psi}}_i^\top{\boldsymbol{\rho}}_n=\rho_{ni}^{\rm (r)}$ gilt. Wegen ${\boldsymbol{\psi}}_1^\top={\boldsymbol{\pi}}^\top$ gilt somit insbesondere, dass ${\boldsymbol{\psi}}_1^\top{\boldsymbol{\rho}}_n=1$.
  • Weil außerdem ${\boldsymbol{\phi}}_i={\mathbf{D}}^{-1}{\boldsymbol{\phi}}_i^*$ bzw. ${\boldsymbol{\psi}}_i={\mathbf{D}}{\boldsymbol{\phi}}_i^*$ für jedes $i\in E$ gilt, ergibt sich hieraus, dass
    

    $$\sum\limits_{i=2}^\ell \theta_{{\mathbf{M}},i}({\boldsymbol{\phi}... ...{\psi}}_i^\top{\boldsymbol{\rho}}_n,\,{\boldsymbol{\rho}}_n)_{\boldsymbol{\pi}} = \sum\limits_{i=2}^\ell\sum\limits_{j=1}^\ell \theta_{{\mathbf{M}}... ...j}^{\rm (r)} ({\boldsymbol{\phi}}_i,\,{\boldsymbol{\phi}}_j)_{\boldsymbol{\pi}}$$

    $$= \sum\limits_{i=2}^\ell\sum\limits_{j=1}^\ell \theta_{{\mathbf{M}}... ...athbf{D}}^{-1}{\boldsymbol{\phi}}^*_j \bigr)_{\boldsymbol{\pi}}}_{=\delta_i(j)}$$

    $$= \sum\limits_{i=2}^\ell \theta_{{\mathbf{M}},i}\bigl(\rho_{ni}^{\rm (r)}\bigr)^2$$

    $$\le \theta_{{\mathbf{M}},2}\sum\limits_{i=2}^\ell \bigl(\rho_{ni}^{\r... ...^{\rm (r)}}_{ ={\boldsymbol{\psi}}_1^\top{\boldsymbol{\rho}}_n=1}\bigr)^2\Bigr)$$

    $$= \theta_{{\mathbf{M}},2}\Biggl(\sum\limits_{i=1}^\ell\sum\limits_{... ...mbol{\pi}}-1\Bigr)}_{={\rm Var\,}_{\boldsymbol{\pi}}({\boldsymbol{\rho}}_n)}\,.$$

    
    

• Insgesamt haben wir also gezeigt, dass
  $$\bigl(({\mathbf{I}}-{\mathbf{M}}){\boldsymbol{\rho}}_n,\,{\boldsy... ...{\mathbf{M}},2}\bigr) {\rm Var\,}_{\boldsymbol{\pi}}({\boldsymbol{\rho}}_n)\,.$$
  • Wegen (113) und (114) folgt hieraus, dass
    $$\chi^2_n\ge\chi^2_{n+1}+\bigl(1-\theta_{{\mathbf{M}},2}\bigr)\chi^2_n$$   bzw.$$\qquad \chi^2_{n+1}\le\theta_{{\mathbf{M}},2}\;\chi^2_n\,.$$

  • Somit gilt $\chi^2_n\le\theta^n_{{\mathbf{M}},2}\;\chi^2_0$ für jedes $n\ge 1$, und die Behauptung ergibt sich nun aus Lemma 2.7.
    
    $\Box$