ˇ Limitn´ı vety prof. RNDr. Roman Koteck´y DrSc., Dr. Rudolf Blaˇzek, PhD Katedra teoreticke´ informatiky Fakulta informaˇcn´ıch technologi´ı ˇ Cesk e´ vysoke´ uˇcen´ı technicke´ v Praze c Rudolf Blaˇzek, Roman Koteck´y, 2011
ˇ Pravdepodobnost a statistika ´ ska 8 BI-PST, LS 2010/11, Pˇrednaˇ
´ ı fond. Evropsk´y socialn´ Praha & EU: Investujeme do vaˇs´ı budoucnosti
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
1 / 19
Rekapitulace
ˇ a´ hustota pravdepodobnosti ˇ ´ ˇ a´ jevem A: Podm´ınen fX |A nahodn e´ veliˇciny X podm´ınen hustota fX |A pro kterou P (X ∈ B | A) =
( fX |X ∈D (x ) =
´ Upln´ y rozklad pro hustoty : fX (x ) =
R
f B X |A
(x )dx.
R fX (x ) pro x f (t )dt D X
∈ D,
0 jindy.
Pn
i =1 fX |Ai
(x )P (Ai ).
ˇ ı nahodn ´ ´ Podm´ınen´ e´ veliˇciny X nahodnou veliˇcinou Y : fX |Y (x |y ) =
fX ,Y (x , y ) fY (y )
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
Z ,
P (X ∈ A|Y = y ) =
fX |Y (x |y )dx . A
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
2 / 19
Rekapitulace
ˇ e´ stˇredn´ı hodnoty : Podm´ınen
Z
∞
E (X |A) =
Z
−∞
E (X ) =
∞
x fX |A (x )dx a E (X |Y = y ) =
n X
x fX |Y (x |y )dx . −∞
Z
∞
P (Ai )E (X |Ai ) a E (X ) =
E (X |Y = y )fY (y )dy . −∞
i =1
´ Posledn´ı rovnost muˇ e´ ˚ zeme interpretovat jako tvrzen´ı o stˇredn´ı hodnoteˇ nahodn veliˇciny E (X |Y ) ktera´ nab´yva´ hodnoty E (X |Y = y ) kdykoliv Y = y . A sice, E (E (X |Y )) = E (X ). Bayesova formule : fX (x )fY |X (y |x ) fX |Y (x |y ) = R ∞ −∞ fX (t )fY |X (y |t )dt
pN (n)fY |N (y |n) . a P (N = n|Y = y ) = P k pN (k )fY |N (y , k )
´ Kovariance nahodn´ ych veliˇcin X a Y : Cov(X , Y ) = E (XY ) − E (X )E (Y ).
Cov(X ,Y ) ´ Korelaˇcn´ı coeficient nahodn´ ych veliˇcin X a Y : ρ(X , Y ) = √
var(X )var(Y )
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
.
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
3 / 19
Generuj´ıc´ı funkce
Definice
Definice ˇ moment generuj´ıc´ı funkce) nahodn ´ Generuj´ıc´ı funkce (ˇci pˇresneji, e´ veliˇciny X je funkce M (s) = MX (s) definovana´ vztahem M (s) = E (esX ). ´ ı cˇ i spojitou veliˇcinu, Tj. pro diskretn´ M (s ) =
X
Z
sk
e pX (k ),
∞
M (s ) =
esx fX (x )dx .
−∞
k
Generuj´ıc´ı funkce jednoznaˇcneˇ urˇcuje hustotu fX (resp. funkci pX ) pro veliˇcinu X . ´ e, ˇ umoˇznuje ˇ Specialn vypoˇc´ıtat momenty veliˇciny X : ˇ Veta ´ Pro nahodnou veliˇcinu X s generuj´ıc´ı funkc´ı M(s) plat´ı: E (X n ) = ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
dn ds
M (s) s=0 . n
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
4 / 19
Generuj´ıc´ı funkce
Pˇr´ıklady generuj´ıc´ıch funkc´ı
Pˇr´ıklady ´ Poissonova nahodn a´ veliˇcina : k −λ pX (k ) = λ ke! , k = 0, 1, . . .
M (s) =
∞ X k =0
´ ame: ´ Dostav
d ds
d
esk
λk e−λ s = eλ(e −1) . k!
s s eλ(e −1) = λes eλ(e −1) =⇒ E (X ) = λ,
2
ds
λ(es −1) λ(es −1) s 2 s e = (λ e ) + λ e e =⇒ E (X 2 ) = λ + λ2 a var(X ) = λ. 2
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
5 / 19
Generuj´ıc´ı funkce
Pˇr´ıklady generuj´ıc´ıch funkc´ı
ˇ an´ ´ ı) Pˇr´ıklady (pokracov ´ ı nahodn ´ Exponencialn´ a´ veliˇcina : fX (x ) = λe−λx , x ≥ 0. Pak
Z
∞
M (s) = λ
esx e−λx = λ
0
e(s−λ)x ∞ s−λ
0
=
λ . λ−s
ˇ si, zˇ e M (s) je definovana ´ ´ Vˇsimnete jen pro s ∈ [0, λ). Pro s ≥ λ integral diverguje. Odsud d
λ
ds λ − s d2 ds2
=
λ 1 =⇒ E (X ) = , (λ − s)2 λ
λ 2λ 2 1 = =⇒ E (X 2 ) = 2 a var(X ) = 2 . 3 λ−s (λ − s) λ λ
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
6 / 19
Generuj´ıc´ı funkce
´ ´ ˇ Sumy nezavisl ych ´ nahodn ych ´ velicin
´ ı nahodn´ ´ ´ Sˇc´ıtan´ ych veliˇcin odpov´ıda´ nasoben´ ı jejich generuj´ıc´ıch funkc´ı ´ Pro Z = X + Y mame MZ (s) = E (esZ ) = E (es(X +Y ) ) = E (esX esY ) =
= E (esX )E (esY ) = MX (s)MY (s). ˇ pro nezavisl´ ´ ´ Plat´ı obecne: y soubor nahodn´ ych veliˇcin X1 , . . . , Xn , Z = X1 + · · · + Xn =⇒ MZ (s) = MX1 (s) · · · MXn (s). Pˇr´ıklad ´ ´ Nechˇt X1 , . . . , Xn jsou nezavisl eˇ Bernoulliovy nahodn e´ veliˇciny s parametrem p. Pak MXi (s) = (1 − p)e0s + pe1s = 1 − p + pes , i = 1, . . . , n. ´ ´ ı s Nahodn a´ veliˇcina Z = X1 + · · · + Xn (n hodu˚ “faleˇsnou” minc´ı) je binomialn´ parametry n a p. Jej´ı generuj´ıc´ı funkce je MZ (s) = 1 − p + pes ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
n
. ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
7 / 19
Generuj´ıc´ı funkce
´ ´ ˇ Sumy nezavisl ych ´ nahodn ych ´ velicin
ˇ an´ ´ ı) Pˇr´ıklad (pokracov ´ ´ Nechˇt X a Y jsou nezavisl eˇ Poissonovy nahodn e´ veliˇciny s parametry λ a µ a nechˇt Z = X + Y . Pak s s s MZ (s) = MX (s)MY (s) = eλ(e −1) eµ(e −1) = e(λ+µ)(e −1) .
ˇ Poissonova nahodn ´ Z je opet a´ veliˇciny s parametrem λ + µ : k
(λ + µ) . P (Z = k ) = e−λ−µ k!
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
8 / 19
ˇ Limitn´ı vety
Ocˇ jde?
´ ´ ı velk´ych datov´ych souboru. V limitn´ıch teoremech jde o chovan´ ˚ ˇ ´ ´ Mejme posloupnost X1 , X2 , . . . nezavisl´ ych nahodn´ ych veliˇcin, kaˇzdou z nich s ˇ identick´ym pravdepodobnostn´ ım rozloˇzen´ım ( i.i.d. ) se stˇredn´ı hodnotou µ a 2 varianc´ı σ . Nechˇt Sn = X1 + · · · + Xn ´ o chovan´ ´ ı veliˇciny Sn (a veliˇcin s n´ı pˇr´ıbuzn´ych) je suma prvn´ıch n z nich. Jde nam ´ ´ pro velka´ n. D´ıky nezavislosti mame
var(Sn ) = var(X1 ) + · · · + var(Xn ) = nσ 2 . Rozptyl veliˇciny Sn roste a nemuˇ ˚ ze tedy m´ıt smysluplnou limitu. Jinak je to se stˇredn´ı hodnotou vzorku : Mn =
X1 + · · · + Xn n
=
Sn n
´ Mame E (Mn ) = µ,
a var(Mn ) =
. σ2
n ˇ b´yt rozloˇzena bl´ızko okolo µ. Variance Mn se zmenˇsuje s n, a veliˇcina Mn by mela ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
9 / 19
ˇ Limitn´ı vety
Ocˇ jde?
Veliˇcina mezi Sn a Mn : od Sn odeˇcteme nµ aby stˇredn´ı hodnota byla 0 a pak ˇ ıme σ del´
√
n aby rozptyl byl 1: Zn =
Sn − n µ
√ . σ n
´ ´ a´ kostantn´ı Pro tuto veliˇcinu mame E (Zn ) = 0 a var(Zn ) = 1: jej´ı rozloˇzen´ı zust ˚ av ˇ s n. Pravdepodobnostn´ ı rozloˇzen´ı Zn se ani nerozpl´yva´ ani nekolabuje s n: ´ ımu asymptoticke´ rozloˇzen´ı Zn je pro velke´ n bl´ızko k standardn´ımu normaln´ ´ ı limitn´ı veta ˇ . rozloˇzen´ı: to je centraln´
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
10 / 19
ˇ Limitn´ı vety
Markovova nerovnost
ˇ (Markovova nerovnost) Veta ´ ´ Je-li X nezaporn a´ nahodn a´ veliˇcina, pak P (X ≥ a) ≤
E (X ) a
pro kaˇzde´ a > 0.
Dukaz. ˚ ˇ ´ nerovnosti. Nechtˇ A = {X ≥ a}. Pak X ≥ aIA . Vezmeme stˇredn´ı hodnotu z teto Pˇr´ıklad ˇ eˇ rozloˇzene´ na intervalu [0, 4]. Pak Nechˇt X je stejnomern P (X ≥ 2) ≤
2 2
= 1, P (X ≥ 3) ≤
2 3
= 0.67, P (X ≥ 4) ≤
2 4
= 0.5.
Srovnejme s pˇresn´ymi hodnotami P (X ≥ 2) = 0.5, P (X ≥ 3) = 0.25, P (X ≥ 4) = 0. ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
11 / 19
ˇ Limitn´ı vety
ˇ ˇ Ceby sevova nerovnost
ˇ ˇ (Ceby ˇ Veta sevova nerovnost) ´ Pokud X je nahodn a´ veliˇcina se stˇredn´ı hodnotou µ a varianc´ı σ 2 , plat´ı P (|X − µ| ≥ c ) ≤
σ2 c2
pro kaˇzde´ c > 0.
Dukaz. ˚ Pouˇzijeme Markovovu nerovnost pro veliˇcinu (X − µ)2 s a = c 2 , P (|X − µ| ≥ c ) = P (|X − µ|2 ≥ c 2 ). ´ ame ´ Pro c = k σ dostav P (|X − µ| ≥ k σ) ≤
σ2 1 = 2. 2 2 k σ k
Pˇr´ıklad ˇ ym rozloˇzen´ım dostav ´ ame ´ Pro uvaˇzovan´y pˇr´ıklad se stejnomern´ ´ P (|X − 2| ≥ 1) ≤ 43 , coˇz je prazdn e´ tvrzen´ı vzhledem k tomu, zˇ e kaˇzda´ ˇ ´ pravdepodobnosti ˇ pravdepodobnost je nejv´ysˇ e 1. Skuteˇcna´ hodnota teto je 1/2. ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
12 / 19
ˇ Limitn´ı vety
ˇ ˇ Ceby sevova nerovnost
´ Poznamka ˇ ´ pˇr´ıpadeˇ nejlepˇs´ı moˇzna. ´ Cebyˇ sevova nerovnost je v obecnem Pro kaˇzde´ c existuje X pro ktere´ je to rovnost: Staˇc´ı vz´ıt X s rozloˇzen´ım P (X = +c ) = P (X = −c ) = 21 . Pak E (X ) = 0,
var(X ) = c 2 a tedy P (|X − µ| ≥ c ) = varc 2(X ) = 1.
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
13 / 19
ˇ Limitn´ı vety
´ ˇ ısel Slaby´ zakon velkych ´ c´
2
Xn Uvaˇzujme, Mn = X1 +···+ , E (Mn ) = µ, a var(Mn ) = σn . n σ2 ˇ Podle Cebyˇ sevovy nerovnosti, P (|Mn − µ| ≥ c ) ≤ nc zde´ c > 0. Tedy, 2 pro kaˇ
ˇ (Slaby´ zakon ´ ˇ ısel) Veta velkych ´ c´ ´ ˇ e´ nahodn ´ Nechtˇ X1 , X2 , . . . jsou nezavisl e´ identicky rozdelen e´ veliˇciny se stˇredn´ı hodnotou µ. Pro kaˇzde´ > 0 plat´ı P (|Mn − µ| ≥ ) = P |
X1 + · · · + Xn n
− µ| ≥ → 0 pˇri n → ∞.
´ ım pˇr´ıpadeˇ kdy Xi = IA s P (A) = p pro nejak´ ˇ y nahodn´ ´ Ve specialn´ y jev A, je Mn empiricka´ cˇ etnost jevu A. ´ ´ zˇ e emiricka´ cˇ etnost se bl´ızˇ ´ı stˇredn´ı hodnoteˇ Zakon velk´ych cˇ ´ısel pak ˇr´ıka, ˇ E (IA ) = P (A) = p: empiricka´ cˇ etnost je dobr´ym odhadem pravdepodobnosti p, ˇ ´ nebo naopak, pravdepodobnost p je cˇ etnost v´yskytu udalosti A.
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
14 / 19
ˇ Limitn´ı vety
ˇ Konvergence v pravdepodobnosti
´ ˇ Mame limn→∞ an = a: ∀ > 0∃n0 such that |an − a| ≤ for all n ≥ n0 . Podobne: Definice ´ ´ Nechtˇ X1 , X2 , . . . je posloupnost nahodn´ ych (ne nutneˇ nezavisl´ ych) veliˇcin a nechtˇ ˇ ´ e´ cˇ ´ıslo. Rekneme, zˇ e posloupnost Xn konverguje k a v pravdepodobnosti ˇ a je realn , jestliˇze lim P (|Xn − a| ≥ ) = 0
n→∞
pro kaˇzde´ > 0. ´ ˇ Slab´y zakon velk´ych cˇ ´ısel: stˇredn´ı hodnota Mn konverguje v pravdepodobnosti k a.
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
15 / 19
ˇ Limitn´ı vety
´ ı limitn´ı veta ˇ Centraln´
ˇ eˇ okolo µ, prost´y souˇcet Empiricka´ stˇredn´ı hodnota Mn je koncentrovana´ tesn Sn = nMn roste k nekoneˇcnu s rostouc´ı varianc´ı. S −n µ
Veliˇcina “mezi” Sn and Mn je Zn = σn √n
s E (Zn ) = 0 a var(Zn ) = 1.
ˇ (Centraln´ ´ ı limitn´ı veta) ˇ Veta ´ ´ Nechtˇ X1 , X2 , . . . je posloupnost nezavisl´ ych identicky rozloˇzen´ych nahodn´ ych 2 ˇ veliˇcin se spoleˇcnou stˇredn´ı hodnotou µ a varianc´ı σ a necht Zn =
X1 + · · · + Xn − n µ
√ σ n
.
Pak distribuˇcn´ı funkce veliˇciny Zn konverguje k distribuˇcn´ı funkci standardn´ıho ´ ıho rozloˇzen´ı Φ(z ) = √1 normaln´
2π
Rz
−∞ e
−x 2 /2 dx , v tom smyslu, zˇ e
lim P (Zn ≤ z ) = Φ(z ), pro kaˇzde´ z .
n→∞
s Idea dukazu: MZn (s) = (MX ( σ √ ))n , MX (s) ∼ 1 + 12 σ 2 s2 + o(s2 ) a ˚ n
(1 +
s2 n 2n
) ∼ es
2
/2 .
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
16 / 19
ˇ Limitn´ı vety
´ ı limitn´ı veta ˇ Centraln´
´ ı limitn´ı vety ˇ je v moˇznosti aproximovat sumu nahodn´ ´ V´yznam centraln´ ych veliˇcin: Algoritmus ´ ´ Nechtˇ Sn = X1 + · · · + Xn kde Xk jsou nezavisl e´ identicky rozloˇzene´ nahodn e´ ´ muˇ veliˇciny se spoleˇcnou stˇredn´ı hodnotou µ a varianc´ı σ 2 . Je-li n velke, ˚ zeme ˇ ´ pravdepodobnost P (Sn ≤ c ) aproximovat pomoc´ı nasleduj´ ıc´ıch kroku: ˚ ˇ stˇredn´ı hodnotu nµ a varianci nσ 2 nahodn ´ 1. Vypoˇctete e´ veliˇciny Sn . ˇ normalizovanou hodnotu z = (c − nµ)/σ 2. Vypoˇctete
√
n.
3. Pouˇzijte aproximaci P (Sn ≤ c ) ∼ Φ(z ), ´ ıho rozloˇzen´ı. kde Φ(z ) se z´ıska´ z tabulek standardn´ıho normaln´
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
17 / 19
ˇ Limitn´ı vety
´ ˇ ısel Silny´ zakon velkych ´ c´
´ Stˇredn´ı hodnota se s malou pravdepodobnost´ ˇ Intuice: hod´ıme si minc´ı 100 krat. ı ˇ postupneˇ zmizet jestliˇze v muˇ ˚ ze podstatneˇ liˇsit od 1/2, ale tato deviace by mela ´ hazen´ ı minc´ı budeme pokraˇcovat. ˇ Definice (Konvergence P-skoro jiste) ´ Nechtˇ Y , Y1 , Y2 , . . . je posloupnost nahodn´ ych veliˇcin na (Ω, F, P ). Posloupnost
(Yi )i ≥1 konverguje skoro jisteˇ k Y , pokud
P ω ∈ Ω : Yn (ω) → Y (ω) = 1. Lemma ˇ =⇒ “v pravdepodobnosti”. ˇ “skoro jiste” Dukaz. ˚ P (|Yn − Y | ≥ ) ≤ P (sup |Yk − Y | ≥ ) k ≥n
−→ P (|Yk − Y | ≥ pro ∞ mnoho k ) ≤ P (Yk 6→ Y )
n→∞ ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
18 / 19
ˇ Limitn´ı vety
´ ˇ ısel Silny´ zakon velkych ´ c´
Pˇr´ıklad Opaˇcna´ implikace neplat´ı: ˇ ym Uvaˇzujme posloupnost Yk na intervalul [0, 1] se stejnomern´ ˇ ˇ ım P, definovanou vztahem Yk = Im2−n ,(m+1)2−n pro pravdepodobnostn´ ım rozdelen´ kaˇzde´ k = 2n + m s 0 ≤ m < 2n . P
ˇ Pak Yk → 0, ale nekonverguje k 0 skoro jiste. ˇ (Silny´ zakon ´ ˇ ısel) Veta velkych ´ c´ ´ Nechtˇ (Xi )i ≥1 je posloupnost po dvou nekorelovan´ych nahodn´ ych veliˇcin s koneˇcn´ym druh´ym momentem a omezenou varianc´ı, v := supi var(Xi ) < ∞. Pak 1 n
n X
ˇ (Xi − E (Xi )) → 0 skoro jiste.
i =1
ˇ Roman Kotecky, ´ Rudolf Blaˇzek (FIT CVUT)
ˇ Limitn´ı vety
ˇ BI-PST, LS 2010/11, Pˇredna´ ska 8
19 / 19
