A szeptember 11-i gyakorlat témája Rövid összefoglaló

A gyakorlaton a következő az irodalomban coupon problémának nevezett problémával illetve néhány hozzá kapcsolódó kérdéssel foglalkoztunk:

Tegyük fel, hogy egy termék megvásárlásakor a termékkel valamilyen cimkét (coupont) is kapunk. Összesen n különböző tipusú coupon van, és ha mindegyiket összegyüjtjük, akkor értékes nyereményt kapunk. Minden vásárlásnál a lehetséges n tipusú coupon valamelyikét egyforma, \frac{1}{n} valószínűséggel kapjuk meg, és az egyes vásárlások esetén szerzett couponok tipusa egymástól független. Hány vásárlást kell tennünk annak érdekében, hogy az összes lehetséges coupont megszerezzük?

Természetesen a szükséges vásárlások száma a véletlentől is függ. De értékes információt ad a szükséges vásárlások számáról, annak várható értéke és szórásnégyzete. Ugyancsak érdekel minket az, hogy a szükséges couponok p-ed részének megszerzéséhez hány vásárlás szükséges. Mi ennek a várható értéke és szórásnégyzete? E kérdés hátterében a következő probléma áll. Szeretnénk tudni, hogy ha a szükséges couponoknak például a 95%-át már megszereztük, akkor a szükséges vásárlások nagyrészét várhatólag már megtettük vagy esetleg a még szükséges 5% megszerzése még több vásárlást igényel. E kérdés eldöntése érdekében érdemes kiszámolni a fenti várható értékeket és szórásnégyzeteket.

Vezessük be a következő η_{1}, η_{2}, …, valószínűségi változókat: η_{j} = k, j = 1, 2, …, 1 ≤ k ≤ n, ha a j-ik vásárlás során a kapott coupon tipusa k. Akkor feltételezésünk formálisan úgy fogalmazható meg, hogy az η_{j}, j = 1, 2, …, valószínűségi változók függetlenek, egyforma eloszlásúak, és P (η_{j} = k) = \frac{1}{n}, j = 1, 2, …, 1 ≤ k ≤ n. Kérdésünk pedig úgy fogalmazható meg, hogy mi az a legkisebb véletlentől függő N szám, melyre az η_{1}, …, η_{N} sorozat az 1, 2, …, n számok mindegyikét felveszi. Mi ennek a véletlen N számnak a várható értéke és szórásnégyzete? Illetve ennek a kérdésnek azt a megfelelőjét tekintettük, amelyben azt követeltük meg, hogy az η_{1}, …, η_{N} sorozat legalább pn értéket vegyen fel. Mind a két probléma vizsgálatában érdemes bevezetni a következő ζ_{j}, j = 1, 2, …, n valószínűségi változókat:

Legyen ζ_{1} = 1. Vegyenek fel a ζ_{1}, ζ_{2}, … valószínűségi változók pozitív egész értékeket, és legyen 1 = ζ_{1} < ζ_{2} < · · ·. Ha a ζ_{s}, 1 ≤ s ≤ j, valószínűségi változókat már definiáltuk, akkor legyen ζ_{j+1} az a legkisebb m index, melyre η_{m} ≠ η_{ζ_{s}}, minden 1 ≤ s ≤ j számra. Szemléletesen a ζ_{j}, j = 1, 2, …, számokat úgy definiáltuk mint azokat a vásárlási időpontokat, melyekben a j-ik alkalommal szereztünk egy új tipusú coupont. A feladat megoldása érdekében a ζ_{j} valószínűségi változók viselkedését kell megértenünk.

1. Lássuk be, hogy a ζ_{1}, ζ_{2}, …, valószínűségi változók függetlenek, és P (ζ_{j} = l) =

p_{j}(l) = (\frac{j − 1}{n})^{l−1} \frac{n − j + 1}{n}, l = 1, 2, . . ..

1a.) Minden 0 < p < 1 számra létezik p_{n} = (1−p)^{n−1}(1−p), n = 1, 2, … alakú eloszlás, azaz létezik olyan ζ valószínűségi változó, melyre P (ζ = n) = (1 − p)^{n−1}p. Mi az

ilyen alakú eloszlások szemléletes tartalma? 1b.) Legyenek ζ_{1}, ζ_{2}, …, olyan pozitív egész értékeket felvevő valószínűségi változók,

melyekre P (ζ_{n} = j_{n}|ζ_{1} = j_{1}, …, ζ_{n−1} = j_{n−1}) = p_{n}(j_{n}) minden j_{1}, …, j_{n} pozitív egészekből álló szám n-esekre. Lássuk be, hogy ekkor ζ_{1}, ζ_{2}, …, független valószínűségi változók, és P (ζ_{n} = j) = p_{n}(j), minden n = 1, 2, … számra.

1a.) Megoldás: Mivel ∑_{n=1}^{∞} p_{n} = ∑_{n=1}^{∞}(1 − p)p^{n−1} = (1 − p)\frac{1}{1 − p} = 1, és p_{n} ≥ 0 minden

n = 1, 2, … számra az adott p_{n} számok valóban eloszlást határoznak meg (a pozitív egész számokon). Tekintsük egy olyan pénzdarab egymástól független dobásait, melyek p valószínűséggel esnek a fej, és 1 − p valószínűséggel az írás oldalra. Akkor p_{n} annak valószínűsége, hogy az n-ik dobásban jelenik meg az első fej-dobás. Ezt az eloszlást az irodalomban (p paraméterű) negatív binomiális eloszlásnak nevezik.

Az 1. feladat állítása szerint ζ_{j} p_{j} = \frac{j − 1}{n} paraméterű negatív binomiális eloszlású valószínűségi változó.

1b.) Megoldás: Azt kell belátni, hogy

P (ζ_{n} = j_{n}, ζ_{n−1} = j_{n−1}, …, ζ_{1} = j_{1}) = ∏_{k=1}^{n} p_{k}(j_{k})

Viszont

P (ζ_{n} = j_{n}, ζ_{n−1} = j_{n−1}, …, ζ_{1} = j_{1})

= ∏_{k=2}^{n} P (ζ_{k} = j_{k}|ζ_{k−1} = j_{k−1}, …, ζ_{1} = j_{1})P (ζ_{1} = j_{1}) = ∏_{k=1}^{n} p_{k}(j_{k})

a feladat feltételei szerint.

1. Megoldás: Az 1b.) feladat eredménye alapján elég belátni, hogy

P (ζ_{k} = j_{k}|ζ_{k−1} = j_{k−1}, …, ζ_{1} = j_{1}) = (\frac{k − 1}{n})^{j_{k}−1} \frac{n − k + 1}{n}

minden k = 1, 2, …, j_{k} = 1, 2, … számokra. Ehhez elegendő belátni, hogy az M = ∑_{l=1} k_{l} pozitív egész számra és minden olyan η_{1}, …, η_{M} sorozatra, melyekre az

η_{1}, …, η_{M−1} sorozat pontosan k −2 különböző értéket vesz fel, az η_{M} valószínűségi változó pedig egy új k−1-ik értéket vesz fel, teljesül az alábbi azonosság: (Az előbb megfogalmazott feltételek azt fejezik ki, hogy egy olyan vásárlás sorozat történt, amelyikben az M-ik vásárláskor szereztük meg a k − 1-ik coupont.) Megmutatjuk, hogy

P (ζ_{k} = j_{k}|η_{1} = l_{1}, …, η_{M} = l_{M}) = (\frac{k − 1}{n})^{j_{k}−1} \frac{n − k + 1}{n}

pozitív egész számok tetszőleges olyan l_{1}, …, l_{M} sorozatára, amelyik pontosan k − 1 különböző értéket vesz fel. Annak belátásához, hogy az utolsó összefüggésből következik a kívánt állítás azt kell észrevenni, hogy az {η_{1} = l_{1}, … η_{M} = l_{M}} események diszjunktak, a {ζ_{k−1} = j_{k−1}, …, ζ_{1} = j_{1}} esemény ilyen alakú (diszjunkt) események uniója, és az utolsó azonosság jobboldalán szereplő valószínűség nem függ az {η_{1} = l_{1}, … η_{M} = l_{M}} feltételtől. A bizonyítandó állítás viszont egyszerűen ellenőrizhető. Azt kell észrevenni, hogy

egymástól független kisérleteket kell vizsgálni, melyek p = \frac{n − k + 1}{n} valószínűséggel járnak sikerrel és 1 − p valószínűséggel sikertelenek. Azt kell nézni, hogy mi annak a valószínűsége, hogy pontosan a j_{k}-ik kisérlet lesz sikeres. A felírt azonosság ezt a valószínűséget adja meg. (Kisérletnek az M-ik vásárlás után következő új vásárlásokat nevezzük, és e kisérleteket akkor nevezzük sikeresnek, ha a vásárlás során új coupont szereztünk.)

Ezután megbeszéltük azt, hogyan kell kiszámítani valószínűségi változük összegének a várható értékét és szórásnégyzetét, mi a jelentősége a függetlenségnek, hogyan lehet számolni abban az esetben is, ha a függetlenség feltéte nem teljesül. Ezt a kérdést későbbi gyakorlatokon részletesen tárgyaltuk, ezért itt nem írom le. Az vizsgált problémában független valószínűségi változók összegének a várható értékét kell vizsgálnunk. A feladat megoldása érdekében érdemes külön tárgyalni a bevezető valószínűség előadáson szerepelt negatív binomiális eloszlás várható értékét és szörásnégyzetét.

2. Számoljuk ki egy (1, p) paraméterű negativ binomiális eloszlású valószínűségi változó azaz egy olyan ξ valószínűségi változó várható értékét és szórásnégyzetét, melyre P (ξ = k) = p^{k−1}(1 − p), k = 1, 2, . . .. Megoldás: Ha ξ (1, p) paraméterű negativ binomiális eloszlású valószínűségi változó, akkor

Eξ = ∑_{k=1}^{∞} k(1 − p)p^{k−1}, Eξ^{2} = ∑_{k=1}^{∞} k^{2}(1 − p)p^{k−1}.

Ezen összegek egyik lehetséges kiszámolása: ∑_{k=0}^{∞} x^{k} = \frac{1}{1 − x}, ha |x| < 1. Két

egymás utáni deriválással kapjuk, hogy ∑_{k=1}^{∞} kx^{k−1} = \frac{1}{(1 − x)^{2}} és ∑_{k=2}^{∞} k(k−1)x^{k−2} =

\frac{2}{(1 − x)^{3}} . Innen ∑_{k=1}^{∞} kp^{k−1} = \frac{1}{(1 − p)^{2}} , ∑_{k=1}^{∞} k^{2}p^{k−1} = ∑_{k=1}^{∞} kp^{k−1} + p ∑_{k=2}^{∞} k(k −

1)p^{k−2} = \frac{1}{(1 − p)^{2}} + \frac{2p}{(1 − p)^{3}} , és Eξ = \frac{1}{1 − p}, Eξ^{2} = \frac{1}{1 − p} + \frac{2p}{(1 − p)^{2}} . Ezért

Var ξ = Eξ^{2} − (Eξ)^{2} = \frac{p}{(1 − p)^{2}} .

3. Oldjuk meg a bevezetésben megfogalmazott feladatot. Lássuk be, hogy n coupon esetén az összes coupon megszerzéséhez szükséges vásárlások ζ számának várható

értéke Eζ = ∑_{k=1}^{n} \frac{n}{n − k + 1}, szórásnégyzete pedig Var ζ = ∑_{k=1}^{n} \frac{n(k − 1)}{(n − k + 1)^{2}} . Szá-

moljuk ki ezen mennyiségek aszimptotikus viselkedését nagy n számokra.

Megoldás: Láttuk, hogy ζ = ∑_{k=1}^{n} ζ_{k}, ahol ζ_{k} független valószínűségi változók negatív binomiális eloszlással p_{k} = \frac{k − 1}{n} paraméterrel, k = 1, …, n. Ezért Eζ = ∑_{k=1}^{n} Eζ_{k},

Var ζ = ∑_{k=1}^{n} Var ζ_{k}. Továbbá, az előző feladat alapján Eζ_{k} = \frac{n}{n − k + 1}, Var ζ_{k} =

\frac{n(k − 1)}{(n − k + 1)^{2}} minden k = 1, …, n számra. Innen következnek a felírt azonosságok.

Továbbá nagy n-re Eζ = ∑_{k=1}^{n} \frac{n}{n − k + 1} ∼ n ∫_{1}^{n} \frac{1}{n − u + 1} du = n log n. Hasonlóan

Var ζ ∼ n ∫_{1}^{n} \frac{(u − 1)}{(n − u + 1)^{2}} du. Továbbá

∫_{1}^{n} \frac{(u − 1)}{(n − u + 1)^{2}} du = − ∫_{1}^{n} \frac{1}{n − u + 1} du + n ∫_{1}^{n} \frac{1}{(n − u + 1)^{2}} du ∼ ∫_{1}^{∞} \frac{n}{u^{2}} du.

Ezért Var ζ ∼ \frac{n^{2}}{3} .

4. Számoljuk ki annak várható értékét és szórásnégyzetét, hogy hány vásárlás szükséges ahhoz, hogy a szükséges couponok p-ed részét megszerezzük. Számoljuk ki a várható érték aszimptotikáját nagy n és rögzített p számra. Megoldás: Ezt a feladatot az elöző feladathoz hasonlóan oldhatjuk meg. Az egyetlen különbség, hogy most nem egytől n-ig, hanem 1-től pn-ig kell összegezni. Ezért a

várható érték ∑_{k=1}^{np} \frac{n}{n − k + 1}, a szórásnégyzet pedig ∑_{k=1}^{np} \frac{n(k − 1)}{(n − k + 1)^{2}} . Hasonlóan az

előző feladat számolásához a várható érték nagy n-re közelítőleg

∫_{1}^{pn} \frac{n}{n − u + 1} du = n ∫_{n−np+1}^{n} \frac{du}{u} = n log \frac{n}{n(1 − p) + 1} ∼ n log \frac{1}{1 − p}.

(Hasonló számolás mutatja, hogy a szórásnégyzet is n-nel lesz arányos.)