A szita formula ´ es alkalmaz´ asai. Gyakran tal´ alkozunk az al´ abbi k´erd´essel, sokszor egy ¨ osszetett feladat r´eszfeladatak´ent. Tekints¨ unk bizonyos A1 , . . . , An esem´enyeket, ´es sz´am´ıtsuk ki annak a val´ osz´ın˝ us´eg´et, hogy legal´ abb az egyik¨ uk bek¨ovetkezik. Form´alisan megfogalmazva, sz´am´ıtsuk ki a P (A1 ∪ · · · ∪ An ) val´ osz´ın˝ us´eget. A k¨ ovetkez˝ o k´et fontos speci´alis esetben egyszer˝ uen meg tudjuk oldani ezt a feladatot: a) Ha az A1 , . . . , An esem´enyek diszjunktak, azaz Ai ∩ Aj = ∅, ha i 6= j, 1 ≤ i, j ≤ n, b) Ha az A1 , . . . , An esem´enyek f¨ uggetlenek. Az a) esetben P (A1 ∪ · · · ∪ An ) = P (A1 ) + · · · + P (An ). A b) esetben P (A1 ∪ · · · ∪ An ) = 1 − P (A1 ∪ · · · ∪ An ) = 1 − P (A¯1 ∩ · · · ∩ A¯n ) = 1 − P (A¯1 ) · · · P (A¯n ) = 1 − (1 − P (A1 )) · · · (1 − P (An )), ahol A¯ = Ω \ A az A esem´eny komplementer´et jel¨oli. (A fenti sz´amol´ asban kihaszn´ altuk azt az eredm´enyt, amely szerint, ha az A1 , . . . , An esem´enyek f¨ uggetlenek, akkor az A¯1 , . . . , A¯n esem´enyek is azok.) Mit mondhatunk az ´ altal´ anos esetben, ha a tekintett A1 , A2 , . . . , An esem´enyek nem felt´etlen¨ ul diszjunktak, ´es nem felt´etlen¨ ul f¨ uggetlenek? Ez nehezebb k´erd´es, ´es az ´ altal´ anos esetben a P (A1 ∪ · · · ∪ An ) val´ osz´ın˝ us´eget nem lehet kifejezni csak a P (Aj ) val´ osz´ın˝ us´egek seg´ıts´eg´evel. De ebben az esetben is van egy hasznos ´es tartalmas eredm´eny, az u ´gynevezett szita formula, amely lehet˝ ov´e teszi a P (A1 ∪ · · · ∪ An ) val´ osz´ın˝ us´eg kisz´ am´ıt´ as´at bizonyos plusz inform´ aci´ok seg´ıts´eg´evel. Ismertetem ezt az eredm´enyt. Tov´ abb´a t´argyalni fogok olyan feladatokat, amelyeket ennek az eredm´enynek a seg´ıts´eg´evel tudunk megoldani. A kombinatorik´ aban is van az ismertetetend˝ o eredm´enynek egy megfelel˝ oje, amelyet ´ szint´en szita formul´ anak neveznek. Erdemes ezt a k´et eredm´enyt, amelyek, mint k´es˝obb l´atni fogjuk val´ oj´aban ekvivalensek p´arhuzamosan ismertetni. Annak ´erdek´eben, hogy megk¨ ul¨ onb¨oztess¨ uk ˝ oket, kombinatorikus ´es val´ osz´ın˝ us´egsz´am´ıt´ asi szita formul´ ar´ ol fogok besz´elni. El˝osz¨ or a kombinatorikus szita formul´ at ismertetem: Legyen adva egy v´eges A halmaz, amely el˝ o´all bizonyos nem felt´etlen¨ ul diszjunkt Aj , 1 ≤ j ≤ n, halmazok A = A1 ∪ A2 ∪ · · · ∪ An uni´ojak´ent. Szeretn´enk megsz´ amolni az A halmaz elemeinek |A| sz´am´at. Tekints¨ unk egy olyan esetet, amikor erre k¨ ozvetlen¨ ul nem vagyunk k´epesek, de meg tudjuk sz´amolni az Aj halmazok elemeinek |Aj | sz´am´at minden 1 ≤ j ≤ n n P sz´amra. Ekkor az S1 = |Aj | mennyis´eg term´eszetes becsl´es lenne az |A| sz´amra. De j=1
ez csak egy fels˝o becsl´es az ´ altal´ anos esetben, mert egy olyan elemet, amely mind az Ai mind az Aj halmazban benne van valamely i 6= j indexp´arra k´etszer sz´amoltunk az S1 kifejez´esben holott csak egyszer kellett volna. Ezt korrig´ aland´o vezess¨ uk be az 1
S2 =
P
|Ai ∩ Aj | ¨ osszeget, ´es vegy¨ uk az S1 − S2 becsl´est. Ekkor azonban csak
1≤i<j≤n
az S1 − S2 ≤ |A| egyenl˝otlens´eget kapjuk, mert p´eld´aul egy olyan elemet, amely h´arom halmazban van benne h´aromszor sz´amoltuk az S1 ¨ osszegben ´es h´aromszor vontuk le az S2 o¨sszegben, teh´at az ilyen pontok l´etez´es´et nem vett¨ uk figyelembe az S1 − S2 becsl´esben. (Ha az Ai , Aj ´es Ak halmazban van a tekintett pont akkor pozit´ıv el˝ ojellel sz´amoltuk az S1 ¨ osszeg |Ai |, |Aj | ´es |Ak | tagjaiban ´es negat´ıv el˝ ojellel az S2 o¨sszeg |Ai ∩ Aj |, |Ai ∩A | ´ e s |A ∩A | tagjaiban.) Ez´ e rt korrig´ a ljuk ezt az o ¨ sszeget is. Vezess¨ uk be az j k Pk S3 = |Ai ∩Aj ∩Ak | kifejez´eseket. Ekkor be lehet l´atni, hogy S1 −S2 +S3 ≥ |A|. 1≤i<j
Ha azonoss´agot akarunk kapni akkor ezt a korrekci´ os elj´ar´ ast tov´ abb kell folytatni, mert p´eld´aul a 4 k¨ ul¨ onb¨oz˝ o Aj halmazban szerepl˝o elemeket figyelembe v´eve . . . A fenti, kiss´e nagyvonal´ uan t´argyalt gondolatmenetet r´eszletesebben kidolgozva ´es folytatva a k¨ ovetkez˝ o eredm´enyhez jutunk.
Kombinatorikus szita formula. Legyenek adva bizonyos v´eges sok elemet tartalmaz´ o A1 , . . . , An halmazok, ´es tekints¨ uk ezek A = A1 ∪ A2 ∪ · · · ∪ An uni´ oj´ at. Jel¨ olje |X| egy v´eges X halmaz elemeinek a sz´ am´ at. Az A halmaz elemeinek |A| sz´ am´ at a k¨ ovetkez˝ o formul´ aval fejezhetj¨ uk ki. Vezess¨ uk be az X
Sk =
|Aj1 ∩ · · · ∩ Ajk |,
1 ≤ k ≤ n,
1≤j1 <···<jk ≤n
mennyis´egeket. Ekkor |A| = |A1 ∪ · · · ∪ An | = S1 − S2 + S3 − · · · + (−1)n+1 Sn . Tov´ abb´ a, S1 − S2 =
n X
|Aj | −
X
|Aj ∩ Ak | ≤ |A| = |A1 ∪ · · · ∪ An | ≤ S1 =
1≤j
j=1
n X
|Aj |
j=1
´es a ´ltal´ aban 2l X
(−1)
k+1
Sk ≤ |A| = |A1 ∪ · · · ∪ An | ≤
k=1
2l−1 X
(−1)k+1 Sk
k=1
minden l ≥ 1 indexre. (Legyen Sk = 0, ha k > n.) Ez az egyenl˝ otlens´eg azt jelenti, hogy a kombinatorikus szita formul´ aban szerepl˝ o S1 − S2 + S3 − · · · el˝ ojeles o ¨sszeg p´ aratlan sz´ am´ u tagot tartalmaz´ o r´eszlet¨ osszegei fels˝ o ´es p´ aros sz´ am´ u tagot tartalmaz´ o r´eszlet¨ osszegei als´ o becsl´est adnak az |A| = |A1 ∪ · · · ∪ An | mennyis´egre. Ezen eredm´eny val´ osz´ın˝ us´egsz´am´ıt´ asi megfelel˝ oje, a val´ osz´ın˝ us´egsz´am´ıt´ asi szita formula hasonl´o eredm´enyt ´ all´ıt bizonyos A1 , . . . , An esem´enyek uni´oj´anak a val´ osz´ın˝ us´eg´er˝ ol. 2
Val´ osz´ın˝ us´ egsz´ am´ıt´ asi szita formula. Legyenek adva tetsz˝ oleges A1 , . . . , An esem´enyek egy (Ω, A, P ) val´ osz´ın˝ us´egi mez˝ on. Ekkor P (A1 ∪ · · · ∪ An ) = S1 − S2 + S3 − · · · + (−1)n+1 Sn , ahol Sk =
X
P (Aj1 ∩ · · · ∩ Ajk ),
1 ≤ k ≤ n.
1≤j1 <···<jk ≤n
Tov´ abb´ a, S1 − S2 =
n X
P (Aj ) −
P (Aj ∩ Ak ) ≤ P (A1 ∪ · · · ∪ An ) ≤ S1 =
1≤j
j=1
´es a ´ltal´ aban
X
2l X
(−1)
k+1
n X
P (Aj )
j=1
Sk ≤ P (A1 ∪ · · · ∪ An ) ≤
k=1
2l−1 X
(−1)k+1 Sk
k=1
minden l ≥ 1 indexre. (Legyen Sk = 0, ha k > n.) Ez az egyenl˝ otlens´eg azt jelenti, hogy a P (A1 ∪ · · · ∪ An ) val´ osz´ın˝ us´eget a szita formul´ aban kifejez˝ o S1 − S2 + S3 − · · · el˝ ojeles o ¨sszeg p´ aratlan sz´ am´ u tagot tartalmaz´ o r´eszlet¨ osszegei fel¨ ulr˝ ol ´es p´ aros sz´ am´ u tagot tartalmaz´ o r´eszlet¨ osszegei alulr´ ol becs¨ ulik meg a vizsg´ alt val´ osz´ın˝ us´eget. H´ azi feladat: Mutassuk meg, hogy a val´ osz´ın˝ us´egsz´am´ıt´ asi szita formula a kor´ abban ismertetett k´epleteket adja speci´alis esetk´ent diszjunkt vagy f¨ uggetlen A1 , . . . , An esem´enyek uni´oj´anak P (A1 ∪ · · · ∪ An ) val´ osz´ın˝ us´eg´ere. Mutatok egy olyan feladatot, amelyet viszonylag k¨ onnyen meg tudunk oldani az el˝ obb megfogalmazott val´ osz´ın˝ us´egsz´am´ıt´ asi szita formula seg´ıts´eg´evel. Feladat: Egy est´elyen megjelenik n h´azasp´ ar. Egy t´ancmester, aki nem tudja, hogy kik h´azast´ arsak ´es kik nem, v´eletlen m´ odon p´arba rendezi a f´erfiakat ´es n˝oket a t´anc el˝ ott. Mi a val´ osz´ın˝ us´ege annak, hogy egyetlen h´azasp´ ar sem t´ancol egy¨ utt? Mi ennek a val´ osz´ın˝ us´egnek a hat´ar´ert´eke, ha n → ∞? Megold´ as: Defini´ aljuk a k¨ ovetkez˝ o Aj esem´enyeket: Aj = a j-ik h´azasp´ ar egy¨ utt t´ancol, 1 ≤ j ≤ n. osz´ın˝ us´eg ´erdekel. Ekkor minket a P (A1 ∪ · · · ∪ An ) = 1 − P (A1 ∪ · · · ∪ An ) val´ Sz´ amoljuk ki a P (A1 ∪ · · · ∪ An ) val´ osz´ın˝ us´eget a val´ osz´ın˝ us´egsz´am´ıt´ asi szita formula seg´ıts´eg´evel. Ennek ´erdek´eben vegy¨ uk ´eszre, hogy a P (Aj1 ∩ · · · ∩ Ajk ) = (n−k)! azonoss´ag ´erv´enyes minden lehets´eges 1 ≤ j1 < · · · < jk ≤ n sz´am-k-asra. n! Ugyanis az ¨ osszes lehets´eges p´arba´ all´ıt´ asok sz´ama n!, m´ıg az olyan p´arba´ all´ıt´ asok sz´ama, amelyben a j1 -ik, j2 -ik, . . . , jk -ik h´azasp´ ar egy p´arba ker¨ ul (n − k)!. 3
Ez´ert aval´ osz´ın˝ us´egsz´am´ıt´ asi szita formul´ aban bevezetett Sk mennyis´eg ´ert´eke 1 = minden 1 ≤ k ≤ n sz´ a mra. Sk = nk (n−k)! n! k! Innen ad´ odik, hogy a minket ´erdekl˝ o val´ osz´ın˝ us´eg n h´azasp´ ar eset´en P (A1 ∪ · · · ∪ An ) = 1 − P (A1 ∪ · · · ∪ An ) n
= 1 − S1 + S2 + · · · + (−1) Sn =
n X (−1)k
k=0
k!
,
ahonnan P (A1 ∪ · · · ∪ An ) =
n X (−1)k
k=0
k!
→
∞ X (−1)k
k=0
k!
=
1 e
ha n → ∞.
Teh´ at nagy n sz´amra annak a val´ osz´ın˝ us´ege, hogy egy h´azasp´ ar sem fog egy¨ utt 1 t´ancolni k¨ ozel´ıt˝ oleg e . Mutatok h´arom m´ asik feladatot is, ahol a szita formula j´ ol alkalmazhat´o. 1. feladat: Egy urn´ab´ ol, amelyben az 1, . . . , n sz´amokat tartalmaz´ o lapok vannak, kih´ uzunk m lapot visszatev´essel. Minden lapot egyforma val´ osz´ın˝ us´eggel h´ uzunk. Mi annak a val´ osz´ın˝ us´ege, hogy az 1, . . . , k sz´amot tartalmaz´ o lapok mindegyik´et kih´ uztuk? Mi ennek a val´ osz´ın˝ us´egnek a hat´ar´ert´eke r¨ogz´ıtett k sz´amra ´es m = n h´ uz´ assz´ amra, ha n → ∞? Megold´ as: Jel¨olje Aj , 1 ≤ j ≤ k, azt az esem´enyt, hogy a j sz´amot tartal¯ egy B esem´eny komplementer´et. Ekkor maz´ o lapot nem h´ uztuk ki, ´es jel¨olje B a P (A¯1 ∩ A¯2 ∩ · · · ∩ A¯k ) = P (A1 ∪ A2 ∪ · · · ∪ Ak ) = 1 − P (A1 ∪ A2 ∪ · ·· ∪ Ak ) m minval´ osz´ın˝ us´eget kell kisz´ amolnunk. Tov´ abb´a, P (Aj1 ∩ A2 ∩ · · · ∩ Ajl ) = n−l n den r¨ogz´ıtett 1 ≤ j1 < · · · < jl ≤ k indexsorozatra, mert ez egy olyan esem´eny val´ osz´ın˝ us´eg´evel egyenl˝o, ahol m (egym´ ast´ ol f¨ uggetlen) h´ uz´ as mindegyik´eben n P lehet˝ os´eg k¨ oz¨ ul l sz´am kih´ uz´ as´at tiltjuk meg. Innen Sl = 1≤j1 <···<jl ≤k P (Aj1 ∩ n−l m k · · · ∩ Ajl ) = l , minden 1 ≤ l ≤ k indexre, ´es a szita formula alapj´ an a n k keresett val´ osz´ın˝ us´eg 1 − P (A1 ∪ A2 ∪ · · · ∪ Ak ) = 1 − S1 + S2 − · · · + (−1) Sk = k m P 1− (−1)l kl 1 − nl . Ennek hat´ar´ert´eke m = n ´es n → ∞ eset´en 1 − l=1
k P
l=1
(−1)l
k l
2. feladat:
e−l =
k P
l=0
k l
− 1e
l
= 1−
1 k , e
mert lim 1 − n→∞
l n n
= e−l .
Le´ırunk egy 20 hossz´ us´ ag´ u sz´ot, amelyik csak A, B, C ´es D bet˝ ut tartalmaz. V´alasszuk ki a sz´o mindegyik bet˝ uj´et egym´ ast´ ol f¨ uggetlen¨ ul egyforma val´ osz´ın˝ us´eggel. a.) Mi annak a val´ osz´ın˝ us´ege, hogy a fel´ırt sz´o mind a n´egy bet˝ ut tartalmazza? 4
b.) H´any olyan 20 hossz´ us´ ag´ u n´egy bet˝ us sz´o van, amelyik mind a n´egy bet˝ ut tartalmazza? Megold´ as: Jel¨olje, 1, 2, 3 ´es 4 a n´egy bet˝ ut. Ezzel a megfogalmaz´assal az a) r´esz megegyezik az els˝ o feladat probl´em´aj´aval, ha n = k = 4, ´es m = 20. Ez´ert az a) 4 20 P r´esz eredm´enye 1 − (−1)l 4l 1 − 4l . l=1
¨ Osszesen 420 20 hossz´ us´ ag´ u 4 bet˝ ub˝ ol ´ all´ o sz´ as´ab´ ol o van.4 Ez´ert az a) r´esz megold´ P 20 = 420 − k¨ ovetkezik, hogy a b) r´esz megold´ asa 420 1 − (−1)l 4l 1 − 4l l=1
4 P
(−1)l
l=1
4 l
420 − l . Ez az eredm´eny egy´ebk´ent k¨ ozvetlen¨ ul is levezethet˝ o a kom
binatorikus szita formula seg´ıts´eg´evel. 3. feladat:
Egy cornflake gy´art´ o c´eg minden dobozba betesz egy kupont, ´es o¨sszesen 10 k¨ ul¨onb¨oz˝ o kupont haszn´ al. Mekkora annak a val´ osz´ın˝ us´ege, hogy mind a 10 kupont megkapja egy olyan v´ as´arl´ o, aki 25 doboz cornflake-et vesz? Megold´ as: Jel¨olje Aj , 1 ≤ j ≤ 10, azt az esem´enyt, hogy a j-ik kupont megkapta ! 10 T a v´ as´arl´ o, ´es A¯j ennek az esem´enynek a komplementer´et. Ekkor a P Aj j=1 ! ! 10 10 T S val´ osz´ın˝ us´eget kell kisz´ amolnunk. Viszont P Aj = 1 − P A¯j , ´es j=1
P
10 S A¯j
j=1
!
=
10 P
k=1
(−1)k Sk , ahol Sk =
P
j=1
P (A¯j1 ∩ A¯j2 ∩ · · · ∩ A¯jk ), ´es a {j1 , . . . , jk }
indexhalmaz a fenti szumm´aban az {1, . . . , 10} halmaz ¨ osszes k elem˝ u r´eszhalmaz´ab´ ol ´ all. 25 , annak a val´ osz´ın˝ us´ege, hogy a lehets´eges Viszont P (A¯j1 ∩A¯j2 ∩· · ·∩A¯jk ) = 10−k 10 10 kuponb´ol mind a 25 v´ as´arl´ asn´ al a j1 , . . . jk index˝ u kuponokt´ ol k¨ ul¨ onb¨oz˝ o 10 − k 10−k 25 10 minden 1 ≤ k ≤ 10 indexre kupon valamelyik´et kapjuk. Ez´ert Sk = k ! 10 10 9 T P k 25 k = 10-re Sk = S10 = 0, ahonnan P Aj = . 1 − (−1)k 10 10 k j=1
k=0
A val´ osz´ın˝ us´egsz´am´ıt´ asi szita formula bizony´ıt´ as´at egy kieg´esz´ıt´esben fogom t´argyalni. Al´abb megmutatom, hogy a kombinatorikus szita formula egyszer˝ uen levezethet˝o a val´ osz´ın˝ us´egsz´am´ıt´ asi szita formul´ ab´ ol, ´es vice versa. A kombinatorikus szita formula igazol´asa ´erdek´eben tekints¨ unk bizonyos A1 , . . . , An v´eges halmazokat, ´es jel¨olj¨ uk e halmazok uni´oj´at A = A1 ∪ · · · ∪ An -nel. Legyen A = {x1 , . . . , xN } egy N elem˝ u halmaz, ´es vezess¨ uk be azt a val´ osz´ın˝ us´egi mez˝ ot, amelyben az A halmaz elemeit v´ alaszthatjuk ki egyenletes eloszl´ assal. R´eszletesebben kifejtve, a k¨ ovetkez˝ o (Ω, A, P ) val´ osz´ın˝ us´egi mez˝ ot defini´aljuk: Ω = A, A az A halmaz o¨sszes r´eszhalmaz´ ab´ ol ´ all´ o σ-algebra, P ({xj }) = N1 minden 1 ≤ j ≤ N sz´amra, ahonnan 5
P (B) = |B| N minden B ⊂ A halmazra. Megmutatom, hogy a kombinatorikus szita formul´ at megkaphatjuk a val´ osz´ın˝ us´egi szita formula seg´ıts´eg´evel, ha azt a most defini´alt (Ω, A, P ) val´ osz´ın˝ us´egi mez˝ on az A1 , . . . , An halmazokra alkalmazzuk. Jel¨olj¨ uk a kombinatorikus szita formul´ aban defini´alt Sj , 1 ≤ j ≤ n, o¨sszegek megfelel˝ oit a val´ osz´ın˝ us´egi szita formul´ aban S¯j -vel. Ekkor ny´ılv´an Sj = N S¯j . Tov´ abb´a, mivel P (A) = 1, a val´ osz´ın˝ us´egi szita formula azt adja, hogy S1 − S2 + S3 − · · · + n+1 ¯ ¯ ¯ (−1) Sn = N (S1 − S2 + S3 − · · · + (−1)n+1 S¯n ) = N P (A) = N , ´es mivel |A| = N , ezt kellett bizony´ıtanunk. A kombinatorikus szita formul´ aban megfogalmazott egyenl˝otlens´egek hasonl´oan vezethet˝ ok le ezen ´ all´ıt´ asok megfelel˝ oib˝ol a val´ osz´ın˝ us´egsz´am´ıt´ asi szita formul´ aban. Megford´ıtva, a val´ osz´ın˝ us´egsz´am´ıt´ asi szita formula is egyszer˝ uen levezethet˝ o a kombinatorikus szita formul´ ab´ ol. Annak ´erdek´eben, hogy ezt megtegy¨ uk tekints¨ uk azt az (Ω, A, P ) val´ osz´ın˝ us´egi mez˝ ot, ahol az A1 , . . . , An esem´enyek defini´alva vannak, ´es ¯ = B(ω) ¯ defini´aljuk minden ω ∈ Ω elemi esem´enyre ´es B ∈ A halmazra azt a B hal¯ ¯ mazt, amelyre B(ω) = {ω}, ha ω ∈ B, ´es B(ω) = ∅, ha ω ∈ / B. Fel´ırom a kombinatorikai szitaformul´ at az A¯1 (ω) ∪ · · · ∪ A¯n (ω) halmaz sz´amoss´ ag´ ara minden ω ∈ Ω elemi esem´enyre, majd megmutatom, hogy ezt az azonoss´agot az ω szerint ki´atlagolva, azaz v´ arhat´ o ´ert´eket v´eve megkapjuk a val´ osz´ın˝ us´egsz´am´ıt´ asi szita formul´ at. ¯ ¯ A kombinatorikai szita formula szerint |A1 (ω) ∪ · · · ∪ An (ω)| = S¯1 (ω) − S¯2 (ω) + P n+1 |A¯j1 (ω) ∩ · · · ∩ A¯jk (ω)| = S¯n (ω), ahol S¯k (ω) = S¯3 (ω) − · · · + (−1) 1≤j <···<j ≤n 1 k P IAj1 ∩···∩Ajk (ω), 1 ≤ k ≤ n. Itt ´es a tov´ abbiakban IB (ω) jel¨oli egy B ∈ A 1≤j1 <···<jk ≤n
halmaz indik´atorf¨ uggv´eny´et. Tov´ abb´a |A¯1 (ω) ∪ · · · ∪ A¯n (ω)| = IA1 ∪···∪An (ω). Teh´ at n+1 ¯ ¯ ¯ ¯ ¯ IA1 ∪···∪An (ω) = S1 (ω) − S2 (ω) + S3 (ω) − · · · + (−1) Sn (ω). Mivel E Sk (ω) = Sk . 1 ≤ k ≤ n, a fenti azonoss´agban v´ arhat´ o ´ert´eket v´eve megkapjuk a P (A1 ∪ · · · ∪ An ) = S1 − S2 + S3 − · · · + (−1)n+1 Sn azonoss´agot. A val´ osz´ın˝ us´egsz´am´ıt´ asi szita formul´ aban fel´ırt egyenl˝otlens´egek hasonl´oan bizony´ıthat´ oak. A 2l X
(−1)k+1 S¯k (ω) ≤ IA1 ∪···∪An (ω) ≤
k=1
2l−1 X
(−1)k+1 S¯k (ω)
k=1
egyenl˝otlens´eget kell fel´ırni a kombinatorikus szita formula seg´ıts´eg´evel, ´es v´ arhat´ o ´ert´eket kell venni ebben a rel´ aci´oban.
6
1. kieg´ esz´ıt´ es. A val´ osz´ın˝ us´egsz´ am´ıt´ asi szita formula ´es annak egy a ´ltal´ anos´ıt´ asa. A val´ osz´ın˝ us´egsz´am´ıt´ asi szita formula egy olyan bizony´ıt´ as´at ismertetem, amely egy onmag´ ¨ aban is ´erdekes, ´es m´ as esetekben is alkalmazhat´o eredm´enyen alapul. Ezt az al´ abbi lemm´aban fogalmazom meg. Lemma. Legyenek adva valamely A1 , . . . , An esem´enyek egy (Ω, A, P ) val´ osz´ın˝ us´egi mez˝ on, ´es defini´ aljuk ezek felhaszn´ al´ as´ aval v´eges sok uni´ o, metszet ´es komplementer seg´ıts´eg´evel bizonyos Bj = fj (A1 , . . . , An ), 1 ≤ j ≤ k, esem´enyeket. R¨ ogz´ıts¨ unk valamely c1 , . . . , ck val´ os sz´ amokat. A k X
cj P (Bj ) =
j=1
k X
cj P (fj (A1 , . . . , An )) ≥ 0
j=1
egyenl˝ otlens´eg teljes¨ ul tetsz˝ oleges val´ osz´ın˝ us´egi mez˝ on defini´ alt tetsz˝ oleges A1 , . . . , An n halmazokra, ha speci´ alisan teljes¨ ul abban a (2 sz´ am´ u) speci´ alis esetben, amikor mindegyik Aj halmaz vagy az Ω biztos vagy az ∅ u ¨res esem´eny. = Ω \ Aj az Aj halmaz komplementer´et. Vezess¨ uk A lemma bizony´ıt´ asa. Jel¨olje A−1 j 1 be az Aj = Aj jel¨ol´est, ´es jel¨olj¨on (k1 , . . . , kn ), kj = ±1, 1 ≤ j ≤ n, valamely n hossz´ us´ ag´ u ±1 sorozatot. ´Irjuk fel mindegyik Bj = fj (A1 , . . . , An ) esem´enyt konjunkt´ıv norm´ alforma alakban. Felhaszn´alva, hogy a konjunkt´ıv norm´ alform´ aban diszjunkt halmazok uni´oja jelenik meg, a vizsg´aland´o egyenl˝otlens´eg fel´ırhat´ o X (A) d(k1 , . . . , kn )P Ak11 ∩ · · · ∩ Aknn ≥ 0 (k1 ,...,kn ): kj =±1, j=1,...,n
alakban alkalmas d(k1 , . . . , kn ) egy¨ utthat´okkal. Az (A) egyenl˝otlens´eg ny´ılv´an ´erv´enyes minden A1 , . . . , An halmazrendszerre, ha d(k1 , . . . , kn ) ≥ 0 minden (k1 , . . . , kn ) argumentumra. Ez´ert el´eg megmutatni, hogy amennyiben az (A) egyenl˝otlens´eg teljes¨ ul minden olyan speci´ alis esetben, amikor az Aj , 1 ≤ j ≤ n, halmazok mindegyike vagy az Ω biztos vagy az ∅ u ¨res esem´eny, akkor d(k1 , . . . , kn ) ≥ 0 az o¨sszes (k1 , . . . , kn ) argumentumra. Ezt megmutatand´ o, r¨ogz´ıts¨ unk egy n hossz´ us´ ag´ u (k1 , . . . , kn ) ±1 sorozatot, ´es defini´aljuk ennek seg´ıts´eg´evel A1 , . . . , An halmazoknak azt a sorozat´at, amelyre Aj = Ω, ha kj = 1, ´es Aj = ∅, ha kj = −1, 1 ≤ j ≤ n. Ezzel a v´ alaszt´ assal az (A) formula baloldal´ an szerepl˝o kifejez´es d(k1 , . . . , kn )-nel egyenl˝o, ez´ert ez csak u ´gy lehet nem negat´ıv, ha d(k1 , . . . , kn ) ≥ 0. Mivel ezt az ´ervet minden lehets´eges (k1 , . . . , kn ) ±1 sorozatra alkalmazhatjuk innen k¨ ovetkezik a lemma ´ all´ıt´ asa. A val´ osz´ın˝ us´egsz´ am´ıt´ asi szita formula bizony´ıt´ asa a lemma seg´ıts´eg´evel. A lemma alapj´ an a val´ osz´ın˝ us´egsz´am´ıt´ asi szita formula azonoss´ag´ at elegend˝ o abban a speci´ alis esetben bel´ atni, ha mindegyik Aj esem´eny vagy a biztos vagy az u ¨res esem´eny. Ekkor ugyanis a szita formula azonoss´ag´ aban szerepl˝o kifejez´esek bal ´es jobboldal´ an szerepl˝o formul´ ak k¨ ul¨ onbs´eg´er˝ ol tudjuk, hogy az egyr´eszt nagyobb vagy egyenl˝o, m´ asr´eszt kisebb egyenl˝o, mint nulla. Ez´ert az null´ aval egyenl˝o. Tekints¨ uk azokat az eseteket, amikor az Aj 7
esem´enyek k¨ oz¨ ott r darab biztos ´es n − r u ¨res esem´eny van, 0 ≤ r ≤ n. Feltehetj¨ uk, hogy r ≥ 1, mert r = 0 eset´en, amikor mindegyik Aj esem´eny az u ¨res halmaz, az r azonoss´ag mindk´et oldala null´ aval egyenl˝o. Ha 1 ≤ r ≤ n, akkor Sl = l az 1 ≤ l ≤ r esetben, ´es Sl = 0, ha l > r. Ez´ert az 1 ≤ r ≤ n esetben a szita formula jobboldal´ an a´ll´ o r r r P P P kifejez´es (−1)l+1 Sl = (−1)l+1 rl = 1 − (−1)l rl = 1 − (1 − 1)r = 1, a baloldali l=1
l=1
l=0
kifejez´es pedig szint´en P (A1 ∪ · · · ∪ An ) = P (Ω) = 1. Hasonl´ o meggondol´asok alapj´ an a szita formul´ aban megfogalmazott egyenl˝otlens´es s P P gek igazol´as´ahoz el´eg azt megmutatni, hogy 1− (−1)l+1 rl ≤ 0, azaz (−1)l rl ≤ 0,
ha 1 ≤ s ≤ r, ´es s p´aratlan sz´am, ´es
s P
l=0
l=1
(−1)l
l=0
r l
≥ 0, ha 1 ≤ s ≤ r, ´es s p´aros
sz´am. (A bizony´ıtand´ o´ all´ıt´ as ezen redukci´ oj´ahoz u ´gy jutunk a fenti lemma seg´ıts´eg´evel, hogy r-val jel¨olj¨ uk azon Aj halmazok sz´am´at, amelyekre Aj = Ω, ´es fel´ırjuk, hogy mit jelent a lemma szerint bizony´ıtand´ o ´ all´ıt´ as ebben az esetben. Az r = 0 esetben az ellen˝ orizend˝ o egyenl˝otlens´egek nyilv´anval´ oan teljes¨ ulnek, mert ekkor minden tekintett kifejez´es null´ aval egyenl˝o.) A bizony´ıtand´ o egyenl˝otlens´egek k¨ ovetkeznek az al´ abbi tartalmasabb azonoss´agb´ol. s X r−1 r , 0 ≤ s ≤ r. = (−1)s (−1)l s l l=0
Ez azonoss´ag ny´ılv´anval´ o az s = 0 esetben, az ´ altal´ anos esetben pedig az s v´ altoz´ o s P s r−1 s r szerinti indukci´ oval kapjuk, hogy (−1)l rl = (−1)s−1 r−1 s . s−1 + (−1) s = (−1) l=0
Ismertetem a szita formula egy hasonl´oan bizony´ıthat´ o´ altal´ anos´ıt´ as´at.
A szita formula egy ´ altal´ anos´ıt´ asa. Legyenek adva tetsz˝ oleges A1 , . . . , An esem´enyek egy (Ω, A, P ) val´ osz´ın˝ us´egi mez˝ on, ´es vezess¨ uk be az N = N (ω) val´ osz´ın˝ us´egi v´ altoz´ ot, amely egyen˝ o azon j indexek sz´ am´ aval, amelyekre az ω ∈ Aj rel´ aci´ o teljes¨ ul. Ekkor n−r X i i+r Si+r , minden 0 ≤ r ≤ n sz´ amra, P (N = r) = (−1) i i=0 ahol S0 = 1,
Sk =
X
P (Ai1 ∩ · · · ∩ Aik ) ,
1 ≤ k ≤ n.
1≤i1 <···
Tov´ abb´ a ezen o ¨sszeg r´eszlet¨ osszegei felv´ altva als´ o illetve fels˝ o becsl´est adnak a tekintett val´ osz´ın˝ us´egekre, azaz s X i i+r (−1) Si+r ≥ P (N = r) ha 0 ≤ s ≤ n − r ´es s p´ aros sz´ am. i i=0 ´es
s X i=0
(−1)
i
i+r Si+r ≤ P (N = r) i
ha 0 ≤ s ≤ n − r ´es s p´ aratlan sz´ am. 8
Megjegyz´es. Mivel P (N = 0) = 1 − P (A1 ∪ · · · ∪ An ) ´es S0 = 1 ez az eredm´eny az r = 0 esetben megegyezik a szita formul´ aval. A szita formula a ´ltal´ anos´ıt´ as´ anak a bizony´ıt´ asa. A szita formula bizony´ıt´ as´ahoz hasonl´oan ebben az esetben is reduk´ alhatjuk a bizony´ıtand´ o ´ all´ıt´ as igazol´as´at arra a speci´alis esetre, amikor a tekintett Aj esem´enyek k¨ oz¨ ott k darab Ω biztos ´es n − k darab u ¨res esem´eny van, 0 ≤ k ≤ n. S˝ot, azt is feltehetj¨ uk, hogy k > r. Ugyanis k < r eset´en a fel´ırt azonoss´ag illetve egyenl˝otlens´egek mind a k´et oldala 0-val, m´ıg k = r eset´en 1-gyel egyenl˝o. Ugyanis Sr+i = 0, ha r + i > k, ami minden i ≥ 0-ra teljes¨ ul, ha k < r. Ez´ert ebben az esetben a tekintett azonoss´ag ´es egyenl˝otlens´egek jobboldal´ an 0 all. A k = r esetben Sr+i = 0, ha i ≥ 1, ´es Sr+0 = 1. M´asr´eszt P (N = r) = 0, ha ´ k 6= r, ´es P (N = r) = k, ha k = r. Ezekb˝ol az ´ all´ıt´ asokb´ol k¨ ovetkezik az a´ll´ıt´ as fenti redukci´ oj´anak a jogoss´aga. M´asr´eszt a tekintett speci´alis esetben (amikor pontosan biztos esem´eny k kdarab k k−r k = , ´es i+r van, ´es a t¨obbi n − k esem´eny pedig u ¨res) Sr+i = r+i i . Innen r i+r i a bizony´ıtand´ o azonoss´ag jobboldal´ an ´ all´ o kifejez´es n−r n−r n−r X X X k−r k i k i i+r i i+r = Sr+i = (−1) (−1) (−1) r i i r+i i i=0 i=0 i=0 k−r k−r k X k X i k−r (1 − 1)k−r = 0, = (−1) = r i=0 i r i=0 ha k > r. Innen k¨ ovetkezik, hogy a fel´ırt azonoss´ag val´ oban ´erv´enyes. Az egyenl˝otlenk−r P s´egek bizony´ıt´ asa hasonl´o, csak ebben az esetben a sz´amol´ as v´eg´en a =0 (−1)i k−r i
azonoss´ag helyett a szita formula bizony´ıt´ asa sor´ an m´ ar igazolt a 0 ≤ s ≤ k − r ´es s p´aros sz´am, ´es
s P
s P
i=0
(−1)i
i=0
(−1)i
i=0
sz´am egyenl˝otlens´egeket kell haszn´ alni.
k−r i
k−r i
≥ 0, ha
≤ 0, ha 0 ≤ s ≤ k − r ´es s p´aratlan
Bebizony´ıtok egy hasonl´o azonoss´agot, amelyben a P (N ≥ r) val´ osz´ın˝ us´eget sz´amoljuk ki az Sk mennyis´egek seg´ıts´eg´evel, azaz annak a val´ osz´ın˝ us´eg´et, hogy legal´ abb r darab Aj esem´eny k¨ ovetkezett be. Megmutatom, hogy ez a formula egyszer˝ uen levezethet˝o az el˝ oz˝ o eredm´enyben bizony´ıtott a P (N = r) val´ osz´ın˝ us´eget kifejez˝ o azonoss´agb´ol. Formula a P (N ≥ r) val´ osz´ın˝ us´ eg kifejez´ es´ ere. A szita formula el˝ obb megfogalmazott a ´ltal´ anos´ıt´ as´ aban bevezetett jel¨ ol´eseket alkalmazva fel´ırhatjuk a n−r X i i+r−1 P (N ≥ r) = Si+r , minden 1 ≤ r ≤ n sz´ amra, (−1) i i=0 azonoss´ agot, ahol
S0 = 1,
Sk =
X
P (Ai1 ∩ · · · ∩ Aik ) ,
1≤i1 <···
9
1 ≤ k ≤ n.
A formula bizony´ıt´ asa. A k´eplet r = n-re ´erv´enyes, mert P (N ≥ n) = Sn , ´es az azonoss´ag jobboldal´ an ´ all´ o kifejez´es is ezzel egyenl˝o az r = n esetben. (Ekkor az o¨sszeg csak az i = 0 tagot tartalmazza.) Az azonoss´agot r szerinti backward indukci´ oval ´es a P (N = r) kifejez´esre m´ ar bizony´ıtott azonoss´ag seg´ıts´eg´evel bizony´ıtjuk be. Ugyanis, ha az azonoss´agot tudjuk r + 1-re, akkor fel´ırhatjuk a P (N ≥ r) = P (N = r) + P (N ≥ r + 1) n−r−1 n−r X X i i+r i i+r Si+r+1 Si+r + (−1) = (−1) i i i=0 i=0 azonoss´agot. Mivel
n−r−1 P
(−1)i
i=0
juk, hogy
n−r X
i+r i
Si+r+1 =
n−r P i=1
(−1)i−1
i+r−1 i−1
Si+r , innen azt kap-
i+r i+r−1 P (N ≥ r) = − (−1) Si+r + Sr i i − 1 i=1 n−r X i i+r−1 Si+r + Sr , = (−1) i i=1 mivel
i+r i
=
i−r−1 i−1
Feladat:
+
i+r−1 i
i
, ´es ezt az azonoss´agot kellett bizony´ıtani.
Tekints¨ uk a jegyzet elej´en megfogalmazott p´eld´at, ´es sz´amoljuk ki az a´ltal´ anos´ıtott szita formula seg´ıts´eg´evel annak val´ osz´ın˝ us´eg´et, hogy pontosan r, r ≥ 0, h´azasp´ ar t´ancol egy¨ utt. Mi e val´ osz´ın˝ us´eg hat´ar´ert´eke, ha n → ∞? 1 . Ez´ert az Megold´ as: Az eredeti feladat megold´ asa sor´ an kisz´ amoltuk, hogy Sk = k! altal´ ´ anos´ıtott szita formula alapj´ an annak a val´ osz´ın˝ us´ege, hogy az n h´azasp´ arb´ol all´ ´ o t´arsas´agban az egy¨ utt t´ancol´ o h´azasp´ arok Nn sz´ama pontosan r P (Nn = r) =
n−r X i=0
(−1)
i
n−r n−r X 1 1 X i+r 1 i i+r (−1)i . = Si+r = (−1) (i + r)! r! i=0 i! i i i=0
Innen
∞
1 X 11 1 lim P (N = r) = . (−1)i = n→∞ r! i=0 i! r! e Megjegyz´es. Az el˝ oz˝ o feladat eredm´enye speci´alisan azt jelenti, hogy a feladatban tekintett egym´ assal t´ancol´ o h´azasp´ arok sz´am´anak eloszl´ asa tart az 1 param´eter˝ u Poisson eloszl´ ashoz, ha n → ∞. 10
Tekints¨ uk a k¨ ovetkez˝ o m´ odos´ıtott feladatot. Legyen adva n h´azasp´ ar, ´es t´ancoljanak a feles´egek egym´ as ut´ an egy v´eletlen¨ ul kiv´alasztott f´erfival u ´gy, hogy minden f´erfit egyforma val´ osz´ın˝ us´eggel v´ alasztanak, ´es minden egyes ilyen p´ arv´ alaszt´ as f¨ uggetlen egym´ ast´ ol. (Lehets´eges, hogy lesz olyan f´erj, amely t¨obbsz¨ or, illetve olyan f´erj, amely egyszer sem t´ancolt.) K´erd´es: Mi annak a val´ osz´ın˝ us´ege, hogy pontosan r feles´eg t´ancolt a f´erj´evel? Mi ennek a val´ osz´ın˝ us´egnek a hat´ar´ert´eke r¨ogz´ıtett r sz´amra, ha a h´azasp´ arok n sz´ama tart a v´egtelenhez? Ezt a feladatot a benne szerepl˝o f¨ uggetlens´egi tulajdons´agok miatt k¨ onnyen meg 1 r n 1 n−r lehet oldani. Nevezetesen a keresett val´ osz´ın˝ us´eg ´ert´eke r n 1− n , aminek a n−r 1 −1 = hat´ar´ert´eke r¨ogz´ıtett r sz´amra n → ∞ eset´en r! e . (Vegy¨ uk ´eszre, hogy 1 − n1 −r n r 1 1 − n1 → e−1 , ´es nr n1 → r! 1 − n1 , ha n → ∞.) Egy´ebk´ent a kapott eredm´eny a f¨ uggetlen val´ osz´ın˝ us´egi v´ altoz´ okra vonatkoz´ o Poisson eloszl´ as´ u hat´areloszl´ast´etel speci´ alis esete, amely azt adja, hogy a keresett hat´ar´ert´ek megegyezik annak a val´ osz´ın˝ us´eg´evel, hogy egy 1 param´eter˝ u Poisson eloszl´ as´ u val´osz´ın˝ us´egi v´ altoz´ o az r ´ert´eket veszi fel. Teh´ at a tekintett k´et feladatban ugyanaz a hat´areloszl´as jelent meg. Ez a k¨ ovetkez˝ o t´ennyel van kapcsolatban. Az eredeti feladatban az a megk¨ ot´es, hogy az a f´erj, akit egyszer kijel¨ oltek t´ancpartnernek nem v´ alaszthat´o m´egegyszer t´ancpartnernek a f¨ uggetlen p´arv´ alaszt´ as bizonyos megszor´ıt´ as´at jelenti, de ez egy nagyon enyhe megszor´ıt´ as. Ez´ert a f´erj¨ ukkel t´ancol´ o feles´egek sz´ama fel´ırhat´ o, mint olyan val´ osz´ın˝ us´egi v´ altoz´ ok osszege, amelyek ugyan nem f¨ ¨ uggetlenek, de majdnem azok. Ez´ert o¨sszeg¨ uk hasonl´o hat´areloszl´ast´etelt teljes´ıt, mint amilyennel a f¨ uggetlen esetben tal´ alkoztunk. 2. kieg´ esz´ıt´ es. A vizsg´ alt hat´ areloszl´ ast´etel egy m´ as bizony´ıt´ asa. Tanuls´ agos lehet megmutatni, hogy hogyan lehet egyszer˝ uen (a szita formula haszn´ alata n´elk¨ ul) bebizony´ıtani azt, hogy az e jegyzet feladat´aban vizsg´alt egy¨ utt t´ancol´ o h´azasp´arok sz´am´anak a hat´areloszl´asa az 1 param´eter˝ u Poisson eloszl´ as, ha a h´azasp´ arok sz´ama tart a v´egtelenhez. A bizony´ıt´ as a k¨ ovetekez˝ o k´et lemm´an alapul. 1. lemma. Tekints¨ uk a k¨ ovetkez˝ o feladatot. Egy est´elyen megjelenik n h´ azasp´ ar. Egy t´ ancmester, aki nem tudja, hogy kik h´ azast´ arsak ´es kik nem, v´eletlen m´ odon p´ arba rendezi a f´erfiakat ´es n˝ oket a t´ anc el˝ ott. Jel¨ olje Tn az egy¨ utt t´ ancol´ o h´ azasp´ arok sz´ am´ at. Tn 1 amra. Mutassuk meg, hogy E k = k! minden 1 ≤ k ≤ n sz´
2. lemma. Legyen ζ = ζλ egy λ param´eter˝ u Poisson eloszl´ as´ u val´ osz´ın˝ us´egi v´ altoz´ o. λk ζ Ekkor E k = k! minden k = 1, 2, . . . sz´ amra
1. lemma bizony´ıt´ asa. Vezess¨ uk be minden 1 ≤ j1 < j2 < · · · < jk ≤ n k hossz´ us´ ag´ u sorozatra a k¨ ovetkez˝ o η(j1 , . . . , jk ) val´ osz´ın˝ us´egi v´ altoz´ ot: η(j1 , . . . , jk ) = 1, ha a j1 -ik, j2 -ik, . . . jk -ik h´azasp´ arok mindegyike egym´ assal t´ancol, ´es η(j1 , . . . , jk ) = 0 egy´ebk´ent. Ekkor X Tn = η(j1 , . . . , jk ), k 1≤j1 <···<jk ≤n
11
ahonnan
Tn = E k
Viszont Eη(j1 , . . . , jk ) =
(n−k)! n! ,
X
Eη(j1 , . . . , jk ).
1≤j1 <···<jk ≤n
ahonnan E
2. lemma bizony´ıt´ asa.
Tn k
=
n (n−k)! k n!
=
1 k! ,
amint a´ll´ıtottuk.
X ∞ n ∞ ∞ X n λ −λ 1 λn−k ζ λk −λ X λn−k λk −λ k E = e =e λ = e = . k n! k! (n − k)! k! (n − k)! k! k n=k
n=k
n=k
Az 1. ´es 2. lemm´ab´ ol k¨ ovetkezik, hogy az 1. lemm´aban defini´alt Tn valamint egy a 2. lemm´aban tekintett ζ = ζ1 λ = 1 param´eter˝ u Poisson eloszl´ as´ u val´ osz´ın˝ us´egi v´ altoz´ ok momentumaira ´erv´enyes a lim ETnk = Eζ k azonoss´ag minden k = 1, 2, . . . n→∞ sz´amra. Val´ oban, vegy¨ uk ´eszre, hogy a E T0n = E ζ0 = 1, ami az ott megfogalmazott η es all´ıt´ ´ a sok megfelel˝ o je az ‘elfajul´ o ’ k = 0 esetben. Tov´ a bb´ a megadhat´ o az E k kifejez´ η 1 1 k k−1 + · · · + B1,k Eη + B0,k ) alak´ u E k = k! Eη(η − 1) · · · (η − k + 1) = k! (Eη + Bk−1,k Eη form´aban alkalmas Bj,k , 0 ≤ j ≤ k − 1 konstansokkal. Ezen konstansok ´ert´ekeit explicit m´ odon meg lehet adni, de erre nem lesz sz¨ uks´eg¨ unk. Ebb˝ ol a rel´ aci´ob´ ol az is k¨ ovetkezik, hogy az Eη k momentumot ki lehet fejezni az E ηj , 0 ≤ j ≤ k, kifejez´esek line´aris kombin´aci´ojak´ent. Az ETnk momentum hasonl´oan kifejezhet˝o az E Tjn , 0 ≤ j ≤ k, kifejez´esek line´aris kombin´aci´ojak´ent ugyanazon egy¨ utthat´okkal. Ebb˝ ol a t´enyb˝ol, illetve k k az 1. ´es 2. lemm´ab´ ol k¨ ovetkezik, hogy lim ETn = Eζ minden k = 0, 1, 2, . . . sz´amra, n→∞ amint ´ all´ıtottam. Viszont a val´ osz´ın˝ us´egsz´am´ıt´ as alapvet˝ o eredm´enyeib˝ol k¨ ovetkezik, hogy ha teljes¨ ul k k a lim ETn = Eζ rel´ aci´o minden k = 0, 1, 2, . . . sz´amra ´es egy Poisson eloszl´ as´ u ζ n→∞ val´ osz´ın˝ us´egi v´ altoz´ ora, akkor a Tn val´ osz´ın˝ us´egi v´ altoz´ ok eloszl´ asban konverg´ alnak a ζ val´ osz´ın˝ us´egi v´ altoz´ ohoz. Az, hogy eloszl´ asok momentumainak a konvergenci´ aj´ab´ ol egy Poisson eloszl´ as´ u val´ osz´ın˝ us´egi v´ altoz´ o momentumaihoz k¨ ovetkezik az eloszl´ asok konvergenci´ aj´a ezen Poisson eloszl´ as´ u val´ osz´ın˝ us´egi v´ altoz´ o eloszl´ as´ahoz k¨ ovetkezik a k¨ ovetkez˝ o h´arom feladat eredm´enyeib˝ol. Val´ oj´aban egy ´elesebb ´ all´ıt´ as is k¨ ovetkezik ezen feladatok eredm´enyeib˝ol. Az, hogy ha eloszl´ asok egy sorozat´anak minden momentuma konverg´ al egy olyan eloszl´ as megfelel˝ o momentum´ ahoz, amelynek eloszl´ as´at egy´ertelm˝ uen meghat´ arozz´ ak momentumai, akkor az eloszl´ asok sorozata konverg´al ehhez az eloszl´ ashoz. 1. feladat: Legyen adva µnR, n = 1, 2, . . . , val´ osz´ın˝ us´egi m´ert´ekek egy olyan sorozata, amelyre l´etezik a lim xk µn ( dx) = Bk < ∞ hat´ar´ert´ek minden k = 1, 2, . . . indexre. n→∞ Ekkor a µn sorozat relative kompakt, azaz minden µnk r´eszsorozat´anak van µnkj eloszl´ asban konvergens r´eszsorozata.
12
2. feladat: Legyen adva µn , n = 1, 2, . . . , val´ osz´ın˝ us´egi m´ert´ekek egy olyan sorozata, amely eloszl´ konverg´ al egy µ0 val´ osz´ın˝ us´egi m´ert´ekhez, tov´ abb´a amelyre l´etezik a Rasban k lim x µn ( dx) = Bk < ∞ hat´ar´ert´ek minden k = 1, 2, . . . indexre. Ekkor ez a n→∞ R hat´ar´ert´ek teljes´ıti a Bk = xk µ0 ( dx) rel´ aci´ot minden k = 1, 2, . . . indexre. 3. feladat: Legyen µn , n = osz´ın˝ us´egi m´ert´ekek egy olyan sorozata, amelyre R adva R 1,k 2, . . . , val´ k lim x µn ( dx) = x µ0 ( dx) minden k = 1, 2, . . . indexre valamely µ0 val´ osz´ın˝ un→∞ s´egi m´ert´ekkel. Ha a µ0 m´ert´eket meghat´ arozz´ ak momentumai, akkor a µn sorozat eloszl´ asban konverg´ al a µ0 val´ osz´ın˝ us´egi m´ert´ekhez.
Seg´ıts´eg: Az els˝ o feladat megold´ as´aban a val´ osz´ın˝ us´egsz´am´ıt´ as a´ltal´ anos eredm´enyei alapj´ an el´eg ellen˝ orizni, hogy minden ε > 0 sz´amhoz l´etezik olyan K = K(ε) sz´am, amelyre µn (x: |x| R > K) < ε minden n = 1, 2, . . . indexre. Ez igaz, mert a feladat felt´etelei szerint x2 µn ( dx) < B alkalmas B > 0 sz´ammal minden n indexre. RA RA A gyenge konvergenci´ ab´ ol k¨ ovetkezik, hogy lim −A xk µn ( dx) = −A xk µ0 ( dx) n→∞ minden olyan A sz´amra, amely folytonoss´agi pontja a µ0 m´ert´eknek. Ahhoz, hogy a 2. feladatot ennek alapj´ an A → ∞ hat´ar´ atmenettel megoldjuk el´eg bel´ atni, hogy minden k eg´ e sz ´ e s ε > 0 val´ o s sz´ a mra l´ e tezik olyan B = B(k, ε) sz´ a m, amelyR R k k re x: |x|>B |x| µn ( dx) < ε minden n indexre. Viszont x: |x|>B |x| µn ( dx) < R R 1 |x|2k µn ( dx) < B1k |x|2k µn ( dx) < ε minden n ≥ 1 indexre, ha B el´eg B k x: |x|>B nagy. N´emi plusz munk´ aval l´athat´ o, hogy ez a becsl´es n = 0 indexre is ´erv´enyes. A 3. feladat ´ all´ıt´ asa egyszer˝ uen k¨ ovetkezik az els˝ o ´es m´ asodik feladat eredm´eny´eb˝ ol.
13
