5 Lemat Borela-Cantellego
Nieskończone ciągi eksperymentów
W przyszłości chcemy analizować asymptotyczne zachowanie procesów losowych. W naturalny sposób potrzeba konstrukcji przestrzeni probabilistycznej, na której można wykonać nieskończenie wiele eksperymentów które mogą, ale nie muszą być niezależne. Dla ustalenia uwagi skupimy się jednak na niezależnych eksperymentach. Zakładać będziemy, że mamy ciąg przestrzeni probabilistycznych, w którym \((\Omega_n, \mathcal{F}_n, \mathbb{P}_n)\) opisuje wynik \(n\)-tego eksperymentu. Zakładać będziemy, że \[\begin{equation} \Omega_n \subseteq \mathbb{R}, \quad \mathcal{F}_n \subseteq \mathcal{B}or(\mathbb{R}). \tag{5.1} \end{equation}\] Chcemy udzielić odpowiedzi na pytanie jak skonstruować przestrzeń, na której wszystkie te eksperymenty wykonywane są niezależnie?
Powiedzmy, że interesuje nas nieskończony ciąg rzutów monetą. Skoro ciąg \(n\) rzutów modelujemy przestrzenią skończonych ciągów zer i jedynek \(\{0,1\}^n\), to nieskończony ciąg rzutów będziemy modelować przestrzenią nieskończonych ciągów zer i jedynek \(\{0,1\}^\mathbb{N}\). Nieskończony produkt kartezjański prowadzi do pewnych trudności technicznych przy sprawdzaniu warunku przeliczalnej addytywności, który nakładamy zawsze na rozważane prawdopodobieństwo \(\mathbb{P}\). Trudności te są oczywiście do przejścia. My jednak ograniczymy się do gotowych rozwiązań.
Przykład 5.1 Zamierzamy skonstruować przestrzeń probabilistyczną na której można zdefiniować ciąg niezależnych zdarzeń \(\{A_n\}_{n=1}^{\infty}\) takich, że \(\mathbb{P}[A_n]= 1/2\). Niech \((\Omega, \mathcal{F}, \mathbb{P}) = ([0,1], \mathcal{B}or([0,1]), {\rm Leb})\). Dla każdego \(\omega\in[0,1]\) przyporządkowujemy jego rozwinięcie dwójkowe: \[ \omega =\sum_{n=1}^\infty \frac{\omega_n}{2^n} = 0,\omega_1\omega_2\ldots \] Powyższe przedstawienie nie jest jednoznaczne np. \(1/2 = 0,10000\ldots = 0,01111\ldots\), aby uzyskać jednoznaczność wybieramy rozwinięcie zawierające nieskończenie wiele \(1\). Niech \[ A_n = \big\{ \omega \in [0,1]:\; \omega_n = 0 \big\}, \] czyli \[\begin{align*} A_1 &= [0,1/2),\\ A_2 &= [0,1/4)\cup [1/2,3/4),\\ A_3 &= [0,1/8)\cup [1/4, 3/8) \cup [1/2,5/8)\cup [3/4,7/8),\\ A_4 & = \cdots \end{align*}\] Wtedy \(\mathbb{P}[A_n]=1/2\). Ponadto można pokazać, że zbiory \(\{A_n\}\) są niezależne (zadanie).
Powyższy przykład pokazuje, że w przypadku rzutów monetą można wskazać bardzo konkretną przestrzeń, którą możemy modelować nieskończony ciąg eksperymentów. Jeżeli bylibyśmy zainteresowani rzutami kostką, to konstrukcję z powyższego przykładu można przeprowadzić dla rozwinięć w systemie szóstkowym.
Co jeżeli nasz ciąg eksperymentów jest bardziej skomplikowany? Jeżeli w chwilach nieparzystych rzucamy jedną kością, a w chwilach parzystych rzucamy monetą z wyłączeniem chwil podzielnych przez 128, w których losujemy punkt z przedziału \([0,42]\)?
Potrzebne nam jest ogólne narzędzie (maszynka) do konstruowania przestrzeni probabilistycznych dla nieskończonych ciągów eksperymentów.
Twierdzenie 5.1 (Kołmogorowa o istnieniu procesu) Załóżmy, że \(\{\mathbb{P}_n'\}_{n \in \mathbb{N}}\) jest ciągiem miar probabilistycznych takim, że
- dla każdego \(n \in \mathbb{N}\), \(\mathbb{P}_n'\) jest miarą na \(\mathbb{R}^n, \mathcal{B}or(\mathbb{R}^n)\).
- Spełniony jest warunek zgodności: \[ \mathbb{P}_{n+1}'(A_1\times A_2 \times \ldots \times A_n\times \mathbb{R}) = \mathbb{P}_{n}'(A_1\times A_2 \times \ldots \times A_n). \]
Wówczas istnieje jedyna miara probabilistyczna \(\mathbb{P}\) na \((\mathbb{R}^\mathbb{N}, \mathcal{B}or(\mathbb{R}^\mathbb{N}))\) taka, że \[ \mathbb{P}'(A_1\times A_2 \times \ldots \times A_n\times \mathbb{R}\times \ldots) = \mathbb{P}_{n}'(A_1\times A_2 \times \ldots \times A_n). \]
Proof. Do znalezienia tutaj, Theorem A.3.1.
\(\mathcal{B}or(\mathbb{R}^\mathbb{N})\) jest \(\sigma\)-ciałem generowanym przez skończenie wymiarowe prostokąty \[\begin{equation*} B_1\times B_2 \times \cdots \times B_n \times \mathbb{R} \times \mathbb{R} \times \cdots, \end{equation*}\] dla \(n \in \mathbb{N}\), \(B_1, \ldots B_n \in \mathcal{B}or(\mathbb{R})\).
Powyższe twierdzenie dostarcza ogólne narzędzie gwarantujące istnienie miary probabilistycznej. Zauważmy też, że działa ono nie tylko dla niezależnych eksperymentów. Jedynym warunkiem jest zgodność miar. W niektórych przypadkach można bezpośrednio skonstruować przestrzeń probabilistyczną.
Wniosek 5.1 Istnieje przestrzeń probabilistyczna \((\Omega, \mathcal{F}, \mathbb{P})\) opisująca nieskończony ciąg niezależnych eksperymentów.
Proof. Niech \((\Omega_n, \mathcal{F}_n, \mathbb{P}_n)\) będzie ciągiem przestrzeni probabilistycznych spełniających (5.1). Wówczas \[\begin{equation*} \mathbb{P}'_n = \mathbb{P}_1\otimes \mathbb{P}_2\otimes \cdots \otimes \mathbb{P}_n \end{equation*}\] opisuje pierwsze \(n\) eksperymentów wykonanych niezależnie. Rodzina ta jest zgodna, bo \[\begin{multline*} \mathbb{P}_{n+1}'[B_1\times B_2\times \cdots B_{n} \times \mathbb{R}] \\ = \mathbb{P}_1[B_1]\mathbb{P}_2[B_2] \cdots \mathbb{P}_n[B_n]\mathbb{P}_{n+1}[\mathbb{R}] \\ \mathbb{P}_{n}'[B_1\times B_2\times \cdots B_{n}] \\ \end{multline*}\] Z Twierdzenia 5.1 wynika, że istnieje \(\mathbb{P}\) na \(\mathbb{R}^\mathbb{N}\) taka, że \[ \mathbb{P}'(A_1\times A_2 \times \ldots \times A_n\times \mathbb{R}\times \ldots) = \mathbb{P}_{n}'(A_1\times A_2 \times \ldots \times A_n). \] Okazuje się, że jest to szukana przez nas miara probabilistyczna modelująca niezależne eksperymenty. Niech \[\begin{align*} \tilde{A}_1 & = A_1\times \mathbb{R}\times \mathbb{R}\times \ldots \\ \tilde{A}_2 & = \mathbb{R}\times A_2 \times \mathbb{R} \times \ldots \\ \tilde{A}_3 & = \mathbb{R} \times \mathbb{R} \times A_3 \times \mathbb{R} \ldots \end{align*}\] Wówczas \(\tilde{A}_j\) jest kopią \(A_j\) w nieskończonym produkcie. Wówczas dla każdego \(j \in \mathbb{N}\), \[\begin{equation*} \mathbb{P}[\tilde A_j] = \mathbb{P}_j[A_j]. \end{equation*}\] Skoro \[\begin{equation*} A_1\times A_2 \times \ldots \times A_n \times \mathbb{R} \ldots = \tilde{A}_1\cap \tilde{A}_2\cap \ldots \tilde{A}_n, \end{equation*}\] to \[\begin{equation*} \mathbb{P}[\tilde{A}_1\cap \tilde{A}_2\cap \ldots \tilde{A}_n] = \mathbb{P}[\tilde A_1]\mathbb{P}[\tilde A_2] \cdots \mathbb{P}[\tilde A_n]. \end{equation*}\] Czyli miara \(\mathbb{P}\) reprodukuje eksperymenty w sposób niezależny.
Badając eksperymenty losowe polegające na nieskończonych powtórzeniach jednego eksperymentu, powiedzmy, że wykonujemy nieskończenie wiele rzutów monetą.
Definicja 5.1 Dana jest przestrzeń probabilistyczna \((\Omega, \mathcal{F}, \mathbb{P})\) oraz ciąg zdarzeń \(\{A_n\}_{n\in \mathbb{N}} \subseteq \mathcal{F}\). Granicą górną ciągu zdarzeń \(\{A_n\}_{n \in \mathbb{N}}\) nazywamy zdarzenie \[\begin{multline*} \limsup_{n\in \mathbb{N}} A_n = \bigcap_{m=1}^\infty \bigcup_{n=m}^\infty A_n \\ = \left( A_1\cup A_2\cup A_3\cup\ldots \right)\cap \left( A_2\cup A_3\cup\ldots \right)\cap \left( A_3\cup\ldots \right) \cap \ldots. \end{multline*}\]
Przypomnijmy, że element należy do przekroju zbiorów wtedy i tylko wtedy, gdy należy do każdego z nich. Element należy do sumy zbiorów wtedy i tylko wtedy, gdy należy do jednego ze zbiorów. Mamy więc \[\begin{multline*} \omega \in \bigcap_{m=1}^\infty\bigcup_{n=m}^{\infty }A_n \iff \forall m \geq 1, \: \omega \in \bigcup_{n=m}^{\infty} A_m \\ \iff \forall m\geq 1, \: \exists n\geq m, \: \omega \in A_n. \end{multline*}\] Reasumując, \(\omega\in \limsup A_n\) wtedy i tylko wtedy, gdy \(\omega\) należy do nieskończenie wielu zbiorów \(A_i\). Innymi słowy, \(\limsup A_n\) to zdarzenie polegające na tym, że zaszło nieskończenie wiele spośród zdarzeń \(A_1, A_2, \ldots\). Dla przykładu, rzucamy nieskończenie wiele razy kostką i \(A_n\) oznacza zdarzenie, że w \(n\)-tym rzucie kostką wypadła \(6\), to \(\limsup A_n\) jest zdarzeniem, że wypadło nieskończenie wiele \(6\).
Niezwykle przydatnym narzędziem będzie lemat wskazujący warunki przy których zachodzi nieskończenie wiele zdarzeń.
Lemma 5.1 (Borel-Cantelli) Załóżmy, że \((\Omega, \mathcal{F}, \mathbb{P})\) jest przestrzenią probabilistyczną oraz niech \(\{A_n\}_{n \in \mathbb{N}}\subseteq \mathcal{F}\) będzie ciągiem zdarzeń.
- Jeżeli \(\sum_{n=1}^\infty \mathbb{P}[A_n] < \infty\), to \[\mathbb{P}[\limsup A_n] = 0,\] tzn. z prawdopodobieństwem \(1\) zachodzi jedynie skończenie wiele spośród zdarzeń \(A_n\).
- Jeżeli \(A_1,A_2,\ldots\) są niezależnymi zdarzeniami oraz
\(\sum_{n=1}^\infty \mathbb{P}[A_n] = \infty\), to \[\mathbb{P}[\limsup A_n] =1,\] tzn. z prawdopodobieństwem \(1\) zachodzi nieskończenie wiele zdarzeń \(A_n\).
Proof. Korzystając z ciągłości miary, a następnie z jej podaddytywności otrzymujemy \[\begin{equation*} \mathbb{P}[\limsup A_n] = \mathbb{P}\left[ \bigcap_{m=1}^\infty \bigcup_{n=m}^\infty A_n \right] =\lim_{m\to\infty} \mathbb{P}\left[ \bigcup_{n=m}^\infty A_n \right]\le \lim_{m\to\infty} \sum_{n=m}^\infty \mathbb{P}[A_n] = 0, \end{equation*}\] gdzie ostatnia równość wynika z sumowalności szeregu. Aby wykazać punkt 2, wystarczy pokazać, że \[ 0 = \mathbb{P}\left[ (\limsup A_n)^c\right]= \mathbb{P}\left[\left( \bigcap_{m=1}^\infty \bigcup_{n=m}^\infty A_n\right)^c \right] = \mathbb{P}\left[ \bigcup_{m=1}^\infty \bigcap_{n=m}^\infty A_n^c \right]. \] Skoro \[\begin{equation*} \mathbb{P}\left[ \bigcup_{m=1}^\infty \bigcap_{n=m}^\infty A_n^c \right] \leq \sum_{m=1}^\infty\mathbb{P}\left[ \bigcap_{n=m}^\infty A_n^c \right], \end{equation*}\] to wystarczy udowodnić, że dla każdego \(m\) mamy \[ \mathbb{P}\left[ \bigcap_{n=m}^\infty A_n^c \right] = 0. \] W tym celu piszemy (kolejno korzystamy z twierdzenia o ciągłości, niezależności zbiorów \(A_n\) oraz nierówności \(1-x\le e^{-x}\)) \[\begin{multline*} \mathbb{P}\left[ \bigcap_{n=m}^\infty A_n^c \right] = \lim_{k\to \infty} \mathbb{P}\left[ \bigcap_{n=m}^k A_n^c \right] = \lim_{k\to \infty} \prod_{n=m}^k \mathbb{P}\left[ A_n^c \right] \\ = \lim_{k\to \infty} \prod_{n=m}^k \left( 1 - \mathbb{P}\left[ A_n \right]\right) \le \lim_{k\to \infty} e^{-\sum_{n=m}^k \mathbb{P}[ A_n]} = e^{-\sum_{n=m}^\infty \mathbb{P}[ A_n]} = 0. \end{multline*}\]
Przykład 5.2 Uzasadnimy, że jeżeli będziemy rzucać odpowiednio długo kostką, to z prawdopodobieństwem \(1\) wyrzucimy dowolną liczbę szóstek. Niech \(\Omega = \{1,2,\ldots,6\}^\mathbb{N}\), \(\mathcal{F} = 2^\Omega\). Ponadto niech \(\mathbb{P}\) będzie odpowiednią miarą probabilistyczną. Oznaczmy przez \(A_n\) zdarzenie, że w rzucie o numerze \(n\), wypadło \(6\). Wówczas \(\mathbb{P}[A_n] = 1/6\). Zdarzania \(A_i\) są niezależne oraz \[ \sum_{n=1}^\infty \mathbb{P}\left[A_n\right] = \sum_{n=1}^\infty 1/6 = \infty. \] Lemat Borela - Cantelliego pociąga \[ \mathbb{P}\left[\limsup A_n\right] =1. \]
Przykład 5.3 Jeżeli będziemy rzucać odpowiednio długo kostką, to z prawdopodobieństwem \(1\) wyrzucimy w kolejnych rzutach ciąg złożony z kolejnych \(10\) jedynek i kolejnych \(10\) szóstek. Niech \(\Omega = \{1,2,\ldots,6\}^\mathbb{N}\), \(\mathcal{F} = 2^\Omega\). Ponadto niech \(\mathbb{P}\) będzie odpowiednią miarą probabilistyczną. Oznaczmy przez \(A_n\) zdarzenie, że w rzutach o numerach \(n, n+1, \ldots, n+19\) wypadnie żądany ciąg. Wówczas \(\mathbb{P}[A_n] = 1/6^{20}\).
Zdarzania \(A_i\) nie są niezależne, więc nie możemy dla nich użyć lematu Borela-Cantallego. Zdefiniujmy jednak \(\widetilde A_n = A_{20n}\). Wówczas zbiory \(\widetilde A_n\) są niezależne oraz \[ \sum_{n=1}^\infty \mathbb{P}\left[\widetilde A_n\right] = \sum_{n=1}^\infty \frac 1{6^{20}} = \infty. \] Lemat Borela - Cantelliego pociąga \[ \mathbb{P}\left[\limsup \widetilde A_n\right] =1, \] a więc z prawdopodobieństwem \(1\) zdarzenia \(\widetilde A_n\) (a zatem również \(A_n\)) zachodzą nieskończenie wiele razy. W szczególności z prawdopodobieństwem \(1\) zajdzie przynajmniej jedno ze zdarzeń \(A_n\).
Ostatni przykład można powtórzyć dla dowolnego ciągu wyników. W szczególności pociąga to Twierdzenie o nieskończonej liczbie małp, które można sparafrazować w następujący sposób: jeżeli małpa będzie naciskać w sposób losowy klawisze maszyny do pisania przez nieskończenie długi czas, to z prawdopodobieństwem jeden napisze ona wszystkie dzieła Mickiewicza.
Przykład 5.4 Rzucamy nieskończenie wiele razy niesymetryczną monetą (orzeł wypada na niej z prawdopodobieństwem \(p\not=1/2\)). Niech \(A_n\) oznacza zdarzenie, że w pierwszych \(n\) rzutach wypadło tyle samo orłów co reszek. Pokażemy że z prawdopodobieństwem \(1\) zachodzi jedynie skończenie wiele zdarzeń \(A_n\). Dla nieparzystej liczby rzutów mamy oczywiście \(\mathbb{P}[A_{2n+1}] = 0\), natomiast dla parzystej liczby \[ \mathbb{P}[A_{2n}] = {2n \choose n} p^n(1-p)^n \sim \frac{4^np^n(1-p)^n}{\sqrt{n\pi}}, \] gdzie ostatnia implikacja wynika ze wzoru Stirlinga \[\begin{equation} n! \sim \sqrt{2\pi n} \bigg(\frac{n}{e}\bigg)^n, \end{equation}\] a zapis \(a_n\sim b_n\) oznacza, że \(\lim_{n\to\infty} \frac{a_n}{b_n}=1\).
Funkcja \(x\to 4x(1-x)\) na przedziale \([0,1]\) przyjmuje maksimum równe 1 dla \(x=1/2\), zatem dla \(p\not= 1/2\), \(4p(1-p)\), a to z kolei, na mocy kryterium Cauchy’ego oznacza zbieżność szeregu \[ \sum_n \mathbb{P}[A_n] <\infty. \] Z lematu Borella-Cantallego zdarzenia \(A_n\) z prawdopodobieństwem jeden zachodzą jedynie skończenie wiele razy. (Zauważmy jednak, że liczba tych zdarzeń jest losowa).
Jak zmienia się rysunek, gdy \(p>1/2\)? Jakie zachowanie obserwujemy dla małych wartości \(p-1/2\)?