Zacznijmy ten wykład od zastanowienia się nad tym czym jest prawdopodobieństwo pojawiające się w jego tytule, i czym jest losowość, która się z prawdopodobieństwem kojarzy. Wydaje się, że mamy z tymi pojęciami do czynienia całkiem często na co dzień. Oto kilka sytuacji, w których pojawia się pojęcie prawdopodobieństwa/szans:
Zauważmy w tym miejscu, że pojęcie prawdopodobieństwa jest tu używane na bardzo różne sposoby:
Pojęcie losowości jest równie skomplikowane jak pojęcie prawdopodobieństwa:
Ale co to właściwie znaczy, że coś jest losowe? Że nie da się tego przewidzieć? A nie da się przewidzieć wyniku rzutu monetą? Może się da... A wynik meczu? Kto wie, może problem leży w naszej niewystarczającej mocy obliczeniowej i nieumiejętności wystarczającego dokładnego uwzględnienia wszystkich parametrów.
Z powyższych rozważań wynika, że pojęcia prawdopodobieństwa i losowości, tak jak są one rozumiane i używane w języku codziennym, są dość niejasne i trudno byłoby uprawiać ścisłą naukę za ich pomocą. Dlatego nie będziemy tego robić. Zamiast tego zdefiniujemy w bardzo skrupulatny sposób pewną klasę obiektów matematycznych, formalnych modeli zjawisk o charakterze losowym, tzw. przestrzenie probabilistyczne. O przestrzeniach probabilistycznych można rozumować w sposób zupełnie ścisły, a problemy, o których wspomnieliśmy na początku wykładu zaczynają się pojawiać dopiero wtedy, gdy pytamy o to jaka przestrzeń probabilistyczna najlepiej opisuje interesującą nas sytuację.
Warto w tym miejscu zwrócić uwagę na jeszcze jedną rzecz. Jak pokazała nasza wstępna dyskusja z pojęciami szans i losowości spotykamy się bardzo często na co dzień. Dlatego, o ile napotkany na ulicy przechodzień prawdopodobnie nie będzie się czuł szczególnie mocno w teorii przestrzeni Banacha, czy nawet całkowaniu, o tyle prawdopodobnie będzie miał bardzo wiele do powiedzenia na temat tego jak prawdopodobne są różne wyniki opisanego przez nas doświadczenia o charakterze losowym. Czyli wszyscy jesteśmy "ekspertami od prawdopodobieństwa". Taka sytuacja jest oczywiście w jakimś sensie dobra - nie musimy się uczyć wszystkiego od początku - ale też może być bardzo niebezpieczna. Mętna i pozbawiona solidnych podstaw wiedza jest często dużo gorsza niż brak jakiejkolwiek wiedzy. Dlatego zachęcam Państwa do świeżego spojrzenia na to, co będzie się działo w kolejnych wykładach i, w miarę możliwości, oderwania się od wszelkiego rodzaju intuicji i "wiedzy" ze szkoły średniej, przynajmniej przez jakiś czas. Formalizm, który tu zdefiniujemy dość długo będzie sprawiał wrażenie zbędnego obciążenia, aż do momentu kiedy nagle okaże się niezbędny, co może się okazać bardzo nieprzyjemną niespodzianką dla kogoś, kto się do niego nie przyzwyczai.
Zanim zdefiniujemy przestrzeń probabilistyczną wprowadzimy kilka definicji, które w znacznym stopniu ułatwią dalsze rozważania. Za pomocą przestrzeni probabilistycznych będziemy modelować tzw. doświadczenia losowe:
Definicja (doświadczenie losowe i zdarzenie elementarne)
Doświadczeniem/eksperymentem losowym nazywamy dowolny proces (lub ciąg czynności) taki, że:
Uwaga 1.1 Powyższa definicja ma nieco inny charakter niż definicje, z którymi spotykamy się z reguły w teoriach matematycznym. Nie definiujemy tutaj formalnie pojęcia doświadczenia losowego, staramy się raczej wskazać jakie jego cechy będą dla nas istotne, oraz wprowadzić kluczowe terminy.
W szczególności założenia powtarzalności doświadczenia nie należy traktować zbyt dosłownie. Na przykład rozwiązując zadania o pojedynku, w którym każdy z uczestników z pewnym prawdopodobieństwem ginie, trudno sobie wyobrazić powtarzanie doświadczenia dowolnie wiele razy. W tego typu sytuacjach mamy na myśli raczej pewnego rodzaju eksperyment myślowy, niż faktyczne powtarzanie eksperymentu. Tym niemniej, założenie powtarzalności jest dość istotne jako podstawa intuicji częstościowej, o której powiemy później.
Definicja (zdarzenie)
Zdarzeniem nazywamy dowolny podzbiór zbioru zdarzeń elementarnych.
Przykład 1.2
Jeśli rozważanym doświadczeniem losowym jest rzut kostką, to zbiorem zdarzeń elementarnych może być na przykład zbiór \(\Omega = \{1,\ldots,6\}\). W tym przypadku zdarzeniami są np. zbiory \(A = \{2,4,6\}\), \(B=\{1,2,3,4\}\), \(C = \{1,2,3,4,5,6\}\), czy \(D = \emptyset \). Każde takie zdarzenie \(X \subseteq \Omega\) należy interpretować jako "wynikiem doświadczenia było jedno ze zdarzeń elementarnych w \(X\)". W szczególności:
To ostatnie zdarzenie jest oczywiście niemożliwe (i tak się je właśnie często nazywa), co nie zmienia faktu, że jest ono zdarzeniem.
Naszym modelem eksperymentu losowego będzie przestrzeń probabilistyczna. Przestrzeń probabilistyczna będzie się składać ze zbioru zdarzeń elementarnych oraz z pewnego sposobu przypisania zdarzenim liczb z przedziału \([0,1]\), które będziemy nazywać ich prawdopodobieństwami. Definicja, której użyjemy będzie zaskakująco skomplikowana. Dlatego zanim ją podamy, zobaczmy dlaczego nie działają naturalne, prostsze pomysły.
Definicja przestrzeni probabilistycznej - pierwsze podejście
Najbardziej naturalną i najprostszą metodą definiowania przestrzeni probabilistycznej wydaje się przyjęci, że przestrzeń taka jest parą \( (\Omega,P)\), gdzie \(P:\Omega \rightarrow [0,1]\) jest funkcją przypisującą prawdpodobieństwo każdemu zdarzeniu elementarnemu. Funkcję taką możemy w naturalny sposób rozszerzyć na dowolne podzbiory \(A \subseteq \Omega\) w następujący sposób
\( P(A) = \sum_{a \in A} P(a)\).
Problemy z tym podejściem pojawią się, gdy spróbujemy wymodelować w ten sposób losowanie punktu z odcinka \([0,1]\). Intuicyjnie, każdy punkt powinien być równie prawdopodobny, ale skoro tak, to prawdopodobieństwa wszystkich punktów muszą być równe \(0\), w przeciwnym przypadku dostaniemy \(P(\Omega) = \infty\).
Widać więc, że nie możemy definiować \(P\) wychodząc od zdarzeń elementarnych - trzeba \(P\) definiować bezpośrednio na podzbiorach \(\Omega\).
Definicja przestrzeni probabilistycznej - drugie podejście
Kolejny naturalny pomysł to zdefiniowanie przestrzeni probabilistycznej jako pary \((\Omega,P)\), gdzie \(P:2^\Omega \rightarrow \mathbb{R}\). Oczywiście funkcja \(P\) pojawiająca się w tej definicji powinna spełniać pewne naturalne własności, np. \(P(A \cup B) = P(A)+P(B)\), jeśli \(A,B \subseteq \Omega\) są rozłączne. Okazuje się, że takie funkcje \(P\) to nic innego jak miary, o których była mowa na wykładzie z analizy matematycznej. I tu pojawia się problem: Jeśli, tak jak poprzednio, spróbujemy zdefiniować przestrzeń probabilistyczną odpowiadającą losowaniu punktu z odcinka, to będziemy musieli określić miarę \(P:2^{[0,1]} \rightarrow [0,1]\). Co więcej, aby miara ta odpowiadała naszej intuicji losowania punktu z odcinka powinna ona spełniać pewne dodatkowe własności, np. \(P(A) = P(a+A)\) dla dowolnych \(a \in [0,1]\) oraz \(A,a+A \subseteq [0,1]\), gdzie \(a+A = \{a+x : x \in A\}\). Niestety, jak wiemy z wykładu z analizy matematycznej, takiej miary skonstruwać się nie da. Najlepsze co możemy zrobić to zdefiniować miarę na dość dużej rodzinie podzbiorów \([0,1]\), tzw. zbiorach mierzalnych w sensie Lebesgue'a.
Powyższe rozważania prowadzą do następującej definicji przestrzeni probabilistycznej:
Definicja (przestrzeń probabilistyczna)
Przestrzenią probabilistyczną nazywamy trójkę \((\Omega,\mathcal{F},P)\), gdzie \(\mathcal{F} \subseteq 2^\Omega\) oraz \(P:\mathcal{F} \rightarrow [0,1]\). Ponadto \(\mathcal{F}\) musi spełniać następujące warunki:
a \(P\) następujące warunki:
Uwaga 1.3
W kolejnych wykładach bardzo często będziemy mieli do czynienia z sytuacjami, w których \(\Omega\) jest zbiorem skończonym, ew. nieskończonym przeliczalnym. W takich sytuacjach problemy z mierzalnością nie mogą się pojawić i w powyższej definicji można zawsze przyjąć \(\mathcal{F} = 2^\Omega\). Dla uproszczenia notacji będziemy wtedy zamiast pisać \((\Omega,P)\) zamiast \( (\Omega,\mathcal{F},P)\), oraz \(A \subseteq \Omega\) zamiast \(A \in \mathcal{F}\).
Uwaga 1.4
Dość często będą nas interesowały wartości \(P\) na podzbiorach jednoelementowych. Będziemy wtedy dla uproszczenia pisać \(P(x)\) zamiast \(P(\{x\})\).
Wprost z definicji przestrzeni probabilistycznej prosto wynika wiele naturalnych własności prawdopodobieństwa, oto kilka z nich:
Fakt 1.5 (własności prawdopodobieństwa)
Niech \((\Omega,\mathcal{F},P)\) będzie przestrzenią probabilistyczną. Wtedy:
Dowód
Z zamkniętości \(\mathcal{F}\) na dopełnienia wynika, że \(\bar{A} \in \mathcal{F}\). Możemy więc użyć przeliczalnej addytywności \(P\) i dostajemy \(P(A)+P(\bar{A}) = P(\Omega) =1\), co daje tezę.
2. wynika z 1. dla \(A=\emptyset\).
3. wynika z zamkniętości \(\mathcal{F}\) na przeliczalne sumy i praw de Morgana,
4. wynika z przeliczalnej addytywności \(P\). Mamy bowiem \(P(B) = P(A) + P(B \setminus A)\) (to, że \(B \setminus A = B \cap \bar{A} \in \mathcal{F}\) wynika z 3.),
Wreszcie, aby pokazać 5. zdefiniujmy dla \(B_i = A_i \setminus \bigcup_{j=1}^{i-1} A_j\) dla \(i=1,2,\ldots\). Wtedy mamy \(\bigcup_{i=1}^\infty A_i = \bigcup_{i=1}^\infty B_i\) oraz \(B_i \subseteq A_i\) i ponadto \(B_i\) są parami rozłączne , a zatem:
\( P(\bigcup_{i=1}^\infty A_i) = P(\bigcup_{i=1}^\infty B_i) = \sum_{i=1}^\infty P(B_i) \le \sum_{i=1}^\infty P(A_i) \).
Zastanowimy się teraz jak powinna wyglądać funkcja \(P\) z definicji przestrzeni probabilistycznej. Jest dość jasne, że podane przez nas aksjomaty nie wyznaczają \(P\) jednoznacznie. Na przykład, jeśli rzucamy monetą i bierzemy \(\Omega = \{O,R\}\), to z aksjomatów wynika jedynie, że
\(P(\emptyset)=0,\ P(\Omega) = 1,\ (P(O)+P(R) = 1\).
A ile jest równe \(P(O)\) czy \(P(R)\)? Wiele osób uważa, że teoria prawdopodobieństwa w jakiś sposób dowodzi tego, że \(P(O)=P(R)=\frac{1}{2}\), czyli w szczególności, że wynika to z aksjomatów. Nic z tych rzeczy, i dobrze, że tak nie jest. Gdyby z aksjomatów wynikało, że \(P(O)=\frac{1}{2}\), to nie bylibyśmy w stanie wymodelować oszukanej monety!
No dobrze, ale w takim razie skąd weźmie się wartość \(P(O)\)? Otóż naszym zadaniem jest, w ramach budowania probabilistycznego modelu rozpatrywanego doświadczenia, dobranie \(P\) tak, aby jak najlepiej opisywało to doświadczenie. Dobrym punktem wyjścia do definicji \(P\) jest często intuicja częstościowa: Jeśli wykonamy bardzo wiele powtórzeń tego samego eksperymentu, to frakcja powtórzeń, w których zaszło zdarzenie \(A\) powinna zbiegać do prawdopodobieństwa \(A\).
Uwaga 1.6
Opisanej powyżej intuicji częstościowej można użyć do innej (nieaksjomatycznej) definicji przestrzeni probabilistycznej odpowiadającej doświadczeniu losowemu. Możemy mianowicie każdemu zdarzeniu \(A\) przypisać prawdopodobieństwo \(P(A)\), które jest granicą frakcji powtórzeń doświadczenia, dla których \(A\) zaszło. Takie podejście niesie ze sobą wiele problemów, zaczynając od tego, że nie jest całkiem jasne dlaczego taka granica miałaby w ogóle istnieć (w tym miejscu warto się zastanowić nad tym co się stanie jeśli spróbujemy użyć tego podejścia do modelowania losowania punktu z odcinka). W naszym podejściu intuicja częstościowa prawdopodobieństwa jest używana tylko przy wyborze modelu, natomiast sama definicja przestrzeni probabilistycznej jest całkowicie od niej niezależna.
Co daje intuicja częstościowa w przypadku rzutu monetą? Intuicyjnie wydaje się jasne, że na dłuższą metę orzeł i reszka powinny wypadać równie często, to jest w połowie rzutów. Jeśli prawdopodobieństwa mają odpowiadać częstościom, to powinniśmy przyjąć \(P(O)=P(R)=\frac{1}{2}\). Mamy wtedy bowiem \(P(O)=P(R)\) oraz \(P(O) + P(R) = P(\Omega) = 1\). Podkreślmy jednak raz jeszcze, że jest to tylko założenie, na dodatek prawie zawsze fałszywe w przypadku fizycznych monet - która moneta jest idealna? Oczywiście monety wyimaginowane są idealne, jeśli tylko tego chcemy.
Rozumowanie, którego użyliśmy przy wyborze probabilistycznego modelu dla rzutu monetą jest stosowane bardzo często, w nieco ogólniejszej postaci, i ma nawet swoją nazwę.
Fakt 1.7 (Schemat klasyczny)
Niech \((\Omega,P)\) będzie skończoną przestrzenią probabilistyczną. Jeśli dla każdych \(x,y \in \Omega\) zachodzi \(P(x) = P(y)\), to:
Oczywisty dowód pomijamy.
Schemat klasyczny ma wiele zastosowań, używając go należy być jednak ostrożnym - schemat klasyczny nie zawsze prowadzi do sensownego modelu.
Przykład 1.8
W XVIII-wiecznej encyklopedii d'Alambert pisze, że prawdopodobieństwo uzyskania co najmniej jednego orła w dwóch rzutach wynosi \(\frac{2}{3}\). Dlaczego? Otóż, możliwe są \(3\) wyniki: O (wtedy dalsze rzuty nie są istotne), RO i RR. Z tych wyników tylko ostatni nam nie pasuje. Zgadzamy się z tym rozumowaniem? Raczej nie. Wydaje się jasne, że wyniki O,RO,RR nie powinny być równie prawdopodobne.
Oczywiście można problem rozważany przez d'Alamberta rozwiązać używając schematu klasycznego. Czy widzisz jak?
Przykład 1.9
Przypuśćmy, że interesuje nas prawdopodobieństwo tego, że w losowej \(5\)-kartowej ręce pokerowej jest dokładnie jedna para (w szczególności nie ma w niej trójki ani dwóch par). Aby obliczyć to prawdopodobieństwo przyjmijmy, że \( \Omega \) to zbiór wszystkich \(5\)-elementowych podzbiorów zbioru \(52\) kart. Niech \(A\) będzie zbiorem wszystkich zbiorów zawierających dokładnie jedną parę. Chcemy obliczyć \(P(A)\). Ponieważ każdy \(5\)-elementowy podzbiór kart powinien być równie prawdopodobny, korzystamy ze schematu klasycznego i dostajemy:
\(P(A) = \frac{|A|}{|\Omega|}\).
Jasne jest, że \(|\Omega| = {52 \choose 5}\), a jaka jest moc \(A\)? Zastanówmy się na ile sposobów można wybrać podzbiór zawierający dokładnie jedną parę:
Ostatecznie dostajemy \(|A| = 13 \cdot 6 \cdot 4^3 \cdot {12 \choose 3}\) oraz \(P(A) = \frac{|A|}{|\Omega|} \approx 0.423 \).
Jak widać użycie schematu klasycznego sprowadziło problem probabilistyczny do problemu kombinatorycznego. Na ćwiczeniach zobaczymy więcej tego rodzaju zadań.
Na koniec wykładu krótka uwaga dotycząca modelowania rzeczywistych doświadczeń przestrzeniami probabilistycznymi: Pamiętajmy, że są to tylko modele i (prawie zawsze) są one jedynie przybliżeniami rzeczywistości. Mówiliśmy już o tym przy okazji przykładu z rzutem monetą, ale zobaczmy jeszcze jeden nieco ciekawszy przykład. Chcemy zbudować model probabilistyczny, który pozwoli nam obliczyć prawdopodobieństwo tego, że losowo wybrana osoba urodziła się \(1\) czerwca. Najprostszy pomysł to przyjąć, że \(\Omega\) składa się z \(365\) dni roku i każdy jest równie prawdopodobny. Ten model prowadzi do odpowiedzi \(\frac{1}{365}\), ale nie jest zbyt dobry. Dlaczego? Zapomnieliśmy o latach przestępnych. Uwzględnienie lat przestępnych jest nieco problematyczne, bo nie dość, że trzeba w tym celu obliczyć jak duża jest frakcja lat przestępnych, to zapewne chcielibyśmy przy tym uwzględnić to ile lat wstecz patrzymy. Nie interesują nas przecież lata przestępne \(150\) lat temu!
No dobrze, przypuśćmy, że udało nam się jakoś uwzględnić lata przestępne. Czy to jest dobry model? Na pewno jest niezły, ale nie jest idealny. Wiadomo przecież, że nie każda data urodzin jest równie prawdopodobna. W niektórych miesiącach rodzi się, z różnych przyczyn, dużo więcej dzieci niż w innych. Zachęcamy czytelnika do zastanowienia się co jeszcze nie zostało uwzględnione w tym modelu.
Wniosek z tych rozważań jest taki, że model probabilistyczny zawsze będzie kompromisem między prostotą opisu, a dokładnością odwzorowania rzeczywistości.
Przykład 2.1
Test na obecność pewnego wirusa ma skuteczność 95%, tzn. jeśli badana osoba jest chora (t.j. zakażona wirusem), to z prawdopodobieństwem 0.95 test daje wynik pozytywny, a jeśli badana osoba jest zdrowa, to z prawdopodobieństwem 0.95 test daje wynik negatywny. Wiadomo, że średnio 1 osoba na 1000 jest zakażona. Jeśli dla osoby wybranej losowo test dał wynik pozytywny, to jakie jest prawdopodobieństwo tego, że osoba ta jest faktycznie chora?
Powyższe pytanie jest o tyle ciekawe, że choć większość osób ma swoją "teorię" na temat szukanego prawdopodobieństwa, to z reguły jest ona niestety błędna. W amerykańskich szpitalach przeprowadzono kiedyś wśród lekarzy ankietę dotyczącą tego właśnie problemu i wyniki były zatrważające. Większość ankietowanych podało odpowiedź różniącą się rzędem wielkości od prawidłowej!
Próbując rozwiązać powyższy problem zdefiniujemy pojęcie prawdopodobieństwa warunkowego i wyprowadzimy wiele jego własności. Pojęcie to, jak się okaże, ma wiele zastosowań, także w sytuacjach pozornie nie mających z nim nic wspólnego.
Zanim odpowiemy na pytanie postawione w przykładzie, musimy się zastanowić nad tym jaki jest jego sens. Czym jest "prawdopodobieństwo \(A\) jeśli wiemy, że zaszło \(B\)" ?. Przyjrzyjmy się najpierw dużo prostszemu przykładowi.
Przykład 2.2
Nasz kolega rzuca dwiema kostkami i podaje nam sumę oczek. Załóżmy, że podaną sumą jest 5. Jakie jest prawdopodobieństwo, że na pierwszej kostce wypadły 1 lub 2 oczka?
Informacja podana przez kolegę ograniczyła zbiór zdarzeń elementarnych do \(A=\{(1,4),(2,3),(3,2)(4,1)\}\). Zbiór \(A\) zawiera 4 elementy, ale tylko dwa z nich odpowiadają wypadnięciu 1 lub 2 oczek na pierwszej kostce. Sądzimy więc, że szukane prawdopodobieństwo wynosi \(\frac{1}{2}\).
Co dokładnie się tu stało? Obliczyliśmy wartość wyrażenia \(\frac{|A\cap B|}{|A|}=\frac{P(A \cap B)}{P(A)}\), gdzie \(A\) jest zdarzeniem, o którym wiemy, że zaszło, a \(B\) zdarzeniem, którego prawdopodobieństwo chcemy obliczyć. Pierwsze z wyrażeń ma tę wadę, że implicite zakładamy w nim użycie schematu klasycznego. Drugie wyrażenie wady tej nie ma i to jego właśnie użyjemy w definicji:
Definicja (Prawdopodobieństwo warunkowe)
Niech \(A,B \subseteq \Omega\) i \(P(A) > 0\). Wtedy prawdopodobieństwem \(B\) pod warunkiem \(A\) nazywamy:
\(P(B|A) = \frac{P(A \cap B)}{P(A)}\).
Uwaga 2.3
Założenie \(P(A) > 0\) jest konieczne, aby wartość ilorazu była dobrze określona. Można sobie jednak wyobrazić sytuacje, w których \(P(A)=0\), a mimo to pojęcie prawdopodobieństwa warunkowego wydaje się mieć sens. Jeśli na przykład wykonujemy nieskończenie wiele rzutów kostką, to prawdopodobieństwo wyrzucenia za każdym razem tej samej liczby oczek jest równe 0. Jeśli jednak się to zdarzy, to prawdopodobieństwo tego, że były to jedynki powinno być równe \(\frac{1}{6}\). W ogólnym przypadku nie da się w sensowny sposób zdefiniować prawdopodobieństwa warunkowego tak, aby obejmowało ono tego typu sytuacje. Sprawa nie jest jednak całkiem beznadziejna i pewne próby takiej definicji zobaczymy w rozdziale poświęconym zmiennym losowym o rozkładach ciągłych.
Uwaga 2.4
Warto zauważyć, że para \( (\Omega, P(\cdot|A))\) jest przestrzenią probabilistyczną (czytelnikowi pozostawiamy sprawdzenie aksjomatów). Co za tym idzie, wiele z przeprowadzanych przez nas rozważań ma swoje odpowiedniki "warunkowe".
Przykład 2.1 (c.d.)
Wróćmy do przykładu z testem medycznym. Zdefiniujmy następujące zdarzenia:
Uzbrojeni w definicję prawdopodobieństwa warunkowego łatwo zauważymy dwie rzeczy. Po pierwsze, naszym celem jest obliczenie \(P(C|T)\). Po drugie, dane z treści zadania opisują pewne prawdopodobieństwa warunkowe:
Aby znaleźć interesującą nas wartość
\(P(C|T) = \frac{P(C \cap T)}{P(T)} \)
spróbujmy najpierw obliczyć \(P(C \cap T)\)? Popatrzmy na definicję prawdopodobieństwa warunkowego:
\( P(T|C) = \frac{P(T \cap C)}{P(C)}\).
Widać, że:
\(P(T \cap C) = P(C) P(T|C) \).
Sytuacja, z którą mamy tu do czynienia, t.j. obliczanie prawdopodobieństwa iloczynu zdarzeń za pomocą prawdopodobieństwa warunkowego, jest bardzo częsta i ważna. W szczególności istnieje uogólnienie wzoru, który uzyskaliśmy powyżej na więcej niż dwa zdarzenia.
Twierdzenie 2.5 (Wzór iloczynowy)
Niech \(A_1,\ldots,A_n \subseteq \Omega\) będą zdarzeniami takimi, że \(P(A_1 \cap \ldots \cap A_{n-1}) > 0 \). Wtedy
\( P(A_1 \cap \ldots \cap A_n) = P(A_1) \cdot P(A_2 | A_1) \cdot P(A_3 | A_1 \cap A_2) \cdot \ldots \cdot P(A_n | A_1 \cap \ldots \cap A_{n-1}) \)
Uwaga 2.6
Założenie \(P(A_1 \cap \ldots \cap A_{n-1}) > 0 \) jest potrzebne, żeby wszystkie prawdopodobieństwa warunkowe występujące w tezie twierdzenia były dobrze określone.
Dowód
Indukcja. Dla dwóch zdarzeń twierdzenie pokazaliśmy już wcześniej. Jeśli mamy \(n > 2\) zdarzenia, to
\(P(A_1 \cap \ldots \cap A_n) = P((A_1 \cap \ldots \cap A_{n-1}) \cap A_n) = P(A_1 \cap \ldots \cap A_{n-1}) \cdot P(A_n | A_1 \cap \ldots \cap A_{n-1}) \)
z tezy dla dwóch zdarzeń. Wystarczy teraz zastosować do pierwszego członu założenie indukcyjne.
Przykład 2.1 (c.d.)
Wróćmy do przykładu z testem medycznym. Potrafimy obliczyć prawdopodobieństwa \(P(C \cap T)\), i w analogiczny sposób także \(P(C\cap N), P(Z \cap T) \) i \(P(Z\cap N)\).
Aby obliczyć szukane przez nas \(P(C|T) = \frac{P(C \cap T)}{P(T)}\), potrzebujemy jeszcze znaleźć wartość \(P(T)\). Ale to jest proste:
\( P(T) = P(C\cap T+Z\cap T) = P(C\cap T)+P(Z\cap T) = P(C) P(T|C) + P(Z) P(T|Z) \).
Ostatecznie dostajemy więc:
\(P(C|T) = \frac{P(C) P(T|C)}{P(C) P(T|C) + P(Z) P(T|Z)} = \frac{0.001 \cdot 0.95}{0.001 \cdot 0.95 + 0.999 \cdot 0.05} \sim \frac{0.001}{0.05} = 0.02.\)
Komentarz
Jeśli sądziłeś, tak jak większość ankietowanych lekarzy, że \(P(C|T)\) jest bliskie \(0.95\), to spróbuj w tej chwili znaleźć prosty powód dla którego wynik ten nie jest możliwy.
Aby zobaczyć, że wynik ten nie jest możliwy wystarczy wykonać prosty eksperyment myślowy. Losowo wybrana osoba jest chora z prawdopodobieństwem \(0.001\). Jeśli na losowo wybranej osobie przeprowadzimy test, to da on wynik pozytywny z prawdopodobieństwem co najmniej \(0.05\), niezależnie od tego, czy osoba ta jest chora, czy nie. Gdyby faktycznie zachodziło \(P(C|T) \sim 0.95\), to oznaczałoby to, że prawdopodobieństwo tego, że mamy do czynienia z osobą chorą w magiczny sposób rośnie tylko przez to, że ją badamy.
Należy jednak przyznać, że odpowiedzi udzielane przez lekarzy nie są aż tak bardzo odległe od prawdy jak mogłoby nam się wydawać. Lekarze nie są bowiem przyzwyczajeni do pacjentów, którzy są losowo wybierani z całej populacji. U pacjentów, którzy są poddawani testom medycznym z reguły występują objawy zgodne z diagnozowaną chorobą. W takiej sytuacji \(P(C)\) jest dużo większe, niż odpowiednia wartość dla całej populacji.
Sposób w jaki obliczyliśmy \(P(T)\) jest szczególnym przypadkiem bardzo przydatnego twierdzenia:
Twierdzenie 2.7(Wzór na prawdopodobieństwo całkowite)
Niech \(B,A_1,A_2,\ldots \subseteq \Omega\) będą takie, że \(P(A_k) > 0\) dla wszystkich \(k\), i ponadto niech zbiory \(A_1,A_2,\ldots\) stanowią podział \(\Omega\), t.j. niech będą parami rozłączne i \(A_1 \cup A_2 \cup \ldots = \Omega\). Wtedy
\(P(B) = \sum_{k=1}^\infty P(A_k) P(B|A_k).\)
Dowód
\(P(B) = P(B \cap (A_1 \cup A_2 \cup \ldots)) = P((B \cap A_1) \cup P((B \cap A_2) \cup \ldots) = \sum_{k=1}^\infty P(B \cap A_k) = \sum_{k=1}^\infty P(A_k) P(B|A_k).\)
O wzorze na prawdopodobieństwo całkowite można myśleć jako o metodzie obliczania prawdopodobieństwa "przez przypadki", ew. metodą "dziel i rządź". Ze wzoru tego w prosty sposób wynika tzw. wzór Bayesa, który jest uogólnieniem sposobu, w jaki obliczaliśmy \(P(C|T)\).
Twierdzenie 2.8 (Wzór Bayesa)
Niech \(B,A_1,A_2,\ldots\) będą takie jak poprzednio. Wtedy
\(P(A_i|B) = \frac{P(A_i \cap B)}{P(B)}=\frac{P(A_i)P(B|A_i)}{\sum_{k=1}^\infty P(A_k) P(B|A_k)} .\)
Dowód
Teza została sformułowana w taki sposób, że od razu jest swoim dowodem.
Uwaga
Zarówno wzór na prawdopodobieństwo całkowite, jak i twierdzenie Bayesa zachodzą także dla skończonych podziałów \(\Omega\), dowody są analogiczne do przedstawionych powyżej. Nie wynika to wprost z wersji dla podziałów nieskończonych ze względu na założenie \(P(A_k)>0\).
Warto w tym miejscu zaznaczyć, że twierdzenie Bayesa jest fundamentalnym narzędziem probabilistycznym o licznych zastosowaniach. Duża część z nich ma następujący charakter:
A oto kilka przykładowych sytuacji tego typu, z zupełnie różnych dziedzin:
Rozumowania tego typu nazywa się wnioskowaniem Bayesowskim.
Omówimy teraz tzw. "metodę drzewkową", której podstawę teoretyczną stanowią rozważania tego rozdziału. Moglibyśmy metodę tę omówić na przykładzie testu medycznego. Użyjemy jednak nieco innego przykładu, bardziej typowego zastosowania tej metody.
Przykład 2.9
Mamy dwie urny z kulami. W każdej z urn znajduje się pewna liczba kul białych i czarnych, znamy dokładnie zawartości obu urn. Wybieramy losowo urnę, a następnie z wybranej urny losujemy dwie kule. Jakie jest prawdopodobieństwo tego, że obie kule są czarne?
Zdefiniujmy następujące zdarzenia:
Rozwiązanie zadania mogłoby wyglądać tak:
\( P(B_1 \cap B_2) = P(U_1 \cap B_1 \cap B_2) + P(U_2 \cap B_1 \cap B_2) = P(U_1) P(B_1 | U_1) P(B_2 | U_1 \cap B_1) + P(U_2) P(B_1 | U_2) P(B_2 | U_2 \cap B_1).\)
Wszystkie prawdopodobieństwa występujące w ostatnim wyrażeniu są łatwe do obliczenia jeśli znamy zawartości urn.
W metodzie drzewkowej reprezentujemy wszystkie możliwe przebiegi losowania za pomocą drzewa.
TUTAJ OBRAZEK
Krawędzie na najwyższym poziomie odpowiadają wyborowi urny, krawędzie na drugim poziomie - losowaniu pierwszej kuli, krawędzie na trzecim poziomie - losowaniu drugiej kuli. Liczby na krawędziach są odpowiednimi prawdopodobieństwami warunkowymi. Jeśli na przykład wybraliśmy urnę pierwszą i wylosowaliśmy z niej kulę czarną (\(U_1 \cap B_1\)), to prawdopodobieństwo wylosowania kolejnej kuli czarnej, czyli przejścia do zdarzenia \(U_1 \cap B_1 \cap B_2\) wynosi \( P(B_2 | U_1 \cap B_1)\).
W przypadku krawędzi wychodzących z korzenia mamy do czynienia z prawdopodobieństwami absolutnymi, choć oczywiście można uznać, że korzeń odpowiada zdarzeniu \(\Omega\), i wtedy mamy \(P(U_i|\Omega) = P(U_i)\).
Ze wzoru iloczynowego wynika, że prawdopodobieństwo znalezienia się w konkretnym wierzchołku jest równe iloczynowi liczb na ścieżce od korzenia do tego wierzchołka. W szczególności, aby znaleźć \(P(B_1 \cap B_2)\) sumujemy \(P(U_1 \cap B_1 \cap B_2)\) oraz \(P(U_2 \cap B_1 \cap B_2)\) mnożąc liczby na odpowiednich ścieżkach.
Takie "graficzne" rozwiązanie wydaje się bardziej intuicyjne niż nasze pierwsze podejście sprowadzające się do przekształceń algebraicznych, i rzeczywiście często jest bardziej intuicyjne. Używając metody drzewkowej należy jednak być bardzo ostrożnym. Aby narysować drzewo scenariuszy często nie potrzebujemy formalnie definiować wszystkich istotnych zdarzeń (w praktyce często się tego nie robi). Zamiast tego zadowalamy się niezbyt formalnymi opisami sytuacji, którym odpowiadają poszczególne wierzchołki. Ten brak formalizmu często prowadzi do uznania rozwiązania błędnego (ew. rozwiązania innego problemu) za poprawne.
Naszą motywacją do zdefiniowania pojęcia prawdopodobieństwa warunkowego było nadanie sensu pytaniom takim jak w przykładzie 2.1. Okazało się jednak, że prawdopodobieństwo warunkowe może służyć także do formułowania założeń dotyczących zależności między zdarzeniami, np. wartości \(P(T|C)\) w przykładzie 2.1, czy wartości \(P(B_1|U_1)\) w przykładzie 2.9. To drugie zastosowanie pojęcia prawdopodobieństwa warunkowego jest o tyle interesujące, że pozwala ono często unikać formalnej definicji zbioru zdarzeń elementarnych \(\Omega\). Zamiast tego postulujemy pewne zależności między prawdopodobieństwami interesujących nas zdarzeń. Tak właśnie postępujemy we wszystkich przykładach omówionych w tym rozdziale, z wyjątkiem przykładu 2.2.
Przykład 3.1
Przypomnijmy z poprzedniego wykładu przykład 2.2, w którym kolega zdradza nam sumę oczek z dwóch kostek. Przyjmijmy, że zamiast sumy pytamy go o wynik z pierwszej kostki i okazuje się, że było to 5. Jakie jest prawdopodobieństwo tego, że na drugiej kostce wypadło co najwyżej 2?
Do rozwiązania tego problemu moglibyśmy oczywiście użyć metody z poprzedniego wykładu, ale nie jest to konieczne. Wydaje nam się bowiem intuicyjnie oczywiste, że prawdopodobieństwo to jest równe \(\frac{1}{3}\), tzn. jest dokładnie takie, jakie byłoby gdybyśmy w ogóle nie pytali.
Spróbujmy zbadać tę sytuację nieco bardziej formalnie. Jeśli przez \(A\) oznaczymy zdarzenie odpowiadające wypadnięciu 5-ki na pierwszej kostce, a przez \(B\) wypadnięciu co najwyżej 2-ki na drugiej kostce, to sądzimy, że powinno zachodzić:
\( P(B|A) = P(B) \),
czyli
\( P(A \cap B) = P(A) P(B) \).
Drugi z wzorów ma tę zaletę, że jest określony nawet jeśli \(P(A)=0\) i to właśnie on jest podstawą definicji niezależności zdarzeń.
Definicja (niezależność dwóch zdarzeń)
Zdarzenia \(A,B \subseteq \Omega\) nazywamy niezależnymi jeśli \(P(A \cap B) = P(A) P(B)\).
W sytuacji z przykładu 3.1 rozważane zdarzenia są niejako "fizycznie niezależne", opisują one wyniki rzutów dwiema różnymi kostkami. Należy jednak pamiętać, że zdarzenia mogą być niezależne w sensie powyższej definicji, nawet jeśli opisują wyniki tych samych eksperymentów. Dobrze pokazuje to poniższy przykład.
Przykład 3.2
Rzucamy 3 razy monetą. Zdefiniujmy następujące zdarzenia:
Mamy \(P(A)= \frac{1}{2}\) (np. z symetrii) oraz \(P(B) = \frac{3}{4}\) (bo z 8 zdarzeń elementarnych odrzucamy tylko 2). Ponadto \(A \cap B\) odpowiada wypadnięciu dokładnie jednej reszki, więc \(P(A \cap B) = \frac{3}{8}\). Czyli zachodzi \(P(A \cap B) = P(A)P(B)\) pomimo tego, że zdarzenia \(A\) i \(B\) wydają się być od siebie zależne.
Ten przykład pokazuje, że o pojęciu niezależności należy myśleć w terminach informacji, t.j. "czy zajście zdarzenia \(A\) daje mi dodatkową informację na temat zajścia zdarzenia \(B\)?", a nie w terminach związków fizycznych między zdarzeniami.
Na koniec naszych rozważań na temat definicji niezależności zauważmy następujący fakt:
Fakt 3.3
Jeśli zdarzenia \(A,B\) są niezależne, to niezależne są też zdarzenia \(A,\bar{B}\) oraz \(\bar{A},\bar{B}\).
Dowód
Intuicyjnie powyższy fakt jest oczywisty. Jeśli zajście \(B\) nie mówi nam nic o \(A\), to nie zajście \(B\) też nie powinno. Formalnie możemy rozumować tak:
\(P(A \cap \bar{B}) = P(A) - P(A \cap B) = P(A) - P(A)P(B) = P(A)(1-P(B)) = P(A) P(\bar{B}).\)
Druga część tezy wynika natychmiast z pierwszej zaaplikowanej do zdarzeń \(\bar{B},A\).
Jak zdefiniować niezależność więcej niż dwóch zdarzeń? Naturalnym pomysłem jest zażądanie, aby każda para zdarzeń była niezależna, ale nie jest to pomysł szczególnie dobry, co ilustruje poniższy przykład.
Przykład 3.4
Rzucamy dwukrotnie monetą. Definiujemy następujące zdarzenia:
Łatwo sprawdzić, że \(P(O_1) = P(O_2) = P(S) = \frac{1}{2}\).
Ponadto \( O_1 \cap O_2 = O_1 \cap S = O_2 \cap S \) i wspólne prawdopodobieństwo każdego z tych zbiorów wynosi \(\frac{1}{4}\), a zatem każda para zdarzeń jest niezależna. Zauważmy jednak, że z podanej przez nas równości wynika, że zajście którychkolwiek dwóch zdarzeń implikuje zajście trzeciego. Intuicyjnie takie zdarzenia nie powinny być niezależne.
Aby poradzić sobie z sytuacjami takimi jak powyższa, definiujemy niezależność w nieco bardziej restrykcyjny sposób
Definicja (niezależność wielu zdarzeń)
Zdarzenia \(A_1,A_2,\ldots,A_n\) nazywamy niezależnymi jeśli dla dowolnego ciągu indeksów \(i_1 < i_2 < \ldots < i_k\) zachodzi
\( P(A_{i_1} \cap \ldots \cap A_{i_k}) = P(A_{i_1}) \cdot \ldots \cdot P(A_{i_k}) \).
Tak jak w przypadku dwóch zdarzeń, w powyższym warunku możemy dowolną kombinację zdarzeń zastąpić przez ich dopełnienia i otrzymamy definicję równoważną:
Fakt 3.5
Niech \(A_1,A_2,\ldots,A_n\) będą niezależne, i niech ponadto zdarzenia \(B_1,\ldots,B_n\) będą takie, że dla każdego \(i\) zachodzi \(B_i = A_i\) lub \(B_i = \bar{A_i}\). Wtedy zdarzenia \(B_1,B_2,\ldots,B_n\) są niezależne.
Dowód
Przypadek \(n=2\) rozważaliśmy wcześniej. Przypomnijmy, że najpierw pokazaliśmy tezę dla sytuacji, w której tylko jedno ze zdarzeń \(B_i\) jest dopełnieniem odpowiedniego \(A_i\), a następnie z tego wywnioskowaliśmy tezę dla sytuacji, gdy są dwa takie \(B_i\).
Dowód w ogólnym przypadku jest analogiczny, ale musimy użyć indukcji po liczbie \(B_i\) takich, że \(B_i = \bar{A_i}\).
Przyjmijmy, że dla każdego ciągu \(i_1 < i_2 < \ldots < i_k\) takiego, że dla nie więcej niż \(m\) indeksów \(j\) zachodzi \(B_{i_j} = \bar{A_{i_j}}\) pokazaliśmy już tożsamość
\( P(B_{i_1} \cap \ldots \cap B_{i_k}) = P(B_{i_1}) \cdot \ldots \cdot P(B_{i_k}) \).
Chcemy pokazać, że tożsamość ta zachodzi także dla ciągów, dla których równość \(B_{i_j} = \bar{A_{i_j}}\) zachodzi dla \(m+1\) indeksów.
Bez straty ogólności przyjmijmy, że \(i_j = j\) dla wszystkich \(j = 1,\ldots,k\) oraz \(B_k = \bar{A_k}\). Wtedy mamy:
\(P(B_1 \cap \ldots \cap B_k) = P(B_1 \cap \ldots \cap B_{k-1}) - P(B_1 \cap \ldots \cap B_{k-1} \cap A_k) = P(B_1)\cdot\ldots\cdot P(B_{k-1})(1-P(A_k)) = P(B_1)\cdot\ldots\cdot P(B_{k}) ,\)
gdzie dwukrotnie korzystamy z założenia indukcyjnego.
Nasz nieudany pomysł na definicję niezależności też ma swoją nazwę i miejsce w teorii prawdopodobieństwa:
Definicja (niezależność parami)
Zdarzenia \(A_1,A_2,\ldots,A_n\) nazywamy parami niezależnymi jeśli dla każde dwa zdarzenia spośród \(A_1,A_2,\ldots,A_n\) są niezależne.
W sytuacji j.w. mówi się też czasem o 2-niezależności, i ogólniej o k-niezależności, jeśli niezależny jest każdy podzbiór \(k\) zdarzeń.
Po co definiujemy niezależność? Doświadczony probabilista byłby zapewne w stanie omawiać to zagadnienie całymi godzinami. W przypadku naszego elementarnego wykładu odpowiedź jest jednak dość prosta. Niezależność z jednej strony często występuje w interesujących nas doświadczeniach losowych, z drugiej ma bardzo prosty opis w naszej teorii i niezmiernie upraszcza wiele rozważań. W związku z tym niezależność jest bardzo wygodnym założeniem.
Jeśli na przykład wykonujemy 3 rzuty kostką, to sensownie jest przyjąć, że zdarzenia odpowiadające wynikom z różnych kostek są niezależne. Ale skoro tak, to obliczanie prawdopodobieństwa dowolnych zdarzeń można, korzystając z niezależności, sprowadzić do obliczania zdarzeń dotyczących jednej kostki.
I ogólniej: jeśli wykonujemy szereg doświadczeń i sądzimy, że zdarzenia odpowiadające ich wynikom są niezależne, to możemy obliczanie prawdopodobieństw dowolnych zdarzeń sprowadzić do obliczania zdarzeń dotyczących pojedynczych doświadczeń.
W tym sensie można myśleć o niezależności (podobnie jak prawdopodobieństwie warunkowym) jako o metodzie budowania modelu probabilistycznego. Metoda ta polega na odpowiednim komponowaniu mniejszych modeli odpowiadających niezależnym aspektom modelowanego zjawiska.
Rozważania z poprzedniego paragrafu można sformalizować. Choć nie będziemy nigdy wprost z korzystać z rozważań, które za chwilę przeprowadzimy, implicite będą się one pojawiać wielokrotnie. Dlatego warto się z nimi zapoznać pomimo tego, że są one nieco bardziej wymagające matematycznie.
Rozważmy dwa doświadczenia \(D_1, D_2\) takie, że zdarzenia odpowiadające wynikom \(D_1\) są niezależne od zdarzeń odpowiadających wynikom \(D_2\). Dla uproszczenia będziemy w takiej sytuacji po prostu mówić, że same doświadczenia są niezależne. Przyjmijmy, że wynik doświadczenia \(D_1\) jest modelowany przestrzenią \((\Omega_1,P_1)\), a wynik \(D_2\) przestrzenią \((\Omega_2,P_2)\). Jak zdefiniować przestrzeń \((\Omega,P)\) dla doświadczenia \(D\) polegającego na niezależnym wykonaniu \(D_1\) i \(D_2\)? Na pewno \(\Omega=\Omega_1\times \Omega_2\), ale jak zdefiniować P? Powinniśmy zagwarantować, że dla każdego \(A_1, A_2\) zachodzi \(P(A_1 \times A_2) = P(A_1 \times \Omega_2) P(\Omega_1 \times A_2) = P_1(A_1)P_2(A_2)\). Czy da się takie \(P\) znaleźć?
Jeśli \(\Omega_1\) i \(\Omega_2\) są przeliczalne, lub ogólniej jeśli \(P_1\) i \(P_2\) są skoncentrowane na przeliczalnej liczbie elementów, to wystarczy zdefiniować \(P\) na singletonach wzorem \(P( (x_1,x_2) ) = P_1(x_1)P_2(x_2)\), a następnie rozszerzyć na wszystkie zdarzenia sumując odpowiednie singletony. Łatwo sprawdzić, że tak zdefiniowane \(P\) spełnia nasze postulaty. W ogólnym przypadku musimy się odwołać do odpowiedniego twierdzenia z analizy, które gwarantuje istnienie, dla dowolnych dwóch miar \(P_1,P_2\) tzw. miary produktowej, która okazuje się być miarą \(P\), której szukamy.
Co ważne, twierdzenie o istnieniu miary produktowej zachodzi także dla przeliczalnie wielu miar. Możemy zatem z niego skorzystać do konstrukcji przestrzeni probabilistycznej opisującej łączny wynik przeliczalnie wielu niezależnych doświadczeń. Do czego może nam się to przydać? Oto przykład: Wiele doświadczeń dotyczących rzutów monetą (na przykład rzucanie do k-tego orła, itp.) wygodnie jest opisywać zakładając, że rzucamy monetą "w nieskończoność". Łatwo jest zdefiniować model probabilistyczny pojedynczego rzutu monetą. A jak zdefiniować model nieskończonego ciągu rzutów? Łatwo zauważyć, że zadanie to nie jest proste, choćby dlatego, że każdy konkretny ciąg wyników musi mieć prawdopodobieństwo 0. Z pomocą, tak jak poprzednio, przychodzi nam teoria miary, która gwarantuje istnienie odpowiedniej miary produktowej.
Powyższą dyskusję należy traktować jako nieco bardziej formalne uzasadnienie tego, że postulaty w rodzaju "Ponieważ te dwa zdarzenia powinny być niezależne, postuluję aby \(P(A \cap B) = P(A)P(B) \)" dają się zrealizować na gruncie naszej teorii.
Dotychczas nie nakładaliśmy żadnych warunków na to jak wyglądają elementy \(\Omega\). Mogły to być pary liczb, słonie, czy słowa TAK i NIE. Nie miało to dla nas większego znaczenia. Wyobraźmy sobie jednak, że chcemy obliczyć średnią sumę oczek z dwóch kostek albo wykonać histogram wagi słonia. Jak zinterpretować te zadania w obrębie naszej teorii?
Zarówno suma oczek na kostkach, jak i waga słonia, są pewnymi funkcjami, określonymi na odpowiednim \(\Omega\) i przypisującymi każdemu zdarzeniu elementarnemu pewną interesującą nas cechę, która jest liczbą rzeczywistą. W pierwszym przypadku każdemu wynikowi rzutu dwiem kostkami przypisujemy sumę oczek, w drugim każdemu słoniowi jego wagę. Obliczanie średniej i wykonywanie histogramu będzie się odbywać na wartościach tak zdefiniowanej funkcji.
Uwaga 4.1
Definicje i rozważania w tym paragrafie nie są do końca poprawne, ale za to są zupełnie elementarne. Poprawiamy je w następnym paragrafie poświęconym teorii miary.
Prawie definicja (Zmienna losowa)
Niech \( (\Omega,P) \) będzie przestrzenią probabilistyczną. Zmienną losową (określoną na \(\Omega\)) nazywamy dowolną funkcję \(X:\Omega \rightarrow \mathbb{R}\).
Jak widać, wbrew swojej nazwie, zmienne losowe nie są wcale zmiennymi, nie są też w żadnym sensie losowe.
Przykład 4.2
Rzut dwiema kostkami można w naturalny sposób opisać przestrzenią probabilistyczną \( ( \Omega, P) \), gdzie \( \Omega = \{ (i,j) : 1 \le i,j \le 6 \} \), a \(P\) jest zadane schematem klasycznym. Na takiej przestrzeni można określić zmienną losową \(X\) opisującą sumę oczek następująco:
\( X( (i,j) ) = i+j \).
Podobnie możemy postąpić dla iloczynu oczek, oczek na pierwszej kostce, itp.
Zmiennej losowej można użyć do definiowania zdarzeń w jej dziedzinie. Na przykład, za pomocą opisanej powyżej zmiennej \(X\) możemy zdefiniować zdarzenia:
Formalnie, napis \(X \in A\) będziemy interpretować jako zdarzenie \( \{\omega \in \Omega : X(\omega) \in A\} = X^{-1}(A)\), i analogicznie napisy \(X = a\), \(X \le a\), itp.
Można pójść z tą notacją jeszcze dalej, np. \( sin(X) > X/20 \). Dowolny napis postaci \(\phi(X)\), gdzie \(\phi(x)\) jest formułą logiczną zmiennej \(X\) możemy zinterpretować jako \( \{ \omega \in \Omega : \phi(X(\omega))\} = (X \circ \phi)^{-1}(prawda)\).
Nic też nie stoi na przeszkodzie, aby definiować zdarzenia za pomocą więcej niż jednej zmiennej. Jeśli na przykład \(X\) jest, jak poprzednio, sumą oczek z dwóch kostek, a \(Y\) iloczynem, to możemy zdefiniować zdarzenie "suma oczek jest większa niż iloczyn" napisem \( X > Y\). Tak jak poprzednio, dla dowolnej formuły logicznej \(\phi(x,y)\) i zmiennych \(X,Y\) definiujemy zdarzenie \(\phi(X,Y)\) jako \( \{\omega \in \Omega : \phi(X(\omega),Y(\omega))\} \).
W naturalny sposób możemy interpretować formuły trzech i więcej zmiennych.
Jeśli interesują nas własności zmiennej losowej \(X\) takie jak jej średnia wartość, tak czy inaczej zdefiniowany rozrzut wartości itp., to dziedzina \(X\) oraz to jak konkretnie \(X\) jest zdefiniowana nie mają dla nas znaczenia. Cała istotna informacja o zmiennej \(X\) jest zawarta w tzw. rozkładzie \(X\).
Prawie definicja (Rozkład zmiennej losowej)
Rozkładem zmiennej losowej \(X\) nazywamy przestrzeń probabilistyczną \( (\mathbb{R},P_X) \), gdzie
\(P_X(A) = P(X \in A) = P(X^{-1}(A)) \).
Będziemy też pisać \(X \sim Y\), jeśli \(X\) i \(Y\) mają taki sam rozkład.
Nasze dotychczasowe rozważania zawierają niestety drobną lukę logiczną. Otóż w definicji rozkładu \(X\) pojawia się prawdopodobieństwo \(P(X^{-1}(A))\), ale nie jest wcale powiedziane, że wartość ta jest określona. Zgodnie z definicją, przestrzeń probabilistyczna jest trójką \( (\Omega, \mathcal{F},P) \). Umówiliśmy się pomijać \(\sigma\)-ciało \(\mathcal{F}\) wszędzie tam, gdzie jest ono równe \(2^\Omega\) lub po prostu nie ma znaczenia. W przypadku definicji zmiennej losowej \(\mathcal{F}\) ma znaczenie - musimy zagwarantować, że \(X^{-1}(A) \in \mathcal{F}\) dla tych zbiorów \(A\), na których ma być określony rozkład \(X\).
Przyjmiemy, że rozkład ma być określony na borelowskich podzbiorach \(\mathbb{R}\), co prowadzi do następującej definicji zmiennej losowej:
Definicja (Zmienna losowa)
Niech \( (\Omega,\mathcal{F},P) \) będzie przestrzenią probabilistyczną. Zmienną losową (określoną na \(\Omega\)) nazywamy dowolną funkcję \(X:\Omega \rightarrow \mathbb{R}\) taką, że dla dowolnego zbioru borelowskiego \(A \subseteq \mathbb{R}\) zachodzi \(X^{-1}(A) \in \mathcal{F}\) (czyli \(f\) musi być mierzalna względem \(\mathcal{F}\) ).
Z kolei rozkład zmiennej losowej definiujemy następująco (uzupełniamy poprzednią definicję wskazując, które zbiory będą mierzalne):
Definicja (Rozkład zmiennej losowej)
Rozkładem zmiennej losowej \(X\) nazywa przestrzeń probabilistyczną \(\mathbb{R},\mathcal{B},P_X\), gdzie \(\mathcal{B}\) jest rodziną borelowskich podzbiorów \(\mathbb{R}\) oraz
\(P_X(A) = P(X \in A) = P(X^{-1}(A)) \).
Założenie mierzalności funkcji będzie się pojawiać w tym i dalszych wykładach jeszcze kilkukrotnie. Za każdym razem jest to motywowane rozważaniami, które właśnie przeprowadziliśmy.
Omówimy teraz kilka najbardziej typowych rozkładów zmiennych losowych, przy czym przez najbliższych kilka wykładów ograniczymy się do tzw. rozkładów dyskretnych.
Definicja (Rozkład dyskretny)
Zmienna \(X\) ma rozkład dyskretny (lub krócej: jest dyskretna) jeśli zachodzi
\( \sum_{x \in \mathbb{R}} P(X=x) = 1.\)
Innymi słowy, z prawdopodobieństwem \(1\) zmienna \(X\) przyjmuje jedną z przeliczalnie wielu wartości.
Uwaga 4.3
W powyższej definicji pojawia się suma po zbiorze nieprzeliczalnym, co może budzić pewne zaniepokojenie. Proszę jednak zwrócić uwagę, że tylko przeliczalnie wiele wartości w tej sumie może być niezerowych na mocy przeliczalnej addytywności prawdopodobieństwa. W dalszej części wykładu będziemy dość często używać tego rodzaju notacji.
Przykład 4.4
Łatwo podać przykład zmiennej dyskretnej - na przykład liczba rzutów do wypadnięcia pierwszego orła. Przykładem zmiennej niedyskretnej jest czas \(T\) oczekiwania w kolejce. O ile nie jest to bardzo nietypowa kolejka, to dla każdej liczby \(t > 0\) zachodzi \(P(T=t) = 0\) (może się zdarzyć, że \(P(T=0) > 0\)). A zatem \(\sum_{t \in \mathbb{R}} P(T=t) = P(T=0)\) i z reguły jest to wartość mniejsza niż \(1\). Zmiennymi tego rodzaju zajmiemy się za kilka wykładów.
W tym wykładzie interesować nas będą wyłącznie zmienne dyskretne. Co więcej, z reguły będą one przyjmować jedynie wartości naturalne.
Poniższy fakt opisuje bardzo przydatną własność zmiennych dyskretnych, często uznaje się go wręcz za ich definicję:
Fakt 4.5
Jeśli \(X\) jest zmienną dyskretną, a \(A \subseteq \mathbb{R}\), to
\(P(X \in A) = \sum_{x \in A} P(X=x).\)
Dowód
Zachodzi oczywiście \(P(X \in A) \ge \sum_{x \in A} P(X=x)\) na mocy przeliczalnej addytywności prawdopodobieństwa. Podobnie \(P(X \not\in A) \ge \sum_{x \not\in A} P(X=x)\). Dodając stronami dostajemy \(1 \ge 1\), a równość jest możliwa tylko jeśli zachodzi teza.
Fakt 4.5 pokazuje, że cała informacja o zmiennej dyskretnej \(X\) jest zawarta w wartościach \(P(X=x)\). Często wprowadza się oznaczenie \(f_X(x) = P(X=x)\), a funkcję \(f_X\) nazywa się funkcją prawdopodobieństwa \(X\). Nie będziemy tego jednak robić w tym wykładzie.
Przyjrzymy się teraz kilku najważniejszym rozkładom dyskretnym.
Definicja (Rozkład Bernoulliego)
Zmienna \(X\) ma rozkład Bernoulliego jeśli przyjmuje tylko dwie wartości: 0 i 1. Prawdopodobieństwa tych wartości oznacza się zwyczajowo: \(p = P(X=1)\) oraz \(q = P(X=0)\). Wartość 1 nazywa się często sukcesem, a wartość 0 porażką.
Zmienne takie pojawiają się w naturalny sposób, jeśli przeprowadzamy pewne doświadczenie i interesuje na to, czy zakończyło się ono w konkretny sposób, np. w rzucie monetą wypadł orzeł bądź nie, pacjent przeżył operację bądź nie, itp. Jak wkrótce zobaczymy, zmienne o rozkładzie Bernoulliego pełnią często rolę "klocków", z których składa się bardziej skomplikowane zmienne.
Definicja (Rozkład jednostajny (dyskretny))
Zmienna \(X\) ma dyskretny rozkład jednostajny na przedziale \([a,b]\) , gdzie \(a,b \in \mathbb{Z}\) , jeśli przyjmuje wartości \(a,a+1,\ldots,b\), przy czym wszystkie one są równie prawdopodobne, t.j. \(P(X=a) = \ldots = P(X=b) = \frac{1}{b-a+1}\).
Rozkład jednostajny ma na przykład liczba oczek na kostce, czy wynik losowania liczby naturalnej z zadanego przedziału (ten drugi przykład jest dość marny, jako że jest właściwie równoważny definicji).
Przykład 4.6
Rzucamy \(n\) razy monetą, na której orzeł wypada z prawdopodobieństwem \(p\). Niech \(X\) będzie liczbą orłów. Jaki rozkład ma \(X\)?
Mamy oczywiście \(P(X=k) = 0\) dla \(k \not \in \{0,\ldots,n\}\). Jeśli \(k \in \{0,\ldots,n\}\), to mamy \({n \choose k}\) różnych sposobów na uzyskanie \(k\) orłów. Korzystając z niezależności zdarzeń odpowiadających wynikom różnych rzutów łatwo pokazać, że prawdopodobieństwo dla każdego z tych sposobów jest równe \(p^k(1-p)^{n-k}\). A zatem \(P(X=k) = {n \choose k}p^k(1-p)^{n-k}\).
Definicja (Rozkład dwumianowy)
Zmienna \(X\) ma rozkład dwumianowy z parametrami \(n,p\), ozn. \(X \sim Binom(n,p)\), jeśli \(P(X=k) = {n \choose k}p^k(1-p)^{n-k}\) dla \(k=0,\ldots,n\) i \(P(X=k)=0\) dla pozostałych \(k\).
Ciąg niezależnym doświadczeń (tzw. prób), z których każda kończy się sukcesem z tym samym prawdopodobieństwem, nazywamy ciągiem prób Bernoulliego (wynik każdej z prób jest zmienną o rozkładzie Bernoulliego!). Zmienna o rozkładzie dwumianowym opisuje liczbę sukcesów w ciągu prób Bernoulliego.
Uwaga 4.7
Notację \(X \sim Binom(n,p)\) można traktować jako sposób zapisania faktu, że zmienna \(X\) ma rozkład dwumianowy. Można też przyjąć, że \(Binom(n,p)\) jest pewną wzorcową zmienną o rozkładzie dwumianowym i wtedy napis \(X \sim Binom(n,p)\) oznacza, że obie zmienne mają ten sam (dwumianowy) rozkład.
Przykład 4.8
Rzucamy monetą, na której orzeł wypada z prawdopodobieństwem \(p\) aż do uzyskania pierwszego orła. Niech \(X\) będzie liczbą rzutów (łącznie z rzutem, w którym wypadł orzeł). Jaki rozkład ma \(X\)?
Oczywiście \(P(X=k) > 0\) tylko dla \(k \in \mathbb{N}\setminus \{0\}\). Mamy \(P(X=1) = p\). Korzystając z niezależności dostajemy \(P(X=2) = (1-p)p\) i ogólnie \(P(X=k) = (1-p)^{k-1}p\).
Definicja (Rozkład geometryczny)
Zmienna \(X\) ma rozkład geometryczny z parametrem \(p\), ozn. \(X \sim Geom(p)\), jeśli \(P(X=k) = (1-p)^{k-1}p\) dla \(k \in \mathbb{N}\{0\}\) i \(P(X=k)=0\) dla pozostałych \(k\).
Zmienna o rozkładzie geometrycznym opisuje numer pierwszej próby zakończonej sukcesem w ciągu prób Bernoulliego.
Przykład 4.9
Kierownik laboratorium komputerowego otrzymuje średnio \(\lambda\) informacji o awarii komputera na miesiąc. Niech \(X\) będzie liczbą takich informacji w konkretnym miesiącu. Jaki rozkład ma \(X\)?
Podzielmy miesiąc na \(n\) przedziałów czasowych. Załóżmy, że \(n\) jest na tyle duże, że prawdopodobieństwo otrzymania dwóch informacji o awarii w jednym przedziale jest zaniedbywalne. Załóżmy ponadto, że zdarzenia odpowiadające otrzymaniu informacji o awarii w różnych przedziałach są niezależne. Wtedy mamy do czynienia z ciągiem \(n\) prób Bernoulliego. Jakie jest prawdopodobieństwo sukcesu (niezbyt satysfakcjonującego, ale trzymajmy się konwencji)? Skoro spośród \(n\) przedziałów średnio \(\lambda\) powinno zawierać awarię, to intuicyjnie prawdopodobieństwo sukcesu \(p\) powinno być równe \(\frac{\lambda}{n}\). Wydaje się więc, że rozkład naszej zmiennej \(X\) jest dobrze przybliżany przez \(Binom(n,\frac{\lambda}{n})\) dla dużych \(n\), t.j.
\(P(X=k) \sim {n \choose k} (\frac{\lambda}{n})^k (1-\frac{\lambda}{n})^{n-k}\).
Można pokazać (ćwiczenia), że dla \(n \rightarrow \infty\) wyrażenie to zbiega do \( \frac{e^{-\lambda}\lambda^k}{k!}\).
Powyższe rozwiązanie ma oczywiście w jakimś stopniu charakter heurystyczny. W szczególności nie jest wcale jasne, czy nasze założenia są spełnione. Może być na przykład tak, że awarie komputerów mają tendencję do występowania razem (mogą być na przykład powodowane awariami zasilania). Wtedy poszczególne próby nie byłyby niezależne. Okazuje się jednak, że otrzymany przez nas wzór bardzo dobrze opisuje wiele sytuacji praktycznych.
Definicja (Rozkład Poissona)
Zmienna \(X\) ma rozkład Poissona z parametrem \(\lambda\), ozn. \(X \sim Pois(\lambda)\), jeśli \(P(X=k) = \frac{e^{-\lambda}\lambda^k}{k!}\) dla \(k \in \mathbb{N}\) i \(P(X=k)=0\) dla pozostałych \(k\).
Rozkład Poissona dobrze opisuje procesy podobne do sytuacji opisanej w przykładzie 4.9: liczbę telefonów odebranych w centrum obsługi klienta przez godzinę, liczbę błędów ortograficznych na \(1000\) znaków rękopisu, itp.
Istnieje jeszcze inne, nieco zaskakujące, zastosowanie rozkładu Poissona. Zwróćmy uwagę, że rozkład Poissona uzyskaliśmy jako granicę rozkładów dwumianowych z dużym \(n\), małym \(p\) i \(np = \lambda\). W związku z tym można użyć rozkładu Poissona \(Pois(np)\) do przybliżenia rozkładu dwumianowego \(Binom(n,p)\) o ile tylko \(n\) jest duże (\(n\) powinno być dużo większe niż interesująca nas liczba sukcesów \(k\)), a \(p\) małe. Co ciekawe, prowadzi to z reguły do prostszych rachunków.
Przykład 4.10
Gramy \(n=1000000\) razy w loterii, w której prawdopodobieństwo wygrania wynosi \(p=\frac{1}{500000}\). Jakie jest prawdopodobieństwo tego, że wygramy dokładnie \(k=2\) razy?
Liczba wygranych ma rozkład \(Binom(n,p)\), a zatem szukane prawdopodobieństwo jest równe
\( {n \choose 2}p^2 (1-p)^{n-2}.\)
Trzeba to jeszcze tylko obliczyć...
Możemy jednak uniknąć rachunków zauważając, że dla małych \(k\) (a nasze \(k\) jest bardzo małe) możemy uzyskać dobre przybliżenie odpowiedzi korzystając z rozkładu \(Pois(np)\) . Tym razem dostajemy dużo prostszy wzór
\( \frac{e^{-2} 2^2}{2} = \frac{2}{e^2} \sim 0.27.\)
Ponieważ napisy \(X \in A\) czy \(X \ge Y\) interpretujemy jako zdarzenia, możemy bez żadnych dodatkowych definicji używać pojęcia prawdopodobieństwa warunkowego na przykład tak:
\(P(X \in A | B)\)
lub tak:
\(P (X \ge Y | Y \ge 1)\).
Warto w tym miejscu zwrócić szczególną uwagę na pierwsze z wyrażeń. Przypomnijmy, że para \( (\Omega,P(\cdot|B)) \) jest przestrzenią probabilistyczną. Jeśli potraktujemy \(X\) jako zmienną losową określoną na tej przestrzeni, to otrzymamy pewną nową zmienną, z reguły oznaczaną \(X|B\), dla której
\(P( X|B \in A) = P(X \in A | B)\).
Jest to często używany skrót notacyjny. Rozkład zmiennej \(X|B\) nazywa się rozkładem \(X\) pod warunkiem \(B\).
Uwaga 4.11
Nie należy mylić wprowadzonej tu notacji ze spotykaną w literaturze notacją \(X|Y\), gdzie \(X,Y\) są zmiennymi losowymi. Tej drugiej nie będziemy definiować w ramach tego wykładu.
Jak zdefiniować niezależność zmiennych losowych. Następująca intuicyjna definicja działa bardzo dobrze
Definicja (Niezależność zmiennych losowych)
Zmienne losowe \(X,Y\) są niezależne jeśli dla każdych zbiorów borelowskich \(A,B \subseteq \mathbb{R}\) zachodzi
\( P(X \in A \wedge Y \in B) = P(X \in A) P(Y \in B)\).
Uwaga 4.12
Zamiast niezależności zdarzeń \(X \in A\) i \(Y \in B\) dla dowolnych zbiorów borelowskich, można zażądać niezależności dla \(A,B\) przedziałów, lub po prostu niezależności zdarzeń \(X \le x\) i \(Y \le y\) dla dowolnych \(x,y \in \mathbb{R}\). Równoważność tych definicji wynika z definicji zbiorów borelowskich, ale jej dowód nie jest prosty.
Co ciekawe, i bardzo przydatne w obliczeniach, dla dyskretnych zmiennych losowych istnieje prostsza charakteryzacja niezależności
Fakt 4.13
Dyskretne zmienne losowe \(X,Y\) są niezależne wtedy i tylko wtedy, gdy dla każdych \(x,y \in \mathbb{R}\) zachodzi
\(P(X=x \wedge Y = y) = P(X =x) P(Y = y)\).
Dowód
Jeśli dla dowolnych \(x,y \in \mathbb{R}\) zachodzi powyższa równość, to \(X,Y\) są niezależne, bo
\(P(X \in A \wedge Y \in B) = \sum_{x \in A \wedge y \in B} P(X = x \wedge Y = y) = \sum_{x \in A \wedge y \in B} P(X = x)P(Y = y) = \sum_{x \in A} P(X = x)\sum_ {y \in B}P(Y = y) = P(X \in A) P(Y \in B)\).
Implikacja w drugą stronę jest oczywista.
Składając zmienną losową \(X\) z funkcją \(f:\mathbb{R}\rightarrow\mathbb{R}\) otrzymujemy nową zmienną losową oznaczaną \(f(X)\). Oczywiście w ogólnym przypadku musimy założyć, że funkcja \(f\) jest mierzalna.
Przykład 4.14
Jeśli \(X\) jest liczbą oczek w rzucie kostką, to:
Oczywiście zamiast pisać \(f(X)\) i definiować osobno funkcję \(f\) możemy pisać po prostu \(X^2\) czy \(X \mod 2\).
Aby upewnić się, czy dobrze rozumiemy jak składać zmienne losowe z funkcjami, sprawdźmy jak wygląda rozkład zmiennej \(f(X)\):
\( P(f(X) \in A) = P( X \in f^{-1}(A) ) \).
Nie ma powodu, dla którego mielibyśmy się ograniczać do jednej zmiennej i funkcji jednoargumentowych. Jeśli na przykład \(X,Y\) są zmiennymi losowymi, a \(f:\mathbb{R}^2 \rightarrow \mathbb{R}\) jest funkcją mierzalną, to możemy zdefiniować nową zmienną losową \(f(X,Y)\). Analogicznie postępujemy w przypadku większej liczby zmiennych.
W ten sposób, jeśli \(X,Y\) są zmiennymi losowymi, to zmienną losową jest też ich suma \(X+Y\), iloczyn \(XY\), czy nawet \(X^Y\).
Jak wygląda rozkład \(f(X,Y)\)?
\( P(f(X,Y) \in A) = P( (X,Y) \in f^{-1}(A) ).\)
Ten wzór pokazuje, że do obliczenia rozkładu zmiennej \(f(X,Y)\) nie wystarczy znajomość rozkładów zmiennych \(X\) i \(Y\). Musimy znać ich tzw. rozkład łączny tzn. prawdopodobieństwa postaci \(P(X \in A \wedge Y \in B)\).
Sytuacja jest wyjątkowo prosta jeśli zmienne \(X\) i \(Y\) są niezależne. Mamy wtedy:
\( P(f(X,Y) \in A) = P( (X,Y) \in f^{-1}(A) ) = \sum_{(x,y) \in f^{-1}(A)} P(X=x)P(Y=y).\)
W szczególności zachodzi następujący bardzo przydatny fakt:
Fakt 4.15
Jeśli \(X,Y\) są niezależnymi zmiennymi dyskretnymi, to
\(P(X+Y=k) = \sum_{x \in \mathbb{R}} P(X=x) P(Y=k-x)\).
Dowód wynika natychmiast z naszych dotychczasowych rozważań.
W poprzednim wykładzie zdefiniowaliśmy zmienną \(X\), która opisywała sumę oczek na dwóch kostkach. Jaka jest średnia wartość tej zmiennej? Zanim odpowiemy na to pytanie, zastanówmy się co ono właściwie powinno znaczyć.
Intuicyjnie, jeśli będziemy rzucać parą kostek bardzo dużo razy, to średnia z wyników będzie zbiegać do pewnej wartości i tę wartość można nazwać średnią sumą oczek. Jeśli powtórzylibyśmy rzut dwiema kostkami \(n\) razy, to spodziewamy się, że wynik \(k\) uzyskamy mniej więcej \(P(X=k)n\) razy. A zatem średnia suma z \(n\) powtórzeń będzie miała wartość bliską
\( \frac{\sum_{k=2}^{12} P(X=k)nk }{n} = \sum_{k=2}^{12} P(X=k)k\).
Ta wartość wydaje się być rozsądną definicją średniej wartości \(X\).
Uwaga 5.1
W powyższym rozumowaniu uznaliśmy, że jeśli \(n\) jest duże, to w \(n\) powtórzeniach rzutu dwiema kostkami wynik \(k\) uzyskamy mniej więcej \(P(X=k)n\) razy. Ogólniej, w \(n\) powtórzeniach pewnego doświadczenia zdarzenie \(A\) powinno wystąpić mniej więcej \(P(A)n\) razy. Warto zwrócić uwagę, że korzystamy tu z intuicji częstościowej prawdopodobieństwa, o której mówiliśmy już w pierwszym wykładzie. W szczególności nasze uzasadnienie definicji wartości oczekiwanej ma raczej charakter nieformalny. Co ciekawe, wkrótce okaże się, że intuicji częstościowej odpowiada twierdzenie w naszej teorii (szczególny przypadek tzw. Prawa Wielkich Liczb).
Definicja (Wartość oczekiwana)
Niech \(X\) będzie zmienną losową o rozkładzie dyskretnym. Wartością oczekiwaną (ew. średnią) \(X\) nazywamy wartość sumy
\(EX = \sum_{x \in \mathbb{R}} x P(X=x)\),
o ile jest ona absolutnie zbieżna.
Przykład 5.2
Założenie absolutnej zbieżności jest niejako konieczne - nie chcemy, żeby wartość \(EX\) zależała od kolejności sumowania. Z drugiej strony prowadzi ono czasem do zaskakujących wyników. Rozważmy zmienną \(X\) zdefiniowaną następująco: \(X\) przyjmuje tylko wartości postaci \(2^k\) i \(-2^k\) dla \(k \ge 2\), przy czym \(P(X=2^k) = P(X=2^{-k}) = \frac{1}{2^k}\). Zmienna ta ma rozkład symetryczny względem \(0\), intuicyjnie więc jej wartością oczekiwaną powinno być \(0\). Ponieważ jednak szereg definiujący \(EX\) nie jest absolutnie zbieżny (składa się on z nieskończenie wielu wartości \(1\) i nieskończenie wielu \(-1\)), to \(EX\) jest nieokreślone.
Przykład 5.3
Spróbujmy obliczyć wprost z definicji wartość oczekiwaną zmiennej o rozkładzie Bernoulliego i zmiennej o rozkładzie dwumianowym.
Dla \(X\) o rozkładzie Bernoulliego z prawdopodobieństwem sukcesu \(p\) mamy
\(EX = 0 \cdot P(X=0) + 1 \cdot P(X=1) = P(X=1) = p\).
Dla \(Y\) o rozkładzie dwumianowym \(Binom(n,p)\) mamy
\(EY = \sum_{k=0}^n k P(X=k) = \sum_{k=0}^n k {n \choose k}p^k(1-p)^{n-k} = n \sum_{k=1}^n \frac{k}{n}{n \choose k}p^k(1-p)^{n-k}\).
Korzystając z pochłaniania dostajemy
\( n \sum_{k=1}^n {n-1 \choose k-1}p^k(1-p)^{n-k} = np \sum_{k=0}^{n-1} {n-1 \choose k}p^k(1-p)^{n-1-k} = np\).
(bo ostatnia suma jest po prostu rozwinięciem dwumianu \((p+(1-p))^{n-1}\)).
Jest to bardzo interesujący wynik. Zmienna \(Y\) jest sumą \(n\) zmiennych \(Y_1,\ldots,Y_n\), gdzie każda ze zmiennych \(Y_i\) ma rozkład Bernoulliego z prawdopodobieństwem sukcesu \(p\). Okazuje się, że \(EY = \sum_{i=1}^n EY_i\). Czyżby wartość oczekiwana była addytywna, a nasze rozwlekłe obliczenia \(EY\) zupełnie niepotrzebne? Już wkrótce poznamy odpowiedź na to pytanie.
Bardzo przydatną i fundamentalną własność wartości oczekiwanej opisuje poniższe twierdzenie
Twierdzenie 5.4
Niech \(X:\Omega \rightarrow \mathbb{R}\) będzie dyskretną zmienną losową o skończonej wartości oczekiwanej. Niech ponadto \(\Omega\) będzie
przeliczalna, lub ogólniej, niech \(\sum_{\omega \in \Omega} P(\omega) = 1\). Wtedy:
\(EX = \sum_{\omega \in \Omega} P(\omega) X(\omega)\).
Innymi słowy: zamiast sumować po możliwych wartościach zmiennej \(X\) możemy sumować po zdarzeniach elementarnych.
Dowód
\(EX = \sum_{x \in \mathbb{R}} x P(X=x) = \sum_{x \in \mathbb{R}} x \sum_{\omega \in \Omega} P(\omega)[X(\omega) = x] = \sum_{\omega \in \Omega} P(\omega) \sum_{x \in \mathbb{R}}x [X(\omega) = x] = \sum_{\omega \in \Omega} P(\omega) X(\omega)\).
Z twierdzenia 5.4 w prosty sposób wynika następujący:
Wniosek 5.5
Jeśli \(X\) jest zmienną losową o rozkładzie dyskretnym, a \(f:\mathbb{R}\rightarrow \mathbb{R}\) dowolną funkcją, to zachodzi
\(Ef(X) = \sum_{x \in \mathbb{R}} P(X=x) f(x)\),
o ile \(Ef(X)\) istnieje.
Dowód
Wystarczy popatrzeć na \(f\) jako na zmienną losową określoną na \(\mathbb{R},P_X\), ew. powtórzyć dowód twierdzenia 5.4.
Wniosek ten okaże się bardzo przydatny przy obliczaniu wariancji - pojęcia, które wkrótce zdefiniujemy.
Twierdzenie 5.4 ma zaskakująco wiele zastosowań i warto o nim pamiętać, nawet jeśli wydaje się zupełnie oczywiste (a może właśnie szczególnie wtedy). Zobaczmy przykład:
Przykład 5.6
Spróbujmy obliczyć wartość oczekiwaną sumy oczek w rzucie dwiema kostkami. Niech \(X\) będzie zmienną opisującą sumę oczek. Wtedy z definicji \(EX\) mamy
\(EX = \sum_{k=2}^{12} kP(X=k)\).
Należałoby teraz obliczyć wszystkie wartości \(P(X=k)\). Nie jest to bardzo trudne, ale jest nieco uciążliwe i łatwo się przy tych obliczeniach pomylić.
Spróbujmy inaczej. Przyjmijmy, że \(\Omega = \{ (i,j) : 1 \le i,j \le 6\}\) i oczywiście \(P((i,j)) = \frac{1}{36}\) dla każdych \(1 \le i,j \le 6\). Wtedy \(X((i,j)) = i+j\) i z twierdzenia 5.4 mamy
\(EX = \sum_{1 \le i,j \le 6} \frac{1}{36} (i+j)\).
Oczywiście \( \sum_{1 \le i,j \le 6} i = \sum_{1 \le i,j \le 6} j \) z symetrii, więc
\(EX = \frac{1}{36} \cdot 2 \cdot \ \sum_{1 \le i,j \le 6} i = \frac{1}{18} \cdot 6 \cdot \sum_{1 \le i \le 6} i = \frac{1}{3} \cdot 21 = 7\).
Wyprowadzenie wymagające więcej spostrzegawczości niż rachunków, zdecydowanie mniej uciążliwe niż nasz pierwszy pomysł.
Twierdzenie 5.4 pozwala też w prosty sposób pokazać zapowiadaną wcześniej addytywność wartości oczekiwanej (choć nie w pełnej ogólności):
Twierdzenie 5.7(Liniowość wartości oczekiwanej)
Niech \(X,Y\) dyskretne zmienne losowe o skończonej wartości oczekiwanej. Wtedy:
Dowód
Jeśli \(\sum_{\omega \in \Omega} P(\omega) = 1\) (np. \(\Omega\) jest przeliczalna), to pierwszy punkt tezy natychmiast wynika z twierdzenia 5.4:
\(E(cX) = \sum_{\omega \in \Omega} P(\omega) cX(\omega) = c\sum_{\omega \in \Omega} P(\omega) X(\omega) = cEX\).
Drugi punkt nie jest dużo trudniejszy:
\(E(X+Y) = \sum_{\omega \in \Omega} P(\omega) (X+Y)(\omega) = \sum_{\omega \in \Omega} P(\omega) X(\omega) + \sum_{\omega \in \Omega} P(\omega) Y(\omega) = EX+EY\).
Ogólny przypadek nie jest dużo trudniejszy. Zbiory postaci \(X=x\wedge Y=y = \{\omega \in \Omega: X=x,Y=y\}\) stanowią podział \(\Omega\) i zachodzi
\( \sum_{x,y \in \mathbb{R}} P(X=x \wedge Y=y) = 1\)
bo \(X\) i \(Y\) dyskretne. Można zatem myśleć o tych zbiorach jako o elementach pewnej nowej przestrzeni probabilistycznej, na której są określone \(X\) i \(Y\) i która spełnia założenia twierdzenia 5.4. Bardziej formalnie możemy nasz dowód uogólnić następująco:
\(E(X+Y) = \sum_{z \in \mathbb{R}} P(X+Y=z) z = \sum_{z \in \mathbb{R}} \sum_{x,y | x+y=z} P(X=x \wedge Y=y) (x+y)=\sum_{x,y \in \mathbb{R}} P(X=x \wedge Y=y) (x+y) =\)
\(= \sum_{x,y \in \mathbb{R}} P(X=x\wedge Y=y) x + \sum_{x,y\in\mathbb{R}} P(X=x\wedge Y=y) y = EX+EY\).
Podobnie uogólniamy pierwszą część dowodu.
Trudno jest przecenić znaczenie tego twierdzenia - jeśli musielibyśmy wskazać w całym kursie rachunku prawdopodobieństwa jedno twierdzenie o największym znaczeniu w informatyce teoretycznej, to prawdopodobnie byłaby nim właśnie liniowość wartości oczekiwanej. Siła tego twierdzenia bierze się przede wszystkim stąd, że nie wymaga ono żadnych założeń, w szczególności zmienne \(X\) i \(Y\) nie muszą być niezależne.
Przykład 5.8
Spróbujmy raz jeszcze obliczyć oczekiwaną sumę oczek z dwóch kostek. Tym razem przedstawimy sumę oczek \(X\) jako \(X = X_1+X_2\), gdzie \(X_1,X_2\) są wynikami z poszczególnych kostek. Wtedy
\(EX = EX_1+EX_2 = 2\sum_{i=1}^6 \frac{1}{6} i = 7\).
Przykład 5.9
Wrzucamy losowo \(n\) kul do \(n\) urn. Jaka jest wartość oczekiwana frakcji pustych urn?
Niech \(X_i\) będzie zmienną, która przyjmuje wartość \(1\) jeśli \(i\)-ta urna jest pusta, a wartość \(0\) gdy nie jest pusta. Wtedy \(X=X_1+\ldots+X_n\) jest liczbą pustych urn. Mamy
\(EX_i = P(X_i=1) = (1-\frac{1}{n})^n.\)
A zatem z liniowości dostajemy
\(EX = EX_1+\ldots+EX_n = n(1-\frac{1}{n})^n \).
A zatem oczekiwana frakcja pustych urn jest równa
\( (1-\frac{1}{n})^n\).
Co ciekawe dla \( n \rightarrow \infty\) wartość ta zbiega do \(\frac{1}{e}\).
Ten przykład pokazuje siłę twierdzenia o liniowości wartości oczekiwanej. Zachęcamy czytelnika do próby rozwiązania powyższego zadania wprost z definicji.
Skoro \(E(X+Y) = EX+EY\), to naturalne wydaje się pytanie, czy zachodzi \(E(XY) = EXEY\), czyli czy wartość oczekiwana jest multiplikatywna. Łatwo zauważyć, że nie może to być prawdą - wystarczy wziąć \(X\) o rozkładzie Bernoulliego i \(Y=X\).
Okazuje się jednak, że czasem wartość oczekiwana jest multiplikatywna:
Twierdzenie 5.10
Jeśli \(X,Y\) niezależne zmienne dyskretne o skończonych wartościach oczekiwanych, to \(E(XY) = EXEY\).
Dowód
\(E(XY) = \sum_{z \in \mathbb{R}} P(XY = z) z = \sum_{z \in \mathbb{R}} \sum_{x \in \mathbb{R}\setminus \{0\}} z P(X = x \wedge Y = \frac{z}{x}) = \sum_{z \in \mathbb{R}} \sum_{x \in \mathbb{R}\setminus \{0\}} xP(X = x)\frac{z}{x}P(Y = \frac{z}{x})\).
Zmieniając kolejność sumowania i podstawiając \(y = \frac{z}{x}\) dostajemy
\(E(XY) = \sum_{x \in \mathbb{R}\setminus \{0\}} xP(X = x) \sum_{y \in \mathbb{R}} yP(Y = y) = EXEY\).
Na koniec odnotujmy bardzo przydatny wzór na wartość oczekiwaną zmiennej o wartościach naturalnych:
Twierdzenie 5.11
Niech \(X\) będzie zmienną losową o wartościach naturalnych. Wtedy \(EX = \sum_{i =1}^\infty P(X \ge i)\).
Dowód
\(EX = \sum_{i=1}^\infty iP(X=i) = \sum_{i=1}^\infty \sum_{j=1}^i P(X=i) = \sum_{j=1}^\infty \sum_{i=j}^\infty P(X=i) = \sum_{j=1}^\infty P(X \ge j)\).
Przykład
Obliczmy wartość oczekiwaną zmiennej o rozkładzie geometrycznym. Niech \(X \sim Geom(p)\). Wtedy \(P(X \ge i) = (1-p)^{i-1}\) i z powyższego twierdzenia dostajemy
\(EX = \sum_{i \ge 1} P(X \ge i) = \sum_{i \ge 1} (1-p)^{i-1} = \frac{1}{1-(1-p)} = \frac{1}{p}\).
Obliczanie \(EX\) wprost jest istotnie bardziej skomplikowane - sprowadza się, de facto, do powtórzenia dowodu twierdzenia 5.11.
W poprzednim wykładzie zdefiniowaliśmy, dla dowolnej dyskretnej zmiennej losowej \(X\) i zdarzenia \(A\) o niezerowym prawdopodobieństwie, nową zmienną \(X|A\).
Można oczywiście obliczyć wartość oczekiwaną tak zdefiniowanej zmiennej:
\(E(X|A) = \sum_{x \in \mathbb{R}} xP((X|A) = x) = \sum_{x \in \mathbb{R}} xP(X=x|A)\).
Związek między tak określonymi warunkowymi wartościami oczekiwanymi, a zwykłą wartością oczekiwaną, jest taki sam jak między prawdopodobieństwami warunkowymi, a zwykłym prawdopodobieństwem:
Twierdzenie 5.12 (Wzór na całkowitą wartość oczekiwaną)
Niech \(X:\Omega\rightarrow\mathbb{R}\) będzie dyskretną zmienną losową i niech \(A_1,A_2,\ldots\) będzie podziałem \(\Omega\). Wtedy:
\(EX = \sum_{k=1}^\infty P(A_k) E(X|A_k)\).
Dowód
Na mocy twierdzenia o prawdopodobieństwie całkowitym
\( P(X=x) = \sum_{k=1}^\infty P(A_k) P(X=x|A_k)\)
dla każdego \(k \in \mathbb{N}\) i \(x \in \mathbb{R}\). Mnożąc tę tożsamość stronami przez \(x\) i sumując po wszystkich \(x\) dostajemy tezę:
\(EX = \sum_{x \in \mathbb{R}} \sum_{k=1}^\infty xP(A_k) P(X=x|A_k) = \sum_{k=1}^\infty \sum_{x \in \mathbb{R}} xP(A_k) P(X=x|A_k) = \sum_{k=1}^\infty P(A_k) E(X|A_k)\).
Uwaga
Podobnie jak w przypadku wzoru na prawdopodobieństwo całkowite, prawdziwa jest także wersja powyższego twierdzenia dla skończonych podziałów \(\Omega\), dowód analogiczny. Ponadto tak jak w przypadku wzoru na prawdopodobieństwo całkowite, można powyższe twierdzenie traktować jako przepis na obliczanie wartości oczekiwanej przez przypadki.
Przykład 5.13
Korzystając ze wzoru na całkowitą wartość oczekiwaną obliczymy ponownie wartość oczekiwaną zmiennej \(X \sim Geom(p)\).
\(EX = P(X = 1) E(X|X=1) + P(X>1) E(X|X > 1) = p \cdot 1 + (1-p) E(X|X > 1)\).
Zauważmy, że \( X|(X > 1)\) ma taki sam rozkład jak \(1+X \). Intuicyjnie jest to dość oczywiste, (prosty) formalny dowód dużo ogólniejszego faktu pojawi się na ćwiczeniach.
A zatem
\(EX = p + (1-p) E(1+X) = 1 + (1-p)EX\).
Stąd \(pEX = 1\) i ostatecznie \(EX = \frac{1}{p}\).
Wartość oczekiwana niesie bardzo istotną informację na temat zmiennej losowej. Tym niemniej, ograniczanie się w analizie do samej wartości oczekiwanej może być zwodnicze, a czasem wręcz niebezpieczne.
Jest duża różnica między inwestycją, w której z prawdopodobieństwem \(\frac{1}{2}\) zyskujemy \(1,000,000\) zł i z prawdopodobieństwem \(\frac{1}{2}\) tracimy \(800,000\) zł, a inwestycją w której z prawdopodobieństwem \(\frac{1}{2}\) zyskujemy \(101,000\) i z prawdopodobieństwem \(\frac{1}{2}\) zyskujemy \(99,000\). W obu przypadkach wartość oczekiwana zysku wynosi \(100,000\) zł, a pomimo to większość osób bez wahania wybrałaby drugą opcję.
Podobnie, jest duża różnica między algorytmem, którego oczekiwany czas działania jest równy \(cn\log n \), ale który często działa w czasie bliskim zeru i często działa wielokrotnie wolniej niż średnio, a algorytmem o tym samym średnim czasie działania, który prawie zawsze działa w czasie bliskim średniej. Znów jasne jest, że opcja druga jest z reguły bardziej pożądana.
Aby móc porównywać inwestycje w pierwszym przykładzie i algorytmy w drugim, wprowadzimy miarę tego jak bardzo zmienna losowa odchyla się od swojej wartości średniej. Naturalnym pomysłem byłoby rozważenie wielkości \(E|X-EX|\). Pomysł ten jest dobry, a tak zdefiniowaną wielkość nazywa się z reguły średnim odchyleniem \(X\) . Posługiwanie się odchyleniem średnim jest jednak z wielu różnych względów dość problematyczne. W dużym uproszczeniu "pojęcie to nie ma dobrych własności", choćby dlatego, że użyta w definicji wartość bezwględna skutecznie utrudnia korzystanie z narzędzi analitycznych takich jak różniczkowanie.
Zamiast średniego odchylenia będziemy używać pojęć wariancji i odchylenia standardowego:
Definicja (Wariancja i odchylenie standardowe)
Wariancją dyskretnej zmiennej losowej \(X\) nazywamy wartość
\(VarX = E(X-EX)^2\),
o ile ona istnieje.
Odchyleniem standardowym \(X\) nazywamy \(\sigma(X) = \sqrt{VarX}\).
W tym miejscu należy się wyjaśnienie kwestii: po co nam aż dwie wielkości?
Wariancja, w przeciwieństwie do średniego odchylenia, ma bardzo dobre własności i pojawia się w wielu sytuacjach w naturalny sposób. Wbrew pozorom nie jest ona jednak dobrym substytutem średniego odchylenia z tego prostego powodu, że średniego odchylenia nie mierzy. Łatwo to zauważyć, jeśli zastanowimy się co się dzieje z wariancją, jeśli pomnożymy zmienną losową przez stałą:
\( Var(cX) = E(cX-E(cX))^2 = E(c(X-EX))^2= c^2E(X-EX)^ = c^2VarX.\)
To nie wygląda dobrze - sensowna miara średniego odchylenia powinna w takiej sytuacji wzrastać \(|c|\)-krotnie. Rozwiązaniem tego problemu jest odchylenie standardowe, dla którego jak łatwo zauważyć mamy \(\sigma(cX) = |c|\sigma(X)\).
Okazuje się, że odchylenie standardowe jest bardzo dobrą miarą "typowych odchyleń" od średniej, w szczególności ma z reguły wartość bardzo bliską odchyleniu średniemu.
Wariancję rzadko oblicza się wprost z definicji. Jedną z przydatniejszych metod jest poniższy wzór:
Twierdzenie 5.14
\( VarX = E(X^2) - (EX)^2\).
Dowód
\( VarX = E(X-EX)^2 = E(X^2 - 2XEX + (EX)^2) = E(X^2) - 2(EX)^2 + (EX)^2 = E(X^2) - (EX)^2\).
Przykład 5.15
Spróbujmy za pomocą tego wzoru obliczyć wariancję rozkładu Bernoulliego i rozkładu dwumianowego.
Dla zmiennej \(X\) o rozkładzie Bernoulliego z prawdopodobieństwem sukcesu \(p\) mamy:
\(VarX = E(X^2) - (EX)^2 = EX-(EX)^2 = p - p^2 = pq\).
Dla zmiennej \(Y \sim Binom(n,p)\) mamy:
\(VarY = E(Y^2) - (EY)^2 = \sum_{k=0}^n k^2{n \choose k}p^k(1-p)^{n-k} - (np)^2 = n\sum_{k=1}^n k\frac{k}{n}{n \choose k}p^k(1-p)^{n-k} - (np)^2\).
Korzystając z pochłaniania dostajemy:
\( n\sum_{k=1}^n k {n-1 \choose k-1}p^k(1-p)^{n-k} - (np)^2 = np \sum_{k=0}^{n-1} (k+1) {n-1 \choose k}p^k(1-p)^{n-1-k} - (np)^2 = np (\sum_{k=0}^{n-1} k{n-1 \choose k}p^k(1-p)^{n-k} + \sum_{k=0}^{n-1} {n-1 \choose k}p^k(1-p)^{n-k}) - (np)^2\).
Jedno z wyrażeń w nawiasie jest dwumianem \((p+q)^n\), a drugie wartością oczekiwaną zmiennej o rozkładzie \(Binom(n-1,p)\). Dostajemy więc:
\( np ((n-1)p + 1) - (np)^2 = np(np+q) - (np)^2 = (np)^2 + npq - (np)^2 = npq\).
Okazało się, że \(VarY = nVarX\), co sugeruje, że być może wariancja jest addytywna, tak jak wartość oczekiwana (liniowa być nie może, bo \(Var(cX) = c^2VarX\) ). Sprawdźmy:
\(Var(X+Y) = E((X+Y)-E(X+Y))^2 = E((X-EX)+(Y-EY))^2 = E( (X-EX)^2 +2(X-EX)(Y-EY) + (Y-EY)^2) = VarX+VarY + 2E(X-EX)(Y-EY)\).
Prawie się udało, niestety pojawił się dodatkowy człon \(E(X-EX)(Y-EY)\), sprawdźmy czy jest on równy 0:
\( E(X-EX)(Y-EY) = E( XY - XEY - YEX + EXEY) = E(XY) - EXEY - EXEY + EXEY = E(XY) - EXEY \).
I wszystko jasne: wariancja jest addytywna wtw, gdy wartość oczekiwana jest multiplikatywna. Ważny szczególny przypadek takiej sytuacji opisuje poniższe twierdzenie:
Twierdzenie 5.16
Jeśli dyskretne zmienne losowe \(X\) i \(Y\) są niezależne i mają skończoną wariancję, to \(Var(X+Y) = VarX+VarY \).
Dowód
Wynika z wcześniejszych rozważań i multiplikatywności wartości oczekiwanej dla zmiennych niezależnych.
Uwaga 5.17
Człon \(E(X-EX)(Y-EY)\) nazywa się kowariancją X i Y. Kowariancja jest duża/dodatnia dla zmiennych, które razem przyjmują małe wartości i razem duże, czyli są "w tej samej fazie". Małe/ujemne wartości kowariancji oznaczają zmienne "w przeciwnym fazach".
Czasem jesteśmy zmuszeni obliczyć wariancję sumy zmiennych, które nie są niezależne. Poniższy przykład pokazuję bardzo typową sytuację tego rodzaju i standardowy sposób radzenia sobie z zależnością zmiennych 0/1-kowych.
Przykład 5.9 (c.d.)
Obliczmy wariancję liczby pustych urn. Korzystając z twierdzenia 5.14 mamy
\(VarX = E(X^2) - (EX)^2\).
Wartość drugiego członu już znamy, aby obliczyć pierwszy rozbijemy \(X^2\) na poszczególne składniki i skorzystamy z liniowości wartości oczekiwanej
\(E(X^2) = E(\sum_{i=1}^n X_i)^2 = E(\sum_{i=1}^n\sum_{j=1}^n X_iX_j) = \sum_{i=1}^n\sum_{j=1}^n E(X_iX_j)\).
W tej sumie występują dwa rodzaje wyrazów:
Tych pierwszych jest \(n\), drugich - \(n^2-n\).
A zatem
\(VarX = n(1-\frac{1}{n})^n + (n^2-n) (1-\frac{2}{n})^n - n^2 (1-\frac{1}{n})^{2n}\).
Wartość oczekiwana i wariancja są szczególnymi przypadkami następujących dwóch pojęć:
Definicja (Moment)
Jeśli \(X\) jest zmienną losową, to \(k\)-tym momentem zmiennej losowej \(X\) nazywamy wartość wyrażenia \(E(X^k)\), o ile ona istnieje.
Definicja (Moment centralny)
Jeśli \(X\) jest zmienną losową i \(EX < \infty\), to \(k\)-tym momentem centralnym zmiennej losowej \(X\) nazywamy wartość wyrażenia \(E(X-EX)^k \), o ile ona istnieje.
A zatem wartość oczekiwana jest pierwszym momentem zmiennej, a wariancja drugim momentem centralnym.
Z wyższych momentów korzysta się istotnie rzadziej, niż z \(EX\) i \(VarX\), mają one jednak swoje miejsce w zastosowaniach. Czytelnikowi polecamy zastanowienie się, co mierzą trzeci, a co czwarty moment centralny?
Obliczanie wartości oczekiwanej i wariancji wprost z definicji lub za pomocą jednego z wyprowadzonych przez nas wzorów bywa często uciążliwe i pracochłonne. Poznamy teraz metodę, która pozwala często znacznie uprościć te rachunki.
Definicja (Funkcja tworząca prawdopodobieństwa)
Niech \(X\) będzie zmienną losową o wartościach naturalnych. Funkcją tworzącą prawdopodobieństwa zmiennej \(X\) zmiennej \(X\) nazywamy:
\(g_X(t) = \sum_{k=0}^\infty P(X=k) t^k\).
Tak jak to z reguły bywa z funkcjami tworzącymi, często wygodnie jest je traktować jako szeregi formalne i nie przejmować się zbieżnością. Tym niemniej, z twierdzenia o zbieżności zmajoryzowanej wynika łatwo natychmiast następujący:
Fakt 5.18
Szereg definiujący \(g_X(t)\) jest zawsze absolutnie zbieżny co najmniej na przedziale \( [-1,1]\).
Czasem wygodniej jest korzystać z następującej tożsamości:
Fakt 5.19
Dla tych \(t\) dla których szereg definiujący \(g_X(t)\) jest absolutnie zbieżny zachodzi:
\( g_X(t) = E(t^X)\).
Dowód
Oczywisty.
Jak obliczać wartość oczekiwaną i wariancję za pomocą funkcji tworzących prawdopodobieństwa? Wystarczy je zróżniczkować.
(Prawie prawdziwe) twierdzenie
Jeśli \(X\) o wartościach naturalnych ma skończoną wartość oczekiwaną, to:
\(EX = g_X'(1) \).
(Prawie poprawny) dowód
\(g_X'(t) = \sum_{k=0}^\infty kP(X=k) t^{k-1}\).
Podstawiając \(t=1\) dostajemy tezę.
Powyższe rozumowanie wygląda przekonująco, formalnie jednak nie jest całkiem poprawne. Z tego, że szereg \(g_X(t)\) jest zbieżny w przedziale \([-1,1]\) wynika, że możemy go zróżniczkować wewnątrz tego przedziału, ale niekoniecznie w \(t=1\). Dlatego należy sformułować twierdzenie tak:
Twierdzenie 5.20
Jeśli \(X\) o wartościach naturalnych ma skończoną wartość oczekiwaną, to:
\(EX = \lim_{t\rightarrow 1^-} g_X'(t) \).
Dowód
Z twierdzenia Abela suma szeregu potęgowego jest funkcją ciągłą (ew. jednostronnie ciągłą) wszedzie tam gdzie jest zbieżna. A zatem:
\(EX = \sum_{k=0}^\infty kP(X=k) 1^{k-1} = \lim_{t\rightarrow 1^-} (\sum_{k=0}^\infty kP(X=k) t^{k-1}) = \lim_{t\rightarrow 1^-} g_X'(t)\).
W praktyce tego rodzaju niuansy nie mają znaczenia. Funkcje tworzące prawdopodobieństwa, z którymi będziemy mieli do czynienia będą zbieżne na całej prostej rzeczywistej i problemy opisane powyżej nie będą występować. W szczególności prawdziwy będzie wzór \(EX = g_X'(1)\).
Łatwo zgadnąć jak za pomocą funkcji tworzących prawdopodobieństwa oblicza się wariancję. Różniczkując dwukrotnie! Spróbujmy:
\(g_X''(t) = \sum_{k=0}^\infty k(k-1)P(X=k) t^{k-2}\).
A zatem
\(g_X''(1) = E(X(X-1))\)
oraz
\(g_X''(1) + g_X'(1) = E(X^2)\),
o ile oczywiście te pochodne istnieją. Z tego właśnie wzoru będziemy korzystać w praktyce, w ogólnym przypadku zachodzi
Twierdzenie 5.21
Jeśli \(X\) o wartościach naturalnych ma skończoną wartość oczekiwaną i wariancję, to
\(E(X^2) = \lim_{t\rightarrow 1^-} (g_X'(t)+g_X''(t)) \)
oraz
\(VarX = \lim_{t\rightarrow 1^-} (g_X'(t)+g_X''(t) -(g_X'(t))^2)\).
Dowód
Analogiczny jak dla twierdzenia 5.20.
Przykład 5.22
Znajdźmy funkcję tworzącą prawdopodobieństwa rozkładu dwumianowego (w tym przypadku mamy do czynienia z wielomianem tworzącym i większość rozważań powyżej mocno się upraszcza). Niech \(X \sim Binom(n,p)\). Wtedy
\( g_X(t) = \sum_{k=0}^n {n \choose k}p^kq^{n-k} t^k = (q+pt)^n \).
Obliczmy pierwszą i drugą pochodną \(g_X(t)\):
\(g_X'(t) = np(q+pt)^{n-1}\),
\(g_X''(t) = n(n-1)p^2(q+pt)^{n-2}\).
A zatem
\(EX = g_X'(1) = np(q+p)^{n-1} = np\), oraz
\(VarX = g_X''(1) + g_X'(1) - (g_X'(1))^2 = n(n-1)p^2 + np - (np)^2 = np-np^2 = npq.\)
Udowodnimy teraz kilka własności funkcji tworzących prawdopodobieństwa, które znacząco ułatwiają posługiwanie się nimi.
Twierdzenie 5.23
Niech \(X,Y\) będą niezależnymi zmiennymi o wartościach naturalnych. Wtedy
\(g_{X+Y}(t) = g_X(t) g_Y(t) \).
Dowód
Dla \(t \in [-1,1]\) zachodzi
\(g_{X+Y}(t) = E(t^{X+Y}) = E(t^Xt^Y) = E(t^X)E(t^Y) = g_X(t) g_Y(t)\),
więc musi też zachodzić teza.
Twierdzenie to w naturalny sposób uogólnia się na dowolną skończoną liczbę niezależnych zmiennych losowych.
Przykład 5.24
Korzystając z powyższego twierdzenia możemy policzyć \(g_X(t)\) dla \(X \sim Binom(n,p)\) w alternatywny sposób. Zauważmy mianowicie, że dla zmiennej \(Y\) o rozkładzie Bernoulliego z prawdopodobieństwem sukcesu \(p\) mamy
\(g_Y(t) = q+pt\),
a ponieważ \(X\) jest sumą \(n\) niezależnych zmiennych o takim właśnie rozkładzie, to
\(g_X(t) = (g_Y(t))^n = (q+pt)^n\).
Twierdzenie 5.25
Jeśli \(X\) jest zmienną losową o wartościach naturalnych, a \(c \in \mathbb{N}\), to
\(g_{cX}(t) = g_X(t^c)\).
Dowód
\(g_{cX}(t) = \sum_{k=0}^\infty P(cX = k) t^k = \sum_{i=0}^\infty P(cX = ci) t^{ci} = \sum_{i=0}^\infty P(X = i) (t^c)^i = g_X(t^c)\).
Twierdzenie 5.26
Niech \(N,X_1,X_2,\ldots,X_N\) będą niezależnymi zmiennymi losowymi o wartościach naturalnych. Ponadto, niech wszystkie \(X_i\) mają ten sam rozkład \(X_i \sim X\). Wtedy dla \(S = X_1 + \ldots + X_N\) zachodzi
\( g_S(t) = g_N(g_X(t))\)
oraz
\(ES = ENEX\).
Dowód
Dla \(t \in [-1,1]\) mamy z twierdzenia o całkowitej wartości oczekiwanej
\(g_S(t) = E(t^S) = \sum_{k=0}^\infty P(N=k) E(t^S | N=k) = \sum_{k=0}^\infty P(N=k) E(t^{X_1+\ldots+X_k})\).
Z niezalezności \(X_i\) dostajemy
\(g_S(t) = \sum_{k=0}^\infty P(N=k) E(t^{X_1})\cdot \ldots \cdot E(t^{X_k}) = \sum_{k=0}^\infty P(N=k) (g_X(t))^k = g_N(g_X(t))\).
Druga część twierdzenia wynika z pierwszej, ciągłości funkcji tworzących w \(t=1\) oraz tego, że \(g_X(1) = 1\).
\(ES = \lim_{t \rightarrow 1^-} g_S'(t) = \lim_{t \rightarrow 1^-} g_N'(g_X(t))\cdot g_X'(t) = \lim_{t \rightarrow 1^-} g_N'(t) g_X'(t) = ENEX\).
Przykład 5.27
Rzucamy kostką, niech \(N\) będzie wynikiem rzutu. Następnie rzucamy \(N\) razy monetą. Jaki rozkład ma łączna liczba orłów? W szczególności jak wygląda funkcja tworząca prawdopodobieństwa tego rozkładu?
Niech \(X_1,X_2,\ldots,\) będą wynikami rzutów monetą. Wtedy łączna liczba orłów jest równa
\(S = X_1+\ldots+X_N\)
i mamy do czynienia z sytuacją z udowodnionego właśnie twierdzenia.
Ponieważ
\(g_N(t) = \frac{1}{6}\sum_{i=1}^6 t^i\)
oraz
\(g_{X_i}(t) = \frac{1+t}{2}\),
to
\(g_S(t) = \frac{1}{6}\sum_{i=1}^6 (\frac{1+t}{2})^i\).
Zdefiniowane w poprzednim wykładzie pojęcia wartości oczekiwanej umożliwia sformułowanie w języku rachunku prawdopodobieństwa następujących naturalnych pytań
i wielu innych. Sprowadzają się one do znalezienia wartości oczekiwanej odpowiednio zdefiniowanej zmiennej losowej.
W poprzednim wykładzie zdefiniowaliśmy także pojęcia wariancji i odchylenia standardowego, mierzące rozmiar odchyleń zmiennej losowej od jej wartości oczekiwanej. Dla rozkładów, dla których obliczyliśmy wariancję (rozkład dwumianowy, Poissona i geometryczny) te typowe odchylenia są małe, istotnie mniejsze niż wartość oczekiwana. Powinniśmy się więc spodziewać, że z dużym prawdopodobieństwem zmienne losowe będą przyjmować wartości bliskie swoim wartościom oczekiwanym. Na przykład, w \(N\) rzutach monetą nie tylko średnio wypada \(\frac{N}{2}\) orłów, ale też z dużym prawdopodobieństwem liczba orłów jest niezbyt odległa od \(\frac{N}{2}\). Postaramy się teraz pokazać podstawowe metody dowodzenia tego rodzaju stwierdzeń.
Wartości zmiennej losowej odległe od jej wartości oczekiwanej nazywa się z reguły ogonami. Można więc powiedzieć, że naszym celem jest szacowanie prawdopodobieństw ogonów. Często mówi się też po prostu o szacowaniu ogonów.
Jedną z najprostszych i najbardziej ogólnych metod szacowania ogonów jest nierówność Markowa
Twierdzenie 6.1 (Nierówność Markowa)
Niech \(X\) będzie dyskretną zmienną losową o wartościach nieujemnych i niech \(EX < \infty \). Wtedy dla dowolnego \(c > 0\)
\( P(X \ge c EX) \le \frac{1}{c}\)
Dowód
Z definicji \(EX\) mamy
\( EX = \sum_x x P(X=x) \ge \sum_{x \ge cEX} xP(X=x) \ge c EX \cdot P(X \ge cEX) \),
z czego wynika teza.
Powyższy dowód ma bardzo prostą intuicję fizyczną: Jeśli o \(EX\) myśleć jako o środku ciężkości masy rozłożonej zgodnie z \(P\), to na prawo od \(cEX\) nie może być tej masy więcej niż \(\frac{1}{c}\), bo nie dałoby się jej w żaden sposób zrównoważyć. Widać, że kluczowe jest tu założenie o nieujemności zmiennej \(X\). Gdyby zmienna \(X\) mogła przyjmować ujemne wartości to moglibyśmy do równoważenia użyć masy położonej daleko na lewo od \(0\).
Uwaga 6.2
Często podaje się nierówność Markowa w równoważnym sformułowaniu:
\( P(X \ge c) \le \frac{EX}{c}\)
Przykład 6.3
Jakie jest prawdopodobieństwo uzyskania w \(n=1000\) rzutach co najmniej \(\frac{3}{4}N = 750\) orłów? Wydaje się, że prawdopodobieństwo to powinno być bardzo małe. Zobaczmy jakie oszacowanie uzyskamy korzystając z nierówności Markowa.
Niech \(X_1,\ldots,X_n\) będą wynikami poszczególnych rzutów, przy czym wartość 1 oznacza orła, a 0 - reszkę. Wtedy \(X = \sum_{i=1}^n X_i\) jest łączną liczbą orłów. Ponieważ \(EX = \frac{N}{2}\), to z nierówności Markowa dostajemy niezbyt imponujące oszacowanie:
\(P(X \ge \frac{3}{4}N) = P(X \ge \frac{3}{2} EX) \le \frac{2}{3}.\)
Poniższy przykład pokazuje, że nierówność Markowa nie jest zbyt mocna. Pomimo tego jest to nierówność ważna z co najmniej dwóch powodów. Po pierwsze, wymaga bardzo słabych założeń: nieujemności i istnienia wartości oczekiwanej. Czasem dysponujemy jedynie wartością oczekiwaną i nierówność Markowa jest jedynym narzędziem jakiego możemy użyć. Po drugie, jak się wkrótce przekonamy, aplikując nierówność Markowa do odpowiednio zdefiniowanej zmiennej można uzyskać nierówności dużo mocniejsze.
Nierówności Markowa nie da się poprawić, jeżeli dysponujemy jedynie wartością oczekiwaną. Niech na przykład \(X\) będzie zmienną zdefiniowaną następująco: \(P(X=c) = \frac{1}{c}\) oraz \(P(X=0) = 1-\frac{1}{c}\), gdzie \(c > 1\). Wtedy \(EX = 1\) i \(P(X \ge cEX) = \frac{1}{c}\).
Zauważmy jednak, że tak określona zmienna jest skoncentrowana w dwóch punktach - swoich ekstremach. W szczególności, wartości zmiennej \(X\) mają bardzo duży "rozrzut". Można się spodziewać, że dla zmiennych o małym odchyleniu standardowym, a więc dużo bardziej skoncentrowanych wokół wartości oczekiwanej, powinniśmy być w stanie uzyskać dużo lepsze oszacowanie.
Twierdzenie 6.4 (Nierówność Czebyszewa)
Niech \(X\) będzie dyskretną zmienną losową taką, że \(EX < \infty\) oraz \(VarX < \infty\) i niech \(\sigma = \sqrt{VarX}\) będzie odchyleniem standardowym \(X\). Wtedy dla dowolnego \(c > 0\)
\( P(|X-EX|\ge c\sigma) \le \frac{1}{c^2}\).
Dowód
Niech \(Y=(X-EX)^2\). Wtedy korzystając z nierówności Markowa dostajemy
\( P( |X-EX| \ge c\sigma ) = P( (X-EX)^2\ge c^2 VarX) = P( Y \ge c^2 EY) \le 1/c^2\).
Uwaga 6.5
Tak jak w przypadku nierówności Markowa, często używa się alternatywnego sformułowania nierówności Czebyszewa:
\( P(|X-EX|\ge c) \le \frac{VarX}{c^2}\).
Przykład 6.3 (c.d.)
Zobaczmy jakie oszacowanie można uzyskać za pomocą nierówności Czebyszewa.
Zmienna \(X\) ma rozkład Binom\((n,p=\frac{1}{2})\), a zatem \(VarX = npq=\frac{n}{4}\). Korzystając z alternatywnej wersji nierówności Czebyszewa dostajemy:
\(P(X \ge \frac{3}{4}n) = \frac{1}{2} P( |X-EX| \ge \frac{1}{4}n) \le \frac{1}{2} \frac{\frac{n}{4}}{(\frac{1}{4}n)^2} = \frac{2}{n}\)
(w pierwszym kroku skorzystaliśmy z tego, że \( P(X \ge \frac{3}{4}n) = P(X \le \frac{1}{4}n)\) ).
Jest to oszacowanie dużo lepsze niż \(P(X \ge \frac{3}{4}n) \le \frac{2}{3} \) uzyskane z nierówności Markowa. Jak jednak wkrótce zobaczymy, jest ono wciąż bardzo daleko od prawdziwej wartości tego prawdopodobieństwa.
Zanim przejdziemy do kolejnej nierówności, udowodnimy bardzo ważny wniosek z nierówności Czebyszewa
Twierdzenie 6.6 (Słabe Prawo Wielkich Liczb (SPWL))
Niech zmienne losowe \(X_1,X_2,\ldots\) będą niezależne o tym samym rozkładzie \(X\) i niech \(\bar{X_n} =\frac{\sum_{i=1}^n X_i}{n}\) dla \(n =1,2,\ldots\) . Niech ponadto \(\mu = EX < \infty \) i \(\sigma^2 = Var X < \infty\). Wtedy dla każdego \(\varepsilon > 0\)
\( \lim_{n\rightarrow\infty} P(| \bar{X_n}-\mu| > \varepsilon) = 0\).
Dowód
Z liniowości wartości oczekiwanej dla wszystkich \(n=1,2,\ldots\) mamy \(E\bar{X_n} = \mu\). Ponadto z niezależności \(X_i\) wynika, że \(Var\bar{X_n} = \frac{1}{n^2} \cdot n \sigma^2 = \frac{\sigma^2}{n}\). A zatem z nierówności Czebyszewa dostajemy
\(P(| \bar{X_n}-\mu| > \varepsilon) \le \frac{\frac{\sigma^2}{n}}{\varepsilon^2} \rightarrow_{n\rightarrow\infty} 0\),
co kończy dowód.
Uwaga 6.7
Założenie, że zmienne \(X_i\) mają skończoną wariancję nie jest konieczne, ale bez niego nie możemy użyć nierówności Czebyszewa i dowód istotnie się komplikuje.
Prawdziwe jest również następujące twierdzenie:
Twierdzenie 6.8 (Mocne Prawo Wielkich Liczb (MPWL))
Przy założeniach jak w twierdzeniu 6.6 zachodzi
\( P(\lim_{n\rightarrow\infty} \bar{X_n} = \mu) = 1\).
Twierdzenie to pozostawimy bez dowodu. Polecamy jednak czytelnikowi zastanowienie się nad tym dlaczego MPWL jest silniejszym twierdzeniem niż SPWL?
Rozważmy nieskończony ciąg niezależnych powtórzeń tego samego doświadczenia modelowanego przestrzenią \((\Omega,P)\). Niech \(A \subseteq \Omega\) i niech zdarzenia \(A_1,A_2,\ldots\) odpowiadają zajściu \(A\) w doświadczeniach \(1,2,\ldots\). Niech ponadto zmienne \(X_1,X_2\) będą zdefiniowane następująco: \(X_i(\omega) = [\omega \in A_i]\), t.j. zmienna \(X_i\) jest równa \(1\) jeśli \(A_i\) zaszło i \(0\) wpp.
W naszych dotychczasowych rozważaniach dwukrotnie już pojawiała się tzw. intuicja częstościowa, którą można opisać następującą równością:
\( \lim_{n\rightarrow\infty} \frac{\sum_{i=1}^n X_i}{n} = P(A)\).
Używaliśmy tej intuicji dobierając modele probabilistyczne w wykładzie 1 i definiując wartość oczekiwaną w wykładzie 5. Dlatego należy traktować jako dobrą wiadomość to, że intuicję tę można w naszej teorii "udowodnić" aplikując MPWL do zmiennych \(X_1,X_2,\ldots\) (zachęcamy czytelnika do sprawdzenia tego faktu).
Wzorując się na dowodzie nierówności Czebyszewa możemy próbować aplikować nierówność Markowa do dowolnej zmiennej \(Y = f(X)\), o ile tylko funkcja \(f\) jest nieujemna i monotonicznie rosnąca:
\( P(X \ge c) = P(f(X) \ge f(c)) \le \frac{Ef(X)}{f(c)}\).
(w pierwszym kroku korzystamy z monotoniczności \(f\), a w drugim z nierówności Markowa, do której jest potrzebna nieujemność \(f\)).
Oczywiście takie postępowanie ma sens jedynie jeśli:
Okazuje się, że oba te warunki są spełnione, jeśli przyjmiemy \(f(x) = e^{tx}\), gdzie \(t > 0\) jest parametrem, który ustalimy później. W szczególności, podstawą naszych dalszych rozważań będzie następujące twierdzenie:
Twierdzenie 6.9 (Ogólna nierówność typu Chernoffa)
Dla dowolnej zmiennej losowej \(X\) zachodzi
\( P(X \ge c) \le \min_{t>0} \frac{E(e^{tX})}{e^{tc}}\)
oraz
\( P(X \le c) \le \min_{t<0} \frac{E(e^{tX})}{e^{tc}}\).
Dowód
Aby uzyskać pierwszą nierówność powtarzamy rozumowanie przeprowadzone na początku tego paragrafu dla funkcji \(f(x) = e^{tx}\) i otrzymujemy dla dowolnego \(t > 0\)
\( P(X \ge c) = P(e^{tX} \ge e^{tc}) \le \frac{E(e^{tX})}{e^{tc}}\).
Skoro nierówność ta zachodzi dla każdego \(t > 0\), to zachodzi też nierówność z tezy twierdzenia.
Drugą nierówność dostajemy w analogiczny sposób. Dla dowolnego \( t < 0\) zachodzi bowiem
\( P(X \le c) = P(e^{tX} \ge e^{tc}) \le \frac{E(e^{tX})}{e^{tc}}\).
Aby uzyskać konkretne oszacowanie na \(P(X \ge c)\) lub \(P(X \le c)\), bez nieustalonego parametru \(t\) i tajemniczego wyrażenia \(E(e^{tX})\), musimy zdecydować jaki rozkład ma mieć zmienna \(X\). Bardzo ciekawe wyniki można uzyskać w sytuacji opisanej w następującym twierdzeniu:
Twierdzenie 6.10 (nierówność Chernoffa dla prób Poissona)
Niech \(X_1,\ldots,X_n\) niezależne zmienne o rozkładzie 0/1-kowym, przy czym \(P(X_i = 1)=p_i = 1-q_i\). Niech ponadto \(X = \sum_{i=1}^n X_i\) i niech \(\mu = EX = \sum_{i=1}^n p_i\). Wtedy:
Uwaga 6.11
Ciąg zmiennych \(X_i\) jak w twierdzeniu powyżej nazywa się często próbami Poissona (nie mylić z rozkładem Poissona!). Jest to uogólnienie prób Bernoulliego na przypadek niekoniecznie równych prawdopodobieństw sukcesu.
Uwaga 6.12
Może dziwić to, że w tezie twierdzenia sformułowane są aż trzy nierówności. Przyczyna jest bardzo prosta. Formułując konkretną nierówność dokonujemy kompromisu między jej siłą, a prostotą zapisu. Nierówność pierwsza jest najmocniejsza i zachodzi dla wszystkich wartości \(\delta\), jest jednak najbardziej skomplikowana. Nierówności druga i trzecia są słabsze i zachodzą tylko dla pewnych przedziałow wartości \(\delta\), są jednak zdecydowanie prostsze.
Przykład 6.3 (c.d.)
Zanim przejdziemy do dość technicznego dowodu, sprawdźmy jakie oszacowanie możemy uzyskać korzystając z nierówności Chernoffa dla przykładu z rzutami monetą.
\(P (X \ge \frac{3}{4}n) = P(X \ge (1+\frac{1}{2}) \frac{1}{2}n) \le \left( \frac{e^\frac{1}{2}}{(\frac{3}{2})^\frac{3}{2}}\right)^{\frac{1}{2}n} = (\frac{8e}{27})^{\frac{1}{4}n} \sim 0.95^n.\)
To oszacowanie jest nieporównywalnie lepsze od oszacowania uzyskanego za pomocą nierówności Czebyszewa. Jeśli przyjmiemy \(n=1000\) rzutów to dostaniemy:
Zachęceni tak spektakularnym sukcesem przystąpmy do dowodu.
Dowód (nierówności Chernoffa dla prób Poissona)
Wiemy, że zachodzi
\( P(X \ge (1+\delta)\mu) \le \min_{t>0} \frac{E(e^{tX})}{e^{t(1+\delta)\mu}}.\)
Zajmijmy się członem \(E(e^{tX})\). Korzystając z przedstawienia \(X\) jako sumy niezależnych zmiennych 0/1-kowych dostajemy
\(E(e^{tX}) = E(e^{\sum_{i=1}^n tX_i}) = E(\prod_{i=1}^n e^{tX_i}) = \prod_{i=1}^n E(e^{tX_i}) = \prod_{i=1}^n (q_i + p_i e^t)) = \prod_{i=1}^n (1 + p_i (e^t-1)) \le \prod_{i=1}^n e^{p_i(e^t-1)} = e^{\mu(e^t-1)}\).
A zatem
\( P(X \ge (1+\delta)\mu) \le \min_{t>0} \frac{e^{(e^t-1)\mu}}{e^{t(1+\delta)\mu}} = \min_{t>0} e^{(e^t-1-t(1+\delta))\mu}.\)
Dla jakiej wartości parametru \(t\) wyrażenie w wykładniku przyjmuje najmniejszą wartość? Pochodna wykładnika to \((e^t-(1+\delta))\mu\).
Przyrównując ją do zera dostajemy \(t = \ln(1+\delta)\). Podstawiając optymalną wartość \(t\) do naszego oszacowania dostajemy:
\( P(X \ge (1+\delta)\mu) \le e^{(1+\delta-1-(1+\delta)\ln(1+\delta))\mu} = \left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu\),
co dowodzi pierwszej części tezy.
Aby udowodnić drugą część wystarczy pokazać, że dla dowolnego \(\delta \in [0,1]\) zachodzi \( \delta - (1+\delta)\ln(1+\delta) \le -\frac{\delta^2}{3} \), czyli \( \delta - (1+\delta)\ln(1+\delta) + \frac{\delta^2}{3} \le 0\). Niech \(f(\delta) = \delta - (1+\delta)\ln(1+\delta) + \frac{\delta^2}{3}\). Wtedy mamy
\( f'(\delta) = 1 - \frac{1+\delta}{1+\delta} - \ln(1+\delta) + \frac{2}{3}\delta = -\ln(1+\delta) + \frac{2}{3}\delta \),
oraz
\( f''(\delta) = -\frac{1}{1+\delta} + \frac{2}{3}\).
Łatwo zauważyć, że \(f''(\delta) < 0\) dla \( 0 < \delta < \frac{1}{2} \) oraz \(f''(\delta) > 0\) dla \( \frac{1}{2} < \delta\). A zatem, na przedziale \( (0,1]\) druga pochodna \(f\) najpierw maleje, a potem rośnie. Skoro jednak \(f'(0) = 0\) i \(f'(1) = -\ln(2)+\frac{2}{3} < 0\), to musi być \(f'(\delta) < 0\) na całym przedziale \( [0,1]\), czyli \(f\) jest malejąca. A ponieważ \(f(0) = 0\), to \(f\) jest ujemna na całym przedziale \( (0,1] \), co kończy dowód drugiej nierówności.
Trzecia część tezy w prosty sposób wynika z pierwszej. Jeśli \(1+\delta >= 2e\), to mamy:
\(\left(\frac{e^\delta}{(1+\delta)^{1+\delta}}\right)^\mu \le \left(\frac{e}{1+\delta}\right)^{(1+\delta)\mu} \le 2^{-(1+\delta)\mu},\)
co kończy dowód.
Zachodzą również nierówności dla "dolnych ogonów"
Twierdzenie 6.13 (nierówność Chernoffa dla prób Poissona - dolne ogony)
Niech \(X_1,\ldots,X_n\) niezależne zmienne o rozkładzie 0/1-kowym, przy czym \(P(X_i = 1)=p_i = 1-q_i\). Niech ponadto \(X = \sum_{i=1}^n X_i\) i niech \(\mu = EX = \sum_{i=1}^n p_i\). Wtedy dla dowolnego \(0 < \delta < 1\) zachodzi
Dowód, analogiczny do przed chwilą przeprowadzonego, pomijamy.
Uwaga 6.14
Nieprzypadkowo w nierównościach Chernoffa korzysta się z funkcji \(f(x) = e^{tx}\). Wyrażenie \(E(e^{tX})\), które zmuszeni byliśmy szacować, jest w teorii prawdopodobieństwa dobrze znane i zbadane. Nazywa się je z reguły funkcją tworzącą momentów \(X\) i oznacza \(M_X(t)\). Funkcja \(M_X(t)\) przypomina trochę znaną nam funkcję tworzącą prawdopodobieństwa, w szczególności dla \(X\) o wartościach naturalnych zachodzi:
\(M_X(t) = g_X(e^t)\).
Funkcji tworzących momentów można jednak używać dla dowolnych zmiennych, niekoniecznie dyskretnych. Z ciekawszych ich własności warto wspomnieć następujące rozwinięcie w szereg potęgowy
\(M_X(t) = E e^{tX} = E (\sum_{k=1}^\infty X^k t^k / k!) = \sum_{k=1}^\infty E (X^k) t^k / k!\),
które jest możliwe przy pewnych założeniach dotyczących \(X\). Okazuje się, że \(M_X(t)\) jest wykładniczą funkcją tworzącą ciągu momentów \(X\), i stąd jej nazwa.
Z punktu widzenia zastosowań w informatyce, materiał omówiony w ramach tego rozdziału jest szczególnie ważny. Wiele naturalnych i fundamentalnych pytań pojawiających się w zastosowaniach sprowadza się bowiem do szacowania ogonów. Z tego względu umiejętność sprawnego posługiwania się nierównościami probabilistycznymi jest bardzo przydatna. Należy jednak pamiętać, że najmocniejsza nawet ogólna nierówność nie zastąpi solidnej analizy i dobrego zrozumienia konkretnego problemu. Nierzadko najlepsze oszacowanie prawdopodobieństwa ogonów uzyskuje się wprost, bez użycia nierówności. Przykład takiej sytuacji zobaczymy na ćwiczeniach.
Dotychczas koncentrowaliśmy uwagę na zmiennych dyskretnych, t.j. takich, że zachodzi \(\sum_{x \in \mathbb{R}} P(X=x) = 1\). Innymi słowy, istnieje pewien przeliczalny zbiór wartości o niezerowym prawdopodobieństwie, i z prawdopodobieństwem \(1\) zmienna przyjmuje jedną z tych wartości.
Łatwo sobie jednak wyobrazić sytuacje, w których pojawiają się zmienne losowe nie mające tej własności. Jeśli na przykład losujemy punkt z odcinka \([0,1]\) i \(X\) jest wylosowanym punktem, to musi zachodzić \(P(X=x) = 0\) dla każdego \(x \in [0,1]\). Gdyby bowiem było \(P(X=x_0) = p>0\) dla pewnego \(x_0\), to musiałoby też być \(P(X=x) = p\) dla każdego \(x\) (dlaczego \(x_0\) miałby być bardziej prawdopodobny?), co prowadzi do sprzeczności z \(P(X \in [0,1]) = 1\).
Podobnie, jeśli mierzymy (dokładnie, wynikiem może być dowolna liczba rzeczywista) prędkość samochodu na autostradzie, czy wzrost losowo wybranej osoby, to sensownie jest założyć, że prawdopodobieństwo każdego konkretnego wyniku jest równe \(0\).
Jest to dość niepokojąca sytuacja - cała teoria jaką dotychczas omówiliśmy opierała się dość mocno na założeniu dyskretności. W szczególności, własnością zmiennych dyskretnych, która była kluczowa w wielu definicjach i dowodach było to, że dla dowolnego zbioru \(A\subseteq\mathbb{R}\) i zmiennej dyskretnej \(X\) zachodzi \(P(X \in A) = \sum_{x \in A} P(X=x)\).
Okazuje się, że w obu sytuacjach opisanych powyżej, a także w wielu innych, można opisać \(P(X \in A)\) w sposób tylko trochę bardziej skomplikowany.
Definicja (Rozkład ciągły)
Zmienna \(X\) ma rozkład ciągły, jeśli istnieje funkcja \(f_X:\mathbb{R} \rightarrow \mathbb{R}_{\ge 0}\) taka, że dla każdego przedziału \([a,b]\) zachodzi \(P(X \in [a,b]) = \int_a^b f_X(x) dx\) (lub równoważnie: dla każdego zbioru mierzalnego \(A \subseteq \mathbb{R}\) zachodzi \(P(X \in A) = \int_A f_X(x) dx \)).
Funkcję \(f_X\) nazywamy gęstością zmiennej \(X\).
Uwaga 7.1
Łatwo zauważyć, że jeśli \(f\) jest gęstością pewnej zmiennej, to \(\int_{-\infty}^\infty f(x) dx = 1\). Z drugiej strony, jeśli pewna funkcja \(f:\mathbb{R} \rightarrow \mathbb{R}_{\ge 0}\) spełnia ten warunek, to jest gęstością pewnej zmiennej. Dlatego w dalszej części wykładu, definiując rozkład za pomocą funkcji gęstości, będziemy zmuszeni zawsze sprawdzić, czy opisywana przez nas funkcja faktycznie może być gęstością, t.j. czy zachodzi \(\int_{-\infty}^\infty f(x) dx = 1\).
Uwaga 7.2
Zmienną losową o rozkładzie ciągłym można opisać za pomocą więcej niż jednej funkcji gęstości. Jeśli bowiem dowolną funkcję gęstości zmodyfikujemy na zbiorze miary \(0\), to otrzymana funkcja też będzie dobrą funkcją gęstości. Z powodu tej niejednoznaczności w sformułowaniach niektórych twierdzeń tego wykładu pojawiają się słowa "prawie wszędzie".
Jaki jest sens funkcji gęstości? Załóżmy, że \(I\) jest odcinkiem na tyle małym, że \(f_X\) jest na nim niemal stała (znalezienie takiego przedziału może czasem być niemożliwe, ale nie będziemy się tym przejmować, szukamy tylko intuicji). Wtedy
\(P(X \in I) = \int_I f_X(x) dx \approx |I| f_X(x) \),
dla dowolnego \(x \in I\), czyli
\(f_X(x) \approx \frac{P(X \in I)}{|I|}\).
Innymi słowy, \(f_X(x)\) mówi nam jak dużo prawdopodobieństwa przypada na przedział długości \(1\) w okolicy punktu \(x\), czyli jest taką "lokalną gęstością prawdopodobieństwa" w okolicy punktu \(x\), co tłumaczy nazwę.
Przykład 7.3
Mogłoby się wydawać, że każda zmienna losowa musi być albo dyskretna albo ciągła, ale łatwo zauważyć, że tak być nie musi. Wyobraźmy sobie, że chcemy wymodelować czas oczekiwania w kolejce u fryzjera (ew. w sklepie itp.) za pomocą zmiennej losowej \(X\). Z niezerowym prawdopodobieństwem nie będziemy w ogóle czekać, a więc \(P(X=0) > 0\). Jeśli jednak \(X>0\) to wydaje się, że mamy do czynienia z rozkładem ciągłym, w szczególności żadna wartość \(X\) większa niż \(0\) nie będzie mieć niezerowego prawdopodobieństwa. Ta zmienna nie jest ani ciągła, ani dyskretna, jest jednak pewnego rodzaju kombinacją zmiennej ciągłej i dyskretnej. Część prawdopodobieństwa jest skoncentrowana w punkcie \(0\), resztę można opisać funkcją gęstości.
Czy każda zmienna losowa ma taką postać? Na to pytanie odpowiemy w dalszej części tego wykładu.
Naturalnym pojęciem związanym z pojęciem zmiennej losowej jest dystrybuanta.
Definicja (dystrybuanta)
Dystrybuantą zmiennej losowej \(X\) jest funkcja \(F_X:\mathbb{R}\rightarrow\mathbb{R}\) określona \(F_X(x) = P(X \le x)\).
Zacznijmy od sformułowania kilku prostych własności dystrybuanty:
Fakt 7.4 (własności dystrybuanty)
Niech \(X\) będzie zmienną losową, a \(F_X\) jej dystrybuantą. Wtedy
Dowody wszystkich własności są oczywiste. Można też pokazać (dowód jest dość techniczny), że własności te charakteryzują funkcje, które są dystrybuantami:
Twierdzenie 7.5
Jeśli \(F_X:\mathbb{R}\rightarrow\mathbb{R}\) spełnia warunki z faktu 7.4, to istnieje zmienna losowa \(X\), dla której \(F_X\) jest dystrybuantą.
Następne twierdzenie i wniosek z niego pokazują, że patrząc na dystrybuantę można odróżnić zmienne dyskretne od ciągłych (oczywiste dowody pomijamy).
Twierdzenie 7.6
Jeśli \(X\) jest zmienną losową, a \(F_X\) jej dystrybuantą, to dla każdego \(x\in \mathbb{R}\) zachodzi
\( P(X=x) = F_X(x) - F_X(x^-)\),
gdzie
\( F_X(x^-) = \lim_{y \rightarrow x, y < x} F_X(y)\)
jest lewostronną granicą \(F_X\) w \(x\).
Wniosek 7.7
Jeśli \(X\) jest zmienną ciągłą, to \(F_X\) jest funkcją ciągłą. Jeśli natomiast \(X\) jest dyskretna to
\( \sum_{x \in \mathbb{R}} (F_X(x) - F_X(x^-)) = 1\).
Uwaga 7.8
Chciałoby się powiedzieć, że gdy \(X\) jest dyskretna, to \(F_X\) jest schodkowa, i z reguły tak właśnie jest - w szczególności jest to prawdą dla zmiennych o rozkładach, które poznaliśmy w dotychczasowych wykładach. Istnieją jednak zmienne dyskretne, których dystrybuanty nie są stałe na żadnym przedziale. Wystarczy w tym celu przypisać niezerowe prawdopodobieństwa elementom przeliczalnego zbioru gęstego w \(\mathbb{R}\), np. wszystkim liczbom wymiernym.
Następne twierdzenie podaje ważną charakteryzację zmiennych ciągłych za pomocą ich dystrybuant (dowód pomijamy)
Twierdzenie 7.9
Jeśli \(X\) jest zmienną ciągłą, to:
Z drugiej strony, jeśli \(F\) jest dystrybuantą różniczkowalną prawie wszędzie, a \(f = F'\) (tam gdzie \(F\) nie jest różniczkowalna, \(f\) przyjmuje dowolną wartość, np. \(0\)), to \(f\) jest gęstością ciągłej zmiennej losowej, o ile tylko \( \int_{-\infty}^{\infty} f(x) dx = 1\).
To, że ten ostatni warunek jest konieczny pokazuje poniższy przykład. Przy okazji odpowiadamy na pytanie postawione w przykładzie 7.3.
Przykład 7.10 (Funkcja Cantora, czyli diabelskie schody)
Pokażemy zmienną \(X\) taką, że:
Zmienną X zdefiniujemy za pomocą jej dystrybuanty. Rozważmy następujący ciąg funkcji \(F_i\):
Łatwo sprawdzić, że ciąg funkcji \(F_n\) jest zbieżny punktowo do pewnej funkcji. Niech \(F_X=F\) będzie granicą \(F_n\) i niech \(X\) będzie zmienną losową o dystrybuancie \(F\). Łatwo pokazać, że \(F\) jest ciągła, a zatem dla każdego \(x\) zachodzi \(P(X=x) = 0\) na mocy twierdzenia 7.6. Można też pokazać (co jest nieco trudniejsze), że \(F_X\) ma zerową pochodną wszędzie poza zbiorem miary zero (jest to tzw. zbiór Cantora), a zatem nie ma gęstości na żadnym przedziale \([a,b]\) dla którego \(P([a,b]) > 0\).
Definicja (rozkład jednostajny)
Zmienna \(X\) o rozkładzie jednostajnym na przedziale \([a,b]\) dla \(a < b\), ozn. \(X \sim Unif(a,b) \) ma gęstość \(f_X\), gdzie \(f_X(x) = \frac{1}{b-a}\) dla \(x \in [a,b]\) i \(f_X(x) = 0\) dla pozostałych \(x\).
Rozkład \(Unif(a,b)\) pojawia się, gdy losujemy liczbę z przedziału \([a,b]\) tak, aby prawdopodobieństwo uzyskania wyniku w dowolnym przedziale \(I\) było proporcjonalne do długości tego przedziału. Intuicyjnie chcemy, żeby wszystkie liczby były "równie prawdopodobne", choć oczywiście w przypadku losowania z przedziału sformułowanie "równie prawdopodobne" nie ma zbyt wiele sensu (wszystkie wyniki oczywiście są równie prawdopodobne, bo wszystkie mają prawdopodobieństwo \(0\), ale przecież nie o to nam chodzi).
Definicja (rozkład wykładniczy)
Zmienna \(X\) o rozkładzie wykładniczym z parametrem \(\theta > 0\), ozn. \(X \sim Exp(\theta) \) ma gęstość \(f_X\), gdzie \(f_X(x) = \theta e^{-\theta x}\) dla \(x \ge 0\) i \(f_X(x) = 0\) dla \(x < 0\).
Ten rozkład dobrze modeluje czas oczekiwania na zdarzenie, które ma cały czas "taką samą szansę zajścia", na przykład czas do następnego telefonu w centrum telefonicznym, czas do zajścia rozpadu radioaktywnego, itp. Można go też używać do modelowania czasu życia organizmów lub wszelkiego rodzaju sprzętu, aczkolwiek rozkład wykładniczy nie modeluje tych czasów bardzo dobrze. W obu przypadkach śmierć/awaria jest nieco bardziej prawdopodobna na początku, jest też bardziej prawdopodobna po upływie wystarczająco długiego czasu.
Sprawdzimy teraz, że funkcja \(f_X\) z definicji rozkładu wykładniczego rzeczywiście jest gęstością (t.j. ma całkę równą 1), a przy okazji znajdziemy dystrybuantę rozkładu wykładniczego. Dla dowolnego \(a \ge 0\) mamy:
\( \int_{a}^{\infty} f_X(t) dt = \int_a^\infty \theta e^{-\theta t}dt = \int_a^\infty - (e^{-\theta t})' dt = (-e^{-\theta t})|_a^\infty = 0 - (-e^{-\theta a}) = e^{-\theta a}\).
Stąd
\( \int_{-\infty}^\infty f_X(t) dt = \int_0^\infty f_X(t) dt = e^0 = 1\),
czyli \(f_X\) jest gęstością.
Ponadto
\( F_X(a) = P(X < a) = 1-P(X \ge a) = 1-\int_a^\infty f_X(t) dt = 1-e^{-\theta a}.\)
O rozkładzie wykładniczym można myśleć jako o "ciągłej wersji" rozkładu geometrycznego. W szczególności każdej wartości \(\theta > 0\) odpowiada pewna wartość \(p\) taka, że dystrybuanty rozkładów \(Exp(\theta\)) i \(Geom(p)\) przyjmują te same wartości dla wszystkich argumentów naturalnych (ćwiczenia).
Definicja (rozkład normalny lub Gaussa)
Zmienna \(X\) o rozkładzie normalnym o wartości oczekiwanej \(\mu\) i wariancji \(\sigma^2\), ozn. \(N(\mu,\sigma^2)\) ma gęstość
\(f_X(x) = \frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}} \).
Definicja rozkładu normalnego jest dość skomplikowana, jest on jednak niezwykle ważny. Jest ku temu kilka powodów, najważniejszym jest tzw. Centralne Twierdzenie Graniczne (które pojawi się pod koniec tego wykładu), które mówi, że suma dużej liczby niezależnych zmiennych, z których żadna nie dominuje pozostałych (t.j. nie przyjmuje dużo większych wartości, lub inaczej, nie ma decydującego wpływu na wynik) ma w przybliżeniu rozkład normalny. Wiele wielkości ma taki właśnie charakter - jest sumą wielu małych i niezależnych elementów - i co za tym idzie ma rozkład bliski normalnemu.
Każdy na pewno nie raz widział charakterystyczny kształt dzwonu na histogramach ilustrujących różnego rodzaju statystyki.
Często zakłada się na przykład, że wzrost/masa człowieka, ew. wymiary/masa innych organizmów mają rozkład normalny. Należy tu oczywiście być ostrożnym: kobiety są generalnie niższe niż mężczyźni, można też zaobserwować różnice we wzroście pomiędzy poszczególnymi rasami. W związku z tym odpowiedni rozkład nie będzie miał kształtu dzwonu z jednym maksimum, ale raczej sumy kliku dzwonów. Łatwo zrozumieć dlaczego rozumowanie oparte na Centralnym Twierdzeniu Granicznym nie działa w tym przypadku: zarówno płeć jak i rasa są czynnikami, których wpływ na wzrost dominuje pozostałe czynniki. Jeśli jednak odpowiednio ograniczymy rozpatrywaną populację, np. do kobiet rasy białej, to rozkład wzrostu będzie bliski normalnemu.
Spróbujemy teraz sprawdzić, że funkcja \(f_X\) z definicji rozkładu normalnego rzeczywiście jest gęstością. Zacznijmy od przypadku, w którym \(\mu=0\) i \(\sigma^2 = 1\), t.j. od rozkładu \(N(0,1)\).
Chcemy obliczyć całkę \(I = \int_{-\infty}^{\infty} f_X(x) dx\). Zamiast tego obliczymy jej kwadrat
\( I^2 = (\int_{-\infty}^{\infty} f_X(x) dx)(\int_{-\infty}^{\infty} f_X(y) dy) = \int_{-\infty}^{\infty}\int_{-\infty}^{\infty} f_X(x) f_X(y) dydx\).
Mamy z definicji \(f_X\)
\(I^2 = \int_{-\infty}^{\infty}\int_{-\infty}^{\infty} \frac{1}{2\pi} e^{-\frac{x^2+y^2}{2}} dydx\).
Korzystamy z tzw. podstawienia biegunowego t.j. \(x = r\sin\theta\), \(y = r\cos\theta\) i otrzymujemy
\(I^2 = \int_0^{2\pi} \int_0^\infty \frac{1}{2\pi} e^{-\frac{r^2}{2}} r dr d\theta \).
Dodatkowe \(r\) w tej całce jest modułem wyznacznika macierzy pochodnych cząstkowych \(x\) i \(y\) po \(r\) i \(\theta\) zgodnie z wielowymiarowym wzorem na całkowanie przez podstawienie. Łatwo zauważyć, że zewnętrzna całka jest równoważna mnożeniu przez \(2\pi\), a zatem dostajemy
\(I^2 = \int_0^\infty e^{-\frac{r^2}{2}} r dr \).
Funkcja pod całką szczęśliwie (ale zgodnie z planem) jest pochodną funkcji \(-e^{-\frac{r^2}{2}}\), a zatem
\(I^2 = (-e^{-\frac{r^2}{2}})|_0^\infty = 0 - (-1) = 1\),
czyli \(I=1\), co kończy obliczenia dla rozkładu \(N(0,1)\).
Aby uzyskać analogiczny wynik w ogólnym przypadku, t.j. obliczyć całkę
\(J = \int_{-\infty}^\infty \frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{(x-\mu)^2}{2\sigma^2}}dx \)
wystarczy dokonać podstawienia \(y=\frac{x-\mu}{\sigma}\) i okazuje się, że \(J=I=1\).
Uwaga 7.11
Rozkład \(N(0,1)\), od którego rozpoczęliśmy nasze rozważania ma swoją nazwę - jest to tzw. standardowy rozkład normalny. Rozkład ten jak zobaczyliśmy, ma wyjątkowo prostą postać. Często pojawia się on w definicjach innych rozkładów, a także w rozumowaniach - jako najprostszy przypadek rozkładu normalnego. Rozkład ten ma też duże znaczenie historyczne z powodów, które w dzisiejszych czasach mogą nie być zupełnie oczywiste. Występuje on mianowicie w wielu rozumowaniach i procedurach wnioskowania statystycznego. Jednym z kroków takich procedur jest często odczytanie wartości dystrybuanty odpowiedniego rozkładu normalnego, ew. jej odwrotności, w pewnych punktach. W dzisiejszych czasach można te wartości w prosty sposób uzyskać za pomocą dowolnego pakietu statystycznego, kiedyś używano tablic matematycznych. Stablicowanie dystrybuant wszystkich rozkładów normalnych nie jest oczywiście możliwe, dlatego używano tylko tablic dla rozkładu standardowego, a metody wnioskowania formułowano tak, aby takie tablice wystarczały.
Wartość oczekiwaną dla zmiennych ciągłych definiujemy podobnie jak dla zmiennych dyskretnych
Definicja (wartość oczekiwana zmiennej ciągłej)
Niech \(X\) będzie ciągłą zmienną losową o gęstości \(f_X\). Wartością oczekiwaną \(X\) nazywamy
\(EX = \int_{-\infty}^\infty x f_X(x) dx\),
o ile funkcja \(x f_X(x)\) jest całkowalna z modułem.
Uwaga 7.12
Założenie całkowalności z modułem przyjmujemy z przyczyn podobnych jak w przypadku zmiennych dyskretnych. Tak jak poprzednio może ono prowadzić do dość mało intuicyjnych sytuacji. Można na przykład sprawdzić, że zmienna \(X\) o tzw. standardowym rozkładzie Cauchy'ego, t.j. o gęstości zadanej wzorem \(f_X(x) = \frac{1}{\pi(1+x^2)}\) nie ma wartości oczekiwanej pomimo tego, że jej gęstość jest symetryczna względem zera.
Uwaga 7.13
Powyższa definicja mocno przypomina definicję wartości oczekiwanej dla zmiennych dyskretnych. Nie jest to przypadek odosobniony. Jak wkrótce zobaczymy, większość definicji i twierdzeń dotyczących zmiennych dyskretnych ma swoje odpowiedniki ciągłe. Odpowiedniki te powstają z reguły przez zastąpienie sum całkami, a wyrażeń postaci \(P(X=x)\) wyrażeniami \(f_X(x)\). Nie jest to specjalnie zaskakujące - o rozkładach ciągłych możemy myśleć jako o granicach rozkładów dyskretnych.
Definicja wariancji dla zmiennych ciągłych jest taka sama jak dla dyskretnych
Definicja (wariancja zmiennej ciągłej)
Niech \(X\) będzie zmienną losową o rozkładzie ciągłym. Wtedy wariancją \(X\) nazywamy
\(Var(X) = E(X-EX)^2 \),
o ile ta wartość oczekiwana istnieje.
Podstawowe własności wartości oczekiwanej i wariancji przenoszą się z przypadku dyskretnego na ciągły. Poniżej omawiamy dwie takie sytuacje.
Twierdzenie 7.14
Niech \(X\) będzie zmienną o rozkładzie ciągłym i niech \(g:\mathbb{R}\rightarrow\mathbb{R}\) będzie funkcją mierzalną. Wtedy
\(Eg(X) = \int_{-\infty}^\infty g(x) f_X(x) dx \)
o ile \(Eg(X)\) istnieje. Ponadto \(Eg(X)\) istnieje wtedy i tylko wtedy, gdy funkcja \(g(x)f_X(x)\) jest całkowalna z modułem na \(\mathbb{R}\).
Nie będziemy dowodzić powyższego twierdzenia - dowód jest dość techniczny. Zwróćmy jednak uwagę na pewną subtelność: nawet jeśli \(X\) jest ciągła, to \(g(X)\) ciągła być nie musi! We wszystkich interesujących nas sytuacjach \(g(X)\) będzie ciągła, ale może być też dyskretna, a nawet, co łatwo sprawdzić, możemy \(g\) zdefiniować tak, aby \(g(X)\) było "dziwną" zmienną z przykładu 7.10. Wiążą się z tym oczywiście pewne problemy. O ile zdefiniowaliśmy wartość oczekiwaną zarówno dla zmiennych ciągłych jak i dyskretnych, i moglibyśmy podać osobne dowody dla obu sytuacji, o tyle nie mamy pojęcia czym jest wartość oczekiwana zmiennej z przykładu 7.10. Podobnej natury problemy występują także przy innych twierdzeniach omawianych w ramach tego wykładu. Dlatego w większości przypadków zrezygnujemy z podawania pracochłonnych dowodów. Warto jednak zwrócić uwagę, że ogólna ich idea jest z reguły podobna jak w przypadku dyskretnych, szczegóły są jednak dużo bardziej skomplikowane.
Można podać ogólną definicję wartości oczekiwanej, uogólniającą nasze definicje dla zmiennych dyskretnych i ciągłych. Przy tej ogólnej definicji twierdzenie 7.14 pozostaje prawdziwe, tak jak wiele innych twierdzeń tego wykładu. Niestety nie możemy sobie pozwolić na pełniejsze omówienie tego uogólnienia w ramach naszego wykładu, wymagałoby to od nas dużo dokładniejszego zagłębienia się w teorię miary i całki.
Poniższe twierdzenie jest uogólnieniem wzoru \(EX = \sum_{i=1}^\infty P(X \ge i)\) zachodzącego dla zmiennych o wartościach naturalnych na zmienne ciągłe.
Twierdzenie 7.15
Jeśli \(X\) będzie zmienną ciągłą o wartościach nieujemnych i \(EX < \infty\). Wtedy \(EX = \int_0^\infty (1-F_X(t)) dt = \int_0^\infty P(X \ge t) dt\).
Tym razem, wyjątkowo, podamy dowód.
Dowód
Tezę twierdzenia uzyskujemy przez prostą zamianę zmiennych:
\(\int_0^\infty P(X \ge t) dt = \int_{t=0}^\infty \int_{s=t}^\infty f_X(s) ds dt = \int_{s=0}^\infty \int_{t=0}^s f_X(s) dt ds = \int_{s=0}^\infty s f_X(s) ds = EX \).
Uwaga 7.16
Powyższe twierdzenie jest również prawdziwe dla zmiennych dyskretnych (niekoniecznie o wartościach naturalnych). Łatwy dowód pozostawiamy czytelnikowi.
Przykład 7.17 (wartość oczekiwana rozkładu jednostajnego)
Spróbujmy policzyć wartość oczekiwaną zmiennej \(X\) o rozkładzie jednostajnym \(Unif(a,b)\)
\(EX = \int_a^b t \frac{1}{b-a} dt = (\frac{t^2}{2(b-a)})|_a^b = \frac{b^2-a^2}{2(b-a)} = \frac{a+b}{2}\),
czyli bez niespodzianek.
Przykład 7.18 (wartość oczekiwana rozkładu wykładniczego)
Niech \(X \sim Exp(\theta)\). Wtedy, korzystając z twierdzenia 7.15 i wcześniejszego obliczenia \(F_X\) mamy
\( EX = \int_0^\infty P(X \ge t) dt = \int_0^\infty e^{-\theta t} dt = \int_0^\infty (-\frac{e^{-\theta t}}{\theta})' dt = (-\frac{e^{-\theta t}}{\theta})|_0^\infty = 0 - (-\frac{1}{\theta}) = \frac{1}{\theta}\).
Można też oczywiście obliczyć wartość oczekiwaną wprost z definicji.
W przypadku rozkładu normalnego mamy (ćwiczenia):
Fakt 7.19
Zmienna \(X \sim N(\mu,\sigma^2)\) ma wartość oczekiwaną \(EX = \mu\).
W tej części wykładu omówimy sytuacje, w których mamy do czynienia z więcej niż jedną zmienną o rozkładzie ciągłym. W szczególności zdefiniujemy pojęcie niezależności ciągłych zmiennych losowych, przyjrzymy się wartości oczekiwanej i wariancji sumy zmiennych, wreszcie uogólnimy pojęcie prawdopodobieństwa warunkowego na nowe sytuacje, które pojawiają się, gdy mamy do czynienia z ciągłymi zmiennymi losowymi.
Nie ma potrzeby definiować na nowo niezależności zmiennych ciągłych. Definicja, której używaliśmy w przypadku zmiennych dyskretnych jest nadal dobra. Przypomnijmy:
Definicja (Niezależność zmiennych losowych)
Zmienne losowe \(X,Y\) są niezależne, jeśli dla każdych zbiorów borelowskich \(A,B \subseteq \mathbb{R}\) (lub równoważnie dla każdych przedziałów \(A,B \subseteq \mathbb{R}\) zachodzi \( P(X \in A \wedge Y \in B) = P(X \in A) P(Y \in B)\).
W przypadku zmiennych dyskretnych mieliśmy do dyspozycji także prostsze, równoważne sformułowanie niezależności:
\(P(X=a \wedge Y=b) = P(X=a)P(Y=b)\) dla każdych \(a,b\in \mathbb{R}\).
W przypadku zmiennych ciągłych powyższe sformułowanie nie jest dobrą charakteryzacją niezależności - obie strony są zawsze równe \(0\). Intuicyjnie, powinniśmy zastąpić \(P(X=a)\) i \(P(Y=b)\) przez \(f_X(a)\) i \(f_X(b)\), ale czym zastąpić \(P(X=a \wedge Y=b)\) ?
Definicja (łączny rozkład ciągły)
Zmienne losowe \(X,Y\) mają łączny rozkład ciągły, jeśli istnieje funkcja \(f_{X,Y}:\mathbb{R}^2 \rightarrow \mathbb{R}_{\ge 0}\), zwana łączną gęstością \(X\) i \(Y\) taka, że dla dowolnego mierzalnego zbioru \(A \subseteq \mathbb{R}^2\) zachodzi
\( P( (X,Y) \in A) = \int_A f_{X,Y}(x,y) dxdy \).
Fakt 7.20
Jeśli zmienne \(X,Y\) mają łączny rozkład ciągły, to \(X\) i \(Y\) są ciągłe. Ponadto \(f_X(x) = \int_{-\infty}^\infty f_{X,Y}(x,y) dy\) oraz \(f_Y(y) = \int_{-\infty}^\infty f_{X,Y}(x,y) dx\).
Dowód
Aby pokazać, że zmienna \(X\) jest ciągła, wystarczy pokazać, że \(f_X\) jak w tezie faktu jest jej gęstością. Niech \(B \subseteq \mathbb{R}\) będzie zbiorem mierzalnym. Wtedy
\( \int_B f_X(x) dx = \int_B \int_{-\infty}^\infty f_{X,Y}(x,y) dy dx = P( (X,Y) \in B\times(-\infty,\infty)) = P(X \in B)\).
Dowód dla zmiennej \(Y\) jest analogiczny.
Przykład 7.21
Nie jest prawdą, że jeśli zmienne losowe \(X,Y\) są ciągłe, to są też łącznie ciągłe. Wystarczy wziąć dowolny \(X\) o rozkładzie ciągłym, na przykład \(X \sim N(0,1)\) oraz \(Y=X\). Wtedy dla zbioru \(A = \{(x,x):x\in\mathbb{R}\}\) mamy \(P((X,Y) \in A) = 1\), ale oczywiście całka z dowolnej funkcji po zbiorze \(A\) musi być równa zero, bo zbiór ten ma miarę zero. Przykład ten pokazuje, że łączna ciągłość jest dość mocnym założeniem i często może nie zachodzić. Jak się jednak za chwilę przekonamy, jeśli zmienne \(X,Y\) są ciągłe i niezależne, to są też łącznie ciągłe.
Definicja (łączna dystrybuanta)
Łączną dystrybuantą zmiennych losowych \(X,Y\) nazywamy funkcję \(F_{X,Y}(x,y) = P(X \le x \wedge Y \le y)\).
Twierdzenie 7.22
Jeśli zmienne \(X,Y\) mają łączny rozkład ciągły, to \(F_{X,Y}\) jest różniczkowalna (prawie wszędzie) i zachodzi (także prawie wszędzie):
\(f_{X,Y}(x,y) = \frac{\partial\partial F_{X,Y}(x,y)}{\partial x \partial y}\).
Dowód pomijamy.
Jeśli \(X,Y\) są niezależne i łącznie ciągłe, to różniczkując tożsamość \(F_{X,Y}(x,y) = F_X(x)F_Y(y)\) dwukrotnie (po \(x\) i po \(y\)) dostajemy \(f_{X,Y}(x,y) = f_X(x) f_Y(y)\). Oczywiście nie dowodzi to tego, że niezależne zmienne ciągłe są łącznie ciągłe, ale sugeruje w jaki sposób można opisać niezależność za pomocą gęstości.
Twierdzenie 7.23
Niech \(X,Y\) - zmienne o rozkładzie ciągłym. Wtedy \(X,Y\) są niezależne wtedy i tylko wtedy, gdy są łącznie ciągłe z gęstością \(f_{X,Y}(x,y)\) taką, że \(f_{X,Y}(x,y) = f_X(x)f_Y(y)\) (prawie wszędzie).
Dowód
Jeśli \(X\) i \(Y\) są niezależne, to dla dowolnych przedziałów \(A,B \subseteq \mathbb{R}\) zachodzi:
\(P(X \in A \wedge Y \in B) = P(X \in A) P (Y \in B) = \int_A f_X(x) dx \int_B f_Y(y)dy = \int_{A \times B} f_X(x)f_Y(y) dxdy \),
a zatem \(f_{X,Y}(x,y) = f_X(x)f_Y(y)\) jest łączną gęstością \(X\) i \(Y\).
Z drugiej strony jeśli \(X,Y\) są łącznie ciągłe i \(f_{X,Y}(x,y) = f_X(x)f_Y(y)\) prawie wszędzie, to dla dowolnych przedziałów \(A,B \subseteq \mathbb{R}\) całkując obie strony po \(A\times B\) dostajemy
\(P(X \in A \wedge Y \in B) = P(X \in A)P(Y \in B)\).
Sprawdźmy teraz jak wygląda gęstość sumy niezależnych zmiennych ciągłych:
Twierdzenie 7.24
Jeśli \(X,Y\) są niezależnymi zmiennymi ciągłymi i \(Z = X+Y\), to \(Z\) jest ciągła i \(f_Z(z) = \int_{-\infty}^\infty f_X(x) f_Y(z-x)dx\).
Dowód
Wiemy, że \(X,Y\) są niezależne, więc są też łącznie ciągłe z gęstością \(f_{X,Y}(x,y) = f_X(x) f_Y(y)\). A zatem
\( P(Z \le a) = P(X+Y \le a) = \int_{x+y \le a} f_X(x) f_Y(y) dxdy\).
Zmieńmy zmienne na \(z=x+y\) i \(x\). Mamy wtedy
\( P(Z \le a) = \int_{-\infty}^a \int_{-\infty}^\infty f_X(x) f_Y(s-x) dx ds = \int_{-\infty}^a (\int_{-\infty}^\infty f_X(x) f_Y(s-x) dx) ds\).
A zatem wewnętrzna całka jest gęstością \(Z\), co kończy dowód.
Przykład 7.25
Jako przykładowe zastosowanie pokażemy, że suma dwóch niezależnych zmiennych o rozkładzie normalnym ma też rozkład normalny. Ogólny przypadek
tego faktu jest dość uciążliwy w dowodzie, dlatego ograniczymy sie do przypadku \(X \sim Y \sim N(0,1)\). Niech \(Z = X+Y\), wtedy na mocy twierdzenia 7.24 mamy (wszystkie całki są po całej osi rzeczywistej):
\( f_Z(z) = \int \frac{1}{2\pi} e^{-\frac{x^2+(z-x)^2}{2}}dx = \frac{1}{2\pi} \int e^{-\frac{ (\sqrt{2}x - \frac{z}{\sqrt{2}})^2 + \frac{z^2}{2}}{2}} dx \).
Wstawiamy \(y = \sqrt{2}x + \frac{z}{\sqrt{2}}\) (czyli \(dx = \frac{dy}{\sqrt{2}}\) i otrzymujemy:
\( f_Z(z) = \frac{1}{2\pi} \int \frac{1}{\sqrt{2}} e^{-\frac{ y^2 + \frac{z^2}{2}}{2}} dy = \frac{1}{2\sqrt{\pi}} e^{-\frac{z^2}{4}} \int \frac{1}{\sqrt{2\pi}} e^{-\frac{ y^2}{2}} dy = \frac{1}{2\sqrt{\pi}}e^{-\frac{z^2}{4}}\).
W ostatnim przejściu całka jest równa \(1\) bo jest gęstością standardowego rozkładu normalnego. Łatwo zauważyć, że otrzymany wyrażenie opisuje gęstość rozkładu \(N(0,2)\).
Zachodzi też ogólniejszy
Fakt 7.26
Jeśli \(X \sim N(\mu_1,\sigma_1^2)\) i \(Y \sim N(\mu_2,\sigma_2^2)\), to \(Z = X+Y\) ma rozkład \(N(\mu_1+\mu_2,\sigma_1^2+\sigma_2^2)\).
Dowód jest analogiczny, ale rachunki trochę bardziej skomplikowane. Wystarczy ograniczyć się do przypadku \(X\sim N(0,1)\) i \(Y \sim N(0,\sigma^2)\) ze względu na następujący bardzo prosty fakt (ćwiczenia)
Fakt 7.27
Jeśli \(X \sim N(\mu,\sigma^2)\), to \(cX+a \sim N(c\mu+a,c^2\sigma^2)\).
Tak jak w przypadku zmiennych dyskretnych zachodzi następujące twierdzenie (dowód pominiemy)
Twierdzenie 7.28 (liniowość wartości oczekiwanej)
Jeśli \(X,Y\) są zmiennymi ciągłymi i istnieje \(EX\) i \(EY\), to istnieje też \(E(X+Y)\) i zachodzi \(E(X+Y) = EX+EY\).
Z powyższego twierdzenia, podobnie jak w przypadku zmiennych dyskretnych natychmiast otrzymujemy znany nam przydatny
wzór na obliczanie wariancji.
Fakt 7.29 (wzór na wariancję)
Jeśli zmienna ciągła \(X\) ma wariancję, to \(VarX = E(X^2) - (EX)^2 \).
Przykład 7.30 (wariancja zmiennej o rozkładzie jednostajnym)
Niech \(X \sim Unif(a,b)\). Spróbujmy obliczyć \(Var(X)\) korzystając ze wzoru \(VarX = E(X^2) - (EX)^2\). Mamy
\(E(X^2) = \int_{a}^b x^2 \frac{1}{b-a} dx = (\frac{x^3}{3(b-a)})|_a^b = \frac{b^3-a^3}{3(b-a)} = \frac{a^2+ab+b^2}{3}\).
Ponadto wiemy już, że
\((EX)^2 = \frac{(a+b)^2}{4} = \frac{a^2 +2ab+b^2}{4}\).
A zatem
\(VarX = \frac{4a^2+4ab+4b^2}{12}-\frac{3a^2+6ab+3b^2}{12} = \frac{a^2-2ab+b^2}{12} = \frac{(a-b)^2}{12}\).
Przykład 7.31 (wariancja zmiennej o rozkładzie wykładniczym)
Niech \(X \sim Exp(\theta)\). Obliczymy \(Var(X)\) korzystając, jak poprzednio, ze wzoru \(VarX = E(X^2) - (EX)^2\). Mamy
\(E(X^2) = \int_{0}^\infty x^2 \theta e^{-\theta x} dx = \int_{0}^\infty x^2 (-e^{-\theta x})' dx \).
Ze wzoru na całkowanie przez części dostajemy
\(E(X^2) = (-x^2 e^{-\theta x})|_0^\infty + 2\int_{0}^\infty x e^{-\theta x} dx = 0-(-0) + 2 \frac{1}{\theta}EX = \frac{2}{\theta^2}\).
Stąd
\(Var(X) = \frac{2}{\theta^2} - \frac{1}{\theta^2} = \frac{1}{\theta^2}\).
Można też pokazać (ćwiczenia), że
Twierdzenie 7.32
Jeśli \(X \sim N(\mu,\sigma^2)\), to \(VarX = \sigma^2\).
Tak jak w przypadku zmiennych dyskretnych, wartość oczekiwana ogólnie nie jest multiplikatywna, a wariancja addytywna, ale:
Twierdzenie 7.33
Jeśli \(X,Y\) są niezależnymi zmiennymi ciągłymi i istnieje \(EX\) i \(EY\), to istnieje też \(E(XY)\) i zachodzi \(E(XY) = EXEY\).
Twierdzenie 7.34
Jeśli \(X,Y\) są niezależnymi zmiennymi ciągłymi i istnieje \(VarX\) i \(VarY\), to istnieje też \(Var(X+Y)\) i \(Var(X+Y)=VarX+VarY\).
Dowód pierwszego z tych twierdzeń pominiemy, drugie wynika z pierwszego w sposób analogiczny jak dla zmiennych dyskretnych.
W prawdopodobieństwach warunkowych zdarzeń definiowanych przez zmienne ciągłe nie ma w większości przypadków niczego niezwykłego i możemy je obliczać standardowymi sposobami, korzystając ze znanych nam definicji. Dotyczy to na przykład prawdopodobieństw postaci \(P(X \in A | B)\) czy \(P(X \in A | Y \in B)\), o ile \(P(Y \in B) > 0\). Możemy też korzystając z definicji z wykładu o zmiennych dyskretnych zdefiniować warunkowy rozkład ciągłej zmiennej losowej
Nie jest jednak jasne co zrobić z prawdopodobieństwem warunkowym postaci \(P(X \in A | Y = y)\). Z jednej strony możemy często chcieć obliczać wartość tego wyrażenia. Możemy na przykład chcieć zapytać o to jakie jest prawdopodobieństwo tego, że losowa osoba waży co najmniej 80kg, jeśli wiemy, że ma 180cm wzrostu, itp. Z drugiej strony, jeśli spróbujemy obliczyć wartość tego wyrażenia za pomocą znanej nam definicji, to otrzymamy iloraz
\(P(X \in A | Y=y) = \frac{P(X \in A \wedge Y=y)}{P(Y=y)}\),
w którym zarówno licznik i jak i mianownik są równe 0.
Definicja (gęstość warunkowa)
Niech \(X\) i \(Y\) będą zmiennymi o łącznym rozkładzie ciągłym z gęstością \(f_{X,Y}\) i niech \(f_Y\) będzie gęstością \(Y\). Jeśli \(y \in \mathbb{R}\) jest taki, że \(f_Y(y) \neq 0\), to gęstością warunkową \(X\) pod warunkiem \(Y=y\) nazywamy funkcję
\( f_{X|Y=y}(x) = \frac{f_{X,Y}(x,y)}{f_Y(y)} \).
Definicja (prawdopodobieństwo warunkowe)
Przy założeniach jak wyżej i dla dowolnego mierzalnego \(A \subseteq \mathbb{R}\), prawdopodobieństwem warunkowym \(X \in A\) pod warunkiem \(Y=y\) nazywamy
\(P(X \in A | Y=y) = \int_A f_{X|Y=y}(x) dx \).
Zauważmy przede wszystkim, że \(f_{X|Y=y}\) jest funkcją gęstości, t.j. całka z \(f_{X|Y=y}\) po całej osi rzeczywistej wynosi \(1\). Wynika to natychmiast z faktu 7.20.
Dlaczego tak właśnie zostało zdefiniowane prawdopodobieństwo \(P(X \in A | Y=y)\)? Istnieją co najmniej 2 intuicyjne sposoby "wyprowadzenia" tej definicji. Po pierwsze: jeśli wiemy, że \(Y=y_0\), to patrzymy na gęstość \(f_{X,Y}(x,y)\) ograniczoną do \(y=y_0\), czyli po prostu \(f_{X,Y}(x,y_0)\). Chcielibyśmy użyć tej funkcji jako gęstości, ale nie całkuje się ona na \(\mathbb{R}\) do 1. Łatwo to jednak naprawić skalując ją czynnikiem \(f_Y(y)\).
Drugie intuicyjne wyprowadzenie mogłoby wyglądać tak: skoro nie wiemy jak obliczyć \(P(X \in A | Y=y)\), to obliczmy \(P(X \in A | Y \in I_y)\) dla małego przedziału \(I_y\) zawierającego \(y\). Jeśli ten przedział jest na tyle mały, żeby zarówno \(f_Y\) jak i \(f_{X,Y}(x,y)\) dla każdego ustalone \(x\) była na nim prawie stała (pomijamy to czy taki przedział musi istnieć, w końcu szukamy tylko intuicji), to dostajemy:
\(P(X \in A | Y \in I_y) = \frac{\int_{s \in A} \int_{t \in I_y} f_{X,Y}(s,t) dt ds}{ \int_{t \in I_y} f_Y(t) dt} \approx \frac{\int_{s \in A} |I_y| f_{X,Y}(s,y)ds}{|I_y| f_Y(y)} = \int_{s \in A} \frac{f_{X,Y}(s,y)}{f_Y(y)} ds \),
czyli dokładnie to czego się spodziewaliśmy.
Zdefiniowane przez nas prawdopodobieństwo warunkowe ma własności analogiczne do zwykłego prawdopodobieństwa warunkowego, np.
Twierdzenie 7.35 (Wzór na prawdopodobieństwo całkowite)
Jeśli \(X,Y\) są ciągłe i łącznie ciągłe, a \(A \subseteq \mathbb{R}\) jest mierzalny, to zachodzi
\( P(X \in A) = \int_{-\infty}^{\infty} P(X\in A | Y=y) f_Y(y) dy\).
Dowód wynika natychmiast z definicji gęstości warunkowej.
Ostatnią część tego wykładu poświęcimy zapowiadanemu wcześniej Centralnemu Twierdzeniu Granicznemu. Twierdzenie to mówi, że rozkład sumy wielu niezależnych zmiennych o tym samym rozkładzie jest bliski normalnemu (tak naprawdę rozkłady mogą być różne, ważne jest aby mały zbiór zmiennych nie dominował sumy, skoncentrujemy się jednak na najprostszej wersji twierdzenia).
Zastanówmy się jak mogłoby wyglądać to twierdzenie. Niech \(X_1,X_2,\ldots\) będzie ciągiem niezależnych zmiennych o tym samym rozkładzie. Chciałoby się powiedzieć, że rozkład \(Z_n = \sum_{i=1}^n X_i\) zbiega do rozkładu normalnego wraz z rosnącym \(n\), ale takie twierdzenie oczywiście nie może być prawdziwe, bo jeśli na przykład \(\mu = EX_1 = EX_2 = \ldots\) istnieje i jest większe od zera, to kolejne \(Z_n\) będą miały coraz większe wartości oczekiwane i nie mogą do niczego zbiegać.
Może w takim razie załóżmy istnienie \(\mu = EX_1 = EX_2 = \ldots\) i popatrzmy na graniczne zachowanie \(Z_n = \sum_{i=1}^n (X_i - \mu)\). Tutaj mamy \(EZ_n = 0\) dla każdego \(n\), ale niestety jeśli \(\sigma^2 = Var(X_1) = Var(X_2) = \ldots\) istnieje to \(Var(Z_n)\) są coraz większe i tak jak poprzednio ciąg \(Z_n\) nie może do niczego zbiegać. Musimy znormalizować \(Z_n\) tak, aby wszystkie \(Z_n\) miały tę samą wariancję, najprościej dzieląc przez \(\sqrt{n}\sigma\). Dlatego Centralne Twierdzenie Graniczne formułujemy tak:
Twierdzenie 7.36 (Centralne Twierdzenie Graniczne (CTG))
Niech \(X_1,X_2,\ldots\) będzie ciągiem niezależnych zmiennych losowych o tym samym rozkładzie, wartości oczekiwanej \(\mu\) i wariancji \(\sigma^2>0\). Niech ponadto \(Z_n = \frac{\sum_{i=1}^n (X_i - \mu)}{\sqrt{n}\sigma}\). Wtedy rozkład \(Z_n\) zbiega do rozkładu \(N(0,1)\) w następującym sensie:
\( \forall_{z \in \mathbb{R}} \lim_{n \rightarrow \infty} P(Z_n \le z) = \Phi(z)\),
gdzie \(\Phi\) jest dystrybuantą rozkładu \(N(0,1)\).
Zanim zdefiniujemy pojęcie łańcucha Markowa przyjrzyjmy się przykładom sytuacji, które można za ich pomocą opisywać i pytań, na które pozwalają one odpowiadać.
Przykład 8.1 (Student walczy)
Student raz w tygodni bierze udział w zajęciach z rachunku prawdopodobieństwa. Na każde zajęcia przychodzi przygotowany bądź nie. Jeśli w danym tygodniu jest przygotowany, to w następnym jest przygotowany z prawdopodobieństwem 0.7. Jeśli natomiast w danym tygodniu nie jest przygotowany, to w następnym jest przygotowany z prawdopodobieństwem 0.2. Interesują nas odpowiedzi na pytania w rodzaju:
Przykład 8.2 (Turniej trzyosobowy)
Trzech graczy: A, B i C gra turniej systemem "przegrywający odpada". Turniej zaczyna się od pojedynku A z B, a w każdej kolejnej grze gra zawodnik, który w poprzedniej nie grał ze zwycięzcą. Dla każdej pary zawodników znamy ich prawdopodobieństwa wygrania bezpośredniego pojedynku.
Przykład 8.3 (Hazardzista)
Hazardzista zaczyna grać z kapitałem początkowym 1000 zł. W każdej rundzie rozgrywki z prawdopodobieństwem 0.5 wygrywa 10 zł i z prawdopodobieństwem 0.5 przegrywa 10zł. Celem hazardzisty jest zdobycie kwoty 5000zł, ale zakończy grę także jeśli wcześniej zbankrutuje.
Zauważmy, że we wszystkich powyższych przykładach mamy do czynienia z obiektem/systemem/układem, który zawsze znajduje się w jednym z pewnej liczby stanów (student jest w stanie "przygotowany", bądź w stanie "nieprzygotowany", hazardzista w stanie "0zł", "1zł", itd.). Ponadto stan, w którym znajdzie się za chwilę jest wybierany losowo, ale prawdopodobieństwa znalezienia się w poszczególnych stanach zależą tylko od aktualnego stanu.
Formalnie taką sytuację możemy modelować następująco:
Definicja (łańcuch Markowa)
Łańcuchem Markowa o zbiorze stanów \(S \subseteq \mathbb{R}\) nazywamy ciąg zmiennych losowych \(X_0,X_1,X_2,\ldots\) taki, że
\( P(X_n = x_n | X_{n-1} = x_{n-1} \wedge X_{n-2} = x_{n-2} \wedge \ldots \wedge X_0 = x_0 ) = P(X_n = x_n | X_{n-1} = x_{n-1}) = p_{x_{n-1},x_n} \) dla każdego \(n > 0\) i ciągu stanów \(x_0,x_1,\ldots,x_n \in S\).
W tej definicji zmienna \(X_t\) opisuje stan, w którym znajduje się łańcuch Markowa w chwili \(t\). Intuicyjnie, warunek z definicji łańcucha Markowa mówi, że zmienna \(X_t\) zależy tylko od zmiennej \(X_{t-1}\). Co ważne, nie znaczy to, że \(X_t\) jest niezależna od \(X_0,\ldots,x_{t-2}\). Znaczy to jedynie tyle, że "cała zależność \(X_t\) od \(X_0,\ldots,X_{t-1}\) jest zawarta w zależności \(X_t\) od \(X_{t-1}\)".
Uwaga 8.4
Ze względu na definicję zmiennej losowej (przypomnijmy: zmienne losowe mają wartości rzeczywiste), w powyższej definicji zakładamy, że stany łańcucha Markowa są liczbami rzeczywistymi. W praktyce takie ograniczenie jest dość niewygodne, np. w przykładzie z trzyosobowym turniejem naturalne byłoby przyjęcie \(S = \{\{A,B\},\{B,C\},\{A,C\}\}\). Zawsze można jednak przypisać takim ogólniejszym stanom etykiety będące liczbami rzeczywistymi, czy nawet naturalnymi, i w ten sposób uzyskać łańcuch Markowa zgodny z definicją.
Liczby \(p_{i,j}\) występujące w definicji łańcucha Markowa to tzw. prawdopodobieństwa przejścia w jednym kroku. Jeśli w danej chwili łańcuch jest w stanie \(i\), to z prawdopodobieństwem \(p_{i,j}\) znajdzie się w następnej chwili w stanie \(j\). Liczby te wygodnie jest ułożyć w macierz:
Definicja (macierz przejścia)
Macierzą przejścia (w jednym kroku) łańcucha Markowa nazywamy macierz \(M = (p_{i,j})_{ i,j \in S}\).
Uwaga
W dalszej części wykładu będziemy symbolem \(M\) oznaczać zarówno macierz przejścia łańcucha, jak i sam łańcuch.
Z oczywistych względów zachodzi następujący fakt.
Fakt 8.5
Wiersze macierzy przejścia łańcucha Markowa sumują się do 1.
Uwaga 8.6
Może się zdarzyć, że zbiór \(S\) nie będzie skończony (może nawet nie być przeliczalny, ale takie sytuacje nie będą nas interesować). W związku z tym zdefiniowany powyżej obiekt może czasem nie być (skończoną) macierzą. Jak jednak łatwo zauważyć podstawowe operacje macierzowe takie jak mnożenie macierzy przez wektor, czy przez inną macierz, mają sens także dla takich "nieskończonych macierzy". W ogólnym przypadku mogą pojawić się problemy związane ze zbieżnością, ale w naszym przypadku problemy takie nie wystąpią ze względu na Fakt 8.5. W związku z tym, w dalszym ciągu wykładu będziemy ignorowali tę kwestię i mówili po prostu o macierzy przejścia.
Przykład 8.1 (Student walczy, c.d.)
W przykładzie ze studentem mamy dwa stany: 1 - student jest przygotowany, oraz 2 - student nie jest przygotowany. Macierz przejścia wygląda w tym przypadku tak:
\(
\left(
\begin{array}{cc}
0.7 & 0.3 \\
0.2 & 0.8
\end{array}
\right)
\)
Przypuśćmy, że znamy rozkład zmiennej \(X_t\), tzn. prawdopodobieństwa tego, że w chwili \(t\) znajdujemy się w poszczególnych stanach. Jak wygląda rozkład zmiennej \(X_{t+1}\)? I ogólniej, jak wygląda rozkład zmiennej \(X_{t+s}\) dla \(s \in \mathbb{N}\) ? Okazuje się, że można go łatwo obliczyć korzystając z macierzy \(M\).
Fakt 8.7
Niech \(\pi(t)\) będzie rozkładem \(X_t\) reprezentowanym za pomocą wierszowego wektora prawdopodobieństw poszczególnych stanów, t.j.\ \(\pi(t)_s = P(X_t = s)\). Wtedy
\( \pi(t+1) = \pi(t) M\)
i ogólniej
\( \pi(t+s) = \pi(t) M^s \).
Dowód
Ze wzoru na prawdopodobieństwo całkowite mamy:
\(P(X_{t+1} = a) = \sum_{b \in S} P(X_t = b) P(X_{t+1} = a | X_t = b) = \sum_{b \in S} \pi(t)_b M_{b,a}\),
a to jest definicja mnożenia macierzy przez wektor (z lewej strony!).
Ogólniejsza wersja wynika z prostszej przez indukcję.
Powyższy fakt pokazuje siłę macierzowej reprezentacji łańcuchów Markowa. Istnieją bowiem algorytmy pozwalające bardzo szybko obliczyć \(M^s\) nawet dla dużych \(s\) (oparte, na przykład, na rozkładzie Jordana macierzy). Dzięki temu możemy w relatywnie prosty sposób obliczać rozkład \(X_{t+s}\) znając rozkład \(X_t\).
W dalszej części wykładu elementy macierzy \(M^k\) będziemy oznaczać \(p_{i,j}(k)\). W szczególności \(p_{i,j} = p_{i,j}(1)\).
Zastanowimy się teraz jak można odpowiadać na pytania w rodzaju "Jeśli łańcuch Markowa jest w stanie \(b\), to jakie jest prawdopodobieństwo tego, że kiedykolwiek dotrze do stanu \(a\)?". Będziemy to prawdopodobieństwo oznaczać \(f_{b,a}\). Symbol \(f_{a,a}\) będziemy interpretować jako prawdopodobieństwo tego, że wrócimy do stanu \(a\) po wykonaniu co najmniej jednego kroku. Innym naturalnym pomysłem byłoby przyjęcie \(f_{a,a} = 1\), ale wybrana przez nas konwencja jest wygodniejsza w praktyce (choć prowadzi do nieco bardziej skomplikowanych wzorów).
Twierdzenie 8.8
Niech \(M\) będzie łańcuchem Markowa o zbiorze stanów \(S\) i niech \(a,b \in S\). Wtedy
\( f_{b,a} = \sum_{c \in S \setminus a} p_{b,c} f_{c,a} + p_{b,a}\).
Dowód
Przyjmijmy, że \(X_0 = b\) i niech \(A\) będzie zdarzeniem odpowiadającym dotarciu kiedykolwiek do stanu \(a\), formalnie \(A = \{ \omega \in \Omega : \exists_{i \ge 1} X_i(\omega) = a \}\).
Interesuje nas obliczenie P(A).
Ze wzoru na prawdopodobieństwo całkowite mamy
\( P(A) = \sum_{c \in S} P(X_1 = c) P(A|X_1 =c) = \sum_{c \in S} p_{b,c} P(A|X_1 = c) \).
Łatwo zauważyć, że \( P(A | X_1 = c) = f_{c,a} \) dla \(c \neq a\) (zachęcamy czytelnika do uzasadnienia tego formalnie) oraz \(P(A|X_1 = a) = 1\), skąd dostajemy tezę.
Przypomnijmy, że symbolem \(p_{i,j}(k)\) oznaczamy prawdopodobieństwo przejścia ze stanu \(i\) do stanu \(j\) w \(k\) krokach, a symbolem \(f_{i,j}\) prawdopodobieństwo dotarcia (kiedykolwiek) z \(i\) do \(j\). Niech ponadto \(f_{i,j}(k)\) będzie prawdopodobieństwem dotarcia z \(i\) do \(j\) po raz pierwszy po \(k\) krokach. Oczywiście zachodzi \(f_{i,j} = \sum_{k=1}^\infty f_{i,j}(k)\).
Definicja (stan powracający/chwilowy)
Stan \(a\) jest powracający, jeśli \(f_{a,a} = 1\), czyli jeśli wracamy do niego z prawdopodobieństwem \(1\). Stan jest chwilowy, jeśli nie jest powracający.
Przykład 8.9
Łatwo zauważyć oba stany studenta i wszystkie trzy stany turnieju trzyosobowego są powracające. W przykładzie z hazardzistą bankructwo i osiągniecie celu są stanami powracającymi, natomiast wszystkie pozostałe stany są chwilowe.
Twierdzenie 8.10
Stan \(a\) jest powracający wtedy i tylko wtedy, gdy \( \sum_{k \ge 1} p_{a,a}(k) = \infty\).
Uwaga 8.11
Tezę powyższego twierdzenia można interpretować następująco: stan \(a\) jest powracający wtedy i tylko wtedy, gdy średnia liczba powrotów do \(a\) jest nieskończona. Jest to interpretacja bardzo przydatna, ale niestety nie do końca poprawna - liczba powrotów może być nieskończona, a zatem nie jest zmienną losową w sensie naszej definicji.
Dowód
Aby uniknąć problemu, o którym wspomnieliśmy w uwadze 8.11, przyjmijmy, że \(X_0 = a\) oraz niech \(Y_N\) będzie liczbą powrotów do \(a\) w pierwszych \(N\) krokach (ograniczając się do pierwszych \(N\) kroków unikamy nieskończonych wartości). Wtedy z liniowości wartości oczekiwanej
\(EY_N = \sum_{k=1}^N E[X_k=a] = \sum_{k=1}^N P(X_k=a) = \sum_{k=1}^N p_{a,a}(k)\),
a zatem \( \sum_{k \ge 1} p_{a,a}(k) = \infty\) jest granicą \(EY_N\).
Jeśli \(a\) jest stanem powracającym, to \(\sum_{k\ge 1} f_{a,a}(k) = 1\), a zatem istnieje \(K\) takie, że \(\sum_{k=1}^K f_{a,a}(k) \ge 1-\epsilon\), tzn.\ z prawdopodobieństwem \( \ge 1-\epsilon\) wrócimy do stanu \(a\) w nie więcej niż \(K\) krokach. Mamy wtedy \(P(Y_K \ge 1) \ge 1-\epsilon\), a także \(P(Y_{2K} \ge 2) \ge P(Y_K \ge 1)^2 \ge (1-\epsilon)^2\) i ogólnie \(P(Y_{nK} \ge n) \ge (1-\epsilon)^n\).
Dla \(N \ge nK\) dostajemy
\(EY_N = \sum_{i = 1}^\infty P(Y_N \ge i) \ge \sum_{i=1}^n P(Y_N \ge i) \ge \sum_{i=1}^n P(Y_{iK} \ge i) \ge \sum_{i=1}^n (1-\epsilon)^i = \frac{1-(1-\epsilon)^{n+1}}{\epsilon}\).
Biorąc odpowiednio małe \(\epsilon\) i odpowiednio duże \(n\) (a zatem także odpowiednio duże \(N\)) widzimy, że \(EY_N\) może przyjmować dowolnie duże wartości, a co za tym idzie \(\lim_{N \rightarrow \infty} EY_N = \infty\).
Aby pokazać implikację w drugą stronę, przyjmijmy, że \(a\) jest chwilowy. Wtedy \(f_{a,a} < 1\) . Dla dowolnego \(N\) zachodzi \(P(Y_N \ge k) \le f_{a,a}^k\), a zatem \(EY_N = \sum_{k=1}^\infty P(Y_N \ge k) \le \frac{f_{a,a}}{1-f_{a,a}}\), co kończy dowód.
Definicja (stany osiągalne)
Stan \(b\) jest osiągalny ze stanu \(a\) jeśli istnieje takie \(k \in \mathbb{N}\), że \(p_{a,b}(k) > 0\). Zbiór stanów osiągalnych ze stanu \(a\) oznaczamy \(A(a)\).
Definicja (stany komunikujące się)
Stany \(a,b\) komunikują się jeśli \(a \in A(b) \) oraz \(b \in A(a)\).
Uwaga 8.12
Te definicje mają naturalną interpretację grafową. Jeśli zbudujemy graf, w którym wierzchołkami są stany łańcucha, a krawędź skierowana \((a,b)\) istnieje, gdy \(p_{a,b} > 0\), to:
Fakt 8.13
Jeśli stan \(a\) jest powracający, to każdy stan \(b\) osiągalny z \(a\) też jest powracający i zachodzi \(A(a) = A(b)\).
Dowód (szkic)
Ponieważ \(b\) jest osiągalny z \(a\) to dla pewnego \(k\) zachodzi \(p = p_{a,b}(k) > 0\). Z drugiej strony, ponieważ \(a\) jest powracający, to z prawdopodobieństwem \(1\) wrócimy do \(a\) po \(k\)-tym kroku. Stąd \(f_{b,a} = 1\). Niech \(X_0 = b\) i niech \(Y_N\) i \(Z_N\) będą liczbą odwiedzin odpowiednio \(a\) i \(b\) w pierwszych \(N\) krokach. Wtedy wiemy z twierdzenia 8.10, że \(\lim_{N\rightarrow\infty}EY_N = \infty\), ale ponieważ \(EZ_{N+k} \ge pEY_N\) (bo za każdym razem gdy odwiedzamy \(a\) mamy szansę \(p\) na odwiedzenie \(b\) po \(k\) krokach), to dostajemy też \(\lim_{N\rightarrow \infty} EZ_N = \infty\), co w połączeniu z twierdzeniem 8.10 oznacza, że \(b\) jest powracający. Druga część tezy jest oczywista.
(Zachęcamy czytelnika do uzupełnienia powyższej argumentacji.)
Z powyższych rozważań wynika następujący wniosek, bardzo przydatny w szybkiej klasyfikacji stanów łańcucha Markowa.
Wniosek 8.14
Niech \(G\) będzie grafem odpowiadającym skończonemu łańcuchowi Markowa \(M\), jak w uwadze 8.12 i niech \(D\) będzie DAG-iem silnie spójnych składowych \(G\). Wtedy:
Wniosek 8.15
W skończonym łańcuchu Markowa dla każdego stanu \(a\) istnieje stan powracający \(b\) osiągalny z \(a\). W szczególności każdy skończony łańcuch Markowa zawiera stan powracający.
Definicja (łańcuch nieredukowalny)
Łańcuch nazywamy nieredukowalnym (w starszej literaturze nieprzywiedlny), jeśli składa się z jednej klasy powracającej.
Uwaga 8.16
Z wniosku 8.15 wynika, że w przypadku łańcuchów skończonych nie ma potrzeby żądać, by jedyna klasa łańcucha była powracająca - ona musi być powracająca bo zawiera stan powracający. Nie jest to jednak prawdą w przypadku łańcuchów nieskończonych.
Jesteśmy już gotowi odpowiedzieć na pytania postaci "Średnio po ilu krokach łańcuch Markowa dotrze do stanu \(a\)?". Ograniczymy się przy tym do następującej sytuacji: Niech \(M\) będzie skończonym łańcuchem Markowa o dokładnie jednej klasie powracającej i niech \(a\) będzie jednym z jej elementów. Wtedy dla każdego stanu \(b\) zachodzi \(f_{b,a}=1\) (dlaczego?). Interesuje nas obliczenie dla każdego stanu \(b\) średniej liczby kroków \(\mu_{b,a}\) potrzebnej na dotarcie do \(a\). W szczególności przez \(\mu_{a} = \mu_{a,a}\) oznaczamy średnią liczbę kroków potrzebnych, aby wrócić do \(a\).
Twierdzenie 8.17
Niech \(M\) będzie jak powyżej. Wtedy dla każdego \(b \in S\) zachodzi:
\( \mu_{b,a} = \sum_{c \in S \setminus a} p_{b,c}(1+\mu_{c,a}) + p_{b,a} = 1+\sum_{c \in S \setminus a} p_{b,c} \mu_{c,a} \).
Uwaga 8.18
Jeśli w łańcuchu istnieje więcej niż jeden stan powracający, a interesuje nas dojście do któregokolwiek z nich, to możemy skleić wszystkie stany powracające w jeden (zachęcamy czytelnika do uzupełnienia szczegółów). Takie sklejenie można wykonać nawet jeśli istnieje więcej niż jedna klasa powracająca.
W takim przypadku można też próbować obliczać średni czas dojścia do stanu chwilowego pod warunkiem, że do niego w ogóle dojdziemy. Ta sytuacja jest bardziej skomplikowana i nie będziemy się nią tu zajmować.
Dowód
Dowód przebiega analogicznie do dowodu twierdzenia 8.8.
Załóżmy, że \(X_0 = b\) i niech \(\tau = \min_t \{ X_t = a \}\), czyli \(\tau\) jest liczbą kroków, po której po raz pierwszy docieramy do stanu \(a\). Interesuje nas obliczenie
\( \mu_{b,a} = E(\tau) \).
Ze wzoru na całkowitą wartość oczekiwaną mamy
\( \mu_{b,a} = \sum_{c \in S} P(X_1 = c) E(\tau | X_1 = c) = \sum_{c \in S} p_{b,c} E(\tau | X_1 = c)\).
Łatwo zauważyć, że \(E(\tau | X_1 = c) = \mu_{c,a}+1\) dla \(c \neq a\)(zachęcamy czytelnika do uzasadnienia tego formalnie) oraz \(E(\tau|X_1 = a) = 1\), skąd dostajemy tezę.
Postaramy się teraz opisać długookresowe zachowanie łańcucha Markowa. Dzięki temu będziemy odpowiadać na pytania w rodzaju:
Żeby to zrobić, musimy najpierw wprowadzić kilka definicji.
Definicja (okresowość)
Stan \(a\) jest okresowy, jeśli istnieje liczba całkowita \(d > 1\) (zwana okresem \(a\)) taka, że jeśli \(p_{a,a}(k) > 0\) dla pewnego \(k\), to \(d | k\). Stan, który nie jest okresowy nazywamy nieokresowym. Łańcuch Markowa nie zawierający stanów okresowych nazywamy łańcuchem nieokresowym
Przykład 8.19
Rozważmy łańcuch Markowa \(M\) o stanach \(0,1,\ldots,k-1\) i przejściach \(p_{a,b} = 1\) jeśli \(b = (a+1) \mod k\) oraz \(p_{a,b} = 0\) wpp. Wtedy wszystkie stany \(M\) mają okres \(k\).
Fakt 8.20
Jeśli \(a\) jest okresowy z okresem \(d\) to każdy stan \(b\) komunikujący się z \(a\) też jest okresowy z okresem \(d\).
Dowód
Ponieważ \(a\) i \(b\) się komunikują, to mamy \(p_{a,b}(k) > 0\) oraz \(p_{b,a}(l) > 0\) dla pewnych \(k,l > 0\). Gdyby \(b\) nie spełniał tezy, to istniałoby \(i > 0\) niepodzielne przez \(d\) i takie, że \( p_{b,b}(i) > 0\). Ale wtedy moglibyśmy przejść z \(a\) do \(a\) zarówno w \(k+l\) krokach jak i \(k+l+i\) krokach, co nie jest możliwe, bo co najmniej jedna z tych liczb nie jest podzielna przez \(d\).
Możemy już sformułować najważniejszy wynik tego rozdziału:
Twierdzenie 8.21 (ergodyczne)
Dla skończonego nieredukowalnego i nieokresowego łańcucha Markowa \(M\) o zbiorze stanów \(S\) istnieje wektor \(\pi_a, a \in S\) takie, że:
Pojawiający się w powyższym twierdzeniu wektor \(\pi\) nazywa się z reguły rozkładem stacjonarnym, co można łatwo zrozumieć patrząc na pierwsze dwa punkty tezy twierdzenia ergodycznego. Pierwszy z punktów mówi, że \(\pi\) jest rozkładem prawdopodobieństwa na zbiorze stanów \(S\). Drugi punkt mówi, że jest on stacjonarny w następującym sensie: Jeśli \(X_t\) ma rozkład \(\pi\), to \(X_{t+1}\) także ma rozkład \(\pi\).
Najważniejszy jest oczywiście punkt trzeci, który mówi, że niezależnie od tego w jakim stanie łańcuch startuje, po odpowiednio długim czasie zbiegnie do rozkładu \(\pi\). Innymi słowy, niezależnie od rozkładu \(X_0\), dla odpowiednio dużych \(t\), zmienna \(X_t\) będzie miała rozkład dowolnie bliski \(\pi\).
Przykład 8.22
Widać, że twierdzenie ergodyczne jest dokładnie tym czego potrzebujemy, aby móc odpowiadać na pytania, które zadaliśmy na początku tego rozdziału, np. "Na dłuższą metę, jak często student jest przygotowany?". Przypomnijmy, że student znajduje się w jednym z dwóch stanów: 1 - przygotowany, 2 - nieprzygotowany. Macierz przejścia między tymi stanami wygląda następująco:
\( M =
\left(
\begin{array}{cc}
0.7 & 0.3 \\
0.2 & 0.8
\end{array}
\right)
\)
Odpowiedzią na pytanie, o to jak często student jest na dłuższą metę przygotowany jest liczba \(\pi_1\) z twierdzenia ergodycznego. Jak ją znaleźć? Oczywiście za pomocą twierdzenia ergodycznego, a konkretnie dwóch pierwszych punktów tezy tego twierdzenia. Mamy mianowicie:
\( \pi M = \pi \),
czyli
\( 0.7\pi_1 + 0.2 \pi_2 = \pi_1 \) ,
\(0.3\pi_1 + 0.8 \pi_2 = \pi_2\)
(tak naprawdę wystarczy jedno z tych równań, dlaczego?)
oraz
\(\pi_1 + \pi_2 = 1\).
Łatwo dostajemy \(\pi_1 = 0.4\), \(\pi_2 = 0.6\).
Uwaga 8.23
Łatwo zauważyć, że założenia twierdzenia ergodycznego są do pewnego stopnia konieczne:
Ostatnie twierdzenie tego wykładu pokazuje interesujące zastosowanie rozkładu stacjonarnego.
Twierdzenie 8.24
Przy założeniach jak w twierdzeniu ergodycznym dla każdego stanu \(a \in S\) zachodzi \(\mu_{a,a} = \frac{1}{\pi_a}\).
Formalny dowód pominiemy, ale intuicyjnie twierdzenie to powinno być jasne: Skoro na dłuższą metę \(\pi_a\) jest frakcją kroków, w których łańcuch jest w stanie \(a\), to średni odstęp między wystąpieniami stanu \(a\) wynosi \(\frac{1}{\pi_a}\).
Przykład 8.25
Możemy z tego twierdzenia wywnioskować, że jeśli student jest w danym tygodniu przygotowany, to musimy czekać średnio \(\frac{1}{0.4} = 2.5\) tygodnie, aż znów będzie przygotowany. Akurat w tym przypadku ten sam wynik można w bardzo prosty sposób uzyskać wprost z definicji, ale jeśli łańcuch jest bardziej skomplikowany twierdzenie ergodyczne jest często najprostszą metodą.
Łańcuchy Markowa mają mnóstwo bardzo różnorodnych zastosowań. Wspomnimy w tym miejscu o zaledwie kilku z nich:
Wybrano losowo jedną z trzech kartek, pomalowanych z obu stron: czarno-czarnej, czarno-białej i biało-białej, a następnie wybrano losowo jedną z jej stron. Jeśli ta strona jest czarna, to jakie jest prawdopodobieństwo tego, że druga też jest czarna?
Wybieramy losowo numer z książki telefonicznej i pod niego dzwonimy. Osobę, która odbierze pytamy o to, czy ma dwójkę dzieci, a jeśli okaże się, że tak, to:
Uwaga: W tym zadaniu trzeba oczywiście przyjąć pewne założenia co do częstości urodzin chłopców/dziewczynek oraz sposobu w jaki nadawane są im imiona.
Na inżynierii oprogramowania 16 studentów ma być podzielonych na 4 zespoły. Wśród nich jest 4 pracujących, z doświadczeniem w projektowaniu dużych systemów. Jakie jest prawdopodobieństwo, że każdy z nich trafi do innej grupy?
Uwaga: Nie rozwiązuj tego zadania wprost ze schematu klasycznego. Zamiast tego użyj pojęcia prawdopodobieństwa warunkowego.
W 3-osobowym pojedynku trzech kawalerów A, B, C strzela do wybranego przez siebie celu w kolejności A, B, C cyklicznie, aż zostanie tylko jeden z nich. Przypuśćmy, że A trafia z prawdopodobieństwem 0.3, B trafia zawsze, a C z prawdopodobieństwem 0.5. Jaką strategię powinien przyjąć A?
Uwaga: Zakładamy, że pozostali strzelcy postępują racjonalnie, tzn. tak aby maksymalizować swoje szanse przeżycia.
Grasz w turnieju szachowym, w którym z 50% graczy masz szansę wygrania 30%, z 25% graczy szansę 40% i z 25% graczy szansę 50%. Pierwszą partię rozgrywasz z losowym przeciwnikiem. Jakie sa twoje szanse wygrania?
W urnie są dwie kule: biała i czarna. \((n-2)\)-krotnie losujemy kulę z urny, po czym wrzucamy ją z powrotem wraz z drugą kulą tego samego koloru. Jakie jest prawdopodobieństwo tego, że po zakończeniu losowań wśród \(n\) kul dokładnie \(k\) jest białych?
Mamy \(n\) urn. W \(i\)-tej urnie znajduje się \(i-1\) kul białych i \(n-i\) kul czarnych. Wybieramy losowo urnę, a następnie losujemy z niej dwie kule. Oblicz prawdopodobieństwo tego, że są to kule różnych kolorów jeśli losujemy:
Gracz w teleturnieju wybiera jedną z 3 zasłon. Za jedną z zasłon jest ukryty samochód, za pozostałymi nic nie ma. Prowadzący odsłania jedną z pozostałych dwóch zasłon i pokazuje, że niczego za nią nie ma, po czym daje graczowi szansę na zmianę wyboru.
Uwaga: Przeanalizowanie konkretnej sytuacji opisanej w zadaniu jest istotnie bardziej skomplikowane niż porównanie strategii "zawsze zmieniaj" ze strategią "nigdy nie zmieniaj". Czy widzisz dlaczego?
Trzech więźniów A,B,C oczekuje na wykonanie kary śmierci. Więzień A dowiedział się, że dwóch więźniów zostanie ułaskawionych, ale nie wie o których więźniów chodzi. Chciałby o to zapytać strażnika, ale ponieważ ten odmawia udzielania informacji dotyczących jego losu, prosi go o ujawnienie jednego z ułaskawionych więźniów spośród B,C. Strażnik ponownie odmawia twierdząc, że w ten sposób zmniejszyłby szansę A na ułaskawienie z 2/3 do 1/2, a nie chce tego robić, bo lubi A. Czy strażnik słusznie odmawia?
Przypuśćmy, że udało ci sie wygrać pierwsza partię. Jakie jest prawdopodobieństwo, że grałeś z graczem 3-go rodzaju?
Mamy do dyspozycji 3 telefony. Wiemy, że jeden z nich zawsze działa, drugi nigdy nie działa (ale zjada monety), a trzeci działa z prawdopodobieństwem \(p=\frac{1}{2}\) (w pozostałych przypadkach zjada monety). Próbujemy zadzwonić z jednego z automatów i zjada on monetę. Zmieniamy automat i udaje nam się zadzwonić. Próbujemy raz jeszcze (nie zmieniając telefonu) i znów się udaje. Jakie jest prawdopodobieństwo tego, że telefon z którego zadzwoniliśmy 2 razy jest tym, który zawsze działa? Czy odpowiedź zmieniłaby się, gdyby nie było w zadaniu pierwszej (nieudanej) próby?
W sejmie mamy dwie partie. Posłowie partii A nigdy nie zmieniają zdania na żaden temat, a każdy z posłów partii B zmiena zdanie pomiędzy na temat głosowanej ustawy pomiędzy dwoma jej głosowaniami z prawdopodobieństwem \(p\). Wiadomo, że posłowie partii A stanowią frakcję \(f\) wszystkich posłów, pozostali pochodzą z partii B. Obserwujemy losowego posła i głosuje on w ten sam sposób w dwóch kolejnych głosowaniach. Jakie jest prawdopodobieństwo tego, że pochodzi on z partii A?
Dane są dwie urny. W pierwszej urnie znajdują się 2 czerwone kule i 1 czarna, w drugiej 101 czerwonych i 100 czarnych. Ktoś wybiera losowo urnę (nie wiemy którą), z wybranej urny losuje kulę i mówi nam jakiego jest ona koloru. Następnie z tej samej urny losowana jest druga kula, przy czym możemy zażądać, aby uprzednio pierwsza kula wróciła do urny. Naszym zadaniem jest zgadnięcie z której urny są losowane kule. Jak wygląda optymalna strategia?
Uwaga: To zadanie jest dość pracochłonne.
Danych jest \(N+1\) urn. W \(i\)-tej urnie znajduje się \(i\) kul białych i \(N-i\) kul czerwonych, dla \(i=0,...,N\). Wybieramy losowo urnę, a następnie \(n\)-krotnie losujemy z wybranej urny jedną kulę ze zwracaniem. Przypuśćmy, że za każdym razem była to kula czerwona. Jakie jest prawdopodobieństwo tego, że kolejna kula wylosowana z tej urny też będzie czerwona?
Uwaga: Laplace użył tego rozumowania do argumentowania na temat prawdopodobieństwa tego, że słońce następnego dnia wzejdzie na podstawie tego, że wzeszło odpowiednio wiele razy wcześniej. Co sądzisz o tym "zastosowaniu"?
Obliczyć wartość oczekiwaną i wariancję rozkładu geometrycznego.
Obliczyć wartość oczekiwaną i wariancję rozkładu Poissona.
Jan ma przyjaciela, który jest nałogowym hazardzistą i uwielbia grać w ruletkę. Za każdym razem stawia wtedy 10zł na liczbę 13, i jeśli ta liczba wypada (a jest ona jedną z 38 liczb na kole ruletki), wygrywa z powrotem swoje 10zł oraz dodatkowe 350zł, w przeciwnym przypadku traci postawione 10zł. Jan postanawia wyleczyć go z nałogu. Przed każdą wizytą w kasynie zakłada się z przyjacielem o to, że po 36 obstawieniach będzie na minusie. Stawka zakładu wynosi 200zł. Jak dobrze działa takie lekarstwo?
Gramy w następującą grę: Ktoś rzuca monetą, aż do wypadnięcia pierwszego orła. Powiedzmy, że orzeł wypadł w \(i\)-tym rzucie. Następnie do dwóch kopert wkłada odpowiednio \(2^i\) i \(2^{i+1}\) zł. Dostajemy losowo wybraną kopertę i mamy zdecydować, czy chcemy wziąć tę drugą czy nie.
Kasyno oferuje następującą grę: Krupier rzuca monetą do momentu wypadnięcia pierwszego orła. Jeśli pierwszy orzeł wypada w \(i\)-tym rzucie, wygrywamy
\(2^i\) zł. Ile warto zapłacić za granie w tę grę? Zastanów się nad praktycznym sensem tego wyniku.
Na kinowy seans "dla singli" spóźniło się 15 singli: 8 mężczyzn i 7 kobiet. Ponieważ jest już ciemno, a spóźnialscy nie chcą przeszkadzać innym, siadają wszyscy losowo w pierwszym rzędzie, który ma 16 miejsc (czyli o jedno za dużo). Ile będzie średnio par mężczyzna-kobieta siedzących obok siebie?
Kupujemy gumy do żucia, w każdej znajduje się jedna z \(n\) historyjek. Ile gum trzeba średnio kupić, żeby zebrać wszystkie historyjki? Jaka jest wariancja tej wielkości? Zakładamy, że historyjki znajdujące się w kolejno kupowanych gumach są losowe (każda równie prawdopodobna) i niezależne od siebie.
Wrzucamy losowo \(n\) kul do \(n\) urn. Oblicz wartość oczekiwaną i wariancję liczby niepustych urn.
W \(n\)-wierzchołkowym grafie losowym \(G\) każda krawędź istnieje z prawdopodobieństwem \(p\) niezależnie od pozostałych krawędzi. Oblicz wartość oczekiwaną liczby wierzchołków izolowanych i wariancję tej wielkości.
Oblicz wartość oczekiwaną i wariancję rozkładu Poissona korzystając z funkcji tworzących prawdopodobieństwa.
Oblicz wartość oczekiwaną i wariancję rozkładu geometrycznego korzystając z funkcji tworzących prawdopodobieństwa.
W zadaniu dotyczącym problemu kolekcjonera kuponów (zadanie 2 z ćwiczeń 5, część "Liniowość wartości oczekiwanej") oszacuj prawdopodobieństwo tego, że liczba gum, które trzeba kupić aby zdobyć wszystkie historyjki przekroczy swoją wartość oczekiwaną \(c\)-krotnie:
W wyborach bierze udział dwóch kandydatów: A i B. Przeprowadzamy sondaż przedwyborczy. W ramach sondażu pytamy \(n\) osób o to na którego kandydata zamierzają głosować. Zakładamy, że każda z pytanych osób została losowo i niezależnie od pozostałych wybrana ze zbioru osób uprawnionych do głosowania (w szczególności nie wykluczamy powtórzeń). Interesuje nas oszacowanie poparcia kandydata A? Oszacuj jak duże powinno być \(n\), żeby prawdopodobieństwo popełnienia błędu względnego większego niż 1% było mniejsze niż 5%:
Dysponujemy algorytmem, który wypisuje prawidłową odpowiedź z prawdopodobieństwem \(p > \frac{1}{2}\). Przyjmijmy dla uproszczenia, że wynik jest liczbą całkowitą. Aby zwiększyć prawdopodobieństwo uzyskania prawidłowej odpowiedzi wykonujemy algorytm \(n\)-krotnie i za odpowiedź uznajemy medianę z otrzymanych wyników. Oszacuj prawdopodobieństwo uzyskania prawidłowej odpowiedzi.
W zadaniu dotyczącym wierzchołków izolowanych (zadanie 4 z ćwiczeń 5, część "Liniowość wartości oczekiwanej") oszacuj prawdopodobieństwo tego, że w losowym grafie nie ma wierzchołków izolowanych. Zbadaj zależność otrzymanego wyniku od prawdopodobieństwa \(p\) wystąpienia pojedynczej krawędzi.
Oblicz średnie czasy powrotu dla wszystkich stanów łańcucha Markowa o macierzy przejścia
\(P = \left(\begin{array}{cc} \frac{1}{4} & \frac{3}{4} \\ \frac{2}{3} & \frac{1}{3}\\ \end{array}\right)\)
wprost oraz korzystając z twierdzenia ergodycznego.
Dwóch graczy rzuca symetryczną monetą. Jeden obstawia, że najpierw pojawi się ciąg OOR, drugi - że ROO. Jakie prawdopodobieństwo wygranej ma każdy z graczy i jaki jest oczekiwany czas gry?
Na szalce \(2\times2\) hodujemy bakterie. Każde pole może zawierać jedną bakterię. Początkowo kolonia składa się z jednej bakterii. Co sekundę (jednocześnie) każda bakteria umiera z prawdopodobieństwem \(\frac{1}{2}\), a na każdym z pustych pól sąsiadujących w poprzedniej sekundzie z co najmniej jedną bakterią z prawdopodobieństwem \(\frac{1}{2}\) pojawia się nowa bakteria. Oblicz oczekiwany czas życia kolonii i prawdopodobieństwo tego, że kolonia kiedykolwiek zapełni całą szalkę.
Dwaj gracze rzucają na przemian symetryczną monetą. Wygrywa ten, który wyrzuci orła bezpośrednio po orle wyrzuconym przez poprzednika. Jakie jest prawdopodobieństwo tego, że wygra pierwszy gracz? Jaka jest oczekiwana liczba rzutów w całej grze?
Cztery mrówki znajdują się w jednym wierzchołku czworościanu. Co sekundę każda z nich z prawdopodobieństwem \(\frac{1}{4}\) przechodzi do sąsiedniego wierzchołka lub pozostaje na miejscu. Jaka jest oczekiwana liczba zajętych przez mrówki wierzchołków po upływie 1 sekundy? Jaki jest oczekiwany czas pierwszego zajęcia wszystkich wierzchołków jednocześnie?
Dwie cząstki znajdują się w przeciwległych wierzchołkach sześcianu. Co sekundę każda z nich z prawdopodobieństwem \(\frac{1}{4}\) przechodzi do sąsiedniego wierzchołka lub pozostaje na miejscu. Jaki jest oczekiwany czas kolizji cząstek (tzn. spotkania cząstek w jednym wierzchołku)?
Przy okrągłym stole siedzi trzech graczy \(A, B, C\), każdy z jednym żetonem. W każdym kroku gry, jednocześnie każdy gracz z co najmniej jednym żetonem z prawdopodobieństwem \(\frac{1}{2}\) przekazuje żeton graczowi po prawej. Grę wygrywa gracz, który zgromadzi wszystkie żetony. Ile wynosi oczekiwany czas gry?
Gracz rozpoczyna grę z kapitałem \(k\) zł. W każdym kroku gry wygrywa 1zł z prawdopodobieństwem \(p = \frac{1}{2}\), i z tym samym prawdopodobieństwem \(1-p = \frac{1}{2}\) przegrywa 1zł. Gracz kończy grę, gdy albo wygra fortunę (= \(n\) zł) albo zbankrutuje. Oblicz:
W dwóch komorach znajdują się cząstki, w jednej \(k\), w drugiej \(n-k\). W każdym kroku jedna losowo wybrana cząstka zmienia komorę. Oblicz graniczny rozkład liczby cząstek w pierwszej komorze (t.j. rozkład stacjonarny odpowiedniego łańcucha Markowa). Jaki jest średni czas powrotu dla stanu w którym wszystkie cząstki są w pierwszej komorze?