Valószínűségi feladatok

Szerepelt a küvetkező feladat a generátorfüggvény módszer segítségével:

1. Adva n házaspár, valaki véletlenszerűen párbaállítja őket. Mi annak a valószínűsége, hogy van olyan házaspár, mely egy párba kerül. Oldjuk meg ezt a feladatot a következő szita formula segítségével. Lássuk be a következő szita formulát: Ha A_{1}, …, A_{n} tetszőleges események egy valószínűségi mezőn, akkor

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.

2. Lássuk be a szitaformula következő általánosítását: Legyenek A_{1}, …, A_{n} tetszőleges események egy valószínűségi mezőn,

B_{1} = B_{1}(A_{1} …, A_{n}), …, B_{m} = B_{m}(A_{1} …, A_{n}),

ezen események függvényei, azaz ezek a B_{1}, …, B_{m} események az A_{1}, …, A_{n} események segítségével metszet, unió és komplementerképzés segítségével kifejezhetőek. Legyenek c_{1}, …, c_{m} tetszőleges valós számok. A

∑_{j=1}^{m} c_{j}P (B_{j}) ≥ 0

egyenlőtlenség teljesül, ha teljesül abban a 2^{n} számú speciális esetben, ha a B_{j} eseményeket meghatározó A_{1}, …, A_{n} események mindegyike vagy a biztos vagy az üres esemény. Lássuk be a szita formulát e reláció segítségével.

3. Mi a valószínűsége annak, hogy egy 30 tagú véletlen társagágban van két ember akinek ugyanakkor van a születésnapja? Általánosabban, ha adott k ember, mindegyikük kap egy számot (születésnap) 1 és n között egymástól függetlenül, mindegyik számot egyforma valószínűséggel, akkor mi a valószínűsége annak, hogy van két ember aki ugyanazt a számot kapta. Az előző feladatban az igazán érdekes probléma nem is az, hogy mi a pontos értéke

a fenti valószínűségnek, hanem az, hogy nagy n és k paraméterekre milyen ennek a valószínűségnek az aszimptotikus viselkedése. Egyszerűbb és tanulságos ezt a kifejezést az úgynevezett Poisson approximáció segítségével vizsgálni. Ezt tesszük a következő feladatban.

4. Legyen adott n urna, és ξ véletlen számú golyó, melyek eloszlása k paraméterű

Poisson eloszlású valószínűségi változó, azaz P (ξ = k) = \frac{1}{k!}e^{−k}. Dobjuk be a golyókat egymástól (és a ξ valószínűségi valtozó értékétől) függetlenül úgy hogy minden urnába egyforma valószínűséggel esnek a golyók. Lássuk be, hogy az egyes urnákba eső golyók száma n darab egymástól független \frac{k}{n} paraméterű Poisson eloszlású valószínűségi változó. Lássuk be, hogy a nagy számok törvénye szerint ξ ∼ k majdnem egy valószínűséggel, ha k nagy. E tények segítségével mutassuk meg, hogy az előzó feladatban k ∼ c\sqrt{n} esetén a valószínűség értéke tart e^{−c} számhoz n → ∞ esetén.

5. Legyen adva k urna, amelyikbe bedobunk n golyót egymástól függetlenül, az egyes

unákba p_{1}, …, p_{k} valószínűséggel, ∑_{j=1}^{k} p_{j} = 1. Ekkor a nagy számok törvénye sze-

rint az egyes urnákba eső golyók számának relativ gyakorisága tart a p_{1}, …, p_{k} számokhoz, ha n → ∞. Annak valószínűsége, hogy a relatív gyakorisága q_{1}, …, q_{k} valamilyen más q_{1}, …, q_{k} exponenciálisan kicsi. Célunk ebben a feladatban ennek a valószínűségnek a pontosabb meghatározása.

Legyen q_{1}, …, q_{k} olyan, hogy ∑_{j=1}^{k} q_{j} = 1, ε > 0, n_{1}, …, n_{k}, ∑_{j=1}^{k} n_{j} = n az egyes

urnákba eső golyók száma, κ_{j} = \frac{n_{j}}{n}, A_{n} = A_{n}(ε) = \{(1 − ε)q_{j} ≤ κ_{j} ≤ (1 + ε)q_{j}\}. Ekkor

lim_{ε→0} lim sup \frac{1}{n} log P (A_{n}(ε)) = I(\{q_{1}, …, q_{k}\}∥\{p_{1}, …, p_{k}\})
lim_{ε→0} lim sup \frac{1}{n} log P (A_{n}(ε)) = I(\{q_{1}, …, q_{k}\}∥\{p_{1}, …, p_{k}\}),

ahol I(\{q_{1}, …, q_{k}\}∥\{p_{1}, …, p_{k}\}) = − ∑_{j=1}^{k} q_{j} log \frac{p_{j}}{q_{j}}.

Az előző feladat egy olyan relációt fejez ki, amelyik hasznos a következő szemináriumon tárgyalandó entrópiának és az információelméletnek a megértéséhez. Végül egy népszerű kérdéskör, az úgynevezett tiszta fejek probémáját fogjuk vizsgálni. A kérdés az, hogy egyszabályos pénzdarab feldobása során keletkezett n hosszúságú fej-írás sorozat milyen hosszúságú csak fej jeleket tartalmazó blokkot tartalmaz. Durván szólva log nnél valamivel rövidebb sorozat majdnem biztos van, log n-nél valamivel hosszabb sorozat majdnem biztos nincsen.

6. Adjunk jó becslést arra, hogy egy n = A2^{k} hosszúságú szabályos fej-írás sorozat tartalmaz k hosszúságú fej blokkot.Tekintsük az első m darab egymás után kövekező tiszta fej blokkot. (Ha két írás következik egymás után, akkor azt tekintsük úgy, hogy közöttük nulla hosszúságú fej-blokk van.) Milyen becslést tudunk adni arra, hogy az első m blokk tartalmaz vagy nem tartalmaz k hosszúságú sorozatot, hogy a hosszaik összege kisebb vagy nagyobb mint n? Milyen becsléseket kapunk így az eredeti feladatra?

7. Legyen T_{n} annak a valószínűsége, hogy a szabályos fej-írás sorozt első n tagja

nem tartalmaz k hosszúságú tiszta fej sorozatot. Lássuk be, hogy T_{n} = ∑_{j=0}^{k−1} \frac{T_{n−j}}{2^{j}},

T_{1} = ⋯ = T_{k−1} = 1. Lássuk be, hogy a 2^{n}T_{n} sorozat egy általánosított Fibonacci sorozatnak tekinthető. Milyen következtetéseket tudunk ennek alapján levonni ennek viselkedéséről? Mi e sorozat generátor függvénye?