Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Symulacje stochastyczne – 15. Markowowskie Monte Carlo VI. Oszacowania dokładności – MIM UW

Zagadnienia

15. Markowowskie Monte Carlo VI. Oszacowania dokładności

W tym rozdziale zajmiemy się problemem oszacowania błędu markowowskich algorytmów Monte Carlo. W odróżnieniu od wstępnych rozważań w Rozdziale 10, będą nas interesowały ścisłe nierówności, a nie oceny oparte na twierdzeniach granicznych. Skupimy się na rozkładzie spektralnym macierzy przejścia. Jest to najbardziej znana i zapewne najskuteczniejsza metoda otrzymywania dobrych oszacowań, przynajmniej dla łańcuchów odwracalnych na przestrzeni skończonej.

15.1. Reprezentacja spektralna macierzy odwracalnej

Rozważmy łańcuch nieprzywiedlny i odwracalny z macierzą przejścia P i rozkładem stacjonarnym \pi^{\top}. Zakładamy więc, że dla dowolnych x,y\in{\cal X} spełniona jest zależność

\pi(x)P(x,y)=\pi(y)P(y,x).

Niech

\Pi={\rm diag}(\pi)=\left(\begin{array}[]{cccc}\pi(1)&0&\cdots&0\cr 0&\pi(2)&\cdots&0\cr\vdots&\vdots&\ddots&\vdots\cr 0&0&\cdots&\pi(d)\cr\end{array}\right).

Warunek odwracalności możemy zapisać w postaci \Pi P=P^{\top}\Pi. Wyposażmy przestrzeń \mathbb{R}^{d} w iloczyn skalarny

{\langle}f,g{\rangle _{\pi}}=f^{\top}\Pi g=\sum _{x}f(x)g(x)\pi(x),

gdzie f,g\in\mathbb{R} traktujemy jak wektory kolumnowe. Oczywiście, norma funkcji f jest zdefiniowana wzorem \| f{\| _{{\pi}}}^{{2}}={\langle}f,f{\rangle _{\pi}}. Macierz P traktujemy jako operator działający z lewej strony na funkcje, z prawej strony na rozkłady prawdopodobieństwa. Zgodnie z regułami mnożenia macierzy i wektorów, wzory na Pf i \xi^{\top}P są następujące:

Pf(x)=\sum _{y}P(x,y)f(y),\qquad\xi^{\top}P(y)=\sum _{x}\xi(x)P(x,y).

Odwracalność P implikuje

{\langle}f,Pg{\rangle _{\pi}}=f^{\top}\Pi Pg=f^{\top}P^{\top}\Pi g=g^{\top}\Pi Pf={\langle}Pf,g{\rangle _{\pi}}.

Znaczy to, że P jest macierzą operatora samosprzężonego względem iloczynu skalarnego {\langle}\cdot,\cdot{\rangle _{\pi}}. W skrócie powiemy, że P jest \pi-samosprzężona. Wartości własne P są rzeczywiste i zawarte w przedziale [-1,1]. Uporządkujmy je w kolejności malejącej:

1=\lambda _{0}>\lambda _{1}\geq\cdots\lambda _{{d-1}}\geq-1.

Wiadomo, że \lambda _{0}=1 jest pojedynczą wartością własną. Jeśli łańcuch jest nieokresowy, to \lambda _{{d-1}}>-1. Niech

\Lambda={\rm diag}\big(1,\lambda _{1},\ldots,\lambda _{{d-1}}\big).

Reprezentacja spektralna macierzy P jest następująca:

P=V\Lambda V^{\top}\Pi,

gdzie

V^{\top}\Pi V=I

lub, równoważnie, VV^{\top}\Pi=I. Zauważmy, że kolumny macierzy

V=\big(1,v_{1},\ldots,v_{{d-1}}\big)

są prawostronnymi wektorami własnymi macierzy P tworzącymi bazę \pi-ortonormalną. Mamy więc Pv_{i}=\lambda v_{i} (oczywiście, v_{0}=1 jest tu wektorem jedynek) oraz

{\langle}v_{i},v_{j}{\rangle _{\pi}}=v_{i}^{\top}\Pi v_{j}=\mathbb{I}(i=j).

Lewostronne wektory własne P (zapisane wierszowo) są postaci v_{i}^{\top}\Pi: mamy v_{i}^{\top}\Pi P=\lambda _{i}v_{i}^{\top}\Pi. W szczególności, v_{0}^{\top}\Pi=\pi^{\top}. Zapiszmy reprezentację spektralną P w bardziej jawnej formie:

P=\sum _{{i\geq 0}}\lambda _{i}v_{i}v_{i}^{\top}\Pi,

przy tym

\sum _{{i\geq 0}}v_{i}v_{i}^{\top}\Pi=I.

Zauważmy jeszcze, że pierwszy (lub raczej - zerowy) składnik jest macierzą stabilną (o jednakowych wierszach):

v_{0}v_{0}^{\top}\Pi=1\pi^{\top}.

Reprezentacja spektralna prowadzi do zgrabnych wyrażeń na potęgi macierzy. Łatwo zauważyć, że P^{{n}}=V\Lambda^{{n}}V^{\top}\Pi, czyli

P^{{n}}=\sum _{{i\geq 0}}\lambda _{i}^{{n}}v_{i}v_{i}^{\top}\Pi=1\pi^{\top}+\sum _{{i\geq 1}}\lambda _{i}^{{n}}v_{i}v_{i}^{\top}\Pi. (15.1)

Wiemy, że wszystkie wartości własne \lambda _{{i}} z wyjątkiem zerowej (\lambda _{0}=1) oraz, być może, ostatniej (\lambda _{{d-1}}\geq-1) są co do modułu mniejsze niż 1. Jeżeli więc \lambda _{{d-1}}>-1, to wszystkie składniki sumy we wzorze (15.1) z wyjątkiem początkowego zmierzają do zera i w rezultacie

P^{{n}}\to 1\pi^{\top}\quad(n\to\infty).

Jest to nic innego jak teza Słabego Twierdzenia Ergodycznego (Twierdzenie 14.5), otrzymana zupełnie inną metodą, przy założeniu odwracalności. Można pokazać, że warunek \lambda _{{d-1}}>-1 jest równoważny nieokresowości, i jest konieczny (jeśli \lambda _{{d-1}}=-1 to łańcuch ma okres 2).

Następujący lemat będzie podstawą dalszych rozważań i umożliwi ,,przerobienie” STE na jawne wyniki. Zdefiniujmy

\lambda=\max(\lambda _{{1}},\ |\lambda _{{d-1}}|\ ).

Załóżmy, że łańcuch jest nieokresowy, więc \lambda<1. Pokażemy, że operator P ograniczony do podprzestrzeni \{ f:f\perp 1\}\subset\mathbb{R}^{d} ortogonalnej do funkcji stałych jest zwężający, ze stałą \lambda<1.

Lemat 15.1

Jeżeli {\langle}f,1{\rangle _{\pi}}=0 to \| Pf{\| _{{\pi}}}\leq\lambda\| f{\| _{{\pi}}}.

Dowód

Wystarczy zauważyć, że

\begin{split}{\langle}Pf,Pf{\rangle _{\pi}}&={\langle}f,P^{2}f{\rangle _{\pi}}\\
&=f^{\top}\Pi 1\pi^{\top}f+f^{\top}\sum _{{i\geq 1}}\lambda _{i}^{{2n}}v_{i}v_{i}^{\top}\Pi f\\
&=\sum _{{i\geq 1}}\lambda _{i}^{{2n}}{\langle}v_{i},f{\rangle}_{{\pi}}^{2}\\
&\leq\lambda^{{2n}}\sum _{{i\geq 1}}{\langle}v_{i},f{\rangle}_{{\pi}}^{2}\\
&=\lambda^{{2n}}{\langle}f,f{\rangle}.\\
\end{split}

Korzystamy tu z faktu, że P jest samosprzężony, ze wzoru (15.1) i z tego, że f^{\top}\Pi 1=0.

15.1.1. Oszacowanie szybkości zbieżności

Przejdźmy teraz do jawnych oszacowań szybkości zbieżności w STE. Wyniki zawarte z tym podrozdziale pochodzą z pracy Diaconisa i Strooka [5]. Dla rozkładu prawdopodobieństwa \xi^{\top} definiujemy ,,odległość” \chi^{2} od rozkładu stacjonarnego wzorem

\chi^{{2}}(\pi,\xi)=\sum _{{x}}\frac{(\ \xi(x)-\pi(x)\ )^{{2}}}{\pi(x)}=(\xi^{\top}-\pi^{\top})\Pi^{{-1}}(\xi-\pi).

Ta ,,odległość” nie ma własności symetrii, więc nie jest metryką, ale to nie przeszkadza. Istotna jest interpretacja \chi^{2} jako ,,odstępstwa od stacjonarności”. Wykorzystamy podejście spektralne, w szczególności Lemat 15.1. Niech \chi=\sqrt{\chi^{2}}.

Stwierdzenie 15.1 (Diaconis i Strook)

Jeśli łańcuch odwracalny, nieprzywiedlny i nieokresowy ma rozkład początkowy \xi, to

\chi(\pi,P^{{n}}\xi)\leq\lambda^{{n}}\chi(\pi,\xi).
Dowód

Zastosujmy Lemat 15.1 do wektora \Pi^{{-1}}(\xi-\pi) który, jak łatwo zauważyć, jest prostopadły do 1. Otrzymujemy

\chi(\pi,P^{{n}}\xi)=\| P^{n}\Pi^{{-1}}(\xi-\pi){\| _{{\pi}}}\leq\lambda^{n}\|\Pi^{{-1}}(\xi-\pi){\| _{{\pi}}}=\lambda^{{n}}\chi(\pi,\xi).
Wniosek 15.1

Dla łańcucha o rozkładzie początkowym skupionym w punkcie x,

\chi(\pi,P^{{n}}(x,\cdot))\leq\lambda^{{n}}\sqrt{\frac{1-\pi(x)}{\pi(x)}}\leq\frac{\lambda^{{n}}}{\sqrt{\pi(x)}}.

Istotnie, mamy jeszcze jedno wyrażenie na ,,odległość” \chi^{2}: dla dowolnego rozkładu \xi,

\chi^{{2}}(\pi,\xi)=\xi^{\top}\Pi^{{-1}}\xi-1.

Wystarczy teraz podstawić \xi(y)=\mathbb{I}(y=x), aby otrzymać \chi^{{2}}=1/\pi(x)-1.

15.1.2. Oszacowanie normy pełnego wahania

Istnieje prosta nierówność pomiędzy normą pełnego wahania i ,,odległością” \chi^{2}:

\|\ \xi-\pi\ \| _{{\rm tv}}=\frac{1}{2}\sum _{{x}}\ |\ \xi(x)-\pi(x)\ |\leq\frac{1}{2}\ \chi(\pi,\xi).

Wynika to z następującego rachunku:

\begin{split} 4\ \|\ \xi-\pi\ \| _{{\rm tv}}^{{2}}&=\ \left(\sum _{{x}}\ \frac{|\ \xi(x)-\pi(x)\ |}{\sqrt{\pi(x)}}\ \sqrt{\pi(x)}\right)^{{2}}\\
&\leq\ \sum _{{x}}\ \frac{(\ \xi(x)-\pi(x)\ )^{{2}}}{\pi(x)}\ \sum _{{x}}\pi(x)\qquad\text{[\  Cauchy-Schwarz\ ]}\\
&=\ \chi^{{2}}(\pi,\xi).\end{split}

Stąd natychmiast otrzymujemy wniosek

\|\  P_{{n}}(x,\cdot)-\pi\ \| _{{\rm tv}}\leq\frac{1}{2}\ \lambda^{{n}}\ \sqrt{\frac{1-\pi(x)}{\pi(x)}}\leq\frac{\lambda^{{n}}}{2\sqrt{\pi(x)}}.

15.1.3. Oszacowanie obciążenia estymatora

Rozważmy zadanie obliczania wartości oczekiwanej \theta=\mathbb{E}_{\pi}f=\pi^{\top}f dla pewnej funkcji f. Niech \bar{f}=f-1\pi^{\top}f oznacza ,,scentrowaną” funkcję f. Natychmiast widać, że \bar{f}\perp 1 i możemy zastosować Lemat 15.1. Stąd już tylko mały krok do oszacowania różnicy między wartością oczekiwaną \mathbb{E}_{\xi}f(X_{n})=\xi^{\top}P^{n}f i wartością stacjonarną \theta.

Stwierdzenie 15.2

Jeśli łańcuch jest odwracalny, nieprzywiedlny, nieokresowy i ma rozkład początkowy \xi, to

|\ \mathbb{E}_{\xi}f(X_{n})-\theta\ |\leq\lambda^{{n}}\chi(\pi,\xi)\sigma(f),

gdzie \sigma^{2}(f)=\|\bar{f}\| _{\pi}^{2} jest wariancją stacjonarną funkcji f.

Dowód

Mamy

\begin{split}|\ \mathbb{E}_{\xi}f(X_{n})-\theta\ |&=|\ (\xi^{\top}-\pi^{\top})P^{{n}}f\ |=|\ (\xi^{\top}-\pi^{\top})P^{{n}}\bar{f}\ |\\
&=|\ {\langle}\Pi^{{-1}}(\xi-\pi),P^{{n}}\bar{f}{\rangle _{\pi}}\ |\\
&\leq\|\ {\langle}\Pi^{{-1}}(\xi-\pi){\| _{{\pi}}}\ \| P^{{n}}\bar{f}{\| _{{\pi}}}\qquad\text{[\  Cauchy-Schwarz\ ]}\\
&\leq\chi(\pi,\xi)\lambda^{n}\|\bar{f}{\| _{{\pi}}}\qquad\qquad\text{[\  Lemat \ref{lem: kontr}\ ]}.\end{split}

Rozważmy teraz naturalny estymator

\hat{\theta}_{{t,n}}={1\over n}\sum _{{i=t}}^{{t+n-1}}f(X_{i}).

Jest to średnia wzdłuż trajektorii łańcucha, dlugości n i ,,opóźniona” o t. Idea jest jasna: ignorujemy początkowy odcinek trajektorii długości t (tak zwany okres burn-in) aby dać łańcuchowi czas na zbliżenie od rozkładu stacjonarnego. Później obliczmy średnią. W ten sposób redukujemy obciążenie. Precyzuje to następujący wniosek.

Wniosek 15.2

Dla dowolnego n mamy

|\ \mathbb{E}_{\xi}\hat{\theta}_{{t,n}}-\theta\ |\leq\frac{\lambda^{{t}}}{1-\lambda}\chi(\pi,\xi)\sigma(f).

Wynika to z nierówności trójkąta i wzoru na sumę szeregu geometrycznego:

|\ \mathbb{E}_{\xi}\hat{\theta}_{{t,n}}-\theta\ |\leq\sum _{{i=t}}^{{t+n-1}}|\ \mathbb{E}_{\xi}f(X_{i})-\theta\ |\leq\sum _{{i=t}}^{{\infty}}\lambda^{{i}}\chi(\pi,\xi)\sigma(f).

Zwróćmy uwagę, że obciążenie maleje w tempie geometrycznym przy t\to\infty ale zachowuje sią zaledwie jak O(1/n) przy ustalonym t i n\to\infty (ponieważ początkowe wyrazy sumy mają na obciążenie wpływ dominujący).

15.2. Oszacowanie błędu średniokwadratowego estymatora

Oszacowanie błędu średniokwadratowego (BŚK) estymatora MCMC jest znaczne trudniejsze i subtelniejsze, niż obciążenia.

15.2.1. Asymptotyczna wariancja

Zacznijmy od wyprowadzenia kolejnego wzoru na asymptotyczną wariancję. Przypomnijmy, że zgodnie ze Stwierdzeniem 14.1,

{\sigma _{{\rm as}}^{{2}}(f)}=f^{\top}{C}f,

gdzie

\begin{split} C&=\Pi(2Z-I-{1}\pi^{\top})=2\Pi Z-\Pi-\pi\pi^{\top}\\
&=\Pi(2A-I+{1}\pi^{\top})=2\Pi A-\Pi+\pi\pi^{\top}.\\
\end{split}

Skorzystajmy z reprezentacji spektralnej macierzy P:

P-{1}\pi^{\top}=\sum _{{i\geq 1}}\lambda _{{i}}v_{{i}}v_{{i}}^{\top}\Pi=V\left(\begin{array}[]{c|ccc}0&&\cdots&0\\
\cline{1-4}&\lambda _{{1}}&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&\lambda _{{d-1}}\end{array}\right).V^{\top}\Pi

Z definicji macierzy A i wzoru (15.1), ponieważ \sum _{{n=0}}^{\infty}\lambda _{i}^{n}=1/(1-\lambda _{i}), więc

A=\sum _{{n=0}}^{{\infty}}(P^{{n}}-{1}\pi^{\top})=V\left(\begin{array}[]{c|ccc}0&&\cdots&0\\
\cline{1-4}&\ddots&\cdots&\\
\vdots&\vdots&{1}/(1-\lambda _{{i}})&\vdots\\
0&&\cdots&\ddots\end{array}\right)V^{\top}\Pi.

Wreszcie, ponieważ 2/(1-\lambda _{i})-1=(1+\lambda _{i})/(1-\lambda _{i}), więc

\Pi(2A-1+1\pi^{\top})=\Pi V\left(\begin{array}[]{c|ccc}0&&\cdots&0\\
\cline{1-4}&\ddots&\cdots&\\
\vdots&\vdots&(1+\lambda _{i})/(1-\lambda _{i})&\vdots\\
0&&\cdots&\ddots\end{array}\right)V^{\top}\Pi.

Zauważmy teraz, że wektor \alpha=V^{\top}\Pi f zawiera współrzędne wektora f w bazie ON złożonej z prawych wektorów własnych: \alpha _{{i}}=v_{{i}}^{\top}\Pi f=\langle\  v_{{i}},\  f\ \rangle _{{\pi}}. Udowodniliśmy w ten sposób następujący fakt.

Stwierdzenie 15.3

Dla łańcucha odwracalnego, wzór na asymptotyczną wariancję przybiera postać

{\sigma _{{\rm as}}^{{2}}(f)}=\sum _{{i\geq 1}}\ \alpha _{{i}}^{{2}}\ \frac{1+\lambda _{{i}}}{1-\lambda _{{i}}},

gdzie \alpha _{{i}}=v_{{i}}^{\top}\Pi f=\langle\  v_{{i}},\  f\ \rangle _{{\pi}}.

Wynika stąd ważna nierówność.

Wniosek 15.3

Dla łańcucha odwracalnego mamy następujące oszacowanie asymptotycznej wariancji:

{\sigma _{{\rm as}}^{{2}}(f)}\leq\frac{1+\lambda _{{1}}}{1-\lambda _{{1}}}\sigma^{2}(f)

gdzie \lambda _{1} jest największą wartością własną mniejszą od 1, a \sigma^{2}(f) jest wariancją stacjonarną.

Istotnie,

{\sigma _{{\rm as}}^{{2}}(f)}\leq\sum _{{i\geq 1}}\ \alpha _{{i}}^{{2}}\ \frac{1+\lambda _{{i}}}{1-\lambda _{{i}}}\leq\frac{1+\lambda _{{1}}}{1-\lambda _{{1}}}\sum _{{i\geq 1}}\ \alpha _{{i}}^{{2}},

a łatwo widzieć, że \sum _{{i\geq 1}}\ \alpha _{{i}}^{{2}}=\|\bar{f}\| _{\pi}^{2}=\sigma^{2}(f). Zwróćmy uwagę, że we Wniosku 15.3 występuje \lambda _{1}, a nie \lambda=\max(\lambda _{{1}},|\lambda _{{d-1}}|) (największa co do modułu wartość własna mniejsza od 1).

Na zakończenie przytoczę jeszcze kilka sugestywnych wzorów.

Uwaga 15.1

Macierz L=I-P jest nazywana laplasjanem. Zauważmy, że

L=\sum _{{i\geq 1}}(1-\lambda _{{i}})\  v_{{i}}v_{{i}}^{\top}\Pi.

Ponieważ

A=\sum _{{i\geq 1}}\frac{1}{1-\lambda _{{i}}}\  v_{{i}}v_{{i}}^{\top}\Pi,

uzasadnia to interpretację macierzy A jako ,,uogólnionej odwrotności” laplasjanu.

Dorzućmy przy okazji jeszcze jedno wyrażenie na asymptotyczną wariancję:

\begin{split}{\sigma _{{\rm as}}^{{2}}(f)}&=\langle\  f,\ (2A-\mathbb{I}+{\bf{1}}\pi^{{T}})f\ \rangle _{{\pi}}=\langle\  f,\  Af\ \rangle _{{\pi}}+\langle\  Af,\  f\ \rangle _{{\pi}}-\sigma^{{2}}(f).\\
\end{split}

Jeśli \pi^{\top}f=0, to \sigma^{{2}}(f)={\rm Var}_{{\pi}}f=\langle\  f,f\ \rangle _{{\pi}} i ostatni wzór możemy przepisać w postaci

{\sigma _{{\rm as}}^{{2}}(f)}=\sigma^{{2}}(f)\left(2\frac{\langle\  f,\  Af\ \rangle _{{\pi}}}{\langle\  f,\  f\ \rangle _{{\pi}}}-1\right)

15.2.2. Oszacowanie BŚK

Wyniki w tym podrozdziale zostały otrzymane przez Aldousa [1]. Pomysł polega na tym, żeby najpierw otrzymać nierówność dla łańcucha stacjonarnego, a potem postarać się o uogólnienie dla łańcucha o dowolnym rozkładzie początkowym. Przypomnijmy oznaczenia \theta=\mathbb{E}_{\pi}f, {\hat{\theta}_{{n}}}=\sum _{{i=0}}^{{n-1}}f(X_{{i}}).

Stwierdzenie 15.4 (Aldous, 1987)

Dla dla łańcucha nieprzywiedlnego, odwracalnego i stacjonarnego, {\rm MSE}_{\pi} można oszacować w następujący sposób:

\mathbb{E}_{{\pi}}({\hat{\theta}_{{n}}}-\theta)^{{2}}\leq\frac{1+\tilde{\lambda}}{1-\tilde{\lambda}}\sigma^{2}(f)

gdzie \tilde{\lambda}=\max(\lambda _{1},0), zaś \lambda _{1} jest największą wartością własną mniejszą od 1.

Dowód

Korzystamy ze stacjonarności i z rozkładu spektralnego macierzy P.

\begin{split}\mathbb{E}_{{\pi}}({\hat{\theta}_{{n}}}-\theta)^{{2}}&=\mathbb{E}_{{\pi}}\left(\frac{1}{n}\sum _{{i=0}}^{{n-1}}\bar{f}(X_{i})\right)^{2}\\
&=\frac{1}{n^{2}}\sum _{{i=0}}^{{n-1}}\mathbb{E}_{{\pi}}\bar{f}(X_{i})^{2}+\frac{2}{n^{2}}\sum _{{i=0}}^{{n-1}}\sum _{{j=i+1}}^{{n-1}}\mathbb{E}_{{\pi}}\bar{f}(X_{i})\bar{f}(X_{j})\\
&=\frac{1}{n}\mathbb{E}_{{\pi}}\bar{f}(X_{0})^{2}+\frac{2}{n^{2}}\sum _{{k=1}}^{{n-1}}(n-k)\mathbb{E}_{{\pi}}\bar{f}(X_{0})\bar{f}(X_{k})\qquad[k=j-i]\\
&=\frac{1}{n}{\langle}\bar{f},\bar{f}{\rangle _{\pi}}+\frac{2}{n^{2}}\sum _{{k=1}}^{{n-1}}(n-k){\langle}\bar{f},P^{k}\bar{f}{\rangle _{\pi}}\\
&=\frac{1}{n}{\langle}\bar{f},\bar{f}{\rangle _{\pi}}+\frac{2}{n^{2}}\sum _{{k=1}}^{{n-1}}(n-k)\sum _{{i\geq 1}}\tilde{\lambda}_{i}^{k}{\langle}v_{i},f{\rangle _{\pi}}^{2}\\
&=\frac{1}{n}{\langle}\bar{f},\bar{f}{\rangle _{\pi}}+\frac{2}{n^{2}}\sum _{{i\geq 1}}{\langle}v_{i},f{\rangle}_{\pi}^{2}\sum _{{k=1}}^{{n-1}}(n-k)\lambda _{i}^{k}\\
&\leq\frac{1}{n}\sigma^{2}(f)+\frac{2}{n^{2}}\sum _{{\substack{i\geq 1\\
\lambda _{i}>0}}}{\langle}v_{i},f{\rangle}_{\pi}^{2}\sum _{{k=1}}^{{n-1}}(n-k)\lambda _{i}^{k}\qquad[\text{pomijamy składniki dla }\lambda _{i}<0]\\
&\leq\frac{1}{n}\sigma^{2}(f)+\frac{2}{n^{2}}\sigma^{2}(f)\sum _{{k=1}}^{{n-1}}(n-k)\tilde{\lambda}^{k}\\
&\leq\frac{1}{n}\sigma^{2}(f)+\frac{2}{n}\sigma^{2}(f)\sum _{{k=1}}^{{n-1}}\tilde{\lambda}^{k}\\
&\leq\frac{2}{n}\sigma^{2}(f)\left(1+\frac{2\tilde{\lambda}}{1-\tilde{\lambda}}\right)=\frac{1}{n}\sigma^{2}(f)\frac{1+\tilde{\lambda}}{1-\tilde{\lambda}}.\\
\end{split}

Zwróćmy uwagę na miejsce, w którym pomijamy składniki odpowiadające ujemnym wartościom własnym. Uzasadnienie jest takie, że dla , \lambda _{i}<0, składniki sumy \sum _{{k=1}}^{{n-1}}(n-k)\lambda _{i}^{k} są naprzemian ujemne i dodatnie, o malejących wartościach bezwzględnych. Stąd wynika, że \sum _{{k=1}}^{{n-1}}(n-k)\lambda _{i}^{k}<0 i można tę sumę w nierówności opuścić. Jest to ciekawe zjawisko: ujemne wartości własne pomagają, zmniejszają błąd! Działają podobnie jak zmienne antytetyczne.

Niech teraz E(x) oznacza błąd średniokwadratowy dla łańcucha startującego z punktu x\in{\cal X},

e_{n}(x)=\mathbb{E}_{{x}}({\hat{\theta}_{{n}}}-\theta)^{{2}}.

Rozpatrzmy łańcuch o rozkładzie początkowym \xi. Niech

\hat{\theta}_{{t,n}}={1\over n}\sum _{{i=t}}^{{t+n-1}}f(X_{i}).

będzie średnią długości n obliczany po odrzuceniu t początkowych zmiennych.

Stwierdzenie 15.5

Dla dla łańcucha nieprzywiedlnego, odwracalnego startującego z dowolnego rozkładu \xi, {\rm MSE}_{\xi} można oszacować w następujący sposób:

\mathbb{E}_{{\xi}}(\hat{\theta}_{{t,n}}-\theta)^{{2}}\leq\frac{1+\tilde{\lambda}}{1-\tilde{\lambda}}\sigma^{2}(f)+\lambda^{t}\chi(\pi,\xi)\max _{x}|\bar{f}(x)|^{2}

gdzie \tilde{\lambda}=\max(\lambda _{1},0) i \lambda=\max(\lambda _{1},|\lambda _{{d-1}}|).

Dowód

Na mocy Stwierdzeń 15.4 i 15.2 mamy

\begin{split}\mathbb{E}_{{\xi}}(\hat{\theta}_{{t,n}}-\theta)^{{2}}&=\mathbb{E}_{\xi}e_{n}(X_{t})\leq\mathbb{E}_{\pi}e_{n}+|\mathbb{E}_{\xi}e_{n}(X_{t})-\mathbb{E}_{\pi}e_{n}|\\
&\leq\frac{1}{n}\sigma^{2}(f)\frac{1+\tilde{\lambda}}{1-\tilde{\lambda}}+\lambda^{t}\chi(\pi,\xi)\sigma(e_{n})\\
&\leq\frac{1}{n}\sigma^{2}(f)\frac{1+\tilde{\lambda}}{1-\tilde{\lambda}}+\lambda^{t}\chi(\pi,\xi)\max _{x}|\bar{f}(x)|^{2},\end{split}

bo e_{n}(y)\leq\max _{x}|\bar{f}(x)|^{2}, a więc \sigma(e_{n})\leq\max _{x}|\bar{f}(x)|^{2}.

Nierówność podane przez Aldousa w cytowanej pracy była nieco inna.

Stwierdzenie 15.6 (Aldous, 1987)

Dla dla łańcucha nieprzywiedlnego, odwracalnego startującego z dowolnego rozkładu \xi mamy następujące oszacowanie błędu {MSE_{\xi}}:

\mathbb{E}_{{\xi}}(\hat{\theta}_{{t,n}}-\theta)^{{2}}\leq\left(1+\frac{\lambda^{t}}{\pi _{*}}\right)\frac{1+\tilde{\lambda}}{1-\tilde{\lambda}}\sigma^{2}(f),

gdzie \pi^{*}=\min _{x}\pi(x).

Dowód

Istotnie, załóżmy, że łańcuch startuje z deterministycznie wybranego punktu x\in{\cal X}, czyli \xi=P(x,\cdot). Jeśli otrzymamy oszacowanie niezależne od x, dowód będzie zakończony.

\begin{split}\mathbb{E}_{{x}}(\hat{\theta}_{{t,n}}-\theta)^{{2}}&=\sum _{y}P^{t}(x,y)e_{n}(y)\\
&=\sum _{y}P^{t}(x,y)e_{n}(y)=\sum _{y}\frac{P^{t}(x,y)}{\pi(y)}\pi(y)e_{n}(y)\\
&\leq\left(1+\frac{\lambda^{t}}{\pi _{*}}\right)\sum _{y}\pi(y)e_{n}(y)=\left(1+\frac{\lambda^{t}}{\pi _{*}}\right){{\rm MSE}_{\pi}}.\end{split}

i zastosujmy Stwierdzenie 15.4. Wykorzystaliśmy tu nierówność P^{t}(x,y)/\pi(y)\leq 1+\lambda^{t}/\pi _{*}, która wynika z rozkładu spektralnego:

\begin{split}\frac{P^{t}(x,y)}{\pi(y)}&=P^{t}\Pi^{{-1}}(x,y)=1_{x}^{\top}P^{t}\Pi^{{-1}}1_{y}\\
&=1_{x}^{\top}\sum _{{i=0}}^{{d-1}}\lambda _{i}^{t}v_{i}v_{i}^{\top}1_{y}=1+1_{x}^{\top}\sum _{{i=1}}^{{d-1}}\lambda _{i}^{t}v_{i}v_{i}^{\top}1_{y}\\
&\leq 1+\lambda^{t}\sum _{{i=1}}^{{d-1}}|1_{x}^{\top}v_{i}v_{i}^{\top}1_{y}|\\
&\leq 1+\lambda^{t}\sqrt{\sum _{{i=1}}^{{d-1}}(1_{x}^{\top}v_{i})^{2}}\sqrt{\sum _{{i=1}}^{{d-1}}(v_{i}1_{y}^{\top})^{2}}\\
&\leq 1+\frac{\lambda^{t}}{\sqrt{\pi(x)}\sqrt{\pi(y)}}\leq 1+\frac{\lambda^{t}}{\pi _{*}}.\end{split}

W powyższym wzorze symbol 1_{x}^{\top} oznacza wektor (0,\ldots,0,1,0,\ldots,0), gdzie jedynka stoi na x-tym miejscu. Skorzystaliśmy z nierówności Schwarza.

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.