21 Zastosowania MPWL

21.1 Metoda Monte Carlo

Jednym z twórców tej metody był Stanisław Ulam. Problem jest następujący. Chcemy obliczyć całkę $\int_0^1 f(x)dx$, ale jest to trudne, np. nie potrafimy znaleźć funkcji pierwotnej.

Niech $X_i$ będą niezależnymi zmiennymi losowymi o wartościach w $(0,1)$ i rozkładzie z zadaną gęstością $g$ (można przyjąć $g=1$). Wówczas z MPWL \[ S_n:= \frac 1n\sum_{i=1}^n \frac {f(X_i)}{g(X_i)} \to \mathbb{E} \frac{f(X_1)}{g(X_1)} = \int_0^1 \frac{f(x)}{g(x)}\; g(x)dx = \int_0^1 f(x)dx. \] Dla przykładu, jeżeli $g=1$, to możemy wygenerować ciąg niezależnych zmiennych losowych o rozkładzie jednostajnym na odcinku $(0,1)$ i obliczyć $S_n$ dla dużej wartości $n$ aproksymując w ten sposób wartość całki.

W praktyce warto używać funkcji $g$, ponieważ dobierając ją do kształtu funkcji $f$ można przyśpieszyć zbieżność. W jednym wymiarze metody numeryczne są efektywniejsze (chyba, że funkcja $f$ jest nieregularna). Jednak w wyższych wymiarach metoda Monte Carlo jest skuteczniejsza, gdyż tempo zbieżności zawsze jest rzędu $c/\sqrt n$ (to wynika z kolei z Centralnego Twierdzenia Granicznego), podczas gdy metody numeryczne w wyższych wymiarach są wolniejsze.

Przykład 21.1 Chcemy poznać przybliżoną wartość całki \[\begin{equation*} \int_{-1}^1 e^{-x^2} \mathrm{d}x. \end{equation*}\] W tym celu rozważmy ciąg $\{U_{n}\}_{n \in \mathbb{N}}$ niezależnych zmiennych losowych o rozkładzie jednostajnym na przedziale $[-1,1]$. Wówczas \[\begin{equation*} \mathbb{E} \left[ e^{-U_1^2} \right] = \frac 12\int_{-1}^1 e^{-x^2} \mathrm{d}x. \end{equation*}\] Z mocnego prawa wielkich liczb \[\begin{equation*} \frac 2n \sum_{j=1}^n e^{-U_j^2} \to \int_{-1}^1 e^{-x^2} \mathrm{d}x. \end{equation*}\]

# Ustawienie liczby prób
n <- 10000

# Wygenerowanie n losowych wartości z rozkładu jednostajnego na [-1, 1]
U <- runif(n, min = -1, max = 1)

# Obliczenie wartości funkcji e^(-x^2) dla każdej wartości U
f_values <- exp(-U^2)

# Średnia z tych wartości to przybliżenie całki
# Mnożymy przez długość przedziału (2)
monte_carlo_estimate <- mean(f_values) * 2  

# Wynik
cat('Przybliżona wartość całki:', monte_carlo_estimate)

Przybliżona wartość całki: 1.494209

# Dla porównania: dokładna wartość (przybliżona numerycznie)
exact_value <- integrate(function(x) exp(-x^2), -1, 1)$value
cat("Dokładna wartość całki:", exact_value, "\n")

Dokładna wartość całki: 1.493648

Przykład 21.2 (Igła Buffona) Igłę o długości $l$ rzucamy na podłogę z desek o szerokości $a$ ($l\le a$). Wiemy, że o, przecięcia przez igłę krawędzi deski wynosi $p = \frac{2l}{a\pi}$. Tej formuły użyto do wyznaczenia liczby $\pi$. Mianowicie wykonujemy $n$ rzutów igłą dla bardzo dużego $n$ i definiujemy ciąg zmiennych losowych \[ X_i = \left\{ \begin{array}{cc} 1 & \mbox{ jeżeli w $i$-tym rzucie igła przetnie krawędź} \\ 0 & \mbox{w przeciwnym razie.} \end{array} \right. \] Wówczas zmienne losowe $X_i$ są niezależne i mają ten sam rozkład. Ponadto $\mathbb{E} X_i = \mathbb{P}[X_i=1] = p$. Z~MPWL mamy \[ \frac kn = \frac{\mbox{liczba trafień w krawędź}}{n} = \frac{X_1+\ldots+X_n}{n} \to \mathbb{E} X_1 = p = \frac{2l}{a\pi}, \] a stąd wynika, że \[ \pi \approx \frac {2l}{a} \cdot \frac nk \] W 1901 Mario Lazzarini wykonał 3408 rzutów i otrzymał \[ \pi \approx \frac{355}{113} = 3,141592{\bf 9203}. \] Przypomnijmy $\pi = 3,141592{\bf 65359}$.

Przykład 21.3 Rozważmy następujące zadanie: oblicz \[ \lim_{n\to\infty} \int_0^1\ldots \int_0^1 \frac{x_1^3+\ldots+ x_n^3}{x_1+\ldots+ x_n}dx_1\ldots dx_n. \] Powyższą granicę można obliczyć przy pomocy MPWL. Niech $\{X_n\}$ będzie ciągiem niezależnych zmiennych losowych o rozkładzie $U(0,1)$. Wówczas \[ \int_0^1\ldots \int_0^1 \frac{x_1^3+\ldots+ x_n^3}{x_1+\ldots+ x_n}dx_1\ldots dx_n = \mathbb{E} \bigg[\frac{X_1^3+\ldots+ X_n^3}{X_1+\ldots+ X_n}\bigg]. \] Z MPWL \[ \frac{X_1^3+\ldots+ X_n^3}{X_1+\ldots+ X_n} = \frac{\frac{X_1^3+\ldots+ X_n^3}n}{\frac{X_1+\ldots+ X_n}n} \to \frac{\mathbb{E} X_1^3}{\mathbb{E} X_1} = \frac 12. \] Podsumowując: \[\begin{multline*} \lim_{n\to\infty} \int_0^1\ldots \int_0^1 \frac{x_1^3+\ldots+ x_n^3}{x_1+\ldots+ x_n}dx_1\ldots dx_n \\ = \lim_{n\to\infty} \mathbb{E} \bigg[\frac{X_1^3+\ldots+ X_n^3}{X_1+\ldots+ X_n}\bigg] \overset{{\mbox{tw. Leb.}}}{=} \mathbb{E} \bigg[\lim_{n\to\infty} \frac{X_1^3+\ldots+ X_n^3}{X_1+\ldots+ X_n}\bigg] = \frac 12. \end{multline*}\] Powyżej skorzystaliśmy z twierdzenia Lebesgue’a o zbieżności zdominowanej. Zauważmy, że mogliśmy to zrobić, gdyż funkcja podcałkowa jest mniejsza od 1.

21.2 Dystrybuanta empiryczna

Powtarzamy wielokrotnie pewne doświadczenie o nieznanym rozkładzie. Na podstawie otrzymanych wyników $X_1,\ldots, X_n$ chcemy wyznaczyć ich dystrybuantę $F$. W tym celu definiujemy \[F_n(x) = \frac 1n \sum_{i=1}^n {\bf 1}_{\{X_n\le x\}}.\] Powyższa funkcja $F_n(x) = F_n(x,\omega)$ nazywa się dystrybuantą empiryczną. Zauważmy, że jest to naturalna definicja, dla danego $x$ zliczamy liczbę próbek mniejszych niż $x$ i uśredniamy wynik. Poniższe twierdzenie jest jednym z podstawowych wyników używanych w statystyce:

Twierdzenie 21.1 (Gliwienko - Cantelli) Zachodzi \[ \sup_{x\in \mathbb{R}} |F_n(x) - F(x)| \to 0,\qquad \mbox{p.n.} \]

Dowód twierdzenia pominiemy, zauważmy jednak, że dla zmiennej losowej $Y_k = {\bf 1}_{\{X_n\le x\}}$ zachodzi \[\mathbb{E} Y_k = \mathbb{P}[X_k \le x] = F(x),\] a z MPWL \[ F_n(x) = \frac 1n \sum_{k=1}^{n} {\bf 1}_{\{ X_k \le x\}} = \frac{Y_1+\ldots + Y_n}{n} \to \mathbb{E} Y_1 = F(x) \quad \mbox{p.n.} \]

21.3 Liczby normalne

Liczbę $a\in [0,1]$ nazywamy normalną przy podstawie $d$ ($d\in\{2,3,\ldots \}$), jeżeli ma ona przedstawienie \[ a = \sum_{n=1}^{\infty} \frac{\varepsilon_n}{d^n}, \] dla $\varepsilon_n\in\{0,1,\ldots,d-1\}$ takie, że \[ \frac{\# \{i: \varepsilon_i = k, \ i\le n \}}{n} \to \frac 1d \] dla każdego $k\in \{0,1,\ldots, d-1\}$.

Dosyć łatwo jest wskazać liczby normalne o ustalonej podstawie $d$ (pozostawiamy to jako zadanie). Jednak wskazanie liczby (obliczalnej), która jest normalna przy każdej podstawie $d$ jest problemem otwartym. Tymczasem okazuje się, że prawie każda liczba ma tę własność:

Twierdzenie 21.2 (Borel) Prawie wszystkie liczby (względem miary Lebesgue’a) z przedziału $[0,1]$ są normalne względem każdej podstawy.

Proof. Niech \[\begin{align*} A_d & = \big\{ x\in[0,1]: x \mbox{ jest normalna przy podstawie $d$}\big\},\\ A & = \bigcap_{d=2}^{\infty} A_d = \big\{ x\in[0,1]: x \mbox{ jest normalna przy każdej podstawie $d$}\big\}. \end{align*}\] Rozważmy przestrzeń probabilistyczną $([0,1], \mathcal{B}or([0,1]), {\rm Leb})$.
Wystarczy pokazać, że dla każdego $d$, $\mathbb{P}[A_d]=1$. Ustalmy $d$. Każdą liczbę $x\in[0,1]$ można zapisać w postaci \[ x = \sum_{n=1}^{\infty} \frac{\varepsilon_n(x)}{d^n}, \] dla $\varepsilon_n(x)\in\{0,1,\ldots,d-1\}$. Wtedy $\varepsilon_n(x)$ jest ciągiem niezależnych zmiennych losowych o rozkładzie jednostajnym na $\{ 0,1,\ldots,d-1 \}$ (zadanie!). Ustalmy $k\in\{0,1,\ldots d-1\}$. Niech \[X_n(x) = \left\{ \begin{array}{cc} 1, & \mbox{ jeżeli } \varepsilon_n(x)=k \\ 0, & \mbox{w przeciwnym razie.} \end{array} \right. \] Wówczas $\mathbb{E}[X_n] =\mathbb{P}[X_n=1] = 1/d$ i z MPWL \[ \frac{\{ i\le n:\; \varepsilon_i(x) = k \}}{n} = \frac{X_1+\ldots + X_n}{n} \to \mathbb{E} X_1 = \frac 1d\qquad\mbox{p.n.} \] a zatem $\mathbb{P}[A_d]=1$ oraz $\mathbb{P}[A]=1$.

21.4 Wokół MPWL

Twierdzenie 21.3 Jeżeli $X_n$ jest ciągiem niezależnych zmiennych losowych o takim samym rozkładzie oraz istnieje stała $c$ taka, że \[ \mathbb{P}\bigg[ \lim_n \frac{X_1+\ldots+X_n}{n} = c \bigg] >0, \] to $\mathbb{E}|X_1|<\infty$ oraz $c=\mathbb{E} X_1$.

Proof. Z prawa 0-1 Kołmogorowa \[ \mathbb{P}\bigg[ \lim_n \frac{X_1+\ldots+X_n}{n} = c \bigg] = 1, \] a stąd \[ \frac{X_n}{n} = \frac{S_n}n - \frac{S_{n-1}}{n-1}\cdot \frac{n-1}{n} \to 0 \qquad \mbox{p.n.} \] Zatem z em 1 zajdzie jedynie skończenie wiele zdarzeń $\{|X_n| > n\}$. Lemat Borela-Cantelliego implikuje więc \[ \sum_{n=1}^\infty \mathbb{P}[|X_1|>n] = \sum_{n=1}^\infty \mathbb{P}[|X_n|>n] <\infty, \] a stąd wynika, że \[\mathbb{E} |X_1| \le \sum_{n=1}^\infty \mathbb{P}[|X_1|>n] <\infty.\] Z MPWL wynika więc \[ \frac{X_1+\ldots+ X_n}{n} \to \mathbb{E} X_1\qquad \mbox{p.n.} \]

Twierdzenie 21.4 (MPWL, Etemadi) Niech $\{X_n\}$ będzie ciągiem zmiennych losowych, które są parami niezależne i mają jednakowy rozkład. Jeżeli $\mathbb{E}|X_1|<\infty$, to \[ \frac{X_1+\ldots+ X_n}{n} \to \mathbb{E} X_1\qquad \mbox{p.n.} \]

Dla $c>0$ niech $X^{(c)}$ oznacza obcięcie zmiennej losowej $X$: \[ X^{(c)} = \left\{ \begin{array}{cc} X & \mbox{ dla } |X|\le c \\ 0 & \mbox{ dla } |X|>c \end{array} \right. \]

Twierdzenie 21.5 (Twierdzenie Kołmogorowa o 3 szeregach) Ustalmy $c>0$. Szereg $\sum_n X_n$ niezależnych zmiennych losowych jest zbieżny p.n. wtedy i tylko, gdy następujące 3 szeregi \[ \sum_{n=1}^\infty \mathbb{E} X_n^{(c)}, \quad \sum_{n=1}^{\infty} \mathbb{V}ar\left X_n^{(c)}\right], \quad \sum_{n=1}^{\infty} \mathbb{P}[|X_n|>c] \] są zbieżne.

Remark. Jeżeli powyższe twierdzenie zachodzi dla pewnego $c_0$, to zachodzi również dla każdej innej wartości $c>0$.

Proof. Załóżmy, że wszystkie $3$ powyższe szeregi są zbieżne. Wtedy z twierdzenie Kołmogorowa o 2 szeregach szereg $\sum_n {X_n^{(c)}}$ jest zbieżny p.n. Z warunku $\sum_{n=1}^{\infty} \mathbb{P}[|X_n|>c]<\infty$ i lematu Borela-Cantellego otrzymujemy \[ \mathbb{P}\big[ |X_n| >c \ \mbox{i.o}\big] = 0. \] Zatem $|X_n|>c$ tylko skończenie wiele razy, a więc dla dostatecznie dużych indeksów $X_n = X_n^{(c)}$. Zatem $\sum X_n<\infty$ p.n.

Dowód odwrotnej implikacji pomijamy.

20 Mocne prawo wielkich liczb

22 Dygresja: kompresja