Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Rozdział 1
Rachunek prawdopodobieństwa
1.1 Przestrzeń zdarzeń elementarnych
Podstawowym pojęciem rachunku prawdopodobieństwa jest przestrzeń zdarzeń elemen-
tarnych, którą najczęściej będziemy oznaczać przez &!. W tej książce ograniczymy się
do przypadków, gdy &! jest zbiorem skończonym. Dzięki temu nasze rozważania będą
prostsze.
Elementy przestrzeni &! nazywamy zdarzeniami elementarnymi.
Przykład 1.1 Przypuśćmy, że rzucamy monetą. Przestrzeń zdarzeń elementarnych może
być wtedy określona jako &! = {O, R}, gdzie O oznacza wypadnięcie orła, a R reszki.
Przykład 1.2 W przypadku dwukrotnego rzutu monetą przestrzeń zdarzeń elementarnych
może być określona jako &! = {OO, OR, RO, RR}, gdzie OO oznacza, że dwa razy
wypadł orzeł; OR, że za pierwszym razem wypadł orzeł, a za drugiem reszka; RO, że za
pierwszym razem reszka, a za drugim orzeł; a RR, że dwa razy wypadła reszka.
Przykład 1.3 Przypuśćmy, że mamy urnę z pięcioma ponumerowanymi kulami, i że kule
o numerach 2 i 4 są białe, a kule o numerach 1, 3 i 5 są czarne. Przestrzeń zdarzeń
elementarnych może być zdefiniowana jako &! = {1, 2, 3, 4, 5}.
Przykład 1.4 Przypuśćmy, że mamy urnę jak w poprzednim punkcie i że losujemy dwie
kule z tej urny. Przestrzenią zdarzeń elementarnych może tu być zbiór dwuelementowych
podzbiorów zbioru kul
&! = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {3, 5}, {4, 5}}.
1.1.1 Zdarzenia
Dowolny podzbior A przestrzeni zdarzeń elementarnych &! nazywamy zdarzeniem. Pa-
miętajmy, że rozważamy tylko skończone przestrzenie zdarzeń elementranych. W przy-
padku, gdy &! jest zbiorem nieskończonym, konieczna jest inna definicja zdarzenia. Tak
3
4 Rozdział 1. Rachunek prawdopodobieństwa
więc zdarzenia są elementami zbioru 2&! wszystkich podzbiorów zbioru &!, jest ich 2|&!|.
Cały zbiór &! nazywamy zdarzeniem pewnym, a zbiór pusty " zdarzeniem niemożliwym.
Zdarzenia rozłączne, A )" B = ", nazywamy wykluczającymi się. Zdarzenie A = &! - A
nazywamy zdarzeniem przeciwnym do zdarzenia A.
Przykład 1.5 W przykładzie 1.2, z dwukrotnym rzutem monetą, &! = {OO, OR, RO, RR},
mamy 16 = 24 zdarzeń. Zbiór {OO, OR} jest zdarzeniem polegającym na tym, że za
pierwszym razem wypadł orzeł. Zbiór {OO, OR, RO}, że orzeł wypadł przynajmniej je-
den raz.
Przykład 1.6 W przykładzie 1.3, z kulami, zbiór {2, 4} oznacza zdarzenie, że wylosowa-
no kulę białą, a zbiór {1, 2, 3}, że wylosowano kulę o numerze mniejszym od 4.
Przykład 1.7 W przykładzie 1.4, z losowaniem dwóch kul, zbiór {{2, 4}} oznacza zda-
rzenie, że wylosowano dwie kule białe, a zbiór {{1, 3}, {3, 5}, {3, 5}}, że wylosowano
dwie kule czarne.
1.1.2 Dalsze przykłady przestrzeni zdarzeń elementarnych
Podamy teraz inne przykłady przestrzeni zdarzeń elementarnych.
Przykład 1.8 Zbiór wszystkich czteroelementowych ciągów z wartościami O lub R jako
przestrzeń dla czterokrotnego rzutu monetą. Zdarzenie, że za pierwszym i trzecim razem
wypadł orły to {OOOO, OOOR, OROO, OROR}, a zdarzenie, że za pierwszym i trze-
cim razem wypadło to samo to
{OOOO, OOOR, OROO, OROR, RORO, RORR, RRRO, RRRR}.
Przykład 1.9 Zbiór wszystkich n elementowych ciągów z wartościami O lub R jako prze-
strzeń dla n krotnego rzutu monetą. Podobnie jak w poprzednim przykładzie możemy roz-
patrywać zdarzenie, że za pierwszym i trzecim razem wypadł orzeł lub zdarzenie, że za
pierwszym i trzecim razem wypadło to samo.
Przykład 1.10 Niech G = (V, E) będzie wybranym ustalonym grafem z |V | = n wierz-
chołkami i |E| = m krawędziami. Jako przestrzeń zdarzeń elementarnych wez
my zbiór
wszystkich kolorowań dwoma kolorami wierzchołków grafu G. Przestrzeń zdarzeń ele-
mentarnych jest zbiorem wszystkich funkcji ze zbioru wierzchołków V w zbiór {1, 2}, czy-
li &! = {1, 2}V . Przykładem zdarzenia jest zbiór kolorowań, w których końce wybranej z
góry krawędzi e = {u, v} " E mają różne kolory {f " &! | f(u) = f(v)}.

Przykład 1.11 Zbiór wszystkich funkcji ze zbioru A w zbiór B, czyli &! = BA. Przykła-
dem zdarzenia jest zbiór funkcji, które mają taką samą wartość dla dwóch z góry wybra-
nych punktów a, b " A, czyli {f " &! | f(a) = f(b)}.
Przykład 1.12 Mamy ustalony zbiór V . Przestrzeń zdarzeń elementarnych to wszystkie
grafy ze zbiorem wierzchołków V . Zdarzeniem jest zbiór grafów, w których dwa z góry
wybrane wierzchołki są połączone krawędzią.
1.2. Prawdopodobieństwo 5
Przykład 1.13 Zbiór liter lub słów występujących w jakimś tekście, książce lub liście.
Przykład 1.14 Grupa studencka. Zdarzeniem jest zbiór studentów, którzy otrzymali oce-
nÄ… bardzo dobrÄ… z egzaminu.
Przykład 1.15 Wyborcy. Zdarzeniem są wyborcy, którzy nie brali udziału w ostatnich
wyborach.
1.2 Prawdopodobieństwo
Definicja 1.16 Prawdopodobieństwo, lub rozkład prawdopodobieństwa, jest funkcją
P : 2&! R
określoną na zbiorze zdarzeń (w naszym przypadku na zbiorze wszystkich podzbiorów &!).
Każdemu zdarzeniu A ą" &! przypisujemy liczbę rzeczywistą P (A), jego prawdopodo-
bieństwo. Funkcja ta musi spełniać warunki:
Aksjomaty prawdopodobieństwa
A1) Dla każdego A ą" &!, P (A) e" 0,
A2) P (&!) = 1,
A3) jeżeli zdarzenia A i B są rozłączne, to P (A *" B) = P (A) + P (B).
Zbiór zdarzeń elementarnych &! wraz z określonym na nim prawdopodobieństwem bę-
dziemy nazywać przestrzenią probabilistyczną. W przypadku, gdy przestrzeń zdarzeń
elementarnych jest zbiorem skończonym, wystarczy określić prawdopodobieństwa dla
zdarzeń elementarnych. Muszą być tylko spełnione dwa warunki:
A4) P (É) e" 0, dla każdego É " &!,
A5) P (É) = 1,
É"&!
Prawdopodobieństwo dowolnego zdarzenia A jest wtedy równe
P (A) = P (É).
É"A
A
atwo można sprawdzić, że tak zdefiniowane prawdopodobieństwo spełnia aksjomaty
definicji 1.16.
Przykład 1.17 Dla dwukrotnego rzutu monetą (przykład 1.2) możemy określić takie samo
prawdopodobieństwo dla wszystkich zdarzeń elementarnych
P (OO) = 0.25, P (OR) = 0.25, P (RO) = 0.25, P (RR) = 0.25.
Ale oczywiście funkcja prawdopodobieństwa może być dowolną funkcją spełniającą wa-
runki A4 i A5. Na przykład
P (OO) = 0.27, P (OR) = 0.24, P (RO) = 0, 25, P (RR) = 0, 24
lub
P (OO) = 0.5, P (OR) = 0.3, P (RO) = 0.2, P (RR) = 0.
6 Rozdział 1. Rachunek prawdopodobieństwa
1.2.1 Klasyczna definicja prawdopodobieństwa, rozkład jednostajny
W przypadku, gdy przestrzeń zdarzeń elementarnych jest zbiorem skończonym najczę-
ściej przyjmuje się, że funkcja prawdopodobieństwa przypisuje, każdemu zdarzeniu ele-
mentarnemu taką samą wartość. Mamy wtedy do czynienia z klasyczną definicją prawdo-
podobieństwa lub rozkładem jednostajnym.
Definicja 1.18 RozkÅ‚ad prawdopodobieÅ„stwa, w którym każde zdarzenie elementarne É "
1
&! ma takie samo prawdopodobieÅ„stwo P (É) = nazywamy rozkÅ‚adem jednostajnym.
|&!|
W dalszej części książki będziemy najczęściej zakładać, że mamy jednostajny rozkład
prawdopodobieństwa. W razie odstępstwa będziemy to specjalnie zaznaczać.
Przykład 1.19 (kontynuacja przykładów 1.3 oraz 1.6 z losowaniem jednej kuli) Prawdo-
2
podobieństo zdarzenia, że wylosowano kulę białą wynosi .
5
Przykład 1.20 (kontynuacja przykładów 1.4 oraz 1.7 z losowaniem pary kul). Prawdo-
1
podobieństwo że wylosowano parę kul białych wynosi , a prawdopodobieństwo że wy-
10
3
losowano parÄ™ kul czarnych wynosi .
10
Przykład 1.21 (kontynuacja przykładu 1.8 z czterokrotnym rzutem monetą). Jeżeli zało-
żymy rozkład jednostajny, to prawdopodobieństwo że za pierwszym i trzecim razem wy-
1
padł orzeł wynosi , a prawdopodobieństwo, że za pierwszym i trzecim razem wypadnie
4
1
to samo wynosi .
2
Podobnie w przypadku, gdy n krotnie rzucamy monetą n > 3 (przykład 1.9). Prze-
strzeń zdarzę elementarnych zawiera 2n ciągów, z czego 2n-2 sprzyja zdarzeniu, że za
pierwszym i trzecim razem wypadnie orzeł, a 2n-1 sprzyja zdarzeniu, że za pierwszym i
trzecim razem jest to samo. Tak więc otrzymamy takie same prawdopodobieństwa jak w
przypadku czterokrotnego rzutu monetÄ….
Przykład 1.22 Powróćmy do przypadku kolorowania dwoma kolorami wierzchołków gra-
fu G = (V, E) z |V | = n wierzchołkami (przykład 1.10). Prawdopodobieństwo, że końce
1
wybranej z góry krawędzi e = {u, v} " E mają różne kolory wynosi . Rzeczywiście,
2
wszystkich kolorowań jest 2n. Kolorowań, w których u i v mają kolor biały, jest 2n-2 (na
tyle sposobów można pokolorować pozostałe n - 2 wierzchołków). Tyle samo jest kolo-
rowań, w których u i v mają kolor czarny. Tak więc w połowie kolorowań u i v mają taki
sam kolor, a w połowie mają różne kolory.
1.2.2 Własności prawdopodobieństwa
W następującym twierdzeniu zebrano kilka prostych wniosków wynikających z aksjoma-
tów prawdopodobieństwa.
Twierdzenie 1.23 a) P (") = 0.
b) Jeżeli A ą" B, to P (A) d" P (B) oraz P (B - A) = P (B) - P (A).
c) P (A *" B) = P (A) + P (B) - P (A )" B).
1.3. Prawdopodobieństwo warunkowe 7
d) P (A *" B) d" P (A) + P (B).
Dowód:
a) Z aksjomatu A3 mamy P (") = P (" *" ") = P (") + P ("), a 0 jest jedynÄ… liczbÄ…
spełniającą równość x = x + x.
b) Jeżeli A ą" B, to B = (B - A) *" A oraz (B - A) )" A = ", a więc z aksjomatu A3
P (B) = P (B - A) + P (A) e" P (A).
c) Mamy A *" B = A *" (B - (A )" B)) oraz A )" (B - (A )" B)) = ", a więc z aksjomatu
A3 P (A *" B) = P (A) + P (B - (A )" B)), a ponieważ A )" B ą" B, z wniosku 1.23b
mamy P (B - (A )" B)) = P (B) - P (A )" B).
d) wynika bezpośrednio z c).
Twierdzenie 1.24 Niech A1, . . . , An będzie rodziną parami rozłącznych zdarzeń (to zna-
czy Ai )" Aj = " dla każdej pary indeksów i < j). Wtedy
n n
P Ai = P (Ai)
i=1 i=1
Dowód przez indukcję: Dla n = 1 twierdzenie zachodzi w sposób trywialny. Załóżmy,
że twierdzenie jest prawdziwe dla dowolnej rodziny n zbiorów. Rozpatrzmy
n+1 n
P Ai = P Ai *" An+1 .
i=1 i=1
n
Ponieważ Ai )" An+1 = ", z aksjomatu A3 i z założenia indukcyjnego wynika
i=1
n+1 n n n+1
P Ai = P Ai + P (An+1) = P (Ai) + P (An+1) = P (Ai).
i=1 i=1 i=1 i=1
1.3 Prawdopodobieństwo warunkowe
Definicja 1.25 Prawdopodobieństwo warunkowe zajścia zdarzenia A pod warunkiem, że
zaszło zdarzenie B oznaczane przez P (A|B) określamy jako
P (A )" B)
P (A|B) = .
P (B)
Ma to sens tylko wtedy gdy P (B) > 0.
Możemy powiedzieć, że jest to prawdopodobieństwo zajścia zdarzenia A w sytuacji, gdy
mamy pewność, że zaszło zdarzenie B. Przy klasycznej definicji, gdy prawdopodobień-
stwo oznacza częstość wystąpienia, to prawdopodobieństwo P (A|B) oznacza jaka część
elementów zbioru B należy do zbioru A.
8 Rozdział 1. Rachunek prawdopodobieństwa
Przykład 1.26 Niech w urnie będzie sześć kul o numerach od 1 do 6, i niech kule o
numerach parzystych będą białe, a kule o numerach nieparzystych czarne. Przypuść-
my, że losujemy jedną kulę. Jako przestrzeń zdarzeń elementarnych wybieramy zbiór
&! = {1, 2, 3, 4, 5, 6} z jednostajnym rozkładem prawdopodobieństwa. Rozważmy zdarze-
nie A = {1, 2} polegajÄ…ce na wylosowaniu kuli o numerze mniejszym od 3 oraz zdarzenie
B = {2, 4, 6} polegające na wylosowaniu kuli białej. Prawdopodobieństwo P (A|B) zaj-
P (A)"B)
ścia zdarzenia A pod warunkiem, że zaszło zdarzenie A wynosi P (A|B) = =
P (B)
1 1 1 1
: = . Mówiąc inaczej, wśród białych kul ma numer mniejszy od 3.
6 2 3 3
1
Zauważmy, że P (A|B) = P (A), czyli kul ma numer mniejszy od 3 zarówno w
3
całym zbiorze &! jak i wśród białych kul. Możemy więc powiedzieć, że zajście zdarzenia
A nie zależy od tego, czy zaszło zdarzenie B, czy nie.
Zauważmy, że także zdarzenie B nie zależy od zdarzenia A, ponieważ P (B|A) =
1
P (B) = .
2
To co zauważyliśmy w powyższym przykładzie jest ogólną prawidłowością. Mianowicie,
jeżeli A i B są zdarzeniami o niezerowych prawdopodobieństwach i P (A) = P (A|B)
(zdarzenie A jest niezależne od B), to P (B) = P (B|A) (zdarzenie B jest niezależne od
A). RzeczywiÅ›cie P (A|B) = P (A) pociÄ…ga P (A )" B) = P (A) · P (B), a to pociÄ…ga
P (A )" B)
P (B) = = P (B|A).
P (A)
Czyli relacja niezależności zbiorów jest symetryczna. Zwykle jednak używa się trochę
innej definicji niezależności.
1.4 Zdarzenia niezależne
Definicja 1.27 Zdarzenia A i B sÄ… niezależne, jeżeli P (A )" B) = P (A) · P (B).
Zauważmy, że jeżeli P (A) = 0 lub P (B) = 0, to ponieważ A )" B ‚" A oraz A )" B ‚" B,
na podstawie twierdzenia 1.23, mamy P (A)"B) = 0, czyli zdarzenia A i B są niezależne.
Wniosek 1.28 P (A )" B) = P (A|B) · P (B).
Definicja 1.29 Zdarzenia A1, . . . , An, sÄ…:
" parami niezależne, jeżeli każde dwa zdarzenia są niezależne, to znaczy gdy P (Ai )"
Aj) = P (Ai) · P (Aj) dla każdej pary i < j.
" niezależne, jeżeli dla każdego podzbioru I ą" {1, . . . , n} mamy
P Ai = P (Ai).
i"I i"I
1.5. Prawdopodobieństwo całkowite 9
Przykład 1.30 (Kontynuacja przykładu 1.2, z dwukrotnym rzutem monetą). Niech A1 bę-
dzie zdarzeniem, że za pierwszym razem wypadł orzeł, A2, że za drugim razem wypadł
orzeł, a A3, że w obu rzutach wypadło to samo. Mamy
1
P (A1) = P (A2) = P (A3) =
2
1
P (A1 )" A2) = P (A1 )" A3) = P (A2 )" A3) = P (A1 )" A2 )" A3) = .
4
Jak widać zdarzenia te są parami niezależne, ponieważ dla każdej pary indeksów 1 d" i <
1
j d" 3 mamy P (Ai )" Aj) = P (Ai) · P (Aj) = . Ale zdarzenia te nie sÄ… niezależne,
4
ponieważ
1 1
= P (A1 )" A2 )" A3) = P (A1) · P (A2) · P (A3) = .

4 8
Przykład 1.31 W przypadku n krotnego rzutu monetą, niech Ai oznacza, że za i-tym
razem wypadł orzeł. Wtedy zdarzenia A1, . . . , An są niezależne. A
atwo sprawdzić, że
1
" dla każdego i, P (Ai) = ,
2
1
" dla każdej pary i < j, P (Ai )" Aj) =
4
1
" dla każdej trójki i < j < k, P (Ai )" Aj )" Ak) = ,
8
" i ogólnie, dla każdego podzbioru zbioru indeksów I ą" {1, . . . , n} mamy
|I|
1
P Ai =
2
i"I
1.5 Prawdopodobieństwo całkowite
Twierdzenie 1.32 (wzór na prawdopodobieństwo całkowite.) Niech A1, . . . , An ą" &!,
będą zdarzeniami takimi, że:
" P (Ai) > 0, dla każdego 1 d" i d" n,
" Ai )" Aj = ", dla 1 d" i < j d" n (zdarzenia są parami rozłączne),
" Ai = &! (zdarzenia dają w sumie całą przestrzeń).
1d"id"n
Wtedy prawdopodobieństwo dowolnego zdarzenia B ą" &! wynosi
n
P (B) = P (B|Ai) · P (Ai)
i=1
10 Rozdział 1. Rachunek prawdopodobieństwa
Dowód: Mamy
B = B )" &! = B )" Ai = (B )" Ai).
1d"id"n 1d"id"n
Ponadto (B )" Ai) )" (B )" Aj) = " dla i = j, więc na mocy twierdzenia 1.24 mamy

n
P (B) = P (B )" Ai).
i=1
Z wniosku 1.28 mamy P (B )" Ai) = P (B|Ai) · P (Ai); co daje tezÄ™ twierdzenia.
W przypadku dwóch zdarzeń uzupełniających się A i A = &! - A wzór z twierdze-
nia 1.32 wygląda następująco:
P (B) = P (B|A) · P (A) + P (B|A ) · P (A ). (1.1)
Przykład 1.33 Wyobraz
my sobie dwie urny z kulami. W pierwszej urnie mamy kule o nu-
merach 1,2, w drugiej kule o numerach 3,4,5. Zakładamy, że kule o numerach parzystych
są białe, a kule o numerach nieparzystych są czarne. Rzucamy monetą. Jeżeli wypadnie
orzeł, to losujemy kulę z pierwszej urny, jeżeli reszka, to losujemy z drugiej urny.
Jakie jest prawdopodobieństwo, że wylosujemy kulę białą? Niech B oznacza wyloso-
wanie kuli białej, a A wypadnięcie orła na monecie, wtedy A oznacza, że na monecie
1
wypadła reszka. Mamy P (A) = P (A ) = oraz
2
1
P (B|A) =  jest to prawdopodobieństwo wylosowania kuli białej pod warunkiem,
2
że wypadł orzeł i losowaliśmy z pierwszej urny.
1
P (B|A ) =  jest to prawdopodobieństwo wylosowania kuli białej pod warun-
3
kiem, że wypadła reszka i losowaliśmy z drugiej urny.
Rysunek 1.1: Prawdopodobieństwo całkowite
1 1
2 2
O R
1 1 1 1 1
2 2 3 3 3
1 2 3 4 5
KorzystajÄ…c teraz ze wzoru (1.1) mamy
1 1 1 1 5
P (B) = · + · = .
2 2 3 2 12
1.5. Prawdopodobieństwo całkowite 11
Rozwiązanie tego zadania można przedstawić za pomocą drzewa (rysunek 1.1). Na po-
czątku jesteśmy w korzeniu drzewa. Dwaj synowie korzenia odpowiadają dwóm wynikom
rzutu monetą. Jak wypadnie orzeł, to idziemy w lewo do wierzchołka O, jak wypadnie
reszka, to idziemy w prawo do wierzchołka R. Etykiety przy krawędziach oznaczają praw-
dopodobieństa z jakimi te krawędzie są wybierane. Synowie wierzchołka O odpowiadają
wynikom losowania kul pod warunkiem, że na monecie wypadł orzeł i losujemy z pierw-
szej urny. Etykiety przy krawędziach oznaczają prawdopodobieństa warunkowe z jakimi
te krawędzie są wybierane. Podobnie synowie wierzchołka R odpowiadają wynikom lo-
sowania kul pod warunkiem, że na monecie wypadła reszka i losujemy z drugiej urny.
Każdy liść w drzewie odpowiada jakiemuś wynikowi końcowemu (wylosowaniu kon-
kretnej kuli). Prawdopodobieństo, że będzie taki wynik jest równe iloczynowi etykiet na
drodze prowadzącej od korzenia do tego liścia. Prawdopodobieństwo wylosowania kuli
1 1 1 1 5
biaÅ‚ej (z parzystym numerem) jest równe · + · = .
2 2 2 3 12
Przykład 1.34 Wyobraz
my sobie, że mamy jedną urnę z trzema kulami o numerach 2, 3
i 4 oraz że kule o numerach 2 i 4 są białe, a kula 3 jest czarna. Przypuśćmy, że pierwsza
osoba wylosowała jedną kulę i schowała ją. Jakie jest prawdopodobieństwo, że druga
osoba wylosuje kulę białą?
Rysunek 1.2:
2 1
3 3
B C
1 1
1 0
2 2
BB BC CB CC
RozwiÄ…zanie tego zadania jest przedstawione na drzewie z rysunku 1.2. Synowie ko-
rzenia odpowiadają wynikowi losowania pierwszej osoby. Losuje ona kulę białą, wierz-
2
chołek B, z prawdopodobieństwem , a kulę czarną, wierzchołek C, z prawdopodobień-
3
1
stwem . Synowie wierzchołka B odpowiadają losowaniom drugiego gracza pod warun-
3
kiem, że pierwszy gracz wylosował kułe białą. W tej sytuacji drugi gracz wylosuje kulę
białą, wierzchołek BB, lub czarną, wierzchołek BC, obie z prawdopodobieństwem wa-
1
runkowym . Etykieta BB oznacza, że obaj gracze wylosowali kule białe, a etykieta BC
2
oznacza, że pierwszy gracz wylosował kulę białą, a drugi kulę czarną. Synowie wierz-
chołka C odpowiadają losowaniom drugiego gracza pod warunkiem, że pierwszy gracz
wylosował kułe czarną. Teraz drugi gracz wylosuje kulę białą, wierzchołek CB, z prawdo-
podobieństwem warunkowym 1, a kulę czarną, wierzchołek CC, z prawdopodobieństwem
12 Rozdział 1. Rachunek prawdopodobieństwa
0. Prawdopodobieństwo wylosowania kuli białej przez drugą osobę wynosi
2 1 1 2
· + · 1 = .
3 2 3 3
Zauważmy, że prawdopodobieństwo, że po drugim losowaniu w urnie zostanie biała kula
jest równe
2 1 1 2
· + · 1 = .
3 2 3 3
Jak widać prawdopodobieństwo wylosowania białej kuli jest takie samo dla pierwszego,
drugiego i trzeciego losujÄ…cego.
1.6 Schemat dwumianowy (Bernouliego)
W schemacie dwumianowym (Bernouliego) mamy serię n doświadczeń losowych (na
przykład rzutów monetą). W każdym doświadczeniu możliwe są dwa wyniki: sukces (wy-
padnięcie orła) lub porażka (wypadniećie reszki). Wyniki doświadczeń są niezależne i w
każdym mamy takie samo prawdopodobieństwo sukcesu równe p.
1.6.1 Rzut symetrycznÄ… monetÄ…
Rozpatrzmy trzykrotny rzut symetrycznÄ… monetÄ…. Rysunek 1.3 ilustruje jak w tym przy-
Rysunek 1.3: Trzykrotny rzut symetrycznÄ… monetÄ…
1 1
2 2
O R
1 1 1 1
2 2 2 2
OO OR RO OR
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
OOO OOR ORO ORR ROO ROR RRO RRR
padku rozkłada się prawdopodobieństwo. W korzeniu rzucamy pierwszy raz monetą, je-
żeli wypadnie orzeł, to idziemy do wierzchołka O, jeżeli reszka, to do R. W wierzchołku
1.6. Schemat dwumianowy (Bernouliego) 13
O rzucamy drugi raz, idąc albo do OO lub do OR. Etykieta OO oznacza, że w obu rzutach
wypadł orzeł, a etykieta OR oznacza, że za pierwszym razem wypadł orzeł, a za drugim
reszka. Podobnie w wierzchołku R. Ponieważ drugi rzut jest niezależny od pierwszego,
etykiety na krawędziach wychodzących z O są takie same jak na krawędziach wycho-
dzących z R. Krawędzie wychodzące z wierzchołków z dwoma etykietami odpowiadają
trzeciemu rzutowi. Także tutaj etykiety krawędzi wychodzących z wierzchołków są takie
same, ponieważ trzeci rzut jest niezależny od dwóch pierwszych.
Liście odpowiadają wynikom trzech rzutów. Występują tutaj wszystkie 8 ciągów dłu-
1
gości 3. Każdy z nich jest przyjmowane z prawdopodobieństwem . Otrzymaliśmy więc
8
jednostajny rozkład prawdopodobieństwa na zbiorze
&! = {OOO, OOR, ORO, ORR, ROO, ROR, RRO, RRR}.
Podobnie, przy n krotnym rzucie monetą, jeżeli rzuty są niezależne i w każdym rzucie
1 1
prawdopodobieństwa wypadnięcia orła i reszki wynoszą , , otrzymamy jednostajny
2 2
rozkład na zbiorze wszystkich ciągów długości n z elementami O i R.
1.6.2 Kolorowanie wierzchołków grafu
Rysunek 1.4: Kolorowanie wierzchołków grafu
1 1
2 2
B C
1 1 1 1
2 2 2 2
BB BC CB BC
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
BBB BBC BCB BCC CBB CBC CCB CCC
Przypuśćmy, że mamy graf z trzema wierzchołkami a, b i c, i że jego wierzchoł-
1 1
ki kolorujemy po kolei niezależnie na biało lub czarno z pawdopodobieństwami , .
2 2
Doświadczenie to można zilustrować za pomocą drzewa z rysunku 1.4. W korzeniu wy-
bieramy kolor dla wierzchołka a, jeżeli biały, to idziemy do wierzchołka B, jeżeli czarny,
to do C. W wierzchołku B wybieramy kolor dla wierzchołka b, idąc albo do BB lub do
14 Rozdział 1. Rachunek prawdopodobieństwa
BC. Etykieta BB oznacza, że oba wierzchołki a i b są białe, a etykieta BC oznacza, że
wierzchołek a jest biały, a wierzchołek b czarny. Podobnie w wierzchołku C. Krawędzie
wychodzące z wierzchołków z dwoma kolorami odpowiadają kolorowaniom wierzchołka
c. Także tutaj etykiety krawędzi wychodzących z wierzchołków są takie same, ponie-
waż wybór koloru dla c jest niezależny od wyboru kolorów dla a i b. Liście odpowiadają
ostatecznym kolorowaniom trzech wierzchołków. Występuje tutaj wszystkie 8 kolorowań.
1
Każdy z nich jest przyjmowane z prawdopodobieństwem . Otrzymaliśmy więc jedno-
8
stajny rozkład prawdopodobieństwa na zbiorze wszystkich kolorowań.
Podobnie, kolorując po kolei niezależnie n wierzchołków, na biało lub czarno z praw-
1 1
dopodobieństwami , , otrzymamy jednostajny rozkład na zbiorze wszystkich możli-
2 2
wych kolorowań.
1.6.3 Trzykrotny rzut niesymetrycznÄ… monetÄ…
Rozpatrzmy teraz trzykrotny rzut niesymetryczną monetą, gdy prawdopobieństwo wy-
padnięcia orła wynosi p, a prawdopobieństwo wypadnięcia reszki wynosi q = 1 - p.
Nadal zakładamay, że wyniki poszczególnych rzutów są od siebie niezależne.
Rysunek 1.5: Trzykrotny rzut niesymetrycznÄ… monetÄ…
p q
O R
p q p q
OO OR RO OR
p q p q p q p q
OOO OOR ORO ORR ROO ROR RRO RRR
Rysunek 1.5 ilustruje jak rozkłada się prawdopodobieństwo w takim przypadku. Ety-
kiety wierzchołków mają takie same znaczenie jak w przypadku rzutu symetryczną mo-
netą, Zmieniły się tylko etykiety krawędzi. Krawędzie odpowiadające wypadnięciu orła
majÄ… etykietÄ™ p, a odpowiadajÄ…ce reszce etykietÄ™ q.
Otrzymaliśmy teraz inny rozkład prawdopodobieństwa na zbiorze &!.
1.6. Schemat dwumianowy (Bernouliego) 15
É OOO OOR ORO ORR ROO ROR RRO RRR
P (É) p3 p2q p2q pq2 p2q pq2 pq2 q3
Zauważmy, że prawdopodobieństo, że za pierwszym (drugim lub trzecim) razem wy-
padnie orzeł wynosi
p3 + p2q + p2q + pq2 = p(p2 + 2pq + q2) = p(p + q)2 = p,
a prawdopodobieństo, że za pierwszym (drugim lub trzecim) razem wypadnie reszka wy-
nosi
p2q + pq2 + pq2 + q3 = q(p2 + 2pq + q2) = q(p + q)2 = q.
1.6.4 Ogólny schemat  n krotny rzut niesymetryczną monetą
Ogólnie w schemacie dwumianowym mamy serię n niezależnych doświadczeń. W każ-
dym doświadczeniu prawdopodobieństwo sukcesu wynosi p, a prawdopodobieństwo po-
rażki q = 1 - p. Bez straty ogólności możemy nasze rozważania ograniczyć do n krot-
nego rzutu niesymetryczną monetą. Zakładamy, że rzuty są niezależne i w każdym rzucie
prawdopodobieństwa wypadnięcia orła wynosi p, a reszki q. Otrzymamy wtedy rozkład
na zbiorze wszystkich ciągów długości n z elementami O i R, w którym prawdopodo-
bieÅ„stwo ciÄ…gu É " &! jest równe
pkqn-k,
gdzie k oznacza liczbÄ™ symboli O w ciÄ…gu É.
n
Zauważmy, że ciągów z k orłami jest , więc jeżeli pogrupujemy te prawdopodo-
k
bieństwa według liczby orłów i zsumujemy, to otrzymamy
n
n
pkqn-k = (p + q)n = 1n = 1.
k
k=0
Jeżeli rozważymy tylko ciągi z O na pierwszej (lub na dowolnej i tej) pozycji, to znowu
możemy je pogrupować według liczby symboli O. Dla każdego k od 0 do n - 1, ciągów
n-1
z k + 1 symbolami O jest (trzeba wybrać k pozycji spośród n - 1, na których będą
k
orły). Jeżeli pogrupujemy te prawdopodobieństwa według liczby orłów i zsumujemy, to
otrzymamy prawdopodobieństwo wypadnięcia orła za pierwszym (lub dowolnym i tym
razem) równe
n-1 n-1
n - 1 n - 1
pk+1qn-1-k = p · pkqn-1-k = p(p + q)n-1 = p.
k k
k=0 k=0
Podobnie, jeżeli rozważymy ciągi z R na pierwszej (lub na dowolnej i tej) pozycji, to
znowu możemy je pogrupować według liczby symboli O. Dla każdego k od 0 do n - 1
n-1
ciągów z k symbolami O jest , więc jeżeli pogrupujemy te prawdopodobieństwa
k
według liczby orłów to, zgodnie ze wzorem na dwumian Newtona, otrzymamy
n-1 n-1
n - 1 n - 1
pkqn-k = q · pkqn-1-k = q(p + q)n-1 = q.
k k
k=0 k=0
16 Rozdział 1. Rachunek prawdopodobieństwa
1.7 Zmienna losowa
Definicja 1.35 Zmienna losowa X jest to dowolna funkcja z przestrzeni zdarzeń elemen-
tarnych &! w zbiór liczb rzeczywistych R.
Trzeba tutaj przypomnieć, że w tej książce rozważamy tylko skończone przestrzenie zda-
rzeń elementarnych. W przypadku, gdy &! jest zbiorem nieskończonym definicja zmiennej
losowej jest inna.
Przykład 1.36 Rozważmy trzykrotny rzut symetryczną monetą,
&! = {OOO, OOR, ORO, ORR, ROO, ROR, RRO, RRR}.
Zmienna losowa X oznacza ile razy wypadł orzeł. Jej wartości podane są w następującej
tabeli:
É OOO OOR ORO ORR ROO ROR RRO RRR
X(É) 3 2 2 1 2 1 1 0
MajÄ…c zmiennÄ… losowÄ… X i dowolnÄ… liczbÄ™ rzeczywistÄ… x definiujemy zdarzenie (X = x)
jako
(X = x) = {É " &! | X(É) = x}.
Zauważmy, że jeżeli liczba x nie należy do zbioru wartości X(&!) zmiennej X, to zdarze-
nie (X = x) jest zdarzeniem niemożliwym.
Przykład 1.37 Dla zmiennej losowej X z przykładu 1.36 mamy:
(X = 0) = {RRR},
(X = 1) = {0RR, ROR, RRO},
(X = 2) = {OOR, ORO, OOR},
(X = 3) = {OOO},
Jeżeli x = 0, 1, 2, 3, to (X = x) = ".

1.7.1 Gęstość rozkładu prawdopodobieństwa zmiennej losowej
Definicja 1.38 FunkcjÄ™
f(x) = P (X = x)
nazywamy funkcją gęstości (rozkładu) prawdopodobieństwa zmiennej losowej X.
Przykład 1.39 (Kontynuacja przykładu 1.36) Jeżeli założymy, że każde zdarzenie elemen-
tarne jest równo prawdopodobne, to zmienna losowa X posiada rozkład
x 0 1 2 3
f(x) 1/8 3/8 3/8 1/8
1.7. Zmienna losowa 17
Ponieważ, jak założyliśmy &! jest zbiorem skończonym, to zbiór wartości X(&!) zmiennej
X też jest skończony. Dla x " X(&!) mamy f(x) = P (X = x) = P (") = 0. Tak więc
/
funkcja gęstości przyjmuje wartości niezerowe tylko dla skończenie wielu argumentów.
Zauważmy, że jeżeli x1 = x2, to zdarzenia (X = x1) i (X = x2) wykluczają się.

Lemat 1.40 Jeżeli f jest funkcją gęstości zmiennej losowej X, to
" f(x) e" 0 dla każdego x " R.
" f(x) = 1.
x
Sumę f(x) rozumiemy jako skończoną sumę po zbiorze wartości zmiennej X, czyli
x
f(x) = f(x)
x x"X(&!)
Dowód.
f(x) = P (X = x) = P (É).
x"X(&!) x"X(&!) x"X(&!) X(É)=x
Zauważmy, że ostatnia podwójna suma jest sumÄ… po wszystkich elementach É " &! po-
grupowanych według wartości zmiennej X. Mamy więc
f(x) = P (É) = 1.
x É"&!
W dalszej części przedstawiając funkcję gęstości zmiennej losowej X będziemy roz-
ważać tylko te x, dla których f(x) > 0.
Mając funkcję gęstości rozkładu zmiennej X możemy określać prawdopodobieństwa
zdarzeń opisywanych za pomocą zmiennej X.
Przykład 1.41 Dla zmiennej losowej X z przykładu 1.38. mamy
1 3 1
P (X < 2) = P (X = 0 lub X = 1) = P (X = 0) + P (X = 1) = + = ,
8 8 2
pamiętajmy, że zdarzenia X = 0 oraz X = 1 są rozłączne.
1.7.2 Dalsze przykłady zmiennych losowych
Przykład 1.42 Przypuśćmy, że mamy urnę z czteroma ponumerowanymi kulami {1, 2, 3, 4},
i że kule o numerach parzystych są białe, a kule o numerach nieparzystych czarne. Losu-
jemy dwie kule bez zwracania. Jako przestrzeń zdarzeń elementarnych wybieramy zbiór
dwuelementowych podzbiorów zbioru kul
&! = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}
z jednostajnym rozkładem prawdopodobieństwa.
Niech zmienna losowa X oznacza liczbę białych kul w wylosowanej parze. Jej warto-
ści podane są w następującej tabeli:
18 Rozdział 1. Rachunek prawdopodobieństwa
É {1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4}
X(É) 1 0 1 1 2 1
Gęstość rozkładu prawdopodobieństwa zawiera tabela
x 0 1 2
1 4 1
f(x)
6 6 6
Przykład 1.43 Rozważmy zmienną losową X oznaczającą liczbę różnobarwnych krawę-
dzi w kolorowaniu wierzchołków dowolnego grafu G = (V, E) (przykład 1.10). Przestrze-
nią zdarzeń losowych to zbiór &! = {1, 2}V wszystkich funkcji ze zbioru wierzchołków V
w zbiór {1, 2} dwóch kolorów. Dla każdego kolorowania É " &! wartość X(É) oznacza
ile krawÄ™dzi ma koÅ„ce w różnych kolorach w kolorowaniu É.
W szczególnym przypadku, gdy graf G = (V, E) jest trójkątem z wierzchołkami
V = {a, b, c} i krawędziami E = {{a, b}, {a, c}, {b, c}}. Mamy 8 jednakowo praw-
dopodobnych kolorowań (porównaj podrozdział 1.6.2).
&! = {BBB, BBC, BCB, BCC, CBB, CBC, CCB, CCC}.
Przypominamy, że na przykład, CBB oznacza, że wierzchołek a jest pokolorowany na
czarno, a wierzchołki b i c na biało. A
atwo zauważyć, że zmienna X przyjmuje wartość 0
dla dwóch kolorowań BBB oraz CCC. Dla wszystkich innych kolorowań X przyjmuje
wartość 2. Więc jej rozkład ma postać
x 0 2
2 6
f(x)
8 8
1.7.3 Rozkład jednopunktowy
Z rozkładem jednopunktowym mamy do czynienia, wtedy gdy całe prawdopodobieństwo
jest skupione w jednym punkcie. Mówiąc inaczej zmienna losowa X ma rozkład jedno-
punktowy, jeżeli dla jekiegoś m
P (X = m) = 1.
1.7.4 Rozkład zero-jedynkowy
Zmienna losowa X ma rozkład zero-jedynkowy, jeżeli prawdopodobieństwo jest skupio-
ne tylko w dwóch punktach 0 i 1. Gęstość rozkładu prawdopodobieństwa ma wtedy postać
x 0 1
f(x) q p
dla pewnych dodatnich p, q spełniających warunek p + q = 1.
1.8. A
ączny rozkład prawdopodobieństwa 19
1.8 A
ączny rozkład prawdopodobieństwa
Może się zdażyć, że na tej samej przestrzeni zdarzeń elementarnych mamy określone
dwie lub więcej zmiennych losowych.
Przykład 1.44 Rozważmy losowanie jednej kuli z urny zawierającej siedem ponumero-
wanych kul. &! = {1, 2, 3, 4, 5, 6, 7}. Niech zmienna losowa X2 bedzie zdefiniowana jako
X2(É) = É mod 2,
a zmienna losowa X3 jako
X3(É) = É mod 3.
(X2(É) jest resztÄ… z dzielenia numeru kuli przez 2, a X3(É) resztÄ… z dzielenia przez 3).
Wartości tych dwóch zmiennych zebrane są w tabeli.
É 1 2 3 4 5 6 7
X2(É) 1 0 1 0 1 0 1
X3(É) 1 2 0 1 2 0 1
1.8.1 Gęstość łącznego rozkładu
W przypadku dwóch zmiennych losowych X i Y określonych na tej samej przestrzeni
zdarzeń elementarnych &! mamy tak zwany łączny rozkład prawdopodobieństwa, którego
gęstość jest określona jako
f(x, y) = P (X = x i Y = y).
(X = x i Y = y) jest innym zapisem zdarzenia (X = x) )" (Y = y).
Przykład 1.45 Dla zmiennych X2 i X3 z przykładu 1.44 gęstość łącznego rozkładu praw-
dopodobieństwa przedstawiona jest w tabeli:
X3
0 1 2
X2 0 1/7 1/7 1/7
1 1/7 2/7 1/7
Możemy teraz obliczać prawdopodobieństwa zdarzeń opisywanych przez te zmienne. Na
przykład
P (X2 = X3) = P (X2 = 0 i X3 = 0 lub X2 = 1 i X3 = 1) =
P (X2 = 0 i X3 = 0) + P (X2 = 1 i X3 = 1) = 1/7 + 2/7 = 3/7
lub
P (X2 < X3) = P (X2 = 0 i X3 = 1 lub X2 = 0 i X3 = 2 lub X2 = 1 i X3 = 2) =
= 1/7 + 1/7 + 1/7 = 3/7
A
atwo można zauważyć, że sumując wiersze tabeli łącznego rozkładu można otrzymać
gęstość rozkładu zmiennej X2, a sumując kolumny gęstość rozkładu X3.
20 Rozdział 1. Rachunek prawdopodobieństwa
X3
0 1 2
X2 0 1/7 1/7 1/7 3/7
1 1/7 2/7 1/7 4/7
2/7 3/7 2/7
Przykład 1.46 Rozważmy dwie zmienne losowe X1 i X2 określone na przestrzeni
&! = {OO, OR, RO, RR}
opisujÄ…cej wyniki dwukrotnego rzutu monetÄ….
Zmienna X1 przyjmuje wartość 1, jeżeli za pierwszym razem wypadnie orzeł, oraz
wartość 0, jeżeli za pierwszym razem wypadnie reszka. Podobnie zmienna X2 opisuje
wynik drugiego rzutu. Wartości tych dwóch zmiennych zebrane są w tabeli.
É OO OR RO RR
X1(É) 1 1 0 0
X2(É) 1 0 1 0
A
ączny rozkład prawdopodobieństwa przedstawiony jest w tabeli:
X2
0 1
X1 0 1/4 1/4
1 1/4 1/4
1.9 Niezależność zmiennych losowych
Definicja 1.47 Zmienny losowe X i Y są niezależne jeżeli dla każdej pary liczb x, y
mamy
P (X = x i Y = y) = P (X = x) · P (Y = y)
lub inaczej, gdy
fXY (x, y) = fX(x) · fY (y),
gdzie fXY oznacza gęstość rozkładu łącznego, fX gęstość zmiennej X, a fY gęstość
zmiennej Y .
Przykład 1.48 Zmienne losowe X1 i X2 z przykładu 1.46 są niezależne, a zmienne loso-
we X2 i X3 z przykładu 1.45 nie są niezależne.
Oczywiście może być więcej zmiennych losowych określonych na jednej przestrzeni
Dla trzech zmiennych losowych X, Y , Z gęstość łącznego rozkładu prawdopodobień-
stwa, zdefiniowana jest jako
f(x, y, z) = P (X = x i Y = y i Z = z).
W ogólnym przypadku n zmiennych losowych X1, . . . , Xn gęstośc ich łącznego rozkładu
określona jest jako
f(x1 . . . , xn) = P (X1 = x1, . . . , Xn = xn).
1.9. Niezależność zmiennych losowych 21
Definicja 1.49 Zmienne losowe X, Y , Z są niezależne jeżeli dla każdej trójki liczb x, y i
z mamy
f(x, y, z) = P (X = x) · P (Y = y) · P (Z = z).
Podobnie mamy w przypadku n zmiennych losowych
Definicja 1.50 Zmienne losowe X1, . . . , Xn są niezależne jeżeli dla każdej n-tki liczb
x1, . . . , xn zachodzi
n n
P (Xi = xi) = P (Xi = xi),
i=1 i=1
czyli
n
f(x1, . . . , xn) = fi(xi),
i=1
gdzie f oznacza gęstość rozkładu łącznego, a fi gęstość rozkładu zmiennej Xi.
Przykład 1.51 Rozważmy n krotny rzut symetryczną monetą. Przestrzeń zdarzeń elemen-
tarnych zawiera ciągi długości n o elementach ze zbioru {O, R} i każdy ciąg jest równie
prawdopodobny. Dla każdego i od 1 do n określmy zmienną losową Xi:
1, jeżeli za i-tym razem wypadł orzeł
Xi(É) =
0, jeżeli za i-tym razem wypadła reszka
Zmienne X1, . . . , Xn są niezależne. Prześledz
my to dla n = 3 (patrz podrozdział 1.6.1).
Dla każdej trójki liczb x1, x2, x3 zdarzenie
(X1 = x1 i X2 = x2 i X3 = x3)
zawiera tylko jeden ciąg. Na przykład zdarzenie
(X1 = 1 i X2 = 0 i X3 = 0) = {ORR}.
Czyli dla każdej trójki x1, x2, x3 prawdopodobieństwo
1
P (X1 = x1 i X2 = x2 i X3 = x3) = .
8
1
Z drugiej strony, dla każdego i " {1, 2, 3} mamy P (Xi = xi) = , czyli
2
P (X1 = x1 i X2 = x2 i X3 = x3) = P (X1 = x1) · P (X2 = x2) · P (X3 = x3).
Zmienne X1, . . . , Xn są niezależne także w przypadku rzutu niesymetryczną monetą.
Znowu pokażemy to dla n = 3. W ogólnym przypadku dowód jest podobny. Tak jak dla
rzutu symetryczną monetą dla każdej trójki liczb x1, x2, x3 zdarzenie
(X1 = x1 i X2 = x2 i X3 = x3)
zawiera tylko jeden ciąg. Jego prawdopodobieństwo
P (X1 = x1 i X2 = x2 i X3 = x3) = pkq3-k,
22 Rozdział 1. Rachunek prawdopodobieństwa
gdzie k oznacza liczbÄ™ jedynek w ciÄ…gu (x1, x2, x3).
Z drugiej strony zdarzenie (Xi = 1) zawiera wszystkie ciągi, które na i-tej pozycji
mają O. W podrozdziale 1.6.3 pokazano, że prawdopodobieństwo takiego zdarzenia wy-
nosi p. Podobnie (Xi = 0) zawiera wszystkie ciągi, które na i-tej pozycji mają R, a jego
prawdopodobieństwo wynosi q. Tak więc
P (X1 = x1 i X2 = x2 i X3 = x3) = P (X1 = x1) · P (X2 = x2) · P (X3 = x3).
1.9.1 Własność niezależnych zmiennych losowych
Pokażemy teraz, że jeżeli zmienne losowe X i Y są niezależne, to niezależne są też zmien-
ne X - a i Y - b. Dokładniej
Lemat 1.52 Niech X i Y będą niezależnymi zmiennymi losowymi, a a i b dowolnymi
liczbami rzeczywistymi. Wtedy zmienne X - a i Y - b są niezależne.
Dowód: Niech X1 = X - a oraz Y1 = Y - b. Zayważmy, że X1(É) = x1 wtedy i
tylko wtedy, gdy X(É) = a + x1, czyli zdarzenie X1 = x1 pokrywa siÄ™ ze zdarzeniem
X = a + x1. Podobnie zdarzenie Y1 = y1 pokrywa siÄ™ ze zdarzeniem Y = a + y1.
Mamy więc
P (X1 = x1 i Y1 = y1) = P (X = a + x1 i Y = b + y1) =
P (X = a + x1) · P (Y = b + y1) = P (X1 = x1) · P (Y1 = y1).
Środkowa równość wynika z niezależności zmiennych X i Y .
1.10 Rozkład dwumianowy  Bernoulliego
Przypomnijmy sobie schemat dwumianowy z serią n doświadczeń (rzutów monetą) i z
prawdopodobieństwem sukcesu (wypadnięcia orła) w pojedyńczym doświadczeniu rów-
nym p (podrozdział 1.6.4) Przestrzeń zdarzeń elementarnych jest zbiorem wszystkich cią-
gów dÅ‚ugoÅ›ci n z elementami O i R, w którym prawdopodobieÅ„stwo ciÄ…gu É " &! jest
równe
pkqn-k,
gdzie k oznacza liczbÄ™ symboli O w ciÄ…gu É.
Niech zmienna losowa X oznacza liczbę sukcesów (orłow) w serii. Mówimy, że
zmienna losowa X posiada rozkład dwumianowy (Bernouliego) z parametrami: długo-
ścią serii n i prawdopodobieństwem sukcesu p. Zmienna losowa X przyjmuje wartości k
od 0 do n. Prawdopodobieństwo, że zmienna X posiada wartość k wynosi
n
P (x = k) = pkqn-k.
k
Przykładem zminnej losowej z rozkładem dwumianowym jest zmienna opisana w
przykładzie 1.36, która określa liczbę orłów w serii 3 rzutów.
Dla n = 4 rozkład zmiennej X wygląda następująco:
1.11. Wartość oczekiwana, średnia 23
x 0 1 2 3 4
f(x) q4 4pq3 6p2q2 4p3q p4
Zauważmy, że zmienna losowa X jest sumą zmiennych
n
X(É) = Xi(É),
i=1
gdzie, dla każdego i zmienna Xi oznacza wynik i tego rzutu i jest równa
1, jeżeli za i-tym razem wypadł orzeł
Xi(É) =
0, jeżeli za i-tym razem wypadła reszka
n
RzeczywiÅ›cie, dla każdego ciÄ…gu É suma Xi(É) jest równa liczbie indeksów i "
i=1
{1, . . . , n}, dla których Xi(É) = 1, czyli liczbie pozycji, na których w ciÄ…gu É stoi orzeÅ‚.
1.11 Wartość oczekiwana, średnia
Definicja 1.53 Wartość oczekiwana (średnia) zniennej losowej X to liczba
E(X) = X(É) · P (É).
É"&!
Przykład 1.54 Dla zmiennej losowej X z przykładu 1.36 wartość oczekiwana wynosi
1 12
E(X) = (3 + 2 + 2 + 1 + 2 + 1 + 1 + 0) = = 1.5
8 8
Jeżeli zmienna posiada jednostajny rozkład prawdopodobieństwa, to jej wartość oczeki-
wana jest zwykłą średnią arytmetyczną jej wartości.
1 1
E(X) = X(É) · = · X(É).
|&!| |&!|
É"&! É"&!
W ogólnym przypadku wartość oczekiwana jest nazywana średnią ważoną. Jeżeli mamy
rozkład zmiennej losowej, to wartość oczekiwaną obliczamy według wzoru.
Lemat 1.55 E(X) = x · P (X = x).
x"X(&!)
Dowód: Jeżeli pogrupujemy wyrazy sumy X(É)·P (É) wedÅ‚ug wartoÅ›ci zmiennej
É"&!
X, to otrzymamy
E(X) = X(É) · P (É) = x P (É) = x · P (X = x).
É"&! x"X(&!) X(É)=x x"X(&!)
Przykład 1.56 Przypuśćmy, że mamy informację, że w jakiejś grupie studenckiej połowa
studentów otrzymała ocenę 5 z matematyki dyskretnej, jedna trzecia otrzymała ocenę 4,
a jedna szósta ocenę 3. Jaka jest średnia ocena w tej grupie? Przyjmujemy, że grupa jest
przestrzenią losową, a zmienna losowa X jest oceną studenta. Wtedy wartość oczekiwana
1 1 1 26 1
zmiennej X wynosi E(X) = 5 · + 4 · + 3 · = = 43 i jest Å›redniÄ… ocenÄ… w tej
2 3 6 6
grupie.
24 Rozdział 1. Rachunek prawdopodobieństwa
1.11.1 Własności wartości oczekiwanej
W poniższym twierdzeniu zebrano podstawowe własności wartości oczekiwanej.
Twierdzenie 1.57 a) E(X + Y ) = E(X) + E(Y ).
b) Jeżeli a jest liczbÄ… rzeczywistÄ…, to E(a · X) = a · E(X).
c) Jeżeli zmienne X i Y sÄ… niezależne, to E(X · Y ) = E(X) · E(Y ).
d) Jeżeli X e" 0, to E(X) e" 0.
Dowód:
a)
E(X + Y ) = (X + Y )(É) · P (É) = (X(É) + Y (É)) · P (É) =
É"&! É"&!
X(É) · P (É) + Y (É) · P (É) = E(X) + E(Y ).
É"&! É"&!
b)
E(a·X) = (a·X)(É)·P (É) = a·X(É)·P (É) = a· X(É)·P (É) = a·E(X).
É"&! É"&! É"&!
c)
E(X · Y ) = XY (É)P (É).
É"&!
Pogrupujmy składniki sumy według wartości zmiennych X i Y .
E(X · Y ) = x · y · P (É) =
X(É)=x
x y
Y (É)=y
x · y · P (X = x i Y = y) = x · y · P (X = x) · P (Y = y)
x y x y
= x · P (X = x) · y · P (Y = y) = E(X) · E(Y ).
x y
d) Jeżeli dla każdego É, X(É) e" 0, to X(É) · P (É) e" 0.
É"&!
Punkt a) powyższego twierdzenia można uogólnić (za pomocą indukcji) na sume n
zmiennych.
Twierdzenie 1.58 Wartość oczekiwana sumy k zmiennych X1, . . . , Xk jest równa
k k
E( Xi) = E(Xi).
i=1 i=1
1.11. Wartość oczekiwana, średnia 25
1.11.2 Wartość oczekiwana rozkładu jednopunktowego
Wartość oczekiwana zmiennej X z rozkładem jednopunktowym wynosi
E(X) = m.
Z definicji wartości oczekiwanej wynika następujący fakt:
Lemat 1.59 Jeżeli jakaś zmienna X przyjmuje wartości nieujemne i E(X) = 0, to ma
ona rozkład jednopunktowy.
Założenie, że zmienna X przyjmuje tylko wartości nieujemne jest istotne we wnio-
sku 1.59. Pokazuje to następujący przykład.
Przykład 1.60 Zmienna losowa Z z funkcją gęstości:
zi -1 1
1 1
f(zi)
2 2
ma wartość oczekiwaną E(Z) = 0.
1.11.3 Wartość oczekiwana rozkładu zero-jedynkowego
Wartość oczekiwana zmiennej X z rozkładem zero-jedynkowym wynosi
E(X) = 0q + 1p = p
1.11.4 Wartość oczekiwana rozkładu dwumianowego
Wartość oczekiwana zmiennej losowej X mającej rozkład dwumianowy z długością serii
n i prawdopodobieństwem sukcesu p wynosi E(X) = np.
Wynika to z twierdzenia 1.58 oraz z faktu, że jak zauważyliśmy w podrozdziale 1.10,
n
zmienna X jest sumą n zmienych o rozkładzie zero-jedynkowym X = Xi.
i=1
1.11.5 Wartość oczekiwana liczby różnokolorowych krawędzi
Policzymy teraz wartość oczekiwaną zmiennej X określającej liczbę różnokolorowych
krawędzi w grafie G = (V, E) z n = |V | wierzchołkami (przykład 1.43). W tym celu dla
każdej krawędzi e = {u, v} " E określmy zmienną losową Xe w następujący sposób:
Å„Å‚
1, jeżeli w kolorowaniu É oba koÅ„ce krawÄ™dzi e
òÅ‚
Xe(É) = majÄ… różne kolory,
ół
0, w przeciwnym przypadku.
W przykładzie 1.22 pokazano, że prawdopodobieństwo tego, że dowolna krawędz
ma
1 1
końce w różnych kolorach wynosi , czyli E(Xe) = .
2 2
Zauważmy teraz, że
X = Xe.
e"E
26 Rozdział 1. Rachunek prawdopodobieństwa
RzeczywiÅ›cie dla dowolnego kolorowania É suma X = Xe(É) jest równa liczbie
e"E
krawÄ™dzi; dla których Xe(É) = 1, czyli liczbie krawÄ™dzi z róznymi kolorami na koÅ„cach.
Tak więc mamy
m
E(X) = E(Xe) = .
2
e"E
E(X), czyli średnia liczba różnokolorowych krawędzi w kolorowaniu może być obliczo-
na bez używania terminologii rachunku prawdopodobieństwa. Policzmy ile we wszyst-
kich kolorowaniach jest różnokolorowych krawędzi. Z jednej strony jest to
(liczba różnokolorowych krawÄ™dzi w kolorowaniu É).
É"&!
Z drugiej strony
(liczba kolorowań, w których krawędz
e jest różnokolorowa) = 2n-1 = m·2n-1.
e"E e"E
Przedostatnia równość wynika z tego, że liczba kolorowań, w których e jest różnoko-
lorowa wynosi 2n-1 (połowa wszystkich). Średnia liczba różnokolorowych krawędzi w
kolorowaniu wynosi więc
m · 2n-1 m
= .
2n 2
1.11.6 Własności wartości oczekiwanej c.d.
Często wykorzystywana własność wartości oczekiwanej mówi, że zawsze istnieje przy-
najmniej jedna wartość mniejsza od lub równa wartości średniej oraz wartość większa od
lub równa średniej.
Lemat 1.61 Dla każdej zmiennej losowej X istnieje zdarzenie elementarne É " &! takie,
że P (É) > 0 oraz X(É) e" E(X).
Podobnie istnieje zdarzenie É " &! takie, że P (É) > 0 oraz X(É) d" E(X).
Dowód: Udowodnimy tylko pierwszą część twierdzenia, drugą można udowodnić w po-
dobny sposób. Przypuśćmy, że dla każdego É " &! z dodatnim prawdopodobieÅ„stwem
mamy X(É) < E(X). Ale to prowadzi do sprzecznoÅ›ci
E(X) = X(É) · P (É) < E(X) · P (É) = E(X) P (É) = E(X).
É"&! É"&! É"&!
Przykład 1.62 Wierzchołki dowolnego grafu można pokolorować dwoma kolarami (bia-
łym i czarnym) w taki sposób, że przynajmniej połowa krawędzi ma swoje końce w róż-
nych kolorach. Niech X oznacza liczbę różnokolorowych krawędzi w grafie. W podroz-
m
dziale 1.11.5 pokazano, że wartość oczekiwana zmiennej X wynosi , czyli musi istnieć
2
kolorowanie z co najmniej połową różnokolorowych krawędzi.
1.12. Nierówność Markowa 27
1.12 Nierówność Markowa
Twierdzenie 1.63 (Nierówność Markowa) Jeżeli zmienna losowa X przyjmuje wartości
nieujemne, to dla dowolnej liczby rzeczywistej d > 0
E(X)
P (X e" d) d" .
d
Dowód:
E(X) = x · P (X = x) = x · P (X = x) + x · P (X = x) e"
x
xe"d xx · P (X = x) e" d · P (X = x) = d P (X = x) = d · P (X e" d),
xe"d xe"d xe"d
czyli E(X) e" d · P (X e" d). Po podzieleniu tej nierównoÅ›ci stronami przez d otrzymu-
jemy tezÄ™ twierdzenia.
Zauważmy, że nierówność Markowa jest użyteczna tylko kiedy d > E(X). Jeżeli
E(X)
bowiem d d" E(X), to mamy trywialne oszacowanie P (X e" d) d" 1 d" .
d
Przykład 1.64 Nierówność Markowa wyraża dość prosty fakt. Przypuśćmy, że X określa
liczbę pieniędzy posiadaną przez studenta. Jeżeli wartość średnia zmiennej X wynosi 100
złotych, to tylko połowa studentów może mieć 200 lub więcej złotych. Przypuśćmy bowiem
że 0.5 + część studentów posiada 200 (lub więcej) złotych. Wtedy udział tej bogatej
części studentów w Å›redniej wynosi co najmniej 200 · (0.5 + ) = 100 + 200 · > 100, i
wartość średnia nie może wynosić 100 złotych.
Przykład 1.65 Niech zmienna losowa X posiada rozkład dwumianowy z długością serii
1
n = 1000 oraz prawdopodobieństwem sukcesu p = . Spróbujmy oszacować prawdo-
2
podobieństwo P (X e" 600). Wartość oczekiwana E(X) = np = 500. Z nierówności
Markowa otrzymamy oszacowanie
500 5
P (X e" 600) d" = .
600 6
1
Oszacowanie to jest bardzo grube. Zauważmy, że P (X e" 500) = , ponieważ rozkład
2
jest symetryczny P (X = k) = P (X = 1000 - k) dla każdego k.
1.13 Wariancja
Definicja 1.66 Wariancją zmiennej losowej X o wartości oczekiwanej E(X) = mX
nazywamy liczbÄ™
V ar(X) = E((X - mX)2)
Wariancja V ar(X) jest miarą tego jak bardzo wartości zmiennej X są oddalone od śred-
niej. Im większe rozrzucenie wartości tym większa wariancja. W poniższym twierdzeniu
zebrano podstawowe własności wariancji
28 Rozdział 1. Rachunek prawdopodobieństwa
Twierdzenie 1.67 a) V ar(X) e" 0.
b) V ar(X) = E(X2) - m2
X
c) V ar(aX) = a2V ar(X).
d) Jeżeli zmienne X i Y są niezależne, to V ar(X + Y ) = V ar(X) + V ar(Y ).
e) Jeżeli zmienne X1, . . . , Xk są parami niezależne, to
k k
V ar Xi = V ar(Xi)
i=1 i=1
Dowód:
a) wynika z faktu, że zmienna (X - mX)2 przyjmuje tylko nieujemne wartości,
b) V ar(X) = E((X - mX)2) = E(X2 - 2mX · X + m2 ) = E(X2) - 2mXE(X) +
X
m2 = E(X2) - 2m2 + m2 = E(X2) - m2
X X X X
c) V ar(aX) = E(aX - E(aX))2 = E(a2(X - EX)2) = a2V ar(X).
d) Pamiętajmy, że E(X + Y ) = mX + mY . Mamy
(X+Y -E(X+Y ))2 = (X-mX+Y -mY )2 = (X-mX)2+(y-mY )2+2(X-mX)(Y -mY )
czyli
V ar(X+Y ) = E(X-mX)2+E(Y -mY )2+2E(X-mX)E(Y -mY ) = V ar(X)+V ar(Y ).
Przedstatnia równość wynika z faktu, że na podstawie lematu 1.52 zmienne X -mX oraz
Y - mY są niezależne, a ostatnia równość z faktu, że E(X - mX) = mX - mX = 0.
e) Podobnie jak w przypadku d) korzystając z faktu, że
k k k k k
2
Xi - mX = (Xi - mX )2 + 2 (Xi - mX )(Xj - mX )
i i i j
i=1 i=1 i=1 i=1 j=i+1
oraz z faktu, że zmienne X1 - mX , .... ,Xk - mX są parami niezależne.
1 k
1.13.1 Wariancja rozkładu jednopunktowego
Wariancja zmiennej losowej X z rozkładem jednopunktowym wynosi
V ar(X) = E(X2) - (E(X))2 = m2 - m2 = 0.
Ale i na odwrót
Lemat 1.68 Jeżeli V ar(X) = 0, to zmienna losowa X posiada rozkład jednopunktowy.
Dowód: Ponieważ V ar(X) = E((X - mX)2) = 0, to z lematu 1.59 wynika, że 1 =
P (X - mX = 0) = P (X = mX).
1.13. Wariancja 29
1.13.2 Wariancja rozkładu zero-jedynkowego
Jeżeli X ma rozkład zero-jedynkowy to jego wariancvja wynosi
V ar(X) = E(X2) - (E(X))2 = p - p2 = p(1 - p) = pq.
1.13.3 Wariancja rozkładu dwumianowego
Jeżeli zmienna losowa X ma rozkład dwumianowy z długością serii n i prawdopodobień-
n
stwem sukcesu p, to jest sumą X = Xi niezależnych zmiennych Xi o rozkładach
i=1
zero-jedynkowych. Wariancja każdej zmiennej Xi wynosi V ar(Xi) = pq. Wariancja
zmiennej losowej X wynosi więc
V ar(X) = npq.
1.13.4 Wariancja liczby różnokolorowych krawędzi
Obliczmy variancję zmiennej losowej X oznaczającej liczbę krawędzi dwukolorowych w
kolorawaniu grafu G (patrz podrozdział 1.11.5). Najpierw zauważmy, że zmienne losowe
Xe są parami niezależne. Dokładniej, jeżeli e1 i e2 są dwoma różnymi krawędziami grafu
G, to zmienne Xe i Xe są niezależne. Niech e1 = {u1, v1} i e2 = {u2, v2}. Ponieważ
1 2
krawędzie są różne, to mogą mieć tylko jeden wspólny koniec. Załóżmy, że wierzchołek
v2 " e1. W przykładzie 1.6.2 pokazaliśmy, że jednostajny rozkład pokolorowań otrzy-
/
1
mamy kolorując po kolei wierzchołki niezależnie i ze stałym prawdopodobieństwem:
2
1
dla koloru białego i dla czarnego. Możemy założyć, że wierzchołek v2 jest kolorawny
2
ostatni. A
atwo teraz zauważyć, że przy jednym wyborze koloru dla v2 mamy Xe = Xe ,
1 2
a przy drugim Xe = Xe . A
ączny rozkład prawdopodobieństwa zmiennych Xe i Xe

1 2 1 2
wygląda więc następująco:
Xe
2
0 1
Xe 0 1/4 1/4
1
1 1/4 1/4
czyli zmienne te są niezałeżne.
1
Dla każdej krawędzi e mamy V ar(Xe) = i na podstawie twierdzenia 1.67e mamy
4
m
V ar(X) = .
4
Zauważmy, że cały komplet zmiennych Xe dla wszystkich krawędzi grafu nie musi
być niezależny. Na przykład, jeżeli trzy krawędzie e1, e2 i e3 tworzą trójkąt, to zmienne
Xe , Xe , Xe nie sÄ… niezależne. RzeczywiÅ›cie, jeżeli Xe (É) = Xe (É) = 0, to w
1 2 3 1 2
kolorowaniu É koÅ„ce obu krawÄ™dzi e1 i e2 maja taki sam kolor, ale wtedy, także koÅ„ce
krawÄ™dzi e3 sÄ… w tym samym kolorze i Xe (É) = 0.
3
30 Rozdział 1. Rachunek prawdopodobieństwa
1.14 Nierówność Czebyszewa
Twierdzenie 1.69 (Nierówność Czebyszewa) Dla zmiennej losowej X z wartością ocze-
kiwanÄ… E(X) = mX oraz liczby rzeczywistej > 0 mamy
V ar(X)
P (|X - mX| e" ) d" .
2
Dowód: Rozważmy zmienną losową Y = X - mX. Ponieważ
2 2
|Y (É)| e" Ô! Y (É) e" ,
to
2 2
P (|Y | e" ) = P (Y e" ).
2
Stosując nierówność Markowa dla zmiennej Y mamy
2
E(Y )
2 2
P (|Y | e" ) = P (Y e" ) d"
2
ale
2
E(Y ) = E((X - mX)2) = V ar(X)
Przykład 1.70 (Kontynuacja przykładu 1.65). Dla zmienneja losowej X z rozkładem
1
dwumianowy z parametrami n = 1000 oraz p = spróbujmy oszacować prawdo-
2
podobieństwo P (X e" 600). Wartość oczekiwana E(X) = np = 500, a wariancja
V ar(X) = npq = 250. Z symetrii rozkładu wynika, że
1
P (X e" 600) = P (|x - 500| e" 100)
2
i z nierówności Czebyszewa otrzymamy
1 250 1
P (X e" 600) d" · = = 0.0125.
2 10000 80
1.15 Krańce rozkładu dwumianowego
Dla zmiennej losowej X z rozkładem dwumianowym istnieją oszacowania, które w nie-
których przypadkach są lepsze od nierówności Czebyszewa.
Twierdzenie 1.71 (Nierówności Chernoff a) Niech zmienna losowa X posiada rozkład
dwumianowy z długością serii n i prawdopodobieństwem sukcesu p. Oznaczmy wartość
oczekiwaną tego rozkładu przez m = np. Wtedy dla dowolnej liczby rzeczywistej , 0 d"
d" 1, mamy
2
P (X e" (1 + )m) d" e- m/3
oraz
2
P (X d" (1 - )m) d" e- m/2
1.16. Problem dnia urodzin 31
Przykład 1.72 Jeżeli zastosujemy pierwszą nierówność Chernoffa do przykładu 1.70, to
otrzymamy oszacowanie
1 1
P (X e" 600) = P (X e" (1 + )500) d" e-20/3 d"
5 786
Jeżeli skorzystamy z symetrii rozkładu i z drugiej nierówność Chernoffa, to otrzymamy
dużo lepsze oszacowanie
1 1
P (X e" 600) = P (X d" 400) = P (X d" (1 - )500) d" e-10 d"
5 22027
1.16 Problem dnia urodzin
Przypuśćmy, że na przyjęciu jest k osób. Wtedy prawdopodobieństwo, że nowo przybyła
osoba ma urodziny tego samego dnia, co jakaś z osób już obecnych jest nie większe niż
k 365 1
. Tak więc, k musi być większe niż , aby prawdopodobieństwo to przekroczyło .
365 2 2
Zastanówmy się teraz ile osób musi znajdować się w pokoju, aby była duża szansa
1
(większa od ), że dwie osoby mają urodziny tego samego dnia.
2
Dla prostoty przyjmujemy, że problem dnia urodzin jest równoważnu problemowi
wylosowania ciągu k liczb u1, . . . , uk, każda spośród n = 365 możliwości, tak aby wy-
stąpiło w nim jakieś powtórzenie.
Oznaczmy przez Bk zdarzenie przeciwne, że wszystkie wylosowane liczby są różne.
Jeżeli założymy, że wszystkie ciągi są równo prawdopodobne, to prawdopodobieństwo,
że otrzymamy ciąg różnowartościowy wynosi
n(n - 1) · · · (n - k + 1) n - 1 n - 2 n - k + 1
P (Bk) = = 1 · ( ) · ( ) · · · ( ) =
nk n n n
1 2 k - 1
= 1 · (1 - ) · (1 - ) · · · (1 - ).
n n n
Skorzystamy teraz z nierówności 1 + x d" ex
k-1
i=1
P (Bk) d" e-1/ne-2/n · · · e-(k-1)/n = e- i/n =
2
= e-k(k-1)/2n d" e-(k-1)(k-1)/2n = e-(k-1) /2n.
1
Prawdopodobieństwo jest mniejsze od wtedy gdy (k - 1)2 e" 2n ln 2, a to zachodzi
2
"to "
wtedy gdy k e" 1 + 2 ln 2 n. Dla n = 365, zachodzi to dla k e" 24.
Tak więc jeśli w pokoju znajdują się co najmniej 24 osoby, to z prawdopodobieństwem
1
większym od dwie spośród nich mają urodziny w tym samym dniu.
2
1.17 Algorytmy probabilistyczne
Algorytmy probabilistyczne to algorytmy, które w trakcie obliczenia dokonują losowych
wyborów. Prześledzimy teraz kilka prostych przykładów.
32 Rozdział 1. Rachunek prawdopodobieństwa
1.17.1 Algorytm z jednostronnym błędem
Wyobrażmy sobie, że mamy urny z kulami. Urny są dwojakiego rodzaju. Urny pierwszego
rodzaju zawierają wyłącznie kule białe. W urnach drugiego rodzaju są kule białe i czarne
po połowie. Celem algorytmu jest rozpoznanie jakiego rodzaju jest dana urna. Zakładamy
przy tym, że nie możemy obejrzeć wszystkich kul z urny.
Nasz pierwszy algorytm polega na wylosowaniu jednej kuli z danej urny. Jeżeli wy-
losowana kula jest biała, to orzekamy, że urna jest pierwszego rodzaju, a jeżeli kula jest
czarna, to orzekamy, że urna jest drugiego rodzaju. Jeżeli urna naprawdę jest pierwszego
rodzaju, to nasz algorytm na pewno, z prawdopodobieństwem równym 1 da poprawną
odpowiedz
. Jeżeli natomiast urna jest drugiego rodzaju, to poprawną odpowiedz
uzyska-
1
my z prawdopodobieństwem równym . Prawdopodobieńswto błędu można zmniejszyć
2
powtarzajÄ…c losowanie kilka razy.
Drugi algorytm składa się z t rund. W każdej rundzie losujemy jedną kulę i po obej-
rzeniu zwracamy ją spowrotem do urny. Jeżeli w któreś rundzie wylosowano kulę czarną,
to algorytm orzeka, że urna jest drugiego rodzaju. Jeżeli we wszystkich losowaniach wy-
padła kula biała, to algorytm orzeka, że urna jest pierwszego rodzaju. Jeżeli urna jest
pierwszego rodzaju, to drugi algorytm na pewno da poprawnÄ… odpowiedz
. Jeżeli urna jest
drugiego rodzaju, to błąd popełnimy wtedy, gdy t razy z rzędu wylosujemy kulę białą.
1
Zakładając, że losowania kul są niezależne, prawdopodobieństwo błędu wynosi .
2t
1.17.2 Algorytm sprawdzający mnożenie wielomianów
Przypuśćmy, że mamy trzy wielomiany P (x), Q(x) i R(x) i mamy sprawdzić, czy R(x) =
P (x) · Q(x), zachodzi dla każdego rzeczywistego x. Załóżmy, że P (x) i Q(x) sÄ… stopnia
n, a R(x) jest stopnia 2n. Jednym ze sposobów jest pomnożenie wielomianów P (x) i
Q(x) i porównanie współczynników iloczynu z wielomianem R(x). Ta metoda wymaga
około n2 mnożeń. Przedstawimy teraz szybszy algorytm probabilistyczny sprawdzający,
czy dwa wielomiany są dobrze wymnożone.
Algorytm probabilistyczny sprawdzający mnożenie wielomianów.
Dane wejściowe: trzy wielomiany: P (x), Q(x) oraz R(x).
Dane wyjściowe: odpowiedz
, czy P (x) · Q(x) = R(x).
Losuj liczbę naturalną x0 z przedziału od 0 do 4n,
oblicz warości u0 = P (x0), v0 = Q(x0) oraz w0 = R(x0).
porównaj w0 z iloczynem u0 · v0.
Jeżeli w0 = u0 · v0, to

orzekaj, że P (x) · Q(x) = R(x).

Jeżeli w0 = u0 · v0, to
orzekaj, że P (x) · Q(x) = R(x).
W rozdziale pierszym pokazano, że wartość wielomianu P (x) stopnia n w punkcie x0
można obliczyć w czasie proporcjonalnym do n. Jeżeli równość P (x) · Q(x) = R(x) jest
tożsamoÅ›ciÄ…, to dla każdej wylosowanej wartoÅ›ci x0 otrzymamy P (x0) · Q(x0) = R(x0),
czyli nasz algorytm udzieli poprawnej odpowiedzi z prawdopodobieństwem równym 1.
Jeżeli P (x)·Q(x) = R(x) nie jest tożsamoÅ›ciÄ…, to wielomian W (x) = P (x)·Q(x)-R(x)
1.17. Algorytmy probabilistyczne 33
nie jest tożsamościowo równy 0, i algorytm może wylosować x0, które jest pierwiastkiem
wielomianu W (x), i dać błędną odpowiedz
. Ale jak pokazano w rozdziale pierwszym
wielomian stopnia 2n nie ma więcej niż 2n pierwiastków, więc prawdopodobieństwo
1
błędu jest nie większe niż .
2
1.17.3 Algorytmy z błędem obustronnym
W przykładach z poprzedniego podrozdziału tylko jedna z odpowiedzi typu TAK/NIE
może być udzielana błędnie. Czasami mamy do czynienia z sytuacją kiedy błędy są moż-
liwe w obu przypadkach.
Wyobraz
my sobie teraz, że oba rodzaje urn zawierają kule białe i czarne. Urny pierw-
2 1
szego rodzaju zawierają kul białych i kul czarnych, a urny drugiego rodzaju zawierają
3 3
1 2
kul białych i kul czarnych.
3 3
Jak poprzednio algorytm losuje jedną kulę i orzeka że urna jest pierwszego rodza-
ju, jeżeli wylosuje kulę biała, oraz orzeka, że urna jest drugiego rodzaju, jeżeli wylosuje
kulę czarną. Algorytm może teraz popełnić błąd w obu przypadkach. Pradwopodobień-
1
stwo złej odpowiedzi wynosi . Aby zmniejszyć prawdopodobieństwo błędu losujemy
3
ze zwracaniem t razy. Jeżeli więcej było kul białych, to algorytm orzeka, że urna jest
pierwszego rodzaju, a jeżeli więcej było czarnych, to orzeka, że drugiego rodzaju.
Zastanówmy się teraz jakie jest prawdopodobieństwo błędu jeżeli losujemy z urny
pierwszego rodzaju. Niech X oznacza liczbÄ™ wylosowanych kul czarnych. X posiada
1
rozkład dwumianowy długości t z prawdopodobieństwem sukcesu . Algorytm popełni
3
t
błąd, jeżeli liczba sukcesów będzie większa od . Z nierówności Chernoffa prawdopodo-
2
bieństwo to można oszacować w następujący sposób:
t 1 t t
36
P (X e" ) = P (X e" (1 + ) ) d" e- .
2 2 3
Z nierówności Czebyszewa można to oszacować przez
t t t t t 2t t2 8
P (X e" ) = P (X - e" ) e" P (|X - | e" ) e" : = .
2 3 6 3 6 9 36 t
1.17.4 Algorytm kolorownia wierzchołków grafu
1
Wyobraz
my sobie algorytm, który niezależnie i ze stałym prawdopodobieństwem kolo-
2
ruje na biało lub czarno wierzchołki wybranego grafu G = (V, E). Chcemy go wykorzy-
stać do takiego pokolorowania grafu aby mieć dużo krawędzi dwukolorowych. Niech X
m m
oznacza liczbę krawędzi dwukolorowych. Pamiętamy, że EX = oraz V ar(X) = .
2 4
"
m 3
Za pomocą nierówności Czebyszewa pokażemy, że P (X > - m) e" . W tym celu
2 4
oszacujemy prawdopodobieństwo zdarzenia przeciwnego
" "
m m m 1
P (X d" - m) d" P (|X - | d" m) d" = .
2 2 4m 4
34 Rozdział 1. Rachunek prawdopodobieństwa
1.18 Zadania
1. Zaproponuj przestrzeń zdarzeń elementarnych dla rzutu dwiema (rozróżnialnymi)
kostkami. Przedstaw zdarzenie, że suma oczek na obu kostkach wynosi 5.
2. Zaproponuj przestrzeń zdarzeń elementarnych dla losowania dwóch kul z urny za-
wierającej 3 kule białe i 4 czarne. Przedstaw zdarzenie, że wylosowano:
a) dwie kule białe, b) kule w różnych kolorach.
3. Zaproponuj przestrzeń zdarzeń elementarnych dla ustawienia czterech liter a, b, c
i d w ciąg. Przedstaw zdarzenie, że: a) a i b stoją obok siebie; b) a i b są
rozdzielone jednÄ… literÄ….
4. Zaproponuj przestrzeń zdarzeń elementarnych dla następujących doświadczeń: a)
Rzut monetą i kostką. b) Losowanie 13 kart z talii 52 kart. c) Wypełnienie kuponu
totolotka. d) Wypełnienie kuponu totalizatora piłkarskiego.
5. A, B i C są zdarzeniami. Zapisać za pomocą działań na zbiorach zdarzenia:
a) zachodzÄ… wszystkie trzy zdarzenia;
b) zachodzi dokładnie jedno ze zdarzeń A, B lub C;
c) zachodzą dokładnie dwa ze zdarzeń A, B, C;
d) zachodzą co najmniej dwa spośród zdarzeń A, B, C.
6. Cyfry 0, . . . , 9 ustawiono losowo. Jakie jest prawdopodobieństwo: a) że 1 i 2 stoją
obok siebie; b) że pomiędzy 1 i 2 stoją dwie cyfry; c) że 0, 1 i 2 stoją obok siebie.
7. Pokazać, że P (A )" B) e" P (A) + P (B) - 1
1 1 2
8. Dane są P (A ) = , P (A )" B) = i P (A *" B) = . Obliczyć P (B ), P (A )" B )
3 4 3
i P (B - A).
1 1
9. Dane są P (A )" B) = i P (A *" B) = , wiadomo też, że P (A - B) = P (B - A).
4 2
Obliczyć P (B) oraz P (B - A).
10. Udowodnij, że dla dowolnej rodziny zbiorów A1, . . . , An (niekoniecznie parami
rozłącznych) mamy
n n
P Ai d" P (Ai)
i=1 i=1
11. W urnie są 4 kule białe i 3 czarne. Losujemy dwie. Jakie jest prawdopodobieństwo,
że wylosowane kule będą w różnych kolorach?
12. Jakie jest prawdopodobieństwo, że przy okrągłym stole wybrane na początku dwie
osoby usiÄ…dÄ… obok siebie?
1.18. Zadania 35
13. Niech przestrzeń zdarzeń elementarnych będzie zbiorem 3 elementowych ciągów
zero-jedynkowych. Wypisz zdarzenia: a) na pierwszej współrzędnej jest zero; b) na
pierwszej i trzeciej współrzędnej są zera; c) na pierwszej i trzeciej współrzędnej
mamy różne wartości; d) na wszystkich współrzędnych jest to samo.
14. Oblicz prawdopodobieństwa zdarzeń z poprzedniego zadania (rozkład jednostaj-
ny).
15. Niech przestrzeń zdarzeń elementarnych będzie zbiorem n elementowych ciągów
zero-jedynkowych (rozkład jednostajny). Oblicz prawdopodobieństwa zdarzeń z
zadania 13.
16. Policz jakie jest prawdopodobieństwo, że losowo wybrana funkcja posiada takie
same wartości dla dwóch z góry wybranych punktów a i b (patrz przykład 1.11).
17. Dwukrotnie rzucamy monetą. Niech zdarzenie A oznacza, że wypadł dokladnie
jeden orzeł, a zdarzenie B oznacza, że w pierwszym rzucie wypadł orzeł. Oblicz
P (B|A). Czy zdarzenia A i B są niezależne?
18. Rzucamy trzema kostkami. Jakie jest prawdopodobieństwo, że na żadnej kostce nie
wypada szóstka, jeżeli na każdej kostce wypada inna liczba oczek.
19. Mamy dwie urny z kulami. W pierwszej urnie są dwie kule białe i cztery czarne, a
w drugiej urnie trzy białe i trzy czarne. Rzucamy kostką do gry. Jeżeli wypadnie 1
lub 2, to losujemy kulę z pierwszej urny, jeżeli 3,4,5 lub 6, to losujemy z drugiej
urny. Jakie jest prawdopodobieństwo, że wylosujemy kulę białą?
20. W urnie jest n kul w tym k białych. n osób po kolei losuje jedną kulę bez zwracania.
a) Ile wynosi prawdopodobieństwo wylosowania kuli białej dla trzeciej osoby? b)
Ile wynosi prawdopodobieństwo wylosowania kuli białej dla każdej z losujących
osób?
21. Udowodnij, że jeżeli zdarzenia A i B są niezależne, to niezależne są także zdarzenia
A i B oraz A i B .
22. Zmienna X5(x) = x mod 5 jest określona na przestrzeni {1, . . . , 30} z jednostaj-
nym rozkładem. Podaj jej rozkład, wartość oczekiwaną oraz P (X < 3).
23. Zmienna losowa X posiada rozkład:
x 1 2 3 4 5
1 1 1 1 1
P (X = x)
2 4 8 16 16
Oblicz P (Xparzyste), P (X < 3), wartość oczekiwaną EX, wariancję V ar(X)
oraz P (X e" EX).
24. Mamy urnę z czteroma białymi i trzema czarnymi kulami. Losujemy bez zwraca-
nia trzy kule i niech zmienna losowa X oznacza ile wśród wylosowanych jest kul
białych. Podaj gęstość rozkładu zmiennej losowej X oraz jej wartość oczekiwaną.
36 Rozdział 1. Rachunek prawdopodobieństwa
25. W urnie znajduje się pięć monet, trzy pięciozłotowe i cztery dwuzłotowe. Losujemy
dwie monety i niech zmienna losowa Y oznacza sumę nominałów wylosowanych
monet. Oblicz gęstość rozkładu zmiennej losowej Y oraz jej wartość oczekiwaną.
26. Rzucamy monetą aż do wypadnięcia orła, ale nie więcej niż cztery razy. Niech
zmienna losowa Z oznacza liczbę wykonanych rzutów. Podaj gęstość rozkładu
zmiennej losowej Z oraz jej wartość oczekiwaną.
27. W urnie znajduje się sześć monet, dwie pięciozłotowe, dwie dwuzłotowe oraz dwie
jednozłotowe. Losujemy jedną monetę, a jeśli jest to złotówka to losujemy jeszcze
jedną. Niech zmienna losowa Z oznacza sumę nominałów wylosowanych monet.
Oblicz gęstość rozkładu zmiennej losowej Z oraz jej wartość oczekiwaną.
28. Rzucamy dwukrotnie monetą. Określamy dwie zmienne losowe X1 oraz X2. Zmien-
na X1 przyjmuje wartość 1, jeżeli za pierwszym razem wypadnie orzeł, oraz war-
tość 0, jeżeli za pierwszym razem wypadnie reszka. Podobnie zmienna X2 opisuje
wynik drugiego rzutu. Niech zmienna C będzie określona wzorem C = X1 + X2.
Podaj rozkład zmiennej losowej C. Czy zmienne C i X1 są niezależne?
29. W urnie znajduje się pięć kul z numerami 1,2,3,4,5. Losujemy ze zwracaniem dwie
kule. Niech zmienna losowa X oznacza sumę numerów obu kul. Oblicz gęstość
rozkładu zmiennej losowej X oraz jej wartość oczekiwaną.
30. Zmienna losowa Y posiada rozkład:
x -2 -1 0 1 2
1 1 1 1 1
P (X = x)
12 6 2 6 12
Oblicz wartość oczekiwaną EX, wariancję V ar(X) oraz P (|X - EX| e" 1).
Porównaj ostatnią liczbę z wartością otrzymaną z oszacowania Czebyszewa.
31. Podaj przykład nieujemnej zmiennej losowej X oraz liczby d, dla których zachodzi
EX
P (X e" d) = .
d
32. Podaj przykład zmiennej losowej X oraz liczby , dla których zachodzi
V arX
P (|X - EX| e" ) = .
2
33. Mamy graf z czteroma wierzchołkami {a, b, c, d} i krawędziami {{a, b}, {b, c}, {c, d}, {a, d}, }.
Rozważmy przestrzeń wszystkich kolorowań wierzchołków tego grafu dwoma ko-
lorami. Nich zmienna losowa X oznacza liczbę krawędzi z różnymi kolorami na
końcach. Podaj rozkład zmiennej losowej X oraz jej wartość oczekiwaną.
34. A
ączny rozkład zmiennych losowych X i Y przedstawiony jest w tabeli.
1.18. Zadania 37
Y
-1 0 1
1 1 1
X 0
8 4 8
1 1 1
1
6 6 6
Oblicz rozkłady zmiennych X, Y , Z = X + Y , W = 2X - Y .
Oblicz EX, EY , V ar(X), V ar(Y ), E(X + Y ), V ar(X + Y ).
Czy zmienne X i Y są niezależne?
Oblicz prawdopodobieństwa P (X = Y ), P (X < Y ).
35. Na przestrzeni {1, . . . , 30} z jednostajnym rozkładem określamy trzy zmienne X5(x) =
x mod 5, X3(x) = x mod 3, X2(x) = x mod 2. Czy zmienne te są niezależne?
36. Pokazać, że dla każdego 0 < e < 1 istnieje zmienna losowa X taka, że E(X) = 1
oraz P (X < 0.5) = 1 - e.
37. Pokazać, że jeżeli X ma rozkład symetryczny, tzn dla pewnego m, P (X = m -
x) = P (X = m + x) dla każdego x, to EX = m.
38. Pokazać, że V arX = V ar(X + c)
39. Podać przykład dwóch zmiennych X i Y o różnych rozkładach takich, że EX =
EY i V arX = V arY .
40. Przypuśćmy, że zmienna losowa przyjmuje n > 2 wartości x1 < x2 < . . . < xn
każde z dodatnim prawdopodobieństwem.
a) Czy jest możliwe EX = x1 lub EX = xn?
b) Czy jest możliwe EX < x2 lub EX > xn-1?
c) Czy b) jest możliwe jeżeli X ma rozkład jednostajny?
41. Rzucano symetryczną monetą 9 razy. Jakie jest prawdopodobieństwo, że: a) orzeł
wypadł co najmniej raz, b) orzeł wypadł parzystą liczbę razy?
42. Jakie jest prawdopodobieństwo, że w serii sześciu rzutów kostką suma oczek będzie
parzysta.
43. Pokaż, że jeżeli i < j < np, to B(n, p, i) < B(n, p, j); a jeżeli np < i < j, to
n
B(n, p, i) > B(n, p, j), gdzie B(n, p, i) = piqn-i to rozkład dwumianowy.
i
44. Niech zmienna losowa X ma rozkład dwumianowy z parametrami n = 2000,
1
p = . Oszacuj prawdopodobieństwo P (X > 1500) (za pomocą nierówności
2
Markowa, Czebyszewa i Chernoff a).
45. Rozważmy przestrzeń wszystkich grafów ze zbiorem wierzchołków {1, . . . , n} z
jednostajnym rozkładem prawdopodobieństwa. Jakie jest prawdopodobieństwo, że
wierzchołki 1 i 2 są połączone krawędzią?
38 Rozdział 1. Rachunek prawdopodobieństwa
46. Podobnie jak w poprzednim zadaniu rozważmy przestrzeń grafów z czteroma wierz-
chołkami {1, 2, 3, 4}. Jake jest prawdopodobieństwo, że graf jest spójny (każde dwa
jego wierzchołki są połączone ścieżką)?
47. Rozważmy kolorowanie dowolnego grafu G = (V, E) trzema kolorami. Niech
zmienna losowa X oznacza liczbę różnokolorowych krawędzi. Oblicz E(X) oraz
V ar(X).
1.19 Problemy
1.19.1 Niezależność zmiennych losowych
1. Mamy trzy niezależne zmienne losowe X, Y i Z (określone na jakiejś przestrzeni
probabilistycznej). Udowodnij, że każde dwie też są niezależne.
2. Pokaż, że jeżeli zmienne losowe X i Y są niezależne, to dla dowolnych funkcji g i
h, zmienne g ć% X i h ć% Y też są niezależne.
3. Udowodnij, że jeżeli A i B są dowolnymi podzbiorami zbioru liczb rzeczywistych,
to zdarzenia
AX = {É | X(É) " A} oraz BY = {É | Y (É) " B}
są niezależne.
4. Pokazać, że jeżeli mamy zmienna losową X z rozkładem jednopunktowym i do-
wolną inną zmienną Y , to X i Y są niezależne
1.19.2 Suma kwadratów
Niech x1, . . . , xk będą dowolnymi liczbami rzeczywistymi i niech
k
1
m = xi.
k
i=1
Udowodnij, że
k
1
x2 e" m2,
i
k
i=1
przy czym równość zachodzi wtedy i tylko wtedy, gdy xi = m dla każdego i.
Wskazówka: Niech &! = {1, . . . , k} będzie przestrzenią z jednostajnym rozkładem praw-
dopodobieństwa i niech X będzie zmienną losową określoną wzorem X(i) = xi. Oblicz
wariancjÄ™ tej zmiennej losowej.