\magnification=\magstep1
\hsize=16truecm
\input amstex
\define\e {\varepsilon}
 
\centerline{\bf Val\'osz\'{\i}n\H{u}s\'egi feladatok}
\bigskip
 
Szerepelt a k\"uvetkez\H{o} feladat a gener\'atorf\"uggv\'eny
m\'odszer seg\'{\i}ts\'eg\'evel:
\medskip
\item{1.} Adva $n$ h\'azasp\'ar, valaki v\'eletlenszer\H{u}en
p\'arba\'all\'{\i}tja \H{o}ket. Mi annak a
val\'o\-sz\'{\i}\-n\H{u}\-s\'e\-ge,
hogy van olyan h\'azasp\'ar, mely egy p\'arba ker\"ul.
Oldjuk meg ezt a feladatot a k\"ovetkez\H{o} szita formula
seg\'{\i}ts\'eg\'evel.
\item{} L\'assuk be a k\"ovetkez\H{o} szita formul\'at: Ha
$A_1,\dots,A_n$ tetsz\H{o}leges esem\'enyek egy
val\'osz\'{\i}n\H{u}s\'egi mez\H{o}n, akkor
$$
P(A_1\cup \cdots\cup A_n)=S_1-S_2+S_3-\cdots +(-1)^{n+1}S_n,
$$
ahol
$$
S_k=\sum_{1\le j_1<\cdots<j_k\le n} P(A_{j_1}\cap\cdots\cap A_{j_k}),
\quad 1\le k\le n.
$$
\item{2.} L\'assuk be a szitaformula k\"ovetkez\H{o}
\'altal\'anos\'{\i}t\'as\'at: Legyenek $A_1,\dots,A_n$
tet\-sz\H{o}\-le\-ges esem\'enyek egy val\'osz\'{\i}n\H{u}s\'egi
mez\H{o}n,
$$
B_1=B_1(A_1\dots,A_n),\dots, B_m=B_m(A_1\dots,A_n),
$$
ezen esem\'enyek f\"uggv\'enyei, azaz ezek a $B_1,\dots,B_m$
esem\'enyek az $A_1,\dots,A_n$ ese\-m\'e\-nyek seg\'{\i}ts\'eg\'evel
metszet, uni\'o \'es komplementerk\'epz\'es seg\'{\i}ts\'eg\'evel
kifejezhet\H{o}ek. Le\-gye\-nek $c_1,\dots,c_m$ tetsz\H{o}leges
val\'os sz\'amok. A
$$
\sum_{j=1}^m c_jP(B_j)\ge0
$$
egyenl\H{o}tlens\'eg teljes\"ul, ha teljes\"ul abban a $2^n$
sz\'am\'u speci\'alis esetben, ha a $B_j$ esem\'enyeket
meghat\'aroz\'o $A_1,\dots,A_n$ esem\'enyek mindegyike vagy a biztos
vagy az \"ures esem\'eny.
L\'assuk be a szita formul\'at e rel\'aci\'o seg\'{\i}ts\'eg\'evel.
\item{3.} Mi a val\'osz\'{\i}n\H{u}s\'ege annak, hogy egy 30 tag\'u
v\'eletlen t\'arsag\'agban van k\'et ember akinek ugyanakkor van a
sz\"ulet\'esnapja? \'Altal\'anosabban, ha adott $k$ ember,
mindegyik\"uk kap egy sz\'amot (sz\"ulet\'esnap) 1 \'es $n$ k\"oz\"ott
egym\'ast\'ol f\"uggetlen\"ul, mindegyik sz\'amot egyforma
val\'osz\'{\i}n\H{u}s\'eggel, akkor mi a val\'osz\'{\i}n\H{u}s\'ege
annak, hogy van k\'et ember aki ugyanazt a sz\'amot kapta.
\smallskip
Az el\H{o}z\H{o} feladatban az igaz\'an \'erdekes probl\'ema nem is
az, hogy mi a pontos \'ert\'eke a fenti val\'osz\'{\i}n\H{u}s\'egnek,
hanem az, hogy nagy $n$ \'es $k$ param\'eterekre milyen ennek a
val\'osz\'{\i}n\H{u}s\'egnek az aszimptotikus viselked\'ese.
Egyszer\H{u}bb \'es tanuls\'agos  ezt a kifejez\'est az
\'ugynevezett Poisson approxim\'aci\'o seg\'{\i}ts\'eg\'evel
vizsg\'alni. Ezt tessz\"uk a k\"ovetkez\H{o} feladatban.
\smallskip
\item{4.} Legyen adott $n$ urna, \'es $\xi$ v\'eletlen sz\'am\'u
goly\'o, melyek eloszl\'asa $k$ param\'eter\H{u} Poisson eloszl\'as\'u
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o, azaz
$P(\xi=k)=\dfrac1{k!}e^{-k}$. Dobjuk be a goly\'okat egym\'ast\'ol
(\'es a $\xi$ val\'osz\'{\i}n\H{u}s\'egi valtoz\'o \'ert\'ek\'et\H{o}l)
f\"uggetlen\"ul \'ugy hogy minden urn\'aba egyforma
val\'osz\'{\i}n\H{u}s\'eggel esnek  a goly\'ok. L\'assuk be, hogy az
egyes urn\'akba es\H{o} goly\'ok sz\'ama $n$ darab egym\'ast\'ol
f\"uggetlen $\dfrac kn$ param\'eter\H{u} Poisson eloszl\'as\'u
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o. L\'assuk be, hogy
a nagy sz\'amok t\"orv\'enye szerint $\xi\sim k$ majdnem egy
val\'osz\'{\i}n\H{u}s\'eggel, ha $k$ nagy. E t\'enyek
seg\'{\i}ts\'eg\'evel mutassuk meg, hogy az el\H{o}z\'o feladatban
$k\sim c\sqrt n$ eset\'en a val\'osz\'{\i}n\H{u}s\'eg
\'ert\'eke tart $e^{-c}$ sz\'amhoz $n\to\infty$ eset\'en.
\item{5.} Legyen adva $k$ urna, amelyikbe bedobunk $n$ goly\'ot
egym\'ast\'ol f\"uggetlen\"ul, az egyes un\'akba $p_1,\dots,p_k$
val\'osz\'{\i}n\H{u}s\'eggel, $\sum\limits_{j=1}^k p_j=1$. Ekkor a nagy
sz\'amok t\"orv\'enye sze\-rint az egyes urn\'akba es\H{o} goly\'ok
sz\'am\'anak relativ gyakoris\'aga tart a $p_1,\dots,p_k$ sz\'amokhoz,
ha $n\to\infty$. Annak val\'osz\'{\i}n\H{u}s\'ege, hogy a
relat\'{\i}v gyakoris\'aga $q_1,\dots,q_k$ valamilyen m\'as
$q_1,\dots,q_k$ exponenci\'alisan kicsi. C\'elunk ebben a feladatban
ennek a val\'osz\'{\i}n\H{u}s\'egnek a pontosabb meghat\'aroz\'asa.
\item{}  Legyen $q_1,\dots,q_k$ olyan, hogy $\sum\limits_{j=1}^k
q_j=1$, $\e>0$, $n_1,\dots,n_k$, $\sum\limits_{j=1}^kn_j=n$ az egyes
urn\'akba es\H{o} goly\'ok sz\'ama, $\kappa_j=\dfrac {n_j}n$,
$A_n=A_n(\e)=\{(1-\e)q_j\le \kappa_j\le (1+\e)q_j\}$. Ekkor
$$
\align
\lim_{\e\to0}\limsup\dfrac1n\log
P(A_n(\e))&=I(\{q_1,\dots,q_k\}\|\{p_1,\dots,p_k\})\\
\lim_{\e\to0}\limsup\dfrac1n\log
P(A_n(\e))&=I(\{q_1,\dots,q_k\}\|\{p_1,\dots,p_k\}),
\endalign
$$
ahol
$I(\{q_1,\dots,q_k\}\|\{p_1,\dots,p_k\})=-\sum\limits_{j=1}^k q_j\log
\dfrac{p_j}{q_j}$.
\medskip
Az el\H{o}z\H{o} feladat egy olyan rel\'aci\'ot fejez ki, amelyik
hasznos a k\"ovetkez\H{o} sze\-mi\-n\'a\-riu\-mon t\'argyaland\'o
entr\'opi\'anak \'es az inform\'aci\'oelm\'eletnek a
meg\'ert\'es\'ehez. V\'eg\"ul egy n\'epszer\H{u} k\'erd\'esk\"or, az
\'ugynevezett tiszta fejek prob\'em\'aj\'at fogjuk vizsg\'alni. A
k\'erd\'es az, hogy egyszab\'alyos p\'enzdarab feldob\'asa sor\'an
keletkezett $n$ hossz\'us\'ag\'u fej-\'{\i}r\'as sorozat milyen
hossz\'us\'ag\'u csak fej jeleket tartalmaz\'o blokkot tartalmaz.
Durv\'an sz\'olva $\log n$-n\'el valamivel r\"ovidebb sorozat majdnem
biztos van, $\log n$-n\'el valamivel hosszabb sorozat majdnem biztos
nincsen.
\item{6.} Adjunk j\'o becsl\'est arra, hogy egy $n=A2^k$
hossz\'us\'ag\'u szab\'alyos fej-\'{\i}r\'as sorozat tartalmaz $k$
hossz\'us\'ag\'u fej blokkot.Tekints\"uk az els\H{o} $m$ darab egym\'as
ut\'an k\"ovekez\H{o} tiszta fej blokkot. (Ha k\'et \'{\i}r\'as
k\"ovetkezik egym\'as ut\'an, akkor azt tekints\"uk \'ugy, hogy
k\"oz\"ott\"uk nulla hossz\'us\'ag\'u fej-blokk van.) Milyen
becsl\'est tudunk adni arra, hogy az els\H{o} $m$ blokk tartalmaz vagy
nem tartalmaz $k$ hossz\'us\'ag\'u sorozatot, hogy a hosszaik \"osszege
kisebb vagy nagyobb mint $n$? Milyen becsl\'eseket
kapunk \'{\i}gy az eredeti feladatra?
\item{7.} Legyen $T_n$ annak a val\'osz\'{\i}n\H{u}s\'ege, hogy a
szab\'alyos fej-\'{\i}r\'as sorozt els\H{o} $n$ tagja nem tartalmaz $k$
hossz\'us\'ag\'u tiszta fej sorozatot. L\'assuk be, hogy
$T_n=\sum\limits_{j=0}^{k-1}\dfrac{T_{n-j}}{2^j}$,
$T_1=\cdots=T_{k-1}=1$. L\'assuk be, hogy a $2^nT_n$ sorozat egy
\'altal\'anos\'{\i}tott Fibonacci sorozatnak tekinthet\H{o}. Milyen
k\"ovetkeztet\'eseket tudunk ennek alapj\'an levonni ennek
viselked\'es\'er\H{o}l? Mi e sorozat gener\'ator f\"uggv\'enye?
 
\bye