Univerzita Karlova v Praze Matematicko-fyzik´aln´ı fakulta
´ RSK ˇ ´ PRACE ´ BAKALA A
Jan Klik´aˇc Poissonovsk´ a aproximace Katedra pravdˇepodobnosti a matematick´e statistiky (32-KPMS)
Vedouc´ı bakal´aˇrsk´e pr´ace: Ing. Marek Omelka, Ph.D. Studijn´ı program: Matematika Studijn´ı obor: Finanˇcn´ı matematika
Praha 2011
Dˇekuji vedouc´ımu bakal´aˇrsk´e pr´ace panu Ing. Marku Omelkovi Ph.D. za pozornost, kterou vˇenoval m´e pr´aci a za jeho odborn´e rady pˇri vypracov´an´ı t´eto bakal´aˇrsk´e pr´ace.
Prohlaˇsuji, ˇze jsem tuto bakal´aˇrskou pr´aci vypracoval samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u, literatury a dalˇs´ıch odborn´ ych zdroj˚ u. Beru na vˇedom´ı, ˇze se na moji pr´aci vztahuj´ı pr´ava a povinnosti vypl´ yvaj´ıc´ı ze z´akona ˇc. 121/2000 Sb., autorsk´eho z´akona v platn´em znˇen´ı, zejm´ena skuteˇcnost, ˇze Univerzita Karlova v Praze m´a pr´avo na uzavˇren´ı licenˇcn´ı smlouvy o uˇzit´ı t´eto pr´ace jako ˇskoln´ıho d´ıla podle §60 odst. 1 autorsk´eho z´akona.
V ........ dne ............
Podpis autora
N´azev pr´ace: Poissonovsk´a aproximace Autor: Jan Klik´aˇc Katedra: Katedra pravdˇepodobnosti a matematick´e statistiky (32-KPMS) Vedouc´ı bakal´aˇrsk´e pr´ace: Ing. Marek Omelka, Ph.D. Abstrakt: Tato bakal´aˇrsk´a pr´ace se zab´ yv´a poˇc´ıt´an´ım pravdˇepodobnost´ı pˇri vyuˇzit´ı Poissonova rozdˇelen´ı. Pr´ace m´a za u ´kol uk´azat nov´e moˇznosti aproximace Poissonov´ ym rozdˇelen´ım a je rozdˇelena do tˇr´ı kapitol. V prvn´ı kapitole jsou shrnuty poznatky t´ ykaj´ıc´ı se Poissonova rozdˇelen´ı, jeho definice a vlastnosti. Je zde pˇredveden limitn´ı pˇrechod od binomick´eho rozdˇelen´ı k rozdˇelen´ı Poissonovu a pˇr´ıklady demonstruj´ıc´ı pouˇz´ıt´ı tohoto limitn´ıho pˇrechodu. Ve druh´e kapitole je zavedena Brunova vˇeta, kter´a rozˇsiˇruje moˇznosti pˇrechodu k Poissonovu rozdˇelen´ı. N´ahodn´e veliˇciny, jeˇz chceme aproximovat, jiˇz nemus´ı m´ıt binomick´e rozdˇelen´ı, m´ısto toho je pˇredpokl´ad´an vztah pro jejich stˇredn´ı hodnotu. Druh´a ˇc´ast kapitoly zahrnuje praktickou uk´azku pouˇzit´ı Brunovi vˇety. Tˇret´ı kapitola se zab´ yv´a odhadem velikosti chyby, kter´e se dopust´ıme aproximac´ı Poissonov´ ym rozdˇelen´ım. Je zde formulov´ana Stein-Chenova vˇeta pro odhad velikosti chyby Poissonovsk´e aproximace i jej´ı speci´aln´ı pˇr´ıpad.
Kl´ıˇcov´a slova: Poissonovo rozdˇelen´ı, Brunova vˇeta, Stein-Chenova vˇeta
Title: Poisson Approximations Author: Jan Klik´aˇc Department: Department of Probability and Mathematical Statistics, MFF UK Supervisor: Ing. Marek Omelka, Ph.D. Abstract: This bachelor thesis deals with the counting probability using Poisson distribution. The work aims to show new ways of approximating Poisson distribution. The work is divided into three chapters. The first chapter summarizes the findings regarding the Poisson distribution, its definition and properties. It also show a limit transition from the binomial distribution to Poisson distibution and examples demonstrating the usage of this limit transition. Brun Sieve is introduced in the second chapter. It gives a new possibility of transiting to a Poisson distribution. Random variables, which we want to approximate, no longer need to have binomial distribution. Instead the property of expected value is required. The second part of the chapter includes a practical demonstration of the usage of Brun Sieve. In the third chapter we estimate size of the error that we made when approximating to Poisson distribution. There is also formulated Stein-Chen theorem for estimating the error of Poisson approximation and its version for a special case.
Keywords: Poisson distribution, Brun Sieve, Stein-Chen theorem
Obsah ´ Uvod
2
1 Poissonovo rozdˇ elen´ı 1.1 Poissonovo rozdˇelen´ı . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Pˇr´ıklady . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Paradox d´av´an´ı d´ark˚ u . . . . . . . . . . . . . . . . . . . . . . . .
3 3 4 7
2 Brunovo s´ıto 2.1 Brunovo s´ıto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Pouˇzit´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10 10 13
3 Stein-Chenova metoda 19 3.1 Stein-Chenova metoda pro odhad velikosti chyby Poissonovsk´e aproximace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Stein-Chenova metoda za specifick´e podm´ınky . . . . . . . . . . . 27 3.3 Pouˇzit´ı . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 Z´ avˇ er
31
Seznam pouˇ zit´ e literatury
32
Pˇ r´ılohy
33
1
´ Uvod Znalost pojm˚ u jako distribuˇcn´ı funkce, hustota, diskr´etn´ı n´ahodn´a veliˇcina patˇr´ı k z´akladn´ım znalostem o pravdˇepodobnosti, stejnˇe tak znalost z´akladn´ıch rozdˇelen´ı n´ahodn´ ych veliˇcin. Vˇenujeme-li nav´ıc trochu ˇcasu pochopen´ı vztah˚ u mezi rozdˇelen´ımi, zjist´ıme, ˇze z velk´eho poˇctu alternativn´ıch rozdˇelen´ı poskl´ad´ame binomick´e rozdˇelen´ı nebo ˇze od binomick´eho rozdˇelen´ı lze limitn´ım pˇrechodem pˇrej´ıt k rozdˇelen´ı Poissonovu. C´ılem t´eto pr´ace je uk´azat, ˇze se k Poissonovu rozdˇelen´ı d´a dostat v´ıce zp˚ usoby a zjednoduˇsit tak poˇc´ıt´an´ı obt´ıˇznˇejˇs´ıch probl´em˚ u, byt’ za cenu chyby, kter´a pˇrechodem vznik´a. V prvn´ı kapitole bude pˇripomenuta definice Poissonova rozdˇelen´ı a jeho vlastnosti a bude shrnut zn´am´ y pˇrechod od binomick´eho rozdˇelen´ı k rozdˇelen´ı Poissonovu. V praxi pak bude aproximace uk´az´ana na nˇekolika jednoduch´ ych pˇr´ıkladech. ˇ Sirˇs´ı vyuˇzit´ı bude d´ale pˇredvedeno na nˇekolika r˚ uzn´ ych zp˚ usobech pˇridˇelov´an´ı dan´eho mnoˇzstv´ı objekt˚ u dan´emu poˇctu osob. Zbytek pr´ace jiˇz bude zamˇeˇren na prozkoum´an´ı dalˇs´ıch moˇznost´ı jak vyuˇz´ıt jednoduchosti vyˇc´ıslen´ı pravdˇepodobnosti pomoc´ı Poissonova rozdˇelen´ı. Ve druh´e kapitole bude pˇredstavena Brunovu vˇeta, kter´a n´am d´a dalˇs´ı postaˇcuj´ıc´ı podm´ınku pro pouˇzit´ı Poissonovsk´e aproximace. Z´ıskan´e poznatky budou n´aslednˇe prakticky pˇredstaveny pˇri ˇreˇsen´ı narozeninov´eho probl´emu, neboli hled´an´ı pravdˇepodobnosti, s jakou se ve skupinˇe lid´ı najde dvojice, trojice, ˇctveˇrice, atd. osob se stejn´ ym datem narozen´ı. V posledn´ı ˇca´sti pr´ace se budeme zab´ yvat zkoum´an´ım velikosti chyby, kter´e se dopust´ıme, pˇrejdeme-li k Poissonovu rozdˇelen´ı. C´ılem t´eto kapitoly bude dok´az´an´ı faktu, ˇze velikost chyby lze omezit s vyuˇzit´ım Stein-Chenovi vˇety. Ta bude podrobena zkoum´an´ı v teoretick´e ˇc´asti tˇret´ı kapitoly. V praktick´e ˇc´asti bude opˇet pˇredvedeno nˇekolik v´ ypoˇct˚ u, kter´e ˇcten´aˇri pˇribl´ıˇz´ı, jak Stein-Chenovu vˇetu spr´avnˇe vyuˇz´ıt. Vˇsechny v´ ypoˇcty uveden´e v bakal´aˇrsk´e pr´aci byly prov´adˇeny v syst´emu Mathematica 8.0 a jsou zaˇclenˇeny v ˇc´asti Pˇr´ılohy.
2
Kapitola 1 Poissonovo rozdˇ elen´ı ˇ ym probl´emem v pravdˇepodobnosti je modelov´an´ı poˇctu ud´alost´ı, kter´e Cast´ nastanou na spojit´em u ´seku. T´ımto m´ame na mysli nepˇreruˇsen´ y ˇcasov´ y, d´elkov´ y, ’ objemov´ y,... interval, vzhledem k nˇemuˇz poˇcty ud´alost´ı zjiˇst ujeme. Napˇr´ıklad spoleˇcnost zˇrizuj´ıc´ı telefonn´ı u ´stˇrednu pro podporu z´akazn´ık˚ u potˇrebuje vˇedˇet, jak´ y m´a oˇcek´avat objem pˇr´ıchoz´ıch hovor˚ u. Podle toho m˚ uˇze pˇrizp˚ usobit poˇcet telefonn´ıch linek tak, aby vyhovˇela volaj´ıc´ım z´akazn´ık˚ um a z´aroveˇ n zbyteˇcnˇe nevykl´adala n´aklady nav´ıc. Podobnˇe n´as m˚ uˇze zaj´ımat kolik kaz˚ u se objev´ı na 10 metrech l´atky, na kolik z´akazn´ık˚ u se pˇripravit v jednom pracovn´ım dni, jak velkou nehodovost pˇredpokl´adat na frekventovan´e kˇriˇzovatce za 24 hodin, ˇ jak´ y je v´ yskyt bakteri´ı v jednotce objemu vzduchu. Casto uˇz´ıvan´ ym modelem pro ˇreˇsen´ı tˇechto ot´azek, popsan´ ym tak´e v Larson, 1982 [4], se budeme zab´ yvat v t´eto kapitole.
1.1
Poissonovo rozdˇ elen´ı
Definice Poissonova rozdˇ elen´ı. ˇ Rekneme, ˇze n´ahodn´a veliˇcina X m´ a Poissonovo rozdˇelen´ı s parametrem λ > 0, jestliˇze pro vˇsechny hodnoty k = 0, 1, 2, . . . plat´ı PX (k) = P (X = k) =
λk −λ e , k!
k = 0, 1, 2, . . .
Vlastnosti Poissonova rozdˇ elen´ı. Stˇredn´ı hodnota Poissonova rozdˇelen´ı je E[X] = λ. Rozptyl Poissonova rozdˇelen´ı je V ar(X) = λ. Koeficient ˇsikmosti Poissonova rozdˇelenn´ı je γ1 = √1λ . Koeficient ˇspiˇcatosti Poissonova rozdˇelenn´ı je γ2 = λ1 . Vlastnosti Poissonova rozdˇelen´ı jsou jednoduˇse dokazateln´e z obecn´ ych vzorc˚ u a definic E[X − E(X)]3 E[X − E(X)]4 γ1 = , γ = − 3, 2 V ar(X)3/2 V ar(X)2 zde jsou uvedeny pouze pro u ´plnost. 3
K Poissonovu rozdˇelen´ı lze dospˇet jako k limitn´ımu pˇr´ıpadu binomick´eho rozdˇelen´ı, za platnosti n´asleduj´ıc´ıho: n → ∞,
pn → 0,
npn → λ,
kde n znaˇc´ı poˇcet pokus˚ u a pn znaˇc´ı pravdˇepodobnost u ´spˇechu jednotliv´ ych pokus˚ u.
Vezmeme Xn n´ahodnou veliˇcinu s binomick´ ym rozdˇelen´ım Bi(n, pn ) s rozdˇelen´ım pravdˇepodobnosti n k PXn (k) = pn (1 − pn )n−k . k Rovnost uprav´ıme n´asledovnˇe (uvaˇzujeme npn = λ): k n−k n λ λ PXn (k) = 1− k n n −k n λk n! λ λ = 1− 1− k!(n − k)! nk n n n −k n(n − 1) . . . (n − k + 1) λk λ λ = 1− 1− . k! n n nk V limitˇe n → ∞ pro k pevn´e m´ame
λ 1− n
n
→e
−λ
,
λ 1− n
−k → 1,
n(n − 1) . . . (n − k + 1) 1 2 k+1 =1· 1− 1− ... 1 − → 1. nk n n n Odtud jiˇz dost´av´ame PXn (k) →
1.2
λk −λ e , k!
k = 0, 1, 2, ...
Pˇ r´ıklady
Poissonovo rozdˇelen´ı m˚ uˇzeme pouˇz´ıvat pokud plat´ı n´asleduj´ıc´ı dva body. 1. Kaˇzd´a dalˇs´ı ud´alost nast´av´a v dan´em intervalu (ˇcase nebo prostoru) nez´avisle na pˇredchoz´ıch ud´alostech 2. Pr˚ umˇern´ y poˇcet ud´alost´ı nast´av´aj´ıc´ıch v dan´em intervalu je zn´am 4
V n´asleduj´ıc´ıch dvou pˇr´ıkladech demonstrujeme poˇc´ıt´an´ı s Poissonov´ ym rozdˇelen´ım ˇ (Pˇr´ıklady pˇrevzaty ze Zv´ara, Stˇep´ an, 2002 [8]).
Pˇr´ıklad 1. Klasick´ ym pˇr´ıkladem, jeˇz se v´aˇze k Poissonovu rozdˇelen´ı, jsou data z roku 1898 zachycuj´ıc´ı poˇcet u ´mrt´ı prusk´ ych voj´ak˚ u v d˚ usledku kopnut´ı konˇe. V pr˚ ubˇehu 20 let bylo sledov´ano 10 j´ızdn´ıch jednotek vojska, coˇz m˚ uˇzeme br´at, vezmeme-li vu ´vahu, ˇze se od sebe jednotky neliˇsily, jako 200 pozorov´an´ı jedn´e j´ızdn´ı jednotky v jednom roce. Celkem 122 koˇ nsk´ ych kopnut´ı bylo za celou dobu smrteln´ ych, pr˚ umˇern´ y poˇcet u ´mrt´ı v j´ızdn´ı jednotce za rok je tedy 122/200 = 0, 61. Toto lze povaˇzovat za situaci, ve kter´e jde pouˇz´ıt Poissonovo rozdˇelen´ı: n´ahodn´e ud´alosti s malou pravdˇepodobnost´ı v´ yskytu v pr˚ ubˇehu ˇcasov´eho intervalu. Hodnotu 0, 61 pouˇzijeme jako odhad parametru λ. Ptejme se, jak´a je pravdˇepodobnost, ˇze v dan´em roce nedoˇslo k u ´mrt´ı. Pouˇzijeme formuly pro Poissonovo rozdˇelen´ı se stˇredn´ı hodnotou 0, 61 a dost´av´ame PX (0) =
0, 610 −0,61 e = 0, 5434. 0!
Ve 200 pozorov´an´ıch by se tedy mˇelo objevit 200∗0, 5434 = 108, 68 let, ve kter´ ych ’ ke smrti nedoˇslo. Tento odhad je pˇresn´ y, nebot v prusk´ ych datech je zaznamen´ano 109 let bez u ´mrt´ı. Provedeme i dalˇs´ı odhady a porovn´ame s napozorovan´ ymi daty. Vˇse je shrnuto v n´asleduj´ıc´ı tabulce: ´ Umrt´ ı pravdˇepodobnost odhad skuteˇcnost 0 0,54335 108,68 109 1 0,33145 66,29 65 2 0,10110 20,22 22 ≥3 0,02411 4,82 4 Z tabulky jde vidˇet, ˇze se poˇcty vypoˇc´ıtan´e Poissonov´ ym rozdˇelen´ım ve vˇsech pˇr´ıpadech bl´ıˇz´ı pozorovan´ ym dat˚ um. Pro ovˇeˇren´ı spr´avnosti zvolen´eho modelu pouˇzijeme Ch´ı-kvadr´at test dobr´e shody (Pˇr´ıloha 1). Jako nulovou hypot´ezu pokl´ad´ame spr´avnost modelu, hladina v´ yznamnosti je 5%. Testov´a statistika vych´az´ı (109 − 108, 68)2 (65 − 66, 29)2 (22 − 20, 22)2 (4 − 4, 82)2 + + + = 0, 32 108, 68 66, 29 20, 22 4, 82 Stupeˇ n volnosti bereme poˇcet kategori´ı minus 1, kritick´a hodnota Ch´ı-kvadr´at rozdˇelen´ı se tˇremi stupni volnosti X32 (0, 05) = 7, 81. Stupnˇe volnosti 3 Testov´a statistika 0,32 X32 (0, 05) 7,81 Vid´ıme, ˇze testov´a statistika nen´ı vˇetˇs´ı neˇz kritick´a hodnota testu, tedy nezam´ıt´ame nulovou hypot´ezu.
5
Pˇr´ıklad 2. ´ V pr˚ ubˇehu druh´e svˇetov´e v´alky doch´azelo k bombardov´an´ı velk´ ych mˇest. Uzem´ ı Lond´ yna bylo k jist´emu datu zasaˇzeno 537 raketami a odborn´ıci se snaˇzili zjistit, zda ˇslo o c´ılen´e u ´toky na konkr´etn´ı ˇc´asti mˇesta, nebo doch´azelo k n´ahodn´emu dopadu stˇrel. Pˇrevl´adaj´ıc´ı n´azor o n´ahodnosti z´asah˚ u se pokusili potvrdit statistici takto: Plocha mˇesta byla rozdˇelena na ˇctverce, u kter´ ych se zkoumal v´ yskyt z´asah˚ u ˇ raketami. Ctverc˚ u bylo n = 576 a poˇcet ˇctverc˚ u s ˇz´adn´ ym, jedn´ım, ..., pˇeti z´asahy byl zaznamen´an. Pokud jsou z´asahy n´ahodn´e, mˇely by re´aln´e poˇcty pˇribliˇznˇe souhlasit s oˇcek´avan´ ymi poˇcty v sestrojen´em modelu. Vezmeme-li pevnˇe ale libovolnˇe jeden ze ˇctverc˚ u, oznaˇcme jej i, pak Xi , n´ahodn´a veliˇcina oznaˇcuj´ıc´ı poˇcet z´asah˚ u ˇctverce i, m´a binomick´e rozdˇelen´ı s poˇctem opakov´an´ı n = 537 a pravdˇepodobnost´ı u ´spˇechu p = 1/576. Souˇcin np = λ z˚ ust´av´a konstantn´ı a d´ıky velk´emu poˇctu opakov´an´ı m˚ uˇzeme pˇrej´ıt k Poissonovu rozdˇelen´ı. Tedy −λ k λ . e P (Xi = k) = , 1 ≤ i ≤ 576, k! .
kde λ = 537/576 = 0, 9383 je odhad parametru Poissonova rozdˇelen´ı. V´ ysledn´e pravdˇepodobnosti pˇren´asoben´e poˇctem ˇctverc˚ u udavaj´ı oˇcek´avan´ y poˇcet ˇctverc˚ u s jedn´ım, dvˇema, pˇr´ıpadnˇe v´ıce z´asahy. Skuteˇcn´e i oˇcek´avan´e poˇcty jsou shrnuty v n´asleduj´ıc´ı tabulce: k 0 1 2 3 ≥4 skuteˇcn´ y poˇcet 229 211 93 35 8 oˇcek´avan´ y poˇcet 226,7 211,4 98,5 30,6 8,7 kde k je poˇcet z´asah˚ u. Provedeme Ch´ı-kvadr´at test dobr´e shody (Pˇr´ıloha 2). Jako nulovou hypot´ezu bereme, ˇze napozorovan´a data poch´az´ı z Poissonova rozdˇelen´ı, hladina v´ yznamnosti je 5%. Testov´a statistika vych´az´ı (229 − 226, 7)2 (211 − 211, 4)2 (93 − 98, 5)2 (35 − 30, 6)2 (8 − 8, 7)2 + + + + =1 226, 7 211, 4 98, 5 30, 6 8, 7 Stupeˇ n volnosti bereme poˇcet kategori´ı minus 1, kritick´a hodnota Ch´ı-kvadr´at rozdˇelen´ı se ˇctyˇrmi stupni volnosti X42 (0, 05) = 9, 5. Stupnˇe volnosti 4 Testov´a statistika 1 X42 (0, 05) 9,5 Vid´ıme, ˇze testov´a statistika nen´ı vˇetˇs´ı neˇz kritick´a hodnota testu, tedy nezam´ıt´ame nulovou hypot´ezu.
6
1.3
Paradox d´ av´ an´ı d´ ark˚ u
Spoleˇcnost ALFA se rozhodla uspoˇr´adat pro sv´e zamˇestnance v´anoˇcn´ı veˇc´ırek. J´ıdlo a pit´ı bylo zajiˇstˇeno, ale d´arky si museli zamˇestnanci nakoupit sami. Bylo navrˇzeno, ˇze kaˇzd´ y koup´ı jeden d´arek, kter´ y se v pr˚ ubˇehu veˇcera um´ıst´ı pod stromeˇcek a o p˚ ulnoci bude kaˇzd´emu z´ uˇcastnˇen´emu jeden d´arek z hromady pˇred´an. ’ Vˇsichni souhlasili, nebot pˇredpokl´adali, ˇze je pˇri velk´em mnoˇzstv´ı lid´ı velmi mal´a ˇsance, aby si nˇekdo vylosoval sv˚ uj vlastn´ı d´arek. O p˚ ulnoci se d´arky rozdaly a k velk´emu pˇrekvapen´ı vˇsech z´ uˇcastnˇen´ ych si nejeden zamˇestnanec musel sv˚ uj d´arek vymˇenit, nebot’ mu byl pˇridˇelen jeho vlastn´ı. Tento pˇr´ıklad ukazuje, ˇze i kdyˇz je pravdˇepodobnost dost´an´ı vlastn´ıho d´arku 1 (za pˇredpokladu n osob) a ta konverguje pro velk´e n k 0, pravdˇepodobnost, ˇze n ve skupinˇe lid´ı dostane alespoˇ n jeden z nich sv˚ uj vlastn´ı d´arek, je mnohem vˇetˇs´ı. (Tento a mnoho dalˇs´ıch paradox˚ u v matematice m˚ uˇzeme nal´ezt v Sz´ekely, 1986 [6]) Vezmeme skupinu n lid´ı, kde kaˇzd´ y donesl jeden d´arek. Pak existuje n! moˇznost´ı jak d´arky pˇrerozdˇelit, aby kaˇzd´ y dostal jeden d´arek zpˇet. Poˇcet moˇznost´ı M , kdy nikdo nedostane d´arek, kter´ y pˇrinesl, vych´az´ı z principu inkluze a exkluze. Vezmeme Ai jako jev, ˇze i-t´ y ˇclovˇek dostane vlastn´ı d´arek. Potom M = n! − |A1 ∪ A2 ∪ . . . ∪ An | n n n M = n! − (n − 1)! − (n − 2)! + . . . + (−1) 0! , 1 2
(1.1)
kde | | m´a v´ yznam: |A| je poˇcet prvk˚ u mnoˇziny A. V´ıme, ˇze pravdˇepodobnost p0,n s jakou nikdo z n osob nedostane sv˚ uj d´arek z´ısk´ame jako pod´ıl pˇr´ızniv´ ych moˇznost´ı ku vˇsem moˇznostem, tedy pod´ıl v´ yrazu (1.1) a n!. Vyjde n´am n! − n1 (n − 1)! − n2 (n − 2)! + . . . + (−1)n 0! p0,n = n! i h n! n! (n − 2)! + . . . + (−1)n 0! n! − 1!(n−1)! (n − 1)! − 2!(n−2)! = n! (1.2) 1 1 = 1 − 1 − + . . . + (−1)n 2! n! 1 1 1 = − + . . . + (−1)n . 2! 3! n! Pro n > 2 uˇz je p0,n menˇs´ı neˇz 21 . Nav´ıc vezmeme-li n → ∞, pravdˇepodobnost p0,n konverguje z Taylorova rozvoje k hodnotˇe e−1 . (Dostateˇcn´e pˇresnosti je vˇsak dosaˇzeno uˇz u n´ızk´ ych hodnot n, napˇr. pro n = 6 se p0,n shoduje s e−1 s pˇresnost´ı na 4 desetinn´a m´ısta). Tedy pravdˇepodobnost, ˇze alespoˇ n jeden ˇclovˇek dostane d´arek, kter´ y s´am pˇrinesl je vˇetˇs´ı neˇz 50%. Nyn´ı n´aˇs probl´em zobecn´ıme. Ptejme se jak´a je pravdˇepodobnost pk,n toho, ˇze pˇresnˇe k lid´ı z n pˇr´ıtomn´ ych dostane sv˚ uj vlastn´ı d´arek. Vˇsech moˇznost´ı jak d´arky rozdˇelit je st´ale n!. Poˇcet pˇr´ızniv´ ych moˇznost´ı je vˇsak na rozd´ıl od poˇctu moˇznost´ı M , kdy nikdo nedostane sv˚ uj d´arek, vyj´adˇren jako souˇcin poˇctu moˇznost´ı jak vybrat k jedinc˚ u z n osob (kteˇr´ı dostanou sv´e d´arky) a poˇctu moˇznost´ı, kdy ˇz´adn´ y 7
z (n − k) jedinc˚ u nedostane sv˚ uj d´arek z (n − k) zbyl´ ych. Zde opˇet uplatn´ıme princip inkluze a exkluze. Potom h ih n−k i n n−k n (n − k)! − (n − k − 1)! − (n − k − 2)! + . . . + (−1) 0! k 1 2 pk,n = n! n−k n−k (n − k − 1)! − (n − k − 2)! + . . . + (−1)n 0! 1 (n − k)! − 1 2 = . k! (n − k)! (1.3) Stejnˇe jako v (1.2) jde druh´ y zlomek z (1.3) k e−1 pro n → ∞. Tedy pk,n m˚ uˇzeme e−1 aproximovat hodnotou k! . Zvol´ıme-li d´ale parametr λ jako pomˇer d´ark˚ u na osobu, snadno nahl´edneme, ˇze n´ahodn´a veliˇcina urˇcuj´ıc´ı poˇcet osob, kter´e dostanou sv˚ uj vlastn´ı d´arek, m´a aproximativnˇe Poissonovo rozdˇelen´ı s parametrem λ = 1.
Pod´ıvejme se na dalˇs´ı probl´em t´ ykaj´ıc´ı se paradoxu d´av´an´ı d´ark˚ u. Na stejn´e ulici jako spoleˇcnost ALFA m´a sv´e s´ıdlo i spoleˇcnost BETA. Jej´ı veden´ı nechtˇelo z˚ ustat pozadu za konkurenc´ı, a proto i zde prob´ıhal v´anoˇcn´ı veˇc´ırek. BETA nav´ıc pˇri pˇr´ıprav´ach akce ozn´amila, ˇze se postar´a o poˇr´ızen´ı d´ark˚ u pod stromeˇcek, kter´e budou formou tomboly rozd´any n´ahodnˇe vylosovan´ ym jedinc˚ um. Bylo rozhodnuto, ˇze d´ark˚ u bude tolik, kolik lid´ı se zap´ıˇse na veˇc´ırek a pˇri tombole se pro kaˇzd´ y d´arek vylosuje jedno jm´eno, kter´e se pot´e vr´at´ı do osud´ı. D´arky ale byly nakonec objedn´any aˇz na posledn´ı chv´ıli, coˇz se neobeˇslo bez nˇekolika nedorozumˇen´ı v komunikaci. To se pak projevilo pod samotn´ ym stromeˇckem, nebot’ poˇcet d´ark˚ u neodpov´ıdal pˇredstav´am veden´ı. Za t´eto situace si jeden z hloubavˇejˇs´ıch zamˇestnanc˚ u poloˇzil ot´azku, jakou m´a ˇsanci dostat 4 d´arky, kter´e by pak mohl doma rozdˇelit mezi dˇeti. 0 Z matematick´eho hlediska n´as vlastnˇe zaj´ım´a, jak´a je pravdˇepodobnost pk pˇred´an´ı pˇresnˇe k d´ark˚ u dan´emu jedinci, pˇredpokl´ad´ame-li nez´avislost pˇridˇelov´an´ı. Nav´ıc v´ıme, ˇze spoleˇcnosti doˇslo r d´ark˚ u a zamˇestn´av´a pr´avˇe n osob, pˇriˇcemˇz poˇcet d´ark˚ u a osob nen´ı nutnˇe stejn´ y. Cekov´ y poˇcet moˇznost´ı jak d´arky rozdˇelit je nr . Pˇr´ızniv´ ych moˇznost´ı je pr´avˇe tolik, jako souˇcin poˇctu zp˚ usob˚ u, jak vybrat k d´ark˚ u z r moˇzn´ ych, a poˇctu zp˚ usob˚ u, jak rozdˇelit zbyl´ ych (r − k) dar˚ u mezi (n − 1) osob. Dost´av´ame se ke vzorci: r (n − 1)r−k r!(n − 1)r (n − 1)−k 0 k pk = = = nr k!nr (r − k)! r 1 n − 1 r(r − 1) . . . (r − k + 1) = . k! n (n − 1)k Toto je hledan´a pravdˇepodobnost. Zaj´ımav´e je tak´e jej´ı asymptotick´e chov´an´ı v pˇr´ıpadˇe, ˇze s rostouc´ım poˇctem osob n roste i poˇcet d´ark˚ u rn tak, ˇze rn = λ. n→∞ n lim
8
Potom pro n → ∞ rn rn n−1 −λ ’ → e nebot plat´ ı - n−1 = 1− n n -
rn (rn −1)...(rn −k+1) (n−1)k
rn n rn
rn
→ λk
Odtud jiˇz λk −λ e k! a tedy n´ahodn´a veliˇcina zachycuj´ıc´ı poˇcet d´ark˚ u, kter´e dostane jeden jedinec, za pˇredpokladu zachov´an´ı pomˇeru mezi poˇctem osob a d´ark˚ u, m´a asymptoticky Poissonovo rozdˇelen´ı. 0 Pr´avˇe vyˇreˇsen´ y pˇr´ıklad s pravdˇepodobnost´ı pk je tak´e zn´am jako MaxwellBoltzmann˚ uv model. 0
pk →
9
Kapitola 2 Brunovo s´ıto V t´eto kapitole n´as bude zaj´ımat, v jak´em pˇr´ıpadˇe lze pˇrej´ıt k Poissonovu rozdˇelen´ı. Odpovˇed’ n´am poskytne metoda naz´ yvan´a Brunovo s´ıto, d´ıky n´ıˇz dostaneme vhodnou podm´ınku pro pouˇzit´ı aproximace (O Brunovu s´ıtu se m˚ uˇzeme doˇc´ıst tak´e v Alon, Spencer, 1992 [1]). D´ale se v kapitole pod´ıv´ame na nˇekolik praktick´ ych pˇr´ıklad˚ u, kter´e n´am pˇredstavenou metodu v´ıce pˇribl´ıˇz´ı a uk´aˇz´ı jej´ı vyuˇzitelnost. Tato i n´asleduj´ıc´ı kapitola vych´az´ı z Ross, 1996 [5].
2.1
Brunovo s´ıto
Mˇejme n´ahodn´e veliˇciny X1 , . . . , Xn s alternativn´ım rozdˇelen´ım, pro kter´e plat´ı: P (Xi = 1) = λi , P (Xi = 0) = 1 − λi , Oznaˇcme
n X
∼
X=
i = 1, . . . , n.
Xi .
i=1
Pokud jsou n´ahodn´e veliˇciny X1 , . . . , Xn nez´avisl´e a pravdˇepodobnosti λi jsou ∼
pˇribliˇznˇe stejnˇe velk´e (λ1 ≈ λ2 ≈ . . . ≈ λn )1 , m´a X aproximativnˇe binomick´e rozdˇelen´ı s parametry n, λi . Pokud je d´ale n dostateˇcnˇe velk´e a λi dostateˇcnˇe mal´e, ∼ Pn m˚ uˇzeme X aproximovat Poissonov´ ym rozdˇelen´ım s parametrem λ = i=1 λi a tedy plat´ı ∼ e−λ λk P (X = k) ≈ , k = 0, 1, 2, . . . k! Tento pˇrechod od velk´eho poˇctu n´ahodn´ ych veliˇcin s alternativn´ım rozdˇelen´ım k n´ahodn´e veliˇcinˇe s Poissonov´ ym rozdˇelen´ım za u ´ˇcelem zjednoduˇsen´ı v´ ypoˇctu je dobˇre zn´am a ˇcasto pouˇz´ıv´an. K u ´spˇeˇsn´emu uˇzit´ı uveden´e aproximace vˇsak nepotˇrebujeme zn´at informace o veliˇcin´ach X1 , . . . , Xn , jak bude d´ale pˇredvedeno. V t´eto kapitole si uk´aˇzeme jin´ y zp˚ usob, jak pˇrej´ıt k Poissonovu rozdˇelen´ı. Potˇrebnou podm´ınku n´am d´av´a Brunova vˇeta. 1
Symbol ≈ znaˇc´ı pˇribliˇznou rovnost veliˇcin
10
Brunova vˇ eta. Necht’ W je nez´aporn´a celoˇc´ıseln´ a n´ahodn´a veliˇcina. Pokud pro kaˇzd´e i ∈ N ∪ {0} plat´ı W λi E ≈ , (2.1) i i! potom pro libovolnˇe zvolen´e j P (W = j) ≈
e−λ λj , j!
j = 0, 1, 2, . . . .
(2.2)
D˚ ukaz. : Pro u ´ˇcely d˚ ukazu pˇredeˇsl´e vˇety si zavedeme n´ahodnou veliˇcinu Ij , kde j ∈ N ∪ {0} je libovoln´e pevn´e, definovanou takto 1 pokud W = j Ij = 0 jinak. Zˇrejmˇe plat´ı P (W = j) = EIj .
(2.3)
Ted’ uˇz jen staˇc´ı upravit pravou stranu rovnosti (2.3) tak, aby byla splnˇena pˇribliˇzn´a rovnost (2.2). Vyj´adˇr´ıme si n´ahodnou veliˇcinu Ij jin´ ym zp˚ usobem za pouˇzit´ı kombinaˇcn´ıho ˇc´ısla, pˇriˇcemˇz v pˇr´ıpadech W < 0 nebo j > W budeme W br´at rovno 0. j Ij =
W (1 − 1)W −j . j
(2.4)
Toto zaveden´ı je korektn´ı, nebot’ pro W = j je v´ yraz na prav´e stranˇe roven 0 1 · 0 = 1 a v ostatn´ıch pˇr´ıpadech je kombinaˇcn´ı ˇc´ıslo pˇren´asobeno nulou. D´ale pouˇzijeme binomickou vˇetu na v´ yraz (1 − 1)W −j a pokraˇcujeme v u ´pravˇe (2.4).
W −j W X W − j W −j−k Ij = 1 (−1)k j k=0 k ∞ X W W −j 1 = (−1)k j k k=0 ∞ X W j+k 2 = (−1)k . j + k k k=0
(2.5)
’ Rovnost 1 plat´ı, nebot v pˇr´ıpadˇe, kdy k > W − j, pokl´ad´ame kombinaˇcn´ı ˇc´ıslo W −j rovno 0. k Rovnost 2 dostaneme, pokud si rozep´ıˇseme kombinaˇcn´ı ˇc´ısla pomoc´ı faktori´al˚ u a vhodnˇe uprav´ıme, jak ukazuj´ı n´asleduj´ıc´ı rovnosti. 11
W j
W −j k
W! (W − j)! · (W − j)!j! (W − j − k)!k! W! 1 · = (W − j − k)! j!k! W! (j + k)! = · (W − j − k)!(j + k)! j!k! W j+k = . j+k k =
Vyj´adˇren´e Ij (2.5) dosad´ıme do (2.3) a poˇc´ıt´ame. P (W = j) = EIj
! ∞ X W j+k =E (−1)k j+k k k=0 ∞ X W j+k E (−1)k = j + k k k=0 ∞ X j+k λj+k (−1)k pˇredpoklad Brunovy vˇety ≈ (j + k)! k k=0 ∞ X λj+k (j + k)! = (−1)k (j + k)! j!k! k=0
=
∞ λj X (−λ)k j! k=0 k!
=
e−λ λj . j!
T´ımto jsme dok´azali Brunovu vˇetu pro zvolen´e j. To ale vol´ıme libovolnˇe a tedy vˇeta plat´ı pro vˇsechna kladn´a j ∈ N ∪ {0}.
P (W = j) ≈
e−λ λj j!
j = 0, 1, 2, . . .
12
2.2
Pouˇ zit´ı
Aproximace binomick´ eho rozdˇ elen´ı Aproximace binomick´eho rozdˇelen´ı Poissonov´ ym rozdˇelen´ım je zn´am´a a lehce dokazateln´a limitn´ım pˇrechodem. V tomto odd´ıle si uk´aˇzeme odvozen´ı pomoc´ı Brunova s´ıta. Pˇredpokl´adejme n´ahodnou veliˇcinu W s binomick´ ym rozdˇelen´ım a s parametry n a p, kde n je poˇcet nez´avisl´ ych pokus˚ u a p je pravdˇepodobnost u ´spˇechu v jednom pokusu. Oznaˇcme λ = np a d´ale pˇredpokl´adejme dostateˇcnˇe velk´e n a mal´e p. N´ ´spˇeˇsn´ ych pokus˚ u a odtud kombinaˇcn´ı ˇc´ıslo ahodn´a veliˇcina W ud´av´a poˇcet u n W znaˇc´ı poˇcet i-tic, reprezentuje poˇ c et i-tic u ´ spˇ e ˇ s n´ y ch pokus˚ u . Stejnˇ e tak i i kter´e lze vytvoˇrit ze vˇsech pokus˚ u. Nyn´ı postupnˇe vezmeme vˇsechny moˇzn´e i-tice a pˇriˇrad´ıme kaˇzd´e indik´ator Ik s hodnotou 1, je-li vˇsech i pokus˚ uu ´spˇeˇsn´ ych, a 0 pokud je alespoˇ n jeden z nich ne´ uspˇeˇsn´ y. M˚ uˇzeme ps´at
W i
(ni) X
=
Ik .
(2.6)
k=1
Na obˇe strany rovnosti aplikujeme stˇredn´ı hodnotu. n (ni) ( i) X X n i W 1 EIk = p = Ik = E =E i i k=1 k=1
(2.7)
i
z }| { n(n − 1) . . . (n − i + 1) i = p. i!
(2.8)
Rovnost 1 v (2.7) plat´ı nebot’ n´ahodn´a veliˇcina Ik nab´ yv´a hodnoty 1 pouze v pˇr´ıpadˇe i u ´spˇeˇsn´ ych v´ ysledk˚ u, kdy kaˇzd´ y z nich nast´av´a s pravdˇepodobnost´ı p, stˇredn´ı hodnota Ik je proto dle zn´am´eho vzorce pi . Suma pˇres k pak reprezentuje poˇcet i-tic stejnˇe jako kombinaˇcn´ı ˇc´ıslo ni . Ze vztahu λ = np nahl´edneme, ˇze (2.8) m´a pˇribliˇznˇe stejnou hodnotu jako v´ yraz λi , pokud i je mal´e vzhledem k n. V opaˇcn´em pˇr´ıpadˇe, je faktori´al i dostateˇcnˇe i! i velk´ y, aby platil vztah ni pi ≈ 0 ≈ λi! . Tedy W λi E ≈ . i i! To je pˇredpoklad Brunovy vˇety a tedy opravdu plat´ı zn´am´ y fakt, ˇze binomick´e rozdˇelen´ı lze aproximovat rozdˇelen´ım Poissonov´ ym.
13
Narozeninov´ y probl´ em Brunovu vˇetu lze s v´ yhodou pouˇz´ıt i pˇri rozˇs´ıˇren´ı zn´am´eho narozeninov´eho 2 probl´emu . V jeho nejjednoduˇsˇs´ı verzi se pt´ame, jak´a je pravdˇepodobnost, ˇze se ve skupinˇe n´ahodnˇe vybran´ ych jedinc˚ u vyskytne alespoˇ n jedna dvojice se stejn´ ym dnem narozen´ı, pˇredpokl´ad´ame-li, ˇze se jednotliv´e osoby narodili pˇribliˇznˇe rovnomˇernˇe v dan´em ˇcasov´em rozmez´ı a nez´avisle na ostatn´ıch (nejsou zde napˇr´ıklad dvojˇcata). Tato pravdˇepodobnost jde pomˇernˇe jednoduˇse vyj´adˇrit pˇres doplˇ nkov´ y jev, tedy situaci, kdy se ve skupinˇe nenach´az´ı ani jedna dvojice slav´ıc´ı ve stejn´ y den. Tedy, je-li X n´ahodn´a veliˇcina zachycuj´ıc´ı poˇcet dvojic se stejn´ ym dnem narozen´ı, n reprezentuje poˇcet osob a d poˇcet dn´ı, ve kter´ ych sledujeme zda doˇslo ke zdvojen´ ym narozenin´am, potom n−1 (d − 1)(d − 2) . . . (d − n + 1) Y i P (X = 0) = 1 · = . 1− dn−1 d i=1 Za povˇsimnut´ı pak stoj´ı fakt, ˇze jiˇz u 23 osob, je vˇetˇs´ı ˇsance na narozeninovou shodu neˇz ˇsance, ˇze se vˇsichni narodili v r˚ uzn´e dny. N´as bude nicm´enˇe zaj´ımat jak´a je ˇsance, ˇze se ve stejn´ y den narodila m-tice jedinc˚ u. Tento probl´em jiˇz nem´a lehce vyj´adˇriteln´e ˇreˇsen´ı, ale s pomoc´ı Brunovy vˇety lze toto velmi dobˇre aproximovat Poissonov´ ym rozdˇelen´ım. Nejdˇr´ıve se na probl´em pod´ıvejme obecnˇe. Pˇredpokl´adejme posloupnost n´ahodn´ ych pokus˚ u, kter´e mohou skonˇcit jedn´ım z d stejnˇe pravdˇepodobn´ ych v´ ysledk˚ u. ’ Necht d je dostateˇcnˇe velk´e a X znaˇc´ı poˇcet pokus˚ u, kter´e jsou potˇreba, aby bylo nˇekter´eho z d v´ ysledk˚ u dosaˇzeno m-kr´at. Nyn´ı se ptejme, jak´a je pravdˇepodobnost, ˇze poˇcet pokus˚ u X pˇres´ahne danou hodnotu n. Oznaˇc´ıme-li Z jako n´ahodnou veliˇcinu ud´avaj´ıc´ı poˇcet v´ ysledk˚ u, kter´e se jiˇz alespoˇ n m-kr´at opakovali v dosavadn´ıch n pokusech, m˚ uˇzeme ps´at: P (X > n) = P (Z = 0).
(2.9)
Naˇs´ım c´ılem bude uk´azat, ˇze n´ahodn´a veliˇcina Z m´a aproximativnˇe Poissonovo rozdˇelen´ı, kter´e lze jiˇz jednoduˇse vyj´adˇrit a spoˇc´ıtat. K tomu potˇrebujeme uk´azat platnost pˇredpokladu Brunovy vˇety (2.1) pro n´ahodnou veliˇcinu Z. Zvol´ıme si libovolnˇe ale pevnˇe i, i ∈ N ∪ {0}. Vezmeme postupnˇe vˇsechny i-tice ze vˇsech moˇzn´ ych v´ ysledk˚ u d a kaˇzd´e i-tici pˇriˇrad´ıme indik´ator Ij s hodnotou 1 v pˇr´ıpadˇe, ˇze se jedn´a o i-tici v´ ysledk˚ u, kter´e jiˇz byli vˇsechny nabyty alespoˇ n m-kr´at v dosavadn´ıch n pokusech, a s hodnotou 0 v pˇr´ıpadˇe opaˇcn´em. Stˇredn´ı hodnotu v´ yrazu Zi ted’ m˚ uˇzeme s pomoc´ı (2.6) ps´at jako (di) X Z d E = EIj = pn,i,m , i i j=1
(2.10)
kde pn,i,m je pravdˇepodobnost, ˇze se v prvn´ıch n pokusech nabylo kaˇzd´eho z i v´ ysledk˚ u m-kr´at, pˇr´ıpadnˇe v´ıcekr´at. K pˇresnˇejˇs´ımu vyj´adˇren´ı pravdˇepodobnosti pn,i,m budeme potˇrebovat n´asleduj´ıc´ı lemma. 2
O narozeninov´em probl´emu a dalˇs´ıch aplikac´ıch Brunova s´ıta a Chen-Steinovi vˇety pojedn´ av´ a Arratia, 1990 [2]
14
Lemma 2.1. Mˇejme n´ahodnou veliˇcinu N s Poissonov´ym rozdˇelen´ım s parametrem λ, kter´a reprezentuje celkov´y poˇcet pozorovan´ych ud´alost´ı . Pˇredpokl´ adejme, ˇze kaˇzd´a z ud´alost´ı m˚ uˇze skonˇcit jen jedn´ım z i v´ysledk˚ u nez´avisle na ostatn´ıch ud´alostech a pravdˇepodobnost, ˇze skonˇc´ı pr´avˇe k-t´ym v´ysledkem je pk , k = 1, . . . , i. Potom Nk , k = 1, . . . , i, poˇcet ud´alost´ı s v´ysledkem k, jsou nez´avisl´e n´ahodn´e veliˇciny s Poissonov´ym rozdˇelen´ım s parametrem λpk , k = 1, . . . , i. D˚ ukaz. : P Pi Plat´ı ik=1 pk = 1 a N = a nez´aporn´a cel´a ˇc´ısla nk k=1 Nk . Pro libovoln´ P oznaˇcme n = ik=1 nk . Potom dost´av´ame sdruˇzenou pravdˇepodobnost P (Nk = nk , k = 1, . . . , i) = = P (Nk = nk , k = 1, . . . , i|N = n)P (N = n) + P (Nk = nk , k = 1, . . . , i|N 6= n)P (N 6= n) = P (Nk = nk , k = 1, . . . , i|N = n)P (N = n). Vezmeme-li nyn´ı N = n jako poˇcet vˇsech nastal´ ych ud´alost´ı, dost´av´ame, ˇze Nk , k = 1, . . . , i maj´ı multinomick´e rozdˇelen´ı 3 s parametry n, p1 , p2 , . . . pi . Odtud jiˇz plyne P (Nk = nk , k = 1, . . . , i) = n! e−λ λn pn1 1 pn2 2 · · · pni i · n1 !n2 ! · · · ni ! n! ni n1 +n2 +···+ni n1 n2 p p · · · pi λ = 1 2 · e−λ(p1 +p2 +···+pi ) n1 !n2 ! · · · ni ! i Y (λpk )nk e−λpk = . n k! k=1 =
Tedy Nk , k = 1, . . . , i jsou nez´avisl´e n´ahodn´e veliˇciny s Poissonov´ ym rozdˇelen´ım s parametry λpk , k = 1, . . . , i.
Mˇejme i-tici v´ ysledk˚ u, kter´e jiˇz byly nabyty alespoˇ n m-kr´at. Oznaˇcme Y jako n´ahodnou veliˇcinu urˇcuj´ıc´ı poˇcet pokus˚ u z prvn´ıch n, jejichˇz v´ ysledek padl do dan´e i-tice. Potom Y je n´ahodn´a veliˇcina s binomick´ ym rozdˇelen´ım s parameuˇzeme pˇrej´ıt k aproximaci try n, di . Je-li pravdˇepodobnost di dostateˇcnˇe mal´a, m˚ Poissonov´ ym rozdˇelen´ım s parametrem ni . Nyn´ ı vezmeme Yk jako tu ˇc´ast pod yv´a, kus˚ u z Y , kter´e vˇsechny skonˇcili k-t´ ym v´ ysledkem. Z lemmatu 2.1 pot´e vypl´ ˇze Yk , k = 1, . . . , i jsou nez´avisl´e n´ahodn´e veliˇciny s aproximativnˇe Poissonov´ ym 1 n = . Jednotliv´ e Y maj´ ı m´ ıt hodnotu m nebo vˇ e tˇs´ı, rozdˇelen´ım s parametrem ni k d i d toho je dosaˇzeno s pravdˇepodobnost´ı P (Yk ≥ m) = pm+ = 1 −
m−1 X
e
−n d
j=0 3
ˇ ep´ V´ıce o multinomick´em rozdˇelen´ı ve Zv´ ara, Stˇ an, 2002 [8]
15
( nd )j . j!
(2.11)
D´ıky nez´avislosti Y1 , . . . Yk je tedy hledan´a pravdˇepodobnost pn,i,m z (2.10) pˇribliˇznˇe rovna (pm+ )i (rovnost je pouze aproximativn´ı, nebot’ n´ahodn´a veliˇcina Y m´a pouze aproximativn´ı Poissonovo rozdˇelen´ı).
Vrat’me se zpˇet k v´ ypoˇctu stˇredn´ı hodnoty ze vzorce (2.10), kterou nyn´ı m˚ uˇzeme zapsat takto: d d Z = pn,i,m ≈ (pm+ )i . (2.12) E i i i D´ıky tomu, ˇze pod´ıl di je mal´ y (bez tohoto pˇredpokladu by neplatila ani aproximace binomick´eho rozdˇelen´ı Poissonov´ ym u n´ahodn´e veliˇciny Y ), m˚ uˇzeme pravou stranu (2.12) d´ale upravit do hledan´eho tvaru. d(d − 1) · · · (d − i + 1) d (dpm+ )i (pm+ )i = (pm+ )i ≈ . i i! i! V pˇr´ıpadˇe, ˇze pod´ıl
i d
mal´ y nen´ı, dost´av´ame se k pˇribliˇzn´e rovnosti Z (dpm+ )i E ≈0≈ , i i!
nebot’ prav´a strana se rovn´a pˇribliˇznˇe 0 d´ıky faktori´alu ve jmenovateli a tomu, ˇze pravdˇepodobnost pm+ je mal´a, a lev´a strana se rovn´a pˇribliˇznˇe 0 d´ıky tomu, ˇze pravdˇepodobnost pn,i,m je pˇri velk´em i velmi mal´a. Brali jsme libovoln´e i, a proto m´ame pro vˇsechna i platn´ y vztah Z (dpm+ )i ≈ E . i i! T´ımto jsme ovˇeˇrili pˇredpoklad Brunovy vˇety a odtud jiˇz plyne, ˇze n´ahodn´a veliˇcina Z m´a aproximativnˇe Poissonovo rozdˇelen´ı s parametrem dpm+ . D´ıky tomuto faktu jiˇz m˚ uˇzeme lehce zapsat pravdˇepodobnost z (2.9) P (X > n) = P (Z = 0) ≈ exp (−dpm+ ).
16
(2.13)
Pˇr´ıklad 1. Jak´a je pravdˇepodobnost, ˇze mezi 200 lidmi budou alespoˇ n 4 z nich slavit narozeniny ve stejn´ y den? ˇ sen´ı 1. Reˇ Ze zad´an´ı v´ıme: d = 365, m = 4, n = 200. Odtud jiˇz z rovnosti (2.11) plyne p4+ = 1 −
m−1 X j=0
e
−n d
( nd )j = 0, 002433. j!
A tedy podle (2.13) P (X > 200) = P (W = 0) ≈ exp (−365 · 0, 002433) ≈ 0, 411 Mezi 200 lidmi se s pravdˇepodobnost´ı pˇribliˇznˇe 59 procent najde alespoˇ n ˇctveˇrice se stejn´ ym dnem narozen´ı.
ˇ sen´ı 2. Reˇ Vych´az´ıme ze stejn´eho zad´an´ı, ale k ˇreˇsen´ı pˇristoup´ıme empiricky. V programu Mathematica nasimulujeme narozen´ı 200 osob v pr˚ ubˇehu roku a pod´ıv´ame se, zda se objev´ı alespoˇ n ˇctveˇrice lid´ı se stejn´ ym dnem narozen´ı. To provedeme 10 000 000 kr´at a z napozorovan´ ych dat vypoˇc´ıt´ame hledanou pravdˇepodobnost. Cel´ y program je vyps´an v Pˇr´ıloze 3. Pˇri simulaci vych´az´ı poˇcet let, ve kter´ ych se v alespoˇ n jeden den narod´ı alespoˇ n 4 jedinci, na 5 912 702, coˇz pˇri poˇctu 10 000 000 simulac´ı d´av´a pravdˇepodobnost 0,591, ˇze se mezi 200 lidmi najde alespoˇ n ˇctveˇrice se stejn´ ym dnem narozen´ı. Spoˇc´ıt´ame d´ale 99% interval spolehlivosti pro poˇcet let, ve kter´ ych se v alespoˇ n jeden den narod´ı alespoˇ n 4 jedinci. Opˇet vyuˇzijeme programu Mathematica. Poˇcet let X je n´ahodn´a veliˇcina s binomick´ ym rozdˇelen´ım s empiricky zjiˇstˇenou pravdˇepodobnost´ı u ´spˇechu p = 0, 591. Pomoc´ı centr´aln´ı limitn´ı vˇety sestav´ıme interval spolehlivosti. 1 − α = P (|Y | < u1−α/2 ) X −µ = P (| p | < u1−α/2 ) p(1 − p) Tedy interval spolehlivosti je p p X − p(1 − p)u1−α/2 ; X + p(1 − p)u1−α/2 Po dosazen´ı je v´ ysledn´ y interval spolehlivosti p p 5 912 702 − 0, 591(1 − 0, 591) · 2, 576; 5 912 702 + 0, 591(1 − 0, 591) · 2, 576 = = (5 912 700; 5 912 703). 17
ˇ sen´ı 3. Reˇ Opˇet vych´az´ıme ze stejn´eho zad´an´ı. Oznaˇcme • W - poˇcet dn´ı, kdy se narodily alespoˇ n 4 lid´e • Ij - ukazatel, ˇze se v j-t´ y den narodily alespoˇ n 4 lid´e, j=1,...,365 P Pak W = 365 a pˇribliˇznˇe binomick´e rozdˇelen´ı s parametry n = 365 j=1 Ij a W m´ a p = P (Ij = 1). Vyj´adˇr´ıme pravdˇepodobnost p. p = P (Ij = 1) = 1 − P (Ij = 0) = 199 200 364 364200 =1− + 1 200 + 200 365 365
200 2
364198 + 365200
200 3
364197 365200
!
= 0, 00238 Odtud
365 P (W ≥ 1) = 1 − P (W = 0) = 1 − 0, 002380 (1 − 0, 00238)365 = 0, 58. 0
Tedy pravdˇepodobnost, ˇze alespoˇ n v jednom dni oslav´ı narozeniny alespoˇ n 4 lid´e je 58%. Vˇsechna 3 ˇreˇsen´ı vych´az´ı podobnˇe a lze tedy ˇr´ıci, ˇze hledan´a pravdˇepodobnost s jakou se mezi 200 lidmi alespoˇ n 4 narodili ve stejn´ y den, je 0,59. Jako nejpˇresnˇejˇs´ı lze uvaˇzovat ˇreˇsen´ı proveden´e simulacemi vzhledem k jejich velk´emu poˇctu. Zbyl´e dvˇe ˇreˇsen´ı uk´azali, ˇze odhad za pouˇzit´ı Brunova s´ıta je pˇresnˇejˇs´ı neˇz pˇredpoklad, ˇze n´ahodn´e veliˇciny pouˇzit´e k v´ ypoˇctu maj´ı pˇribliˇznˇe binomick´e rozdˇelen´ı.
18
Kapitola 3 Stein-Chenova metoda V minul´e kapitole jsme se zamˇeˇrili na metodu, kter´a n´am urˇcila, za jak´ ych podm´ınek lze pˇrej´ıt k Poissonovu rozdˇelen´ı. V t´eto kapitole se pokus´ıme odhadnout, jak´e chyby se t´ımto pˇrechodem dopust´ıme. Jedn´ım z postup˚ u, jak tuto chybu vyˇc´ıslit, je metoda zn´am´a jako Stein-Chenova metoda pro odhad velikosti chyby Poissonovsk´e aproximace. Tato se vyvinula z p˚ uvodn´ı Steinovy metody pro odhad velikosti chyby vznikl´e pˇri pˇrechodu k norm´aln´ımu rozdˇelen´ı, jeˇz byla formulov´ana v roce 1970 a vyd´ana ve Stein, 1972 [7]. Ta byla o pˇet let pozdˇeji upravena a rozˇs´ıˇrena Louis Chenem do dneˇsn´ı podoby.
3.1
Stein-Chenova metoda pro odhad velikosti chyby Poissonovsk´ e aproximace
Pˇredpokl´adejme n´ahodn´e veliˇciny X1 . . . Xn , pro kter´e plat´ı n´asleduj´ıc´ı: • X1 , . . . , Xn maj´ı alternativn´ı rozdˇelen´ı • Xi nab´ yv´a hodnot 0 a 1 s pravdˇepodobnostmi P (Xi = 1) = λi P (Xi = 0) = 1 − λi ,
i = 1, . . . , n.
D´ale oznaˇcme W a λ n´asleduj´ıc´ımi pˇredpisy W =
n X
Xi ,
λ=
i=1
n X
λi
i=1
a vezmeme mnoˇzinu A ⊂ N ∪ {0}. Naˇs´ım c´ılem bude odhadnou velikost chyby, kter´e se dopust´ıme v pˇr´ıpadˇe aproximov´an´ı pravdˇepodobnosti jevu W ∈ A Poissonov´ ym rozdˇelen´ım s parametrem λ.
19
Stein-Chenova vˇ eta. Necht’ Vi jsou n´ahodn´e veliˇciny, jejichˇz rozdˇelen´ı je stejn´e jako podm´ınˇen´e rozdˇelen´ı P ınky Xi = 1, i = 1, . . . , n. To znamen´a, ˇze pro kaˇzd´e i je Vi taj6=i Xj za podm´ kov´e, ˇze ! X P (Vi = k) = P Xj = k|Xi = 1 , pro vˇsechna k. j6=i
Potom pro jakoukoli mnoˇzinu A ⊂ N ∪ {0} plat´ı n −λ i X X e λ P (W ∈ A) − ≤ min(1, 1/λ) λi E|W − Vi |. i! i=1
i∈A
D˚ ukaz Stein-Chenovi vˇety provedeme v nˇekolika kroc´ıch: 1. Zavedeme pomocnou funkci g. 2. Zformulujeme a dok´aˇzeme dvˇe podp˚ urn´a lemmata. 3. Pouˇzijeme d˚ usledky lemmat pˇri u ´pravˇe funkce g.
Krok 1: Zaveden´ı pomocn´e funkce g. Uk´aˇzeme, ˇze pro pevn´e λ, λ ∈ (0, ∞) a mnoˇzinu A ⊂ N∪{0} m˚ uˇzeme definovat funkci g nad N ∪ {0}, kter´a splˇ nuje n´asleduj´ıc´ı rovnost. E[λg(W + 1) − W g(W )] = P (W ∈ A) −
X e−λ λi i∈A
i!
.
(3.1)
Takov´ato funkce lze sestavit pomoc´ı rekurzivn´ıho z´apisu g(0) = 0,
# X e−λ λi 1 g(j + 1) = I(j ∈ A) − + jg(j) , λ i! i∈A "
kde I(j ∈ A) =
j = 0, 1, 2, . . .
(3.2)
j = 0, 1, 2, . . .
(3.3)
j∈A j∈ / A.
1 0
Rovnici (3.2) uprav´ıme do tvaru λg(j + 1) − jg(j) = I(j ∈ A) −
X e−λ λi i∈A
20
i!
,
Rovnost (3.3) plat´ı pro vˇsechna j nez´aporn´a, m˚ uˇzeme tedy pˇrej´ıt k n´ahodn´e veliˇcinˇe W X e−λ λi λg(W + 1) − W g(W ) = I(W ∈ A) − . (3.4) i! i∈A Aplikujeme stˇredn´ı hodnotu na obˇe strany (3.4) a dost´av´ame E[λg(W + 1) − W g(W )] = P (W ∈ A) −
X e−λ λi i∈A
i!
,
coˇz jsme chtˇeli.
Krok 2: Pomocn´a lemmata. Lemma 3.1. Necht’ Y je n´ahodnou veliˇcinou a W m´a stejn´y v´yznam jako v´yˇse. Potom plat´ı: E[W Y ] =
n X
λi E[Y |Xi = 1].
i=1
D˚ ukaz. : Z pˇredeˇsl´eho textu v´ıme, ˇze n´ahodn´a veliˇcina W = k tomuto faktu m˚ uˇzeme ps´at " n # n X X E[W Y ] = E Xi Y = E[Xi Y ]. i=1
Pn i=1
Xi . Vzhledem
(3.5)
i=1
Nyn´ı pˇrejdeme k podm´ınˇen´e stˇredn´ı hodnotˇe E[Xi Y ] =
1 X
E[Xi Y |Xi = j]P (Xi = j)
j=0
= E[Xi Y |Xi = 0]P (Xi = 0) + E[Xi Y |Xi = 1]P (Xi = 1) = E[0] + E[Y |Xi = 1]λi = E[Y |Xi = 1]λi .
(3.6)
Pravdˇepodobnosti pro Xi jsou zn´amy. Z (3.5) a (3.6) plyne E[W Y ] =
n X
λi E[Y |Xi = 1].
i=1
T´ım jsme dok´azali platnost Lemmatu 3.1.
21
Lemma 3.2. Pro libovoln´e λ ∈ (0, ∞) a libovolnou mnoˇzinu A ⊂ N ∪ {0} plat´ı |g(j) − g(j − 1)| ≤
1 − e−λ ≤ min(1, 1/λ). λ
D˚ ukaz. : D˚ ukaz je moˇzno naj´ıt v kratˇs´ı verzi v Barbour, Eagleson, 1983 [3]. K dok´az´an´ı prvn´ı nerovnosti v Lemmatu 3.2 si zavedeme n´asleduj´ıc´ı oznaˇcen´ı: Uj = {0, 1, . . . , j},
Pλ (B) =
X e−λ λk k∈B
k!
,
Ik (B) = I(k ∈ B),
(3.7)
kde Pλ (B) znaˇc´ı pravdˇepodobnost, ˇze n´ahodn´a veliˇcina s Poissonov´ ym rozdˇelen´ım s parametrem λ patˇr´ı do mnoˇziny B a Ik (B) je indik´ator, zda k je v mnoˇzinˇe B. Nav´ıc pˇrid´ame horn´ı index k funkci g znaˇc´ıc´ı mnoˇzinu, u kter´e rozhodujem, zda do n´ı patˇr´ı hodnoty j. Pˇrep´ıˇseme rekurzivn´ı tvar funkce g (3.2) (ve zbytku d˚ ukazu znaˇc´ıme g A ), A ⊂ N ∪ {0} je libovoln´a mnoˇzina " # X 1 g A (j + 1) = I(j ∈ A) − e−λ λi /i! + jg A (j) λ i∈A 1 1 j1 A = Ij (A) − Pλ (A) + Ij−1 (A) − Pλ (A) + (j − 1)g (j − 1) λ λ λλ 1 1 j j j(j − 1) A = Ij (A) + Ij−1 (A) − Pλ (A) 1 + + g (j − 1) λ λ λ λ λ2 j j(j − 1) 1 Ij (A) + Ij−1 (A) + I (A) − = j−2 λ λ λ2 1 j j(j − 1) j(j − 1)(j − 2) A − Pλ (A) 1 + + + g (j − 2) λ λ λ2 λ3 .. . 1 j j(j − 1) j! = Ij (A) + Ij−1 (A) + Ij−2 (A) + . . . + j I1 (A) − λ λ λ2 λ j j(j − 1) j! j! A 1 + . . . + j + j g (0) − Pλ (A) 1 + + λ λ λ2 λ λ 1 j! λ −λ λj λj−1 λj−2 = e e I (A) + I (A) + I (A) + . . . + 1 · I (A) − j j−1 j−2 1 λ λj j! (j − 1)! (j − 2)! λj 1 j! λ −λ λj−1 λj−2 − e e Pλ (A) + + + ... + 1 λ λj j! (j − 1)! (j − 2)! (3.8) 1 j! λ 1 j! λ e P (A ∩ U ) − e Pλ (A)Pλ (Uj ). (3.9) = λ j λ λj λ λj V (3.8) jsme vytknuli λj!j ze z´avorek a rozepsali 1 = eλ e−λ . Posledn´ı rovnost (3.9) jsme upravili s vyuˇzit´ım oznaˇcen´ı (3.7). 22
Tedy g A (j + 1) =
1 j! λ e P (A ∩ U ) − P (A)P (U ) . λ j λ λ j λ λj
A Vezmeme gm jako funkci definovanou pro kaˇzd´e m ∈ A takto 1 j! λ A gm (j + 1) = e Pλ ({m} ∩ Uj ) − Pλ ({m})Pλ (Uj ) λ λj P A . a oznaˇc´ıme g A = m∈A gm
Zohledn´ıme v jak´em vztahu jsou k sobˇe promˇenn´e m a j a pˇrep´ıˇseme funkci Pro j < m m´ame 1 j! λ λm −λ 1 j! λm A (j + 1) = gm e 0 − e P (U ) = − Pλ (Uj ). (3.10) λ j λ λj m! λ λj m! Naproti tomu pro j ≥ m m´ame 1 j! λm 1 j! λ λm −λ λm −λ A (j + 1) = (3.11) gm e e − e P (U ) = Pλ (Ujc ). λ j λ λj m! m! λ λj m! A Z tˇechto pˇredpis˚ u m˚ uˇzeme vyˇc´ıst vlastnosti funkce gm . V bodech 0, . . . , m, kter´e jsou pokryty pˇredpisem (3.10), je z´aporn´a a klesaj´ıc´ı, v bodech m + 1, m + 2, . . ., jeˇz jsou pokryty pˇredpisem (3.11), je kladn´a a klesaj´ıc´ı. Kladnost a z´apornost jde okamˇzitˇe vidˇet, nebot’ z´avis´ı na znam´enku pˇred v´ yrazy, monot´onie jde vidˇet po rezeps´an´ı Pλ . Funkce (3.10) je klesaj´ıc´ı pro vˇsechna j, nebot’ 1 λm −λ j! j! j! 1 A gm (j + 1) = − e + + ... + +1 , λ m! λj λj−1 (j − 1)! λ 1 λm −λ (j + 1)! (j + 1)! (j + 1)! 1 (j + 1)! 1 A gm (j + 2) = − e + + + ... + +1 . λ m! λj+1 λj 2! λj−1 j! λ A . gm
A A gm (j + 2) > gm (j + 1), j = 0, 1, 2 . . ., protoˇze koeficienty u koresponduj´ıc´ıch A A mocnin λ jsou v pˇr´ıpadˇe gm (j + 2) vˇzdy vˇetˇs´ı neˇz u gm (j + 1). D˚ ukaz o kles´an´ı funkce (3.11) se provede podobnˇe. A Jedin´ y kladn´ y a tedy maxim´aln´ı rozd´ıl po sobˇe jdouc´ıch funkˇcn´ıch hodnot gm je v bodech m a m + 1. Tento nyn´ı omez´ıme zezhora. A A gm (m + 1) − gm (m) =
=
=
= ≤ =
1 m! λm 1 (m − 1)! λm c P (U ) + Pλ (Um−1 ) λ m λ λm m! λ λm−1 m! ∞ m−1 1 X λk −λ 1 λ X λk −λ e + e λ k=m+1 k! λ m k=0 k! ! ∞ m X e−λ λ X λk−1 λk + λ k! m k=1 (k − 1)! k=m+1 ! m ∞ X e−λ λk X λk k + λ k! k=1 k! m k=m+1 ! m ∞ X e−λ λk X λk + λ k! k=1 k! k=m+1 1 − e−λ e−λ λ (e − 1) = . λ λ 23
Pro libovolnou mnoˇzinu A ⊂ N ∪ {0} plat´ı
X
A A g A (m + 1) − g A (m) = Im (A)[gm (m + 1) − gm (m)] +
[gjA (m + 1) − gjA (m)].
j∈A,j6=m
Z pˇredchoz´ıho v´ıme, ˇze pouze prvn´ı sˇc´ıtanec je kladn´ y (za pˇredpokladu, ˇze se A v souˇctu objevuje). T´ımto dost´av´ame odhad pro [g (j) − g A (j − 1)]. g A (j) − g A (j − 1) ≤ sup max+ [g A (m) − g A (m − 1)] = m∈Z+ A⊂Z
A A = sup [gm−1 (m) − gm−1 (m − 1)] ≤ m∈Z+
1 − e−λ . λ
Pro dokonˇcen´ı d˚ ukazu si staˇc´ı uvˇedomit platnost vztahu g A (m+1) = −g A (m+1). 1 j! λ g A (m + 1) = e P (A ∩ U ) − P (A)P (U ) λ j λ λ j λ λj 1 j! λ c c = − j e − [Pλ (Uj ) − Pλ (A ∩ Uj )] + [1 − Pλ (A )]Pλ (Uj ) λλ 1 j! λ c c = − j e Pλ (A ∩ Uj ) − Pλ (A )Pλ (Uj ) λλ c = −g A (m + 1). c
Potom g A (j − 1) − g A (j) ≤ sup max+ [g A (m − 1) − g A (m)] = m∈Z+ A⊂Z
c
c
= sup max [g A (m) − g A (m − 1)] = c + m∈Z+ A ⊂Z c
c
A A = sup [gm−1 (m) − gm−1 (m − 1)] ≤ m∈Z+
Odtud |g A (j) − g A (j − 1)| ≤
1 − e−λ . λ
1 − e−λ . λ
V pˇr´ıpadˇe druh´e nerovnosti v Lemma 3.2 si uvˇedom´ıme, ˇze e−λ je ˇc´ıslo kladn´e menˇs´ı neˇz 1. T´ım p´adem 1 1 − e−λ ≤ λ λ
λ ∈ (0, ∞).
Zamˇeˇr´ıme-li se speci´alnˇe na λ ≤ 1 m˚ uˇzeme horn´ı odhad d´ale omezit jedniˇckou. −λ Pouˇzijeme Taylor˚ uv rozvoj funkce e 1 − e−λ ≤ λ λ2 λ3 λ4 λ5 − + − + . . .) ≤ λ 2! 3! 4! 5! λ2 λ3 λ4 λ5 λ − ( − ) − ( − ) − . . .) ≤ λ. 2! 3! 4! 5!
1 − (1 − λ +
24
Rozd´ıl v z´avork´ach je vˇzdy vˇetˇs´ı neˇz 0 nebot’ λj λj+1 > j! (j + 1)! λ 1> , j+1
λ ∈ (0, 1).
Odtud jiˇz plat´ı
1 − e−λ ≤ min (1, 1/λ). λ ubˇeh funkc´ı 1 − e−λ a λ. Pro n´azornost je v Pˇr´ıloze 4 zobrazen pr˚
´ Krok 3: Uprava funkce g. Pomoc´ı lemmat z kroku 2 uprav´ıme rovnost (3.1) z kroku 1. E[λg(W + 1) − W g(W )] = P (W ∈ A) −
X e−λ λi i∈A
i!
.
(3.12)
Nejprve si jin´ ym zp˚ usobem vyj´adˇr´ıme levou stranu rovnice (3.12). ´ Upravu v´ yrazu E[λg(W + 1)] provedeme n´asledovnˇe, nebot’ λ je voleno libovoln´e ale pevn´e a je definov´ano jako souˇcet stˇredn´ıch hodnot n´ahodn´ ych veliˇcin Xi . E[λg(W + 1)] = λE[g(W + 1)] =
n X
λi E[g(W + 1)].
(3.13)
i=1
´ Upravu v´ yrazu E[W g(W )] provedeme za pomoci lemmatu 3.1, kde nahrad´ıme n´ahodnou veliˇcinu Y funkc´ı g(W ) . Dostaneme rovnost E[W g(W )] = =
n X i=1 n X
λi E[g(W )|Xi = 1] (3.14) λi E[g(Vi + 1)],
i=1
kde je n´ahodn´a veliˇcina Vi definov´ana takto P (Vi = k) = P
X
! Xj = k|Xi = 1 ,
j6=i
25
pro vˇsechna k.
Nyn´ı jiˇz m˚ uˇzeme pokraˇcovat s u ´pravou rovnice (3.12). Jelikoˇz n´as zaj´ım´a velikost odchylky, kter´a m˚ uˇze b´ yt jak kladn´eho tak z´aporn´eho r´azu, pˇrejdeme k absolutn´ı hodnotˇe a n´aslednˇe vyuˇzijeme rovnosti (3.13) a (3.14). X −λ i e λ /i! = E[λg(W + 1) − W g(W )] P (W ∈ A) − i∈A n n X X = λi E[g(W + 1)] − λi E[g(Vi + 1)] i=1 i=1 n X = λi (E[g(W + 1)] − E[g(Vi + 1)] i=1 n X = λi E[g(W + 1) − g(Vi + 1)] . i=1
Z troj´ uheln´ıkov´e nerovnosti d´ale dost´av´ame n n X X λi E[g(W + 1) − g(Vi + 1)] ≤ λi E|g(W + 1) − g(Vi + 1)|. i=1
(3.15)
i=1
K dalˇs´ı u ´pravˇe vyuˇzijeme vlastnosti funkce g, kter´a je shrnuta v lemmatu 3.2. Tento vztah rozˇs´ıˇr´ıme pro libovoln´e i, j, pro kter´e plat´ı i, j = 0, 1, 2 . . . , j ≥ i (Pokud i ≥ j, staˇc´ı prohodit poˇrad´ı v absolutn´ı hodnotˇe). |g(j) − g(i)| = |g(j) − g(j − 1) + g(j − 1) − g(j − 2) + . . . + g(i + 1) − g(i)| ≤ |g(j) − g(j − 1)| + |g(j − 1) − g(j − 2)| + . . . + |g(i + 1) − g(i)| ≤ |j − i| min(1, 1/λ). Aplikac´ı pˇredchoz´ıho na pravou stranu nerovnosti (3.15) dost´av´ame n X
λi E|g(W + 1) − g(Vi + 1)| ≤
i=1
n X i=1
ˇc´ımˇz jsme uzavˇreli d˚ ukaz Stein-Chenovy vˇety.
26
λi min (1, 1/λ)E|W − Vi |,
3.2
Stein-Chenova metoda za specifick´ e podm´ınky
V pˇredchoz´ı podkapitole jsme uk´azali, jak odhadnout velikost chyby poissonovsk´e aproximace. K tomuto odhadu jsme potˇrebovali n´ahodnou veliˇcinu Vi , pro kterou P platilo, ˇze jej´ı rozdˇelen´ı bylo stejn´e jako podm´ınˇen´e rozdˇelen´ı n´ahodn´e veliˇciny j6=i Xi za podm´ınky Xi = 1. V´ ysledn´ y horn´ı odhad obsahoval stˇredn´ı hodnotu v´ yrazu |W −Vi |, kter´a nemus´ı b´ yt lehce spoˇcitateln´a a proto se pokus´ıme naj´ıt dalˇs´ı vlastnost Vi tak, aby se horn´ı odhad poˇcetnˇe zjednoduˇsil. Dobr´a vlastnost by mohla b´ yt takov´a, kter´a n´am dovol´ı odstranit absolutn´ı hodnotu. Pˇredpokl´adejme tedy, ˇze plat´ı W ≥ Vi , i = 1, . . . , n. Takov´ato nerovnost se objevuje v situac´ıch, kdy znalost informace Xi = 1 ovlivn´ı negativnˇe pravdˇepodobnost dosaˇzen´ı hodnoty 1 u ostatn´ıch n´ahodn´ ych veliˇcin Xj . Jin´ ymi slovy pokud Xi = 1, potom Xj , jeˇz byly nulov´e bez zohlednˇen´ı podm´ınky pro Xi , budou s pravdˇepodobnost´ı 1 nulov´e po zohlednˇen´ı podm´ınky pro Xi a Xj , kter´e byly bez zohlednˇen´ı podm´ınky pro Xi jednotkov´e, maj´ı po zohlednˇen´ı podm´ınky pro Xi pravdˇepodobnost vˇetˇs´ı neˇz nula zmˇenit se na nulu. Za v´ıˇse uveden´eho pˇredpokladu m˚ uˇzeme upravit horn´ı odhad ve Stein-Chenovˇe vˇetˇe takto n X
λi E|W − Vi | =
i=1
n X
λi E[W ] −
i=1
= =
n X i=1 n X
n X
λi E[Vi ]
i=1
λi λi
i=1
= λ2 −
n X k=1 n X
E[Xk ] −
n X
λk −
n X
λi (E[Vi + 1] − E[1])
i=1
k=1 n X
λi E[Vi + 1] +
i=1
= λ2 + λ − = λ2 + λ −
λi E[Vi + 1 − 1]
i=1
n X i=1 n X
" λi E 1 +
n X
λi
i=1 n X
# Xj |Xi = 1
j=1,j6=i
λi E[W |Xi = 1].
i=1
Nyn´ı pouˇzijeme lemma 3.1, pˇriˇcemˇz jako n´ahodnou veliˇcinu Y poloˇzme W a aplikujme jej na sumu. n X
λi E|W − Vi | = λ2 + λ − E[W 2 ]
i=1
= λ − [E[W 2 ] − (E[W ])2 ] = λ − V ar(W ). 27
M˚ uˇzeme tedy vyslovit n´asleduj´ıc´ı tvrzen´ı Lemma 3.3.P Mˇejme W = nj=1 Xj a Vi definovan´e stejnˇe jako ve Stein-Chenovˇe vˇetˇe. Pokud pro kaˇzd´e i, i = 1, . . . , n plat´ı nerovnost W ≥ Vi , potom pro kaˇzdou mnoˇzinu A ⊂ N ∪ {0} plat´ı X e−λ λi /i! ≤ min (1, 1/λ)[λ − V ar(W )] P (W ∈ A) − i∈A
3.3
Pouˇ zit´ı
Pˇr´ıklad 1. Jak velk´a je chyba aproximace binomick´eho rozdˇelen´ı Poissonov´ ym?
ˇ sen´ı 1. Reˇ Mˇejme W =
Pn i=1
Xi , kde Xi jsou nez´avisl´e n´ahodn´e veliˇciny, pro kter´e plat´ı P (X = 1) = p,
P (X = 0) = 1 − p.
Veliˇcina W m´a binomick´e rozdˇelen´ı a lze ji aproximovat rozdˇelen´ım Poissonov´ ym s parametrem λ = np. Pomoc´ı Stein-Chenovi vˇety odhadneme chybu, kter´e se aproximac´ı dopust´ıme. N´ahodn´a veliˇcina Vi je d´ıky nez´avislosti Xi d´ana takto Vi =
n X
Xj
j=1,j6=i
Plat´ı W ≥ Vi , i = 1, . . . , n, pouˇzijeme tedy lemma 3.3. X −λ i e λ /i! ≤ min (1, 1/λ)[λ − V ar(W )] P (W ∈ A) − i∈A
= min (1, 1/λ)[np − np(1 − p)] = min (1, 1/λ)np2 .
28
Pˇr´ıklad 2. Mˇejme m m´ıˇck˚ u rozm´ıstˇen´ ych do n n´adob, pˇriˇcemˇz plat´ı, ˇze kaˇzd´ y m´ıˇcek spadne do i-t´e n´adoby s pravdˇepodobnost´ı pi , i = 1, . . . , n. Oznaˇcme Xi jako indik´ator pr´azdnosti i-t´e n´adoby, neboli Xi = 1 pokud je n´adoba pr´azdn´a a Xi = 0 pokud se v n´adobˇe nach´az´ı alespoˇ n jeden m´ıˇcek. D´ale oznaˇcme W jako poˇcet pr´azdn´ ych n´adob, tedy n X W = Xi . i=1
Pokud je m dostateˇcnˇe velk´e, plat´ı, ˇze P (Xi = 1) = (1 − pi )m = λi jsou dostateˇcnˇe mal´a a pˇribliˇznˇe stejnˇe velk´a. N´ahodn´a veliˇcina W m´a tud´ıˇz pˇribliˇznˇe binomick´e rozdˇelen´ı a m˚ uˇzeme tedy aproximativnˇ Pn e pˇrej´ıt od binomick´eho rozdˇelen´ı k Poissonovu rozdˇelen´ı s parametrem λ = i=1 λi . Jak velk´e chyby se t´ımto pˇrechodem dopust´ıme?
ˇ sen´ı 2. Reˇ Vych´azejme ze Stein-Chenovy vˇety. Dle zad´an´ı je jedinou nezn´amou v´ yraz E[|W − Vi |]. W pˇredstavuje poˇcet pr´azdn´ ych n´adob. Vi si vezmeme jako poˇcet pr´azdn´ ych n´adob po pˇr´ıpadn´em vypr´azdnˇen´ı i-t´e n´adoby a pˇrerozdˇelen´ı m´ıˇck˚ u, pˇriˇcemˇz i-tou n´adobu nezapoˇc´ıt´av´ame. Tvrd´ıme, ˇze mezi W a Vi plat´ı vztah W ≥ Vi . Pˇredstavme si m m´ıˇck˚ u rozdˇelen´ ych do n n´adob s pˇr´ısluˇsnou pravdˇepodobnost´ı ’ danou zad´an´ım. Zvolme n´ahodnˇe jednu Pn z n´adob. Tato k-t´a n´adoba je bud to pr´azdn´a, coˇ ych n´adob je o jedna vˇetˇs´ı Pznznamen´a, ˇze poˇcet W = i=1 Xi pr´azdn´ neˇz Vi = i=1,i6=k Xi , nebo je v n´ı urˇcit´ y poˇcet m´ıˇck˚ u. V tom pˇr´ıpadˇe n´adobu vypr´azdn´ıme a m´ıˇcky rozdˇel´ıme do ostatn´ıch n´adob. I v pˇr´ıpadˇe, ˇze vˇsechny padnou do jiˇz naplnˇen´ ych n´adob, platnost vztahu W ≥ Vi z˚ ustane zachov´ana. T´ım sp´ıˇse bude vztah platit v pˇr´ıpadˇe, ˇze pˇrerozdˇelen´ım napln´ıme doposud pr´azdn´e n´adoby. Vztah mezi W a Vi tud´ıˇz plat´ı vˇzdy a proto m˚ uˇzeme ve v´ yrazu E|W − Vi | odstranit absolutn´ı hodnotu. Poˇc´ıtejme E|W − Vi | = E[W − Vi ] = E[W ] − E[Vi ] " # X =λ−E Xj |Xi = 1 =λ−
X
j6=i
j6=i
=λ−
X j6=i
29
(3.16)
E[Xj |Xi = 1] pj 1− 1 − pi
m .
Posledn´ı rovnost v (3.16) plat´ı nebot’ E[Xj |Xi = 1] = P (Xj = 1|Xi = 1) =
P (Xj = 1, Xi = 1) (1 − pj − pi )m . = P (Xi = 1) (1 − pi )m
A tedy pro kaˇzdou mnoˇzinu A ⊂ N ∪ {0} m´ame ze Stein-Chenovi vˇety " m # n X X X p j e−λ λi /i! ≤ min(1, 1/λ) . λi λ − 1− P (W ∈ A) − 1 − p i i=1 i∈A j6=i (3.17)
Pro numerickou ilustraci vezmeme m = 50, n = 10, pi = 0, 1, i = 1, . . . , 10. Potom P (Xi = 1) = (1 − 0, 1)50 = 0, 00515 = λi a tedy λ=
10 X
0, 00515 = 0, 0515.
i=1
Dosad´ıme vˇsechny hodnoty do odhadu (3.17) a vyˇc´ısl´ıme
min(1; 1/0, 0515)
10 X
" 0, 00515 0, 0515 −
i=1
=
10 X
X j6=i
0, 1 1− 1 − 0, 1
50 # =
0, 00515 [0, 0515 − 9 · 0, 00277] =
i=1
= 0, 00137 Chyba, kter´e se dopust´ıme pˇrechodem od binomick´eho rozdˇelen´ı k Poissonovu rozdˇelen´ı bude menˇs´ı neˇz 0, 00137.
30
Z´ avˇ er Hlavn´ı pouˇzit´ı Poissonova rozdˇelen´ı je dobˇre zn´am´e, slouˇz´ı k poˇc´ıt´an´ı pravdˇepodobnost´ı v´ yskyt˚ u jev˚ u v ˇcasov´em nebo prostorov´em u ´seku. Tak´e jako limitn´ı pˇrechod binomick´eho rozdˇelen´ı m´a v´ yznam pˇri zjednoduˇsen´ı v´ ypoˇct˚ u za cenu zanedbateln´e nepˇresnosti. D´ıky zaveden´ı Brunovi vˇety vˇsak m˚ uˇzeme tuto v´ yhodu zjednoduˇsen´ı v´ ypoˇctu uplatnit na ˇsirˇs´ı spektrum n´ahodn´ ych veliˇcin. D˚ uleˇzit´ ym faktorem pˇri tˇechto aproximac´ıch z˚ ust´av´a velikost chyby, kter´e se pˇrechodem k Poissonovu rozdˇelen´ı dopust´ıme. Znalost t´eto chyby n´am pak d´av´a moˇznost v´ ybˇeru, zda k aproximaci v˚ ubec pˇrej´ıt, a v pˇr´ıpadˇe pouˇzit´ı Poissonova rozdˇelen´ı urˇc´ı nepˇresnost s jakou mus´ıme poˇc´ıtat. Stein-Chenova vˇeta, kter´a se zamˇeˇruje na odhad velikosti chyby, je tak dobr´ ym pomocn´ ym n´astrojem pro spr´avnˇe pouˇzit´ı Poissonovsk´e aproximace.
31
Seznam pouˇ zit´ e literatury [1] Alon, N., Spencer, J. The probabilistic method. John Wiley & Sons Inc, New York, 1992. ISBN 978-0-470-17020-5 [2] Arratia, R., Goldstein, L., Gordon, L. Poisson approximation and the Chen-Stein method. Statistical Science. Vol. 5, No. 4. (Nov., 1990), str. 403424. [3] Barbour, A., D., Eagleson, G., K. Poisson approximation for some statistics based on exchangeable trials. Advances in applied probability. Vol. 15, No. 3. (Sep., 1983), str. 585-600. [4] Larson, Harold J. Introduction to probability theory and statistical inference. 3. vyd´an´ı. John Wiley & Sons Inc, 1982. ISBN 978-0-471-05909-7. [5] Ross, Sheldon M. Stochastic processes. John Wiley & Sons Inc, New York, 1996. ISBN 0-471-12062-6 ´kely, G´abor J. Paradoxes in probability theory and mathematical statis[6] Sze tics. Akad´emiai Kiad´o, Budapest, 1996. ISBN 963-05-4151 [7] Stein, Ch. A bound for the error in the normal approximation to the distribution of a sum of dependent random variables. Proc. Sixth Berkeley Symp. on Math. Statist. and Prob. Vol. 2, pp. 583-602. University California Press, Berkeley 1972. ˇ e ´ra, Karel, St ˇpa ´n, Josef. Pravdˇepodobnost a matematick´a statistika. [8] Zva MATFYZPRESS, Praha, 2002 ISBN 80-85863-76-6
32
Pˇ r´ılohy Pˇ r´ıloha 1. pozorovanadata = {109, 65, 22, 4}; ocekavanadata = Join[200 ∗ Table[PDF[PoissonDistribution[0.61], i], {i, 0, 2}], {200 ∗ (1 − Total[Table[PDF[PoissonDistribution[0.61], i], {i, 0, 2}]])}]; PLength[pozorovanadata] (pozorovanadata[[i]]−ocekavanadata[[i]])2 testovastatistika = i=1 ; ocekavanadata[[i]] stupnevolnosti = Length[pozorovanadata] − 1; kritickahodnota = 7.815; (*X32 (0.05)*) Pˇ r´ıloha 2. pozorovanadata = {229, 211, 93, 35, 8}; ocekavanadata = Join[576 ∗ Table[PDF[PoissonDistribution[N [537/576]], i], {i, 0, 3}], {576∗ (1 − Total[Table[PDF[PoissonDistribution[N [537/576]], i], {i, 0, 3}]])}]; P (pozorovanadata[[i]]−ocekavanadata[[i]])2 testovastatistika = Length[pozorovanadata] ; i=1 ocekavanadata[[i]] stupnevolnosti = Length[pozorovanadata] − 1; kritickahodnota = 9.488; (*X42 (0.05)*) Pˇ r´ıloha 3. narozeniny[n , d , opakovani , NarozeniVJedenDen ]:= Module[{dni, DnuSViceNarozeninami, RokSViceNarozeninami, LetSViceNarozeninami}, dni:=Tally[RandomInteger[{1, d}, n]]; DnuSViceNarozeninami:= Total[Map[If[Last[#]>=NarozeniVJedenDen, 1, 0]&, dni]]; RokSViceNarozeninami:=If[DnuSViceNarozeninami > 0, 1, 0]; LetSViceNarozeninami = Total[Table[RokSViceNarozeninami, {opakovani}]]] pocetsimulaci = 10000000; data1 = narozeniny[200, 365, pocetsimulaci, 4] pravdepodobnostuspechu:=N [data1/pocetsimulaci] intervalspolehlivosti = {N [data1 − Sqrt[pravdepodobnostuspechu ∗ (1 − pravdepodobnostuspechu)]∗ Quantile[NormalDistribution[0, 1], 0.995], 10], data1 + Sqrt[pravdepodobnostuspechu ∗ (1 − pravdepodobnostuspechu)]∗ Quantile[NormalDistribution[0, 1], 0.995]} Pˇr´ıloha je ˇreˇsena jako funkce se vstupn´ımi parametry: • n= poˇcet osob, d=poˇcet dn´ı, ve kter´ ych sledujeme shodu narozenin • opakovani=poˇcet simulac´ı • NarozeniVJedenDen=poˇcet shod narozenin v jeden den 33
Data1 zachycuj´ı poˇcet let, ve kter´ ych se narod´ı alespoˇ n zadan´ y poˇcet jedinc˚ u. Pˇri vysok´em poˇctu simulac´ı (> 1000000) m˚ uˇze v´ ypoˇcet trvat delˇs´ı dobu! Pˇ r´ıloha 4. 1.0 1 - ã-Λ 0.8 Λ
0.6 0.4 0.2
0.2
0.4
0.6
0.8
34
1.0
