A szita formula és alkalmazásai.

Gyakran találkozunk az alábbi kérdéssel, sokszor egy összetett feladat részfeladataként. Tekintsünk bizonyos A_{1}, …, A_{n} eseményeket, és számítsuk ki annak a valószínűségét, hogy legalább az egyikük bekövetkezik. Formálisan megfogalmazva, számítsuk ki a P (A_{1} ∪ ⋯ ∪ A_{n}) valószínűséget.

A következő két fontos speciális esetben egyszerűen meg tudjuk oldani ezt a feladatot:

a) Ha az A_{1}, …, A_{n} események diszjunktak, azaz A_{i} ∩ A_{j} = ∅, ha i ≠ j, 1 ≤ i, j ≤ n,

b) Ha az A_{1}, …, A_{n} események függetlenek.

Az a) esetben

P (A_{1} ∪ ⋯ ∪ A_{n}) = P (A_{1}) + ⋯ + P (A_{n}).

A b) esetben

P (A_{1} ∪ ⋯ ∪ A_{n}) = 1 − P (\overline{A_{1} ∪ ⋯ ∪ A_{n}}) = 1 − P (Ā_{1} ∩ ⋯ ∩ Ā_{n})
= 1 − P (Ā_{1}) ⋯ P (Ā_{n}) = 1 − (1 − P (A_{1})) ⋯ (1 − P (A_{n})),

ahol Ā = Ω \ A az A esemény komplementerét jelöli. (A fenti számolásban kihasználtuk azt az eredményt, amely szerint, ha az A_{1}, …, A_{n} események függetlenek, akkor az Ā_{1}, …, Ā_{n} események is azok.)

Mit mondhatunk az általános esetben, ha a tekintett A_{1}, A_{2}, …, A_{n} események nem feltétlenül diszjunktak, és nem feltétlenül függetlenek? Ez nehezebb kérdés, és az általános esetben a P (A_{1} ∪ ⋯ ∪ A_{n}) valószínűséget nem lehet kifejezni csak a P (A_{j}) valószínűségek segítségével. De ebben az esetben is van egy hasznos és tartalmas eredmény, az úgynevezett szita formula, amely lehetővé teszi a P (A_{1} ∪ ⋯ ∪ A_{n}) valószínűség kiszámítását bizonyos plusz információk segítségével. Ismertetem ezt az eredményt. Továbbá tárgyalni fogok olyan feladatokat, amelyeket ennek az eredménynek a segítségével tudunk megoldani.

A kombinatorikában is van az ismertetetendő eredménynek egy megfelelője, amelyet szintén szita formulának neveznek. Érdemes ezt a két eredményt, amelyek, mint később látni fogjuk valójában ekvivalensek párhuzamosan ismertetni. Annak érdekében, hogy megkülönböztessük őket, kombinatorikus és valószínűségszámítási szita formuláról fogok beszélni.

Először a kombinatorikus szita formulát ismertetem: Legyen adva egy véges A halmaz, amely előáll bizonyos nem feltétlenül diszjunkt A_{j}, 1 ≤ j ≤ n, halmazok A = A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{n} uniójaként. Szeretnénk megszámolni az A halmaz elemeinek |A| számát. Tekintsünk egy olyan esetet, amikor erre közvetlenül nem vagyunk képesek, de meg tudjuk számolni az A_{j} halmazok elemeinek |A_{j}| számát minden 1 ≤ j ≤ n

számra. Ekkor az S_{1} = ∑_{j=1}^{n} |A_{j}| mennyiség természetes becslés lenne az |A| számra. De

ez csak egy felső becslés az általános esetben, mert egy olyan elemet, amely mind az A_{i} mind az A_{j} halmazban benne van valamely i ≠ j indexpárra kétszer számoltunk az S_{1} kifejezésben holott csak egyszer kellett volna. Ezt korrigálandó vezessük be az S_{2} = ∑_{1≤i<j≤n} |A_{i} ∩ A_{j}| összeget, és vegyük az S_{1} − S_{2} becslést. Ekkor azonban csak

az S_{1} − S_{2} ≤ |A| egyenlőtlenséget kapjuk, mert például egy olyan elemet, amely három halmazban van benne háromszor számoltuk az S_{1} összegben és háromszor vontuk le az S_{2} összegben, tehát az ilyen pontok létezését nem vettük figyelembe az S_{1} − S_{2} becslésben. (Ha az A_{i}, A_{j} és A_{k} halmazban van a tekintett pont akkor pozitív előjellel számoltuk az S_{1} összeg |A_{i}|, |A_{j}| és |A_{k}| tagjaiban és negatív előjellel az S_{2} összeg |A_{i} ∩ A_{j}|, |A_{i}∩A_{k}| és |A_{j} ∩A_{k}| tagjaiban.) Ezért korrigáljuk ezt az összeget is. Vezessük be az S_{3} = ∑_{1≤i<j<k≤n} |A_{i}∩A_{j}∩A_{k}| kifejezéseket. Ekkor be lehet látni, hogy S_{1}−S_{2}+S_{3} ≥ |A|.

Ha azonosságot akarunk kapni akkor ezt a korrekciós eljárást tovább kell folytatni, mert például a 4 különböző A_{j} halmazban szereplő elemeket figyelembe véve … A fenti, kissé nagyvonalúan tárgyalt gondolatmenetet részletesebben kidolgozva és folytatva a következő eredményhez jutunk.

Kombinatorikus szita formula. Legyenek adva bizonyos véges sok elemet tartalmazó A_{1}, …, A_{n} halmazok, és tekintsük ezek A = A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{n} unióját. Jelölje |X| egy véges X halmaz elemeinek a számát. Az A halmaz elemeinek |A| számát a következő formulával fejezhetjük ki. Vezessük be az

S_{k} = ∑_{1≤j_{1}<···<j_{k}≤n} |A_{j_{1}} ∩ ⋯ ∩ A_{j_{k}}|, 1 ≤ k ≤ n,

mennyiségeket. Ekkor

|A| = |A_{1} ∪ ⋯ ∪ A_{n}| = S_{1} − S_{2} + S_{3} − ⋯ + (−1)^{n+1}S_{n}.

Továbbá,

S_{1} − S_{2} = ∑_{j=1}^{n} |A_{j}| − ∑_{1≤j<k≤n} |A_{j} ∩ A_{k}| ≤ |A| = |A_{1} ∪ ⋯ ∪ A_{n}| ≤ S_{1} = ∑_{j=1}^{n} |A_{j}|

és általában

∑_{k=1}^{2l}(−1)^{k+1}S_{k} ≤ |A| = |A_{1} ∪ ⋯ ∪ A_{n}| ≤ ∑_{k=1}^{2l−1}(−1)^{k+1}S_{k}

minden l ≥ 1 indexre. (Legyen S_{k} = 0, ha k > n.) Ez az egyenlőtlenség azt jelenti, hogy a kombinatorikus szita formulában szereplő S_{1} − S_{2} + S_{3} − ⋯ előjeles összeg páratlan számú tagot tartalmazó részletösszegei felső és páros számú tagot tartalmazó részletösszegei alsó becslést adnak az |A| = |A_{1} ∪ ⋯ ∪ A_{n}| mennyiségre.

Ezen eredmény valószínűségszámítási megfelelője, a valószínűségszámítási szita formula hasonló eredményt állít bizonyos A_{1}, …, A_{n} események uniójának a valószínűségéről.

Valószínűségszámítási szita formula. Legyenek adva tetszőleges A_{1}, …, A_{n} események egy (Ω, A, P) valószínűségi mezőn. Ekkor

P (A_{1} ∪ ⋯ ∪ A_{n}) = S_{1} − S_{2} + S_{3} − ⋯ + (−1)^{n+1}S_{n},

ahol

S_{k} = ∑_{1≤j_{1}<···<j_{k}≤n} P (A_{j_{1}} ∩ ⋯ ∩ A_{j_{k}}), 1 ≤ k ≤ n.

Továbbá,

S_{1} − S_{2} = ∑_{j=1}^{n} P (A_{j}) − ∑_{1≤j<k≤n} P (A_{j} ∩ A_{k}) ≤ P (A_{1} ∪ ⋯ ∪ A_{n}) ≤ S_{1} = ∑_{j=1}^{n} P (A_{j})

és általában

∑_{k=1}^{2l}(−1)^{k+1}S_{k} ≤ P (A_{1} ∪ ⋯ ∪ A_{n}) ≤ ∑_{k=1}^{2l−1}(−1)^{k+1}S_{k}

minden l ≥ 1 indexre. (Legyen S_{k} = 0, ha k > n.) Ez az egyenlőtlenség azt jelenti, hogy a P (A_{1} ∪ ⋯ ∪ A_{n}) valószínűséget a szita formulában kifejező S_{1} − S_{2} + S_{3} − ⋯ előjeles összeg páratlan számú tagot tartalmazó részletösszegei felülről és páros számú tagot tartalmazó részletösszegei alulról becsülik meg a vizsgált valószínűséget.

Házi feladat: Mutassuk meg, hogy a valószínűségszámítási szita formula a korábban ismertetett képleteket adja speciális esetként diszjunkt vagy független A_{1}, …, A_{n} események uniójának P (A_{1} ∪ ⋯ ∪ A_{n}) valószínűségére.

Mutatok egy olyan feladatot, amelyet viszonylag könnyen meg tudunk oldani az előbb megfogalmazott valószínűségszámítási szita formula segítségével.

Feladat:

Egy estélyen megjelenik n házaspár. Egy táncmester, aki nem tudja, hogy kik házastársak és kik nem, véletlen módon párba rendezi a férfiakat és nőket a tánc előtt. Mi a valószínűsége annak, hogy egyetlen házaspár sem táncol együtt? Mi ennek a valószínűségnek a határértéke, ha n → ∞? Megoldás: Definiáljuk a következő A_{j} eseményeket:

A_{j} = a j-ik házaspár együtt táncol, 1 ≤ j ≤ n.

Ekkor minket a P (\overline{A_{1} ∪ ⋯ ∪ A_{n}}) = 1 − P (A_{1} ∪ ⋯ ∪ A_{n}) valószínűség érdekel. Számoljuk ki a P (A_{1} ∪ ⋯ ∪ A_{n}) valószínűséget a valószínűségszámítási szita formula segítségével. Ennek érdekében vegyük észre, hogy a P (A_{j_{1}} ∩ ⋯ ∩ A_{j_{k}}) = \frac{(n−k)!}{n!} azonosság érvényes minden lehetséges 1 ≤ j_{1} < ⋯ < j_{k} ≤ n szám-k-asra. Ugyanis az összes lehetséges párbaállítások száma n!, míg az olyan párbaállítások száma, amelyben a j_{1}-ik, j_{2}-ik, …, j_{k}-ik házaspár egy párba kerül (n − k)!.

Ezért a valószínűségszámítási szita formulában bevezetett S_{k} mennyiség értéke S_{k} = \binom{n}{k} \frac{(n−k)!}{n!} = \frac{1}{k!} minden 1 ≤ k ≤ n számra. Innen adódik, hogy a minket érdeklő valószínűség n házaspár esetén

P (\overline{A_{1} ∪ ⋯ ∪ A_{n}}) = 1 − P (A_{1} ∪ ⋯ ∪ A_{n})

= 1 − S_{1} + S_{2} + ⋯ + (−1)^{n}S_{n} = ∑_{k=0}^{n} \frac{(−1)^{k}}{k!} ,

ahonnan

P (\overline{A_{1} ∪ ⋯ ∪ A_{n}}) = ∑_{k=0}^{n} \frac{(−1)^{k}}{k!} → ∑_{k=0}^{∞} \frac{(−1)^{k}}{k!} = \frac{1}{e} ha n → ∞.

Tehát nagy n számra annak a valószínűsége, hogy egy házaspár sem fog együtt táncolni közelítőleg \frac{1}{e}.

Mutatok három másik feladatot is, ahol a szita formula jól alkalmazható.

1. feladat:

Egy urnából, amelyben az 1, …, n számokat tartalmazó lapok vannak, kihúzunk m lapot visszatevéssel. Minden lapot egyforma valószínűséggel húzunk. Mi annak a valószínűsége, hogy az 1, …, k számot tartalmazó lapok mindegyikét kihúztuk? Mi ennek a valószínűségnek a határértéke rögzített k számra és m = n húzásszámra, ha n → ∞? Megoldás: Jelölje A_{j}, 1 ≤ j ≤ k, azt az eseményt, hogy a j számot tartalmazó lapot nem húztuk ki, és jelölje B̄ egy B esemény komplementerét. Ekkor a P (Ā_{1} ∩ Ā_{2} ∩ ⋯ ∩ Ā_{k}) = P (\overline{A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{k}}) = 1 − P (A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{k}) valószínűséget kell kiszámolnunk. Továbbá, P (A_{j_{1}} ∩ A_{2} ∩ ⋯ ∩ A_{j_{l}}) = (\frac{n−l}{n})^{m} minden rögzített 1 ≤ j_{1} < ⋯ < j_{l} ≤ k indexsorozatra, mert ez egy olyan esemény valószínűségével egyenlő, ahol m (egymástól független) húzás mindegyikében n lehetőség közül l szám kihúzását tiltjuk meg. Innen S_{l} = ∑_{1≤j_{1}<···<j_{l}≤k} P (A_{j_{1}} ∩ ⋯ ∩ A_{j_{l}}) = \binom{k}{l} (\frac{n−l}{n})^{m}, minden 1 ≤ l ≤ k indexre, és a szita formula alapján a keresett valószínűség 1 − P (A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{k}) = 1 − S_{1} + S_{2} − ⋯ + (−1)^{k}S_{k} =

1 − ∑_{l=1}^{k}(−1)^{l}\binom{k}{l} (1 − \frac{l}{n})^{m}. Ennek határértéke m = n és n → ∞ esetén 1 −

∑_{l=1}^{k}(−1)^{l}\binom{k}{l}e^{−l} = ∑_{l=0}^{k} \binom{k}{l} (−\frac{1}{e})^{l} = (1 − \frac{1}{e})^{k}, mert lim_{n→∞} (1 − \frac{l}{n})^{n} = e^{−l}.

2. feladat:

Leírunk egy 20 hosszúságú szót, amelyik csak A, B, C és D betűt tartalmaz. Válasszuk ki a szó mindegyik betűjét egymástól függetlenül egyforma valószínűséggel. a.) Mi annak a valószínűsége, hogy a felírt szó mind a négy betűt tartalmazza? b.) Hány olyan 20 hosszúságú négy betűs szó van, amelyik mind a négy betűt

tartalmazza? Megoldás: Jelölje, 1, 2, 3 és 4 a négy betűt. Ezzel a megfogalmazással az a) rész megegyezik az első feladat problémájával, ha n = k = 4, és m = 20. Ezért az a)

rész eredménye 1 − ∑_{l=1}^{4}(−1)^{l}\binom{4}{l} (1 − \frac{l}{4})^{20}.

Összesen 4^{20} 20 hosszúságú 4 betűből álló szó van. Ezért az a) rész megoldásából

következik, hogy a b) rész megoldása 4^{20} (1 − ∑_{l=1}^{4}(−1)^{l}\binom{4}{l} (1 − \frac{l}{4})^{20}) = 4^{20} −

∑_{l=1}^{4}(−1)^{l}\binom{4}{l} (4^{20} − l). Ez az eredmény egyébként közvetlenül is levezethető a kom-

binatorikus szita formula segítségével.

3. feladat:

Egy cornflake gyártó cég minden dobozba betesz egy kupont, és összesen 10 különböző kupont használ. Mekkora annak a valószínűsége, hogy mind a 10 kupont megkapja egy olyan vásárló, aki 25 doboz cornflake-et vesz? Megoldás: Jelölje A_{j}, 1 ≤ j ≤ 10, azt az eseményt, hogy a j-ik kupont megkapta

a vásárló, és Ā_{j} ennek az eseménynek a komplementerét. Ekkor a P ( ⋂_{j=1}^{10} A_{j})

valószínűséget kell kiszámolnunk. Viszont P ( ⋂_{j=1}^{10} A_{j}) = 1 − P ( ⋃_{j=1}^{10} Ā_{j}), és

P ( ⋃_{j=1}^{10} Ā_{j}) = ∑_{k=1}^{10}(−1)^{k}S_{k}, ahol S_{k} = ∑ P (Ā_{j_{1}} ∩ Ā_{j_{2}} ∩ ⋯ ∩ Ā_{j_{k}}), és a {j_{1}, …, j_{k}}

indexhalmaz a fenti szummában az {1, …, 10} halmaz összes k elemű részhalmazából áll. Viszont P (Ā_{j_{1}}∩Ā_{j_{2}}∩⋯∩Ā_{j_{k}}) = (\frac{10−k}{10} )^{25}, annak a valószínűsége, hogy a lehetséges 10 kuponból mind a 25 vásárlásnál a j_{1}, … j_{k} indexű kuponoktól különböző 10−k kupon valamelyikét kapjuk. Ezért S_{k} = \binom{10}{k} (\frac{10−k}{10} )^{25} minden 1 ≤ k ≤ 10 indexre

k = 10-re S_{k} = S_{10} = 0, ahonnan P ( ⋂_{j=1}^{10} A_{j}) = ∑_{k=0}^{9}(−1)^{k}\binom{10}{k} (1 − \frac{k}{10})^{25}.

A valószínűségszámítási szita formula bizonyítását egy kiegészítésben fogom tárgyalni. Alább megmutatom, hogy a kombinatorikus szita formula egyszerűen levezethető a valószínűségszámítási szita formulából, és vice versa.

A kombinatorikus szita formula igazolása érdekében tekintsünk bizonyos A_{1}, …, A_{n} véges halmazokat, és jelöljük e halmazok unióját A = A_{1} ∪ ⋯ ∪ A_{n}-nel. Legyen A = {x_{1}, …, x_{N}} egy N elemű halmaz, és vezessük be azt a valószínűségi mezőt, amelyben az A halmaz elemeit választhatjuk ki egyenletes eloszlással. Részletesebben kifejtve, a következő (Ω, A, P) valószínűségi mezőt definiáljuk: Ω = A, A az A halmaz összes részhalmazából álló σ-algebra, P (\{x_{j}\}) = \frac{1}{N} minden 1 ≤ j ≤ N számra, ahonnan P (B) = \frac{|B|}{N} minden B ⊂ A halmazra. Megmutatom, hogy a kombinatorikus szita formulát megkaphatjuk a valószínűségi szita formula segítségével, ha azt a most definiált (Ω, A, P) valószínűségi mezőn az A_{1}, …, A_{n} halmazokra alkalmazzuk.

Jelöljük a kombinatorikus szita formulában definiált S_{j}, 1 ≤ j ≤ n, összegek megfelelőit a valószínűségi szita formulában S̄_{j}-vel. Ekkor nyílván S_{j} = NS̄_{j}. Továbbá, mivel P (A) = 1, a valószínűségi szita formula azt adja, hogy S_{1} − S_{2} + S_{3} − ⋯ + (−1)^{n+1}S_{n} = N(S̄_{1} − S̄_{2} + S̄_{3} − ⋯ + (−1)^{n+1}S̄_{n}) = NP (A) = N, és mivel |A| = N, ezt kellett bizonyítanunk. A kombinatorikus szita formulában megfogalmazott egyenlőtlenségek hasonlóan vezethetők le ezen állítások megfelelőiből a valószínűségszámítási szita formulában.

Megfordítva, a valószínűségszámítási szita formula is egyszerűen levezethető a kombinatorikus szita formulából. Annak érdekében, hogy ezt megtegyük tekintsük azt az (Ω, A, P) valószínűségi mezőt, ahol az A_{1}, …, A_{n} események definiálva vannak, és definiáljuk minden ω ∈ Ω elemi eseményre és B ∈ A halmazra azt a B̄ = B̄(ω) halmazt, amelyre B̄(ω) = {ω}, ha ω ∈ B, és B̄(ω) = ∅, ha ω ∉ B. Felírom a kombinatorikai szitaformulát az Ā_{1}(ω) ∪ ⋯ ∪ Ā_{n}(ω) halmaz számosságára minden ω ∈ Ω elemi eseményre, majd megmutatom, hogy ezt az azonosságot az ω szerint kiátlagolva, azaz várható értéket véve megkapjuk a valószínűségszámítási szita formulát.

A kombinatorikai szita formula szerint |Ā_{1}(ω) ∪ ⋯ ∪ Ā_{n}(ω)| = S̄_{1}(ω) − S̄_{2}(ω) +

S̄_{3}(ω) − ⋯ + (−1)^{n+1}S̄_{n}(ω), ahol S̄_{k}(ω) = ∑_{1≤j_{1}<···<j_{k}≤n} |Ā_{j_{1}}(ω) ∩ ⋯ ∩ Ā_{j_{k}}(ω)| =

∑_{1≤j_{1}<···<j_{k}≤n} I_{A_{j_{1}} ∩···∩A_{j_{k}}} (ω), 1 ≤ k ≤ n. Itt és a továbbiakban I_{B}(ω) jelöli egy B ∈ A

halmaz indikátorfüggvényét. Továbbá |Ā_{1}(ω) ∪ ⋯ ∪ Ā_{n}(ω)| = I_{A_{1}∪···∪A_{n}}(ω). Tehát I_{A_{1}∪···∪A_{n}}(ω) = S̄_{1}(ω) − S̄_{2}(ω) + S̄_{3}(ω) − ⋯ + (−1)^{n+1}S̄_{n}(ω). Mivel ES̄_{k}(ω) = S_{k}. 1 ≤ k ≤ n, a fenti azonosságban várható értéket véve megkapjuk a P (A_{1} ∪ ⋯ ∪ A_{n}) = S_{1} − S_{2} + S_{3} − ⋯ + (−1)^{n+1}S_{n} azonosságot. A valószínűségszámítási szita formulában felírt egyenlőtlenségek hasonlóan bizonyíthatóak. A

∑_{k=1}^{2l}(−1)^{k+1}S̄_{k}(ω) ≤ I_{A_{1}∪···∪A_{n}}(ω) ≤ ∑_{k=1}^{2l−1}(−1)^{k+1}S̄_{k}(ω)

egyenlőtlenséget kell felírni a kombinatorikus szita formula segítségével, és várható értéket kell venni ebben a relációban.

1. kiegészítés. A valószínűségszámítási szita formula és annak egy általánosítása.

A valószínűségszámítási szita formula egy olyan bizonyítását ismertetem, amely egy önmagában is érdekes, és más esetekben is alkalmazható eredményen alapul. Ezt az alábbi lemmában fogalmazom meg.

Lemma. Legyenek adva valamely A_{1}, …, A_{n} események egy (Ω, A, P) valószínűségi mezőn, és definiáljuk ezek felhasználásával véges sok unió, metszet és komplementer segítségével bizonyos B_{j} = f_{j}(A_{1}, …, A_{n}), 1 ≤ j ≤ k, eseményeket. Rögzítsünk valamely c_{1}, …, c_{k} valós számokat. A

∑_{j=1}^{k} c_{j}P (B_{j}) = ∑_{j=1}^{k} c_{j}P (f_{j}(A_{1}, …, A_{n})) ≥ 0

egyenlőtlenség teljesül tetszőleges valószínűségi mezőn definiált tetszőleges A_{1}, …, A_{n} halmazokra, ha speciálisan teljesül abban a (2^{n} számú) speciális esetben, amikor mindegyik A_{j} halmaz vagy az Ω biztos vagy az ∅ üres esemény.

A lemma bizonyítása. Jelölje A_{j}^{−1} = Ω \ A_{j} az A_{j} halmaz komplementerét. Vezessük be az A_{j}^{1} = A_{j} jelölést, és jelöljön (k_{1}, …, k_{n}), k_{j} = ±1, 1 ≤ j ≤ n, valamely n hosszúságú ±1 sorozatot. Írjuk fel mindegyik B_{j} = f_{j}(A_{1}, …, A_{n}) eseményt konjunktív normálforma alakban. Felhasználva, hogy a konjunktív normálformában diszjunkt halmazok uniója jelenik meg, a vizsgálandó egyenlőtlenség felírható

(A)  ∑_{(k_{1},...,k_{n}): k_{j}=±1, j=1,...,n} d(k_{1}, …, k_{n})P (A_{1}^{k_{1}} ∩ ⋯ ∩ A_{n}^{k_{n}}) ≥ 0

alakban alkalmas d(k_{1}, …, k_{n}) együtthatókkal. Az (A) egyenlőtlenség nyílván érvényes minden A_{1}, …, A_{n} halmazrendszerre, ha d(k_{1}, …, k_{n}) ≥ 0 minden (k_{1}, …, k_{n}) argumentumra. Ezért elég megmutatni, hogy amennyiben az (A) egyenlőtlenség teljesül minden olyan speciális esetben, amikor az A_{j}, 1 ≤ j ≤ n, halmazok mindegyike vagy az Ω biztos vagy az ∅ üres esemény, akkor d(k_{1}, …, k_{n}) ≥ 0 az összes (k_{1}, …, k_{n}) argumentumra.

Ezt megmutatandó, rögzítsünk egy n hosszúságú (k_{1}, …, k_{n}) ±1 sorozatot, és definiáljuk ennek segítségével A_{1}, …, A_{n} halmazoknak azt a sorozatát, amelyre A_{j} = Ω, ha k_{j} = 1, és A_{j} = ∅, ha k_{j} = −1, 1 ≤ j ≤ n. Ezzel a választással az (A) formula baloldalán szereplő kifejezés d(k_{1}, …, k_{n})-nel egyenlő, ezért ez csak úgy lehet nem negatív, ha d(k_{1}, …, k_{n}) ≥ 0. Mivel ezt az érvet minden lehetséges (k_{1}, …, k_{n}) ±1 sorozatra alkalmazhatjuk innen következik a lemma állítása.

A valószínűségszámítási szita formula bizonyítása a lemma segítségével. A lemma alapján a valószínűségszámítási szita formula azonosságát elegendő abban a speciális esetben belátni, ha mindegyik A_{j} esemény vagy a biztos vagy az üres esemény. Ekkor ugyanis a szita formula azonosságában szereplő kifejezések bal és jobboldalán szereplő formulák különbségéről tudjuk, hogy az egyrészt nagyobb vagy egyenlő, másrészt kisebb egyenlő, mint nulla. Ezért az nullával egyenlő. Tekintsük azokat az eseteket, amikor az A_{j} események között r darab biztos és n − r üres esemény van, 0 ≤ r ≤ n. Feltehetjük, hogy r ≥ 1, mert r = 0 esetén, amikor mindegyik A_{j} esemény az üres halmaz, az azonosság mindkét oldala nullával egyenlő. Ha 1 ≤ r ≤ n, akkor S_{l} = \binom{r}{l} az 1 ≤ l ≤ r esetben, és S_{l} = 0, ha l > r. Ezért az 1 ≤ r ≤ n esetben a szita formula jobboldalán álló

kifejezés ∑_{l=1}^{r}(−1)^{l+1}S_{l} = ∑_{l=1}^{r}(−1)^{l+1}\binom{r}{l} = 1 − ∑_{l=0}^{r}(−1)^{l}\binom{r}{l} = 1 − (1 − 1)^{r} = 1, a baloldali

kifejezés pedig szintén P (A_{1} ∪ ⋯ ∪ A_{n}) = P (Ω) = 1.

Hasonló meggondolások alapján a szita formulában megfogalmazott egyenlőtlensé-

gek igazolásához elég azt megmutatni, hogy 1− ∑_{l=1}^{s}(−1)^{l+1}\binom{r}{l} ≤ 0, azaz ∑_{l=0}^{s}(−1)^{l}\binom{r}{l} ≤ 0,

ha 1 ≤ s ≤ r, és s páratlan szám, és ∑_{l=0}^{s}(−1)^{l}\binom{r}{l} ≥ 0, ha 1 ≤ s ≤ r, és s páros

szám. (A bizonyítandó állítás ezen redukciójához úgy jutunk a fenti lemma segítségével, hogy r-val jelöljük azon A_{j} halmazok számát, amelyekre A_{j} = Ω, és felírjuk, hogy mit jelent a lemma szerint bizonyítandó állítás ebben az esetben. Az r = 0 esetben az ellenőrizendő egyenlőtlenségek nyilvánvalóan teljesülnek, mert ekkor minden tekintett kifejezés nullával egyenlő.)

A bizonyítandó egyenlőtlenségek következnek az alábbi tartalmasabb azonosságból.

∑_{l=0}^{s}(−1)^{l}\binom{r}{l} = (−1)^{s}\binom{r − 1}{s}, 0 ≤ s ≤ r.

Ez azonosság nyílvánvaló az s = 0 esetben, az általános esetben pedig az s változó

szerinti indukcióval kapjuk, hogy ∑_{l=0}^{s}(−1)^{l}\binom{r}{l} = (−1)^{s−1}\binom{r−1}{s−1} + (−1)^{s}\binom{r}{s} = (−1)^{s}\binom{r−1}{s}.

Ismertetem a szita formula egy hasonlóan bizonyítható általánosítását.

A szita formula egy általánosítása. Legyenek adva tetszőleges A_{1}, …, A_{n} események egy (Ω, A, P) valószínűségi mezőn, és vezessük be az N = N(ω) valószínűségi változót, amely egyenő azon j indexek számával, amelyekre az ω ∈ A_{j} reláció teljesül. Ekkor

P (N = r) = ∑_{i=0}^{n−r}(−1)^{i}\binom{i + r}{i}S_{i+r}, minden 0 ≤ r ≤ n számra,

ahol

S_{0} = 1, S_{k} = ∑_{1≤i_{1}<···<i_{k}≤n} P (A_{i_{1}} ∩ ⋯ ∩ A_{i_{k}}) , 1 ≤ k ≤ n.

Továbbá ezen összeg részletösszegei felváltva alsó illetve felső becslést adnak a tekintett valószínűségekre, azaz

∑_{i=0}^{s}(−1)^{i}\binom{i + r}{i}S_{i+r} ≥ P (N = r) ha 0 ≤ s ≤ n − r és s páros szám.

és

∑_{i=0}^{s}(−1)^{i}\binom{i + r}{i}S_{i+r} ≤ P (N = r) ha 0 ≤ s ≤ n − r és s páratlan szám.

Megjegyzés. Mivel P (N = 0) = 1 − P (A_{1} ∪ ⋯ ∪ A_{n}) és S_{0} = 1 ez az eredmény az r = 0 esetben megegyezik a szita formulával.

A szita formula általánosításának a bizonyítása. A szita formula bizonyításához hasonlóan ebben az esetben is redukálhatjuk a bizonyítandó állítás igazolását arra a speciális esetre, amikor a tekintett A_{j} események között k darab Ω biztos és n − k darab üres esemény van, 0 ≤ k ≤ n. Sőt, azt is feltehetjük, hogy k > r. Ugyanis k < r esetén a felírt azonosság illetve egyenlőtlenségek mind a két oldala 0-val, míg k = r esetén 1-gyel egyenlő. Ugyanis S_{r+i} = 0, ha r + i > k, ami minden i ≥ 0-ra teljesül, ha k < r. Ezért ebben az esetben a tekintett azonosság és egyenlőtlenségek jobboldalán 0 áll. A k = r esetben S_{r+i} = 0, ha i ≥ 1, és S_{r+0} = 1. Másrészt P (N = r) = 0, ha k ≠ r, és P (N = r) = k, ha k = r. Ezekből az állításokból következik az állítás fenti redukciójának a jogossága.

Másrészt a tekintett speciális esetben (amikor pontosan k darab biztos esemény van, és a többi n − k esemény pedig üres) S_{r+i} = \binom{k}{r+i}, és \binom{i+r}{i}\binom{k}{i+r} = \binom{k}{r}\binom{k−r}{i}. Innen a bizonyítandó azonosság jobboldalán álló kifejezés

∑_{i=0}^{n−r}(−1)^{i}\binom{i + r}{i}S_{r+i} = ∑_{i=0}^{n−r}(−1)^{i}\binom{i + r}{i}\binom{k}{r + i} = ∑_{i=0}^{n−r}(−1)^{i}\binom{k}{r}\binom{k − r}{i}

= \binom{k}{r} ∑_{i=0}^{k−r}(−1)^{i}\binom{k − r}{i} = \binom{k}{r} ∑_{i=0}^{k−r}(1 − 1)^{k−r} = 0,

ha k > r. Innen következik, hogy a felírt azonosság valóban érvényes. Az egyenlőtlen-

ségek bizonyítása hasonló, csak ebben az esetben a számolás végén a ∑_{i=0}^{k−r}(−1)^{i}\binom{k−r}{i} = 0

azonosság helyett a szita formula bizonyítása során már igazolt a ∑_{i=0}^{s}(−1)^{i}\binom{k−r}{i} ≥ 0, ha

0 ≤ s ≤ k − r és s páros szám, és ∑_{i=0}^{s}(−1)^{i}\binom{k−r}{i} ≤ 0, ha 0 ≤ s ≤ k − r és s páratlan

szám egyenlőtlenségeket kell használni.

Bebizonyítok egy hasonló azonosságot, amelyben a P (N ≥ r) valószínűséget számoljuk ki az S_{k} mennyiségek segítségével, azaz annak a valószínűségét, hogy legalább r darab A_{j} esemény következett be. Megmutatom, hogy ez a formula egyszerűen levezethető az előző eredményben bizonyított a P (N = r) valószínűséget kifejező azonosságból.

Formula a P (N ≥ r) valószínűség kifejezésére. A szita formula előbb megfogalmazott általánosításában bevezetett jelöléseket alkalmazva felírhatjuk a

P (N ≥ r) = ∑_{i=0}^{n−r}(−1)^{i}\binom{i + r − 1}{i}S_{i+r}, minden 1 ≤ r ≤ n számra,

azonosságot, ahol

S_{0} = 1, S_{k} = ∑_{1≤i_{1}<···<i_{k}≤n} P (A_{i_{1}} ∩ ⋯ ∩ A_{i_{k}}) , 1 ≤ k ≤ n.

A formula bizonyítása. A képlet r = n-re érvényes, mert P (N ≥ n) = S_{n}, és az azonosság jobboldalán álló kifejezés is ezzel egyenlő az r = n esetben. (Ekkor az összeg csak az i = 0 tagot tartalmazza.) Az azonosságot r szerinti backward indukcióval és a P (N = r) kifejezésre már bizonyított azonosság segítségével bizonyítjuk be. Ugyanis, ha az azonosságot tudjuk r + 1-re, akkor felírhatjuk a

P (N ≥ r) = P (N = r) + P (N ≥ r + 1)

= ∑_{i=0}^{n−r}(−1)^{i}\binom{i + r}{i}S_{i+r} + ∑_{i=0}^{n−r−1}(−1)^{i}\binom{i + r}{i}S_{i+r+1}

azonosságot. Mivel ∑_{i=0}^{n−r−1}(−1)^{i}\binom{i+r}{i}S_{i+r+1} = ∑_{i=1}^{n−r}(−1)^{i−1}\binom{i+r−1}{i−1}S_{i+r}, innen azt kap-

juk, hogy

P (N ≥ r) = ∑_{i=1}^{n−r}(−1)^{i} (\binom{i + r}{i} − \binom{i + r − 1}{i − 1}) S_{i+r} + S_{r}

= ∑_{i=1}^{n−r}(−1)^{i}\binom{i + r − 1}{i}S_{i+r} + S_{r},

mivel \binom{i+r}{i} = \binom{i−r−1}{i−1} + \binom{i+r−1}{i}, és ezt az azonosságot kellett bizonyítani.

Feladat:

Tekintsük a jegyzet elején megfogalmazott példát, és számoljuk ki az általánosított szita formula segítségével annak valószínűségét, hogy pontosan r, r ≥ 0, házaspár táncol együtt. Mi e valószínűség határértéke, ha n → ∞? Megoldás: Az eredeti feladat megoldása során kiszámoltuk, hogy S_{k} = \frac{1}{k!}. Ezért az általánosított szita formula alapján annak a valószínűsége, hogy az n házaspárból álló társaságban az együtt táncoló házaspárok N_{n} száma pontosan r

P (N_{n} = r) = ∑_{i=0}^{n−r}(−1)^{i}\binom{i + r}{i}S_{i+r} = ∑_{i=0}^{n−r}(−1)^{i}\binom{i + r}{i}\frac{1}{(i + r)!} = \frac{1}{r!} ∑_{i=0}^{n−r}(−1)^{i} \frac{1}{i!}.

Innen

lim_{n→∞} P (N = r) = \frac{1}{r!} ∑_{i=0}^{∞}(−1)^{i} \frac{1}{i!} = \frac{1}{r!} \frac{1}{e}.

Megjegyzés. Az előző feladat eredménye speciálisan azt jelenti, hogy a feladatban tekintett egymással táncoló házaspárok számának eloszlása tart az 1 paraméterű Poisson eloszláshoz, ha n → ∞.

Tekintsük a következő módosított feladatot. Legyen adva n házaspár, és táncoljanak a feleségek egymás után egy véletlenül kiválasztott férfival úgy, hogy minden férfit egyforma valószínűséggel választanak, és minden egyes ilyen párválasztás független egymástól. (Lehetséges, hogy lesz olyan férj, amely többször, illetve olyan férj, amely egyszer sem táncolt.) Kérdés: Mi annak a valószínűsége, hogy pontosan r feleség táncolt a férjével? Mi ennek a valószínűségnek a határértéke rögzített r számra, ha a házaspárok n száma tart a végtelenhez?

Ezt a feladatot a benne szereplő függetlenségi tulajdonságok miatt könnyen meg lehet oldani. Nevezetesen a keresett valószínűség értéke \binom{n}{r} (\frac{1}{n})^{r} (1 − \frac{1}{n})^{n−r}, aminek a határértéke rögzített r számra n → ∞ esetén \frac{1}{r!}e^{−1}. (Vegyük észre, hogy (1 − \frac{1}{n})^{n−r} = (1 − \frac{1}{n})^{−r} (1 − \frac{1}{n})^{n} → e^{−1}, és \binom{n}{r} (\frac{1}{n})^{r} → \frac{1}{r!}, ha n → ∞.) Egyébként a kapott eredmény a független valószínűségi változókra vonatkozó Poisson eloszlású határeloszlástétel speciális esete, amely azt adja, hogy a keresett határérték megegyezik annak a valószínűségével, hogy egy 1 paraméterű Poisson eloszlású valószínűségi változó az r értéket veszi fel.

Tehát a tekintett két feladatban ugyanaz a határeloszlás jelent meg. Ez a következő ténnyel van kapcsolatban. Az eredeti feladatban az a megkötés, hogy az a férj, akit egyszer kijelöltek táncpartnernek nem választható mégegyszer táncpartnernek a független párválasztás bizonyos megszorítását jelenti, de ez egy nagyon enyhe megszorítás. Ezért a férjükkel táncoló feleségek száma felírható, mint olyan valószínűségi változók összege, amelyek ugyan nem függetlenek, de majdnem azok. Ezért összegük hasonló határeloszlástételt teljesít, mint amilyennel a független esetben találkoztunk.

2. kiegészítés. A vizsgált határeloszlástétel egy más bizonyítása.

Tanulságos lehet megmutatni, hogy hogyan lehet egyszerűen (a szita formula használata nélkül) bebizonyítani azt, hogy az e jegyzet feladatában vizsgált együtt táncoló házaspárok számának a határeloszlása az 1 paraméterű Poisson eloszlás, ha a házaspárok száma tart a végtelenhez.

A bizonyítás a követekező két lemmán alapul.

1. lemma. Tekintsük a következő feladatot. Egy estélyen megjelenik n házaspár. Egy táncmester, aki nem tudja, hogy kik házastársak és kik nem, véletlen módon párba rendezi a férfiakat és nőket a tánc előtt. Jelölje T_{n} az együtt táncoló házaspárok számát. Mutassuk meg, hogy E\binom{T_{n}}{k} = \frac{1}{k!} minden 1 ≤ k ≤ n számra.

2. lemma. Legyen ζ = ζ_{λ} egy λ paraméterű Poisson eloszlású valószínűségi változó. Ekkor E\binom{ζ}{k} = \frac{λ^{k}}{k!} minden k = 1, 2, … számra

1. lemma bizonyítása. Vezessük be minden 1 ≤ j_{1} < j_{2} < ⋯ < j_{k} ≤ n k hosszúságú sorozatra a következő η(j_{1}, …, j_{k}) valószínűségi változót: η(j_{1}, …, j_{k}) = 1, ha a j_{1}-ik, j_{2}-ik, … j_{k}-ik házaspárok mindegyike egymással táncol, és η(j_{1}, …, j_{k}) = 0 egyébként. Ekkor

\binom{T_{n}}{k} = ∑_{1≤j_{1}<···<j_{k}≤n} η(j_{1}, …, j_{k}),

ahonnan

E\binom{T_{n}}{k} = ∑_{1≤j_{1}<···<j_{k}≤n} Eη(j_{1}, …, j_{k}).

Viszont Eη(j_{1}, …, j_{k}) = \frac{(n−k)!}{n!}, ahonnan E\binom{T_{n}}{k} = \binom{n}{k} \frac{(n−k)!}{n!} = \frac{1}{k!}, amint állítottuk.

2. lemma bizonyítása.

E\binom{ζ}{k} = ∑_{n=k}^{∞} \binom{n}{k}\frac{λ^{n}}{n!} e^{−λ} = e^{−λ}λ^{k} ∑_{n=k}^{∞} \frac{1}{k!} \frac{λ^{n−k}}{(n − k)!} = \frac{λ^{k}}{k!} e^{−λ} ∑_{n=k}^{∞} \frac{λ^{n−k}}{(n − k)!} = \frac{λ^{k}}{k!} .

Az 1. és 2. lemmából következik, hogy az 1. lemmában definiált T_{n} valamint egy a 2. lemmában tekintett ζ = ζ_{1} λ = 1 paraméterű Poisson eloszlású valószínűségi változók momentumaira érvényes a lim_{n→∞} ET_{n}^{k} = Eζ^{k} azonosság minden k = 1, 2, … számra.

Valóban, vegyük észre, hogy a E\binom{T_{n}}{0} = E\binom{ζ}{0} = 1, ami az ott megfogalmazott állítások megfelelője az ‘elfajuló’ k = 0 esetben. Továbbá megadható az E\binom{η}{k} kifejezés E\binom{η}{k} = \frac{1}{k!}Eη(η −1) ⋯ (η −k +1) = \frac{1}{k!}(Eη^{k} +B_{k−1,k}Eη^{k−1} +⋯+B_{1,k}Eη +B_{0,k}) alakú formában alkalmas B_{j,k}, 0 ≤ j ≤ k − 1 konstansokkal. Ezen konstansok értékeit explicit módon meg lehet adni, de erre nem lesz szükségünk. Ebből a relációból az is következik, hogy az Eη^{k} momentumot ki lehet fejezni az E\binom{η}{j}, 0 ≤ j ≤ k, kifejezések lineáris kombinációjaként. Az ET_{n}^{k} momentum hasonlóan kifejezhető az E\binom{T_{n}}{j}, 0 ≤ j ≤ k, kifejezések lineáris kombinációjaként ugyanazon együtthatókkal. Ebből a tényből, illetve az 1. és 2. lemmából következik, hogy lim_{n→∞} ET_{n}^{k} = Eζ^{k} minden k = 0, 1, 2, … számra, amint állítottam.

Viszont a valószínűségszámítás alapvető eredményeiből következik, hogy ha teljesül a lim_{n→∞} ET_{n}^{k} = Eζ^{k} reláció minden k = 0, 1, 2, … számra és egy Poisson eloszlású ζ valószínűségi változóra, akkor a T_{n} valószínűségi változók eloszlásban konvergálnak a ζ valószínűségi változóhoz.

Az, hogy eloszlások momentumainak a konvergenciájából egy Poisson eloszlású valószínűségi változó momentumaihoz következik az eloszlások konvergenciájá ezen Poisson eloszlású valószínűségi változó eloszlásához következik a következő három feladat eredményeiből. Valójában egy élesebb állítás is következik ezen feladatok eredményeiből. Az, hogy ha eloszlások egy sorozatának minden momentuma konvergál egy olyan eloszlás megfelelő momentumához, amelynek eloszlását egyértelműen meghatározzák momentumai, akkor az eloszlások sorozata konvergál ehhez az eloszláshoz.

1. feladat:

Legyen adva μ_{n}, n = 1, 2, …, valószínűségi mértékek egy olyan sorozata, amelyre létezik a lim_{n→∞} ∫ x^{k}μ_{n}( dx) = B_{k} < ∞ határérték minden k = 1, 2, … indexre. Ekkor a μ_{n} sorozat relative kompakt, azaz minden μ_{n_{k}} részsorozatának van μ_{n_{k_{j}}} eloszlásban konvergens részsorozata.

2. feladat: Legyen adva μ_{n}, n = 1, 2, …, valószínűségi mértékek egy olyan sorozata, amely eloszlásban konvergál egy μ_{0} valószínűségi mértékhez, továbbá amelyre létezik a lim_{n→∞} ∫ x^{k}μ_{n}( dx) = B_{k} < ∞ határérték minden k = 1, 2, … indexre. Ekkor ez a

határérték teljesíti a B_{k} = ∫ x^{k}μ_{0}( dx) relációt minden k = 1, 2, … indexre.

3. feladat: Legyen adva μ_{n}, n = 1, 2, …, valószínűségi mértékek egy olyan sorozata, amelyre lim_{n→∞} ∫ x^{k}μ_{n}( dx) = ∫ x^{k}μ_{0}( dx) minden k = 1, 2, … indexre valamely μ_{0} valószínűségi mértékkel. Ha a μ_{0} mértéket meghatározzák momentumai, akkor a μ_{n} sorozat eloszlásban konvergál a μ_{0} valószínűségi mértékhez.

Segítség: Az első feladat megoldásában a valószínűségszámítás általános eredményei alapján elég ellenőrizni, hogy minden ε > 0 számhoz létezik olyan K = K(ε) szám, amelyre μ_{n}(x: |x| > K) < ε minden n = 1, 2, … indexre. Ez igaz, mert a feladat feltételei szerint ∫ x^{2}μ_{n}( dx) < B alkalmas B > 0 számmal minden n indexre. A gyenge konvergenciából következik, hogy lim_{n→∞} ∫_{−A}^{A} x^{k}μ_{n}( dx) = ∫_{−A}^{A} x^{k}μ_{0}( dx) minden olyan A számra, amely folytonossági pontja a μ_{0} mértéknek. Ahhoz, hogy a 2. feladatot ennek alapján A → ∞ határátmenettel megoldjuk elég belátni, hogy minden k egész és ε > 0 valós számra létezik olyan B = B(k, ε) szám, amelyre ∫_{x: |x|>B} |x|^{k}μ_{n}( dx) < ε minden n indexre. Viszont ∫_{x: |x|>B} |x|^{k}μ_{n}( dx) < \frac{1}{B^{k}} ∫_{x: |x|>B} |x|^{2k}μ_{n}( dx) < \frac{1}{B^{k}} ∫ |x|^{2k}μ_{n}( dx) < ε minden n ≥ 1 indexre, ha B elég nagy. Némi plusz munkával látható, hogy ez a becslés n = 0 indexre is érvényes. A 3. feladat állítása egyszerűen következik az első és második feladat eredményéből.