Zagadnienia

15.1 Reprezentacja spektralna macierzy odwracalnej
15.2 Oszacowanie błędu średniokwadratowego estymatora
- 15.2.1 Asymptotyczna wariancja
- 15.2.2 Oszacowanie BŚK

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.

Symulacje stochastyczne i metody Monte Carlo

Zagadnienia

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

15.1. Reprezentacja spektralna macierzy odwracalnej

Lemat 15.1

Dowód

15.1.1. Oszacowanie szybkości zbieżności

Stwierdzenie 15.1 (Diaconis i Strook)

Dowód

Wniosek 15.1

15.1.2. Oszacowanie normy pełnego wahania

15.1.3. Oszacowanie obciążenia estymatora

Stwierdzenie 15.2

Dowód

Wniosek 15.2

15.2. Oszacowanie błędu średniokwadratowego estymatora

15.2.1. Asymptotyczna wariancja

Stwierdzenie 15.3

Wniosek 15.3

Uwaga 15.1

15.2.2. Oszacowanie BŚK

Stwierdzenie 15.4 (Aldous, 1987)

Dowód

Stwierdzenie 15.5

Dowód

Stwierdzenie 15.6 (Aldous, 1987)

Dowód