\magnification=\magstep1
\input amstex
\hsize=16truecm
 
\parskip=3pt plus 1pt
\define\A{{\bold A}}
\define\BB{{\bold B}}
\define\DD{{\bold D}}
\define\T{{\bold T}}
\define\U{{\bold U}}
\define\({\left(}
\define\){\right)}
\define\[{\left[}
\define\]{\right]}
\define\e{\varepsilon}
\define\oo{\omega}
\define\const{\text{\rm const.}\,}
\define\supp {\sup\limits}
\define\inff{\inf\limits}
\define\summ{\sum\limits}
\define\prodd{\prod\limits}
\define\limm{\lim\limits}
\define\limsupp{\limsup\limits}
\define\liminff{\liminf\limits}
\define\bigcapp{\bigcap\limits}
\define\bigcupp{\bigcup\limits}
\define\Var{\text{\rm Var}\,}
 
%\nopagenumbers
 
\noindent{\bf A szeptember 11-i gyakorlat t\'em\'aja} \hfill\break
{\it R\"ovid \"osszefoglal\'o} \bigskip
 
A gyakorlaton a k\"ovetkez\H{o} az irodalomban coupon probl\'em\'anak
nevezett prob\-l\'e\-m\'a\-val illetve n\'eh\'any hozz\'a
kapcsol\'od\'o k\'erd\'essel foglalkoztunk:
 
Tegy\"uk fel, hogy egy term\'ek megv\'as\'arl\'asakor a term\'ekkel
valamilyen cimk\'et (cou\-pont) is kapunk. \"Osszesen $n$
k\"ul\"onb\"oz\H{o} tipus\'u coupon van, \'es ha mindegyiket
\"ossze\-gy\"ujt\-j\"uk, akkor \'ert\'ekes nyerem\'enyt kapunk. Minden
v\'as\'arl\'asn\'al a lehets\'eges $n$ tipus\'u coupon valamelyik\'et
egyforma, $\frac1n$ val\'osz\'{\i}n\H{u}s\'eggel kapjuk meg, \'es az
egyes v\'as\'arl\'asok eset\'en szerzett couponok tipusa
egym\'ast\'ol f\"uggetlen. H\'any v\'as\'arl\'ast kell tenn\"unk annak
\'erdek\'eben, hogy az \"osszes lehets\'eges coupont megszerezz\"uk?
 
Term\'eszetesen a sz\"uks\'eges v\'as\'arl\'asok sz\'ama a
v\'eletlent\H{o}l is f\"ugg. De \'ert\'ekes inform\'aci\'ot ad a
sz\"uks\'eges v\'as\'arl\'asok sz\'am\'ar\'ol, annak v\'arhat\'o
\'ert\'eke \'es sz\'or\'asn\'egyzete. Ugyancsak \'erdekel minket az,
hogy a sz\"uks\'eges couponok $p$-ed r\'esz\'enek megszerz\'es\'ehez
h\'any v\'as\'arl\'as sz\"uks\'eges. Mi ennek a v\'arhat\'o \'ert\'eke
\'es sz\'or\'asn\'egyzete? E k\'erd\'es h\'atter\'eben a
k\"ovetkez\H{o} probl\'ema \'all. Szeretn\'enk tudni, hogy ha a
sz\"uks\'eges couponoknak p\'eld\'aul a 95\%-\'at m\'ar megszerezt\"uk,
akkor a sz\"uks\'eges v\'as\'arl\'asok nagyr\'esz\'et
v\'ar\-ha\-t\'o\-lag m\'ar megtett\"uk vagy esetleg a m\'eg
sz\"uks\'eges 5\% megszerz\'ese m\'eg t\"obb v\'as\'arl\'ast ig\'enyel.
E k\'erd\'es eld\"ont\'ese \'erdek\'eben \'erdemes kisz\'amolni a fenti
v\'arhat\'o \'ert\'ekeket \'es sz\'o\-r\'as\-n\'egy\-ze\-teket.
 
Vezess\"uk be a k\"ovetkez\H{o} $\eta_1,\eta_2,\dots,$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okat: $\eta_j=k$, $j=1,2,\dots$,
$1\le k\le n$, ha a $j$-ik v\'as\'arl\'as sor\'an a kapott coupon
tipusa $k$. Akkor felt\'etelez\'es\"unk form\'alisan \'ugy
fogalmazhat\'o meg, hogy az $\eta_j$, $j=1,2,\dots$,
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok f\"uggetlenek, egyforma
eloszl\'as\'uak, \'es $P(\eta_j=k)=\frac1n$, $j=1,2,\dots$, $1\le k\le
n$. K\'erd\'es\"unk pedig \'ugy fogalmazhat\'o meg, hogy
mi az a legkisebb v\'eletlent\H{o}l f\"ugg\H{o} $N$ sz\'am, melyre az
$\eta_1,\dots,\eta_N$ sorozat az $1,2,\dots,n$ sz\'amok mindegyik\'et
felveszi. Mi ennek a v\'eletlen $N$ sz\'amnak a v\'arhat\'o \'ert\'eke
\'es sz\'or\'asn\'egyzete? Illetve ennek a k\'erd\'esnek azt a
megfelel\H{o}j\'et tekintett\"uk, amelyben azt k\"ovetelt\"uk meg,
hogy az $\eta_1,\dots,\eta_N$ sorozat legal\'abb $pn$ \'ert\'eket
vegyen fel. Mind a k\'et probl\'ema vizsg\'alat\'aban \'erdemes
bevezetni a k\"ovetkez\H{o} $\zeta_j$, $j=1,2,\dots,n$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okat:
 
Legyen $\zeta_1=1$. Vegyenek fel a $\zeta_1,\zeta_2,\dots$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok pozit\'{\i}v eg\'esz
\'ert\'ekeket, \'es legyen $1=\zeta_1<\zeta_2<\cdots$.
Ha a $\zeta_s$, $1\le s\le j$, val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'okat m\'ar defini\'altuk, akkor legyen $\zeta_{j+1}$ az
a legkisebb $m$ index, melyre $\eta_m\neq\eta_{\zeta_s}$, minden
$1\le s\le j$ sz\'amra. Szeml\'eletesen a $\zeta_j$, $j=1,2,\dots$,
sz\'amokat \'ugy defini\'altuk mint azokat a v\'as\'arl\'asi
id\H{o}pontokat, melyekben a $j$-ik alkalommal szerezt\"unk egy \'uj
tipus\'u coupont. A feladat megold\'asa \'erdek\'eben a $\zeta_j$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok viselked\'es\'et kell
meg\'erten\"unk.
\medskip
\item{1.} L\'assuk be, hogy a $\zeta_1,\zeta_2,\dots$,
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok f\"uggetlenek, \'es
$P(\zeta_j=l)=p_j(l)=\(\dfrac {j-1}n\)^{l-1}\dfrac{n-j+1}n$,
$l=1,2,\dots$.
\item{1a.)}  Minden $0<p<1$ sz\'amra l\'etezik  $p_n=(1-p)^{n-1}(1-p)$,
$n=1,2,\dots$ alak\'u eloszl\'as, azaz l\'etezik olyan $\zeta$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o, melyre
$P(\zeta=n)=(1-p)^{n-1}p$. Mi az ilyen alak\'u eloszl\'asok
szeml\'eletes tartalma?
\item{1b.)} Legyenek $\zeta_1,\zeta_2,\dots$, olyan pozit\'{\i}v
eg\'esz  \'ert\'ekeket felvev\H{o} val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'ok, melyekre
$P(\zeta_n=j_n|\zeta_1=j_1,\dots,\zeta_{n-1}=j_{n-1})=p_n(j_n)$ minden
$j_1,\dots,j_n$ pozit\'{\i}v eg\'eszekb\H{o}l \'all\'o sz\'am
$n$-esekre. L\'assuk be, hogy  ekkor $\zeta_1,\zeta_2,\dots$,
f\"uggetlen va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'egi v\'altoz\'ok, \'es
$P(\zeta_n=j)=p_n(j)$, minden $n=1,2,\dots$ sz\'amra.
\item{1a.)} {\it Megold\'as:}\/ Mivel $\summ_{n=1}^\infty p_n=
\summ_{n=1}^\infty(1-p) p^{n-1}=(1-p)\dfrac1{1-p}=1$, \'es $p_n\ge0$
minden $n=1,2,\dots$ sz\'amra az adott $p_n$ sz\'amok val\'oban
eloszl\'ast hat\'aroznak meg (a pozit\'{\i}v eg\'esz sz\'amokon).
Tekints\"uk egy olyan p\'enzdarab egym\'ast\'ol f\"uggetlen dob\'asait,
melyek $p$ val\'osz\'{\i}n\H{u}s\'eggel esnek a fej, \'es $1-p$
val\'osz\'{\i}n\H{u}s\'eggel az \'{\i}r\'as oldalra. Akkor $p_n$ annak
val\'osz\'{\i}n\H{u}s\'ege, hogy az $n$-ik dob\'asban jelenik meg az
els\H{o} fej-dob\'as. Ezt az eloszl\'ast az irodalomban ($p$
param\'eter\H{u}) negat\'{\i}v binomi\'alis eloszl\'asnak nevezik.
Az 1. feladat \'all\'{\i}t\'asa szerint $\zeta_j$  $p_j=\dfrac{j-1}n$
param\'eter\H{u} negat\'{\i}v binomi\'alis eloszl\'as\'u
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o.
\item{1b.)} {\it Megold\'as:}\/ Azt kell bel\'atni, hogy
$$
P(\zeta_n=j_n,\zeta_{n-1}=j_{n-1},\dots,\zeta_1=j_1)
=\prod_{k=1}^n p_k(j_k)
$$
Viszont
$$
\align
&P(\zeta_n=j_n,\zeta_{n-1}=j_{n-1},\dots,\zeta_1=j_1)\\
&\qquad =\prod_{k=2}^n
P(\zeta_k=j_k|\zeta_{k-1}=j_{k-1},\dots,\zeta_1=j_1) P(\zeta_1=j_1)
=\prod_{k=1}^n p_k(j_k)
\endalign
$$
a feladat felt\'etelei szerint.
\item{1.} {\it Megold\'as:}\/ Az 1b.) feladat eredm\'enye alapj\'an
el\'eg bel\'atni, hogy
$$
P(\zeta_k=j_k|\zeta_{k-1}=j_{k-1},\dots,\zeta_1=j_1)=
\(\dfrac {k-1}n\)^{j_k-1}\dfrac{n-k+1}n
$$
minden $k=1,2,\dots$, $j_k=1,2,\dots$ sz\'amokra. Ehhez elegend\H{o}
bel\'atni, hogy az $M=\summ_{l=1}k_l$ pozit\'{\i}v eg\'esz sz\'amra
\'es minden olyan $\eta_1,\dots,\eta_M$ sorozatra, melyekre az
$\eta_1,\dots,\eta_{M-1}$ sorozat pontosan $k-2$ k\"ul\"onb\"oz\H{o}
\'ert\'eket vesz fel, az $\eta_M$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o pedig egy \'uj $k-1$-ik \'ert\'eket vesz fel,
teljes\"ul az al\'abbi azonoss\'ag: (Az el\H{o}bb megfogalmazott
felt\'etelek azt fejezik ki, hogy egy olyan v\'as\'arl\'as sorozat
t\"ort\'ent, amelyikben az $M$-ik v\'as\'arl\'askor szerezt\"uk meg a
$k-1$-ik coupont.) Megmutatjuk, hogy
$$
P(\zeta_k=j_k|\eta_1=l_1,\dots,\eta_{M}=l_M)=
\(\dfrac {k-1}n\)^{j_k-1}\dfrac{n-k+1}n
$$
pozit\'{\i}v eg\'esz sz\'amok tetsz\H{o}leges olyan $l_1,\dots,l_M$
sorozat\'ara, amelyik pontosan $k-1$ k\"ul\"onb\"oz\H{o} \'ert\'eket
vesz fel. Annak bel\'at\'as\'ahoz, hogy az utols\'o
\"osszef\"ugg\'esb\H{o}l k\"ovetkezik a k\'{\i}v\'ant \'all\'{\i}t\'as
azt kell \'eszrevenni, hogy az $\{\eta_1=l_1,\dots\eta_M=l_M\}$
esem\'enyek disz\-junk\-tak, a
$\{\zeta_{k-1}=j_{k-1},\dots,\zeta_1=j_1\}$
esem\'eny ilyen alak\'u (disz\-junkt) esem\'enyek uni\'oja, \'es az
utols\'o azonoss\'ag jobboldal\'an szerepl\H{o}
val\'osz\'{\i}n\H{u}s\'eg nem f\"ugg az
$\{\eta_1=l_1,\dots\eta_M=l_M\}$ felt\'etelt\H{o}l.
\item{} A bizony\'{\i}tand\'o \'all\'{\i}t\'as viszont egyszer\H{u}en
ellen\H{o}rizhet\H{o}. Azt kell \'eszrevenni, hogy egym\'ast\'ol
f\"uggetlen kis\'erleteket kell vizsg\'alni, melyek $p=\dfrac{n-k+1}n$
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'eg\-gel j\'arnak sikerrel \'es $1-p$
val\'osz\'{\i}n\H{u}s\'eggel sikertelenek. Azt kell n\'ezni, hogy mi
annak a val\'osz\'{\i}n\H{u}s\'ege, hogy pontosan a $j_k$-ik kis\'erlet
lesz sikeres. A fel\'{\i}rt azonoss\'ag ezt a
val\'osz\'{\i}n\H{u}s\'eget adja meg. (Kis\'erletnek az $M$-ik
v\'as\'arl\'as ut\'an k\"ovetkez\H{o} \'uj v\'as\'arl\'asokat
nevezz\"uk, \'es e kis\'erleteket akkor nevezz\"uk sikeresnek, ha a
v\'as\'arl\'as sor\'an \'uj coupont szerezt\"unk.) \medskip
 
Ezut\'an megbesz\'elt\"uk azt, hogyan kell kisz\'am\'{\i}tani
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\"uk \"osszeg\'enek a v\'arhat\'o
\'ert\'ek\'et \'es sz\'or\'asn\'egyzet\'et, mi a jelent\H{o}s\'ege a
f\"uggetlens\'egnek, hogyan lehet sz\'amolni abban az esetben is, ha
a f\"uggetlens\'eg felt\'ete nem teljes\"ul. Ezt a k\'erd\'est
k\'es\H{o}bbi gyakorlatokon r\'eszletesen t\'argyaltuk, ez\'ert itt
nem \'{\i}rom le. Az vizsg\'alt prob\-l\'e\-m\'a\-ban f\"uggetlen
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok \"osszeg\'enek a v\'arhat\'o
\'ert\'ek\'et kell vizsg\'alnunk. A feladat megold\'asa \'erdek\'eben
\'erdemes k\"ul\"on t\'argyalni a bevezet\H{o} val\'osz\'{\i}n\H{u}s\'eg
el\H{o}ad\'ason
szerepelt negat\'{\i}v binomi\'alis eloszl\'as v\'arhat\'o
\'ert\'ek\'et \'es sz\"or\'asn\'egyzet\'et.
\item{2.} Sz\'amoljuk ki egy $(1,p)$ param\'eter\H{u}
negativ binomi\'alis eloszl\'as\'u va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'egi
v\'al\-to\-z\'o azaz egy olyan $\xi$ va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'egi
v\'altoz\'o v\'arhat\'o \'ert\'ek\'et \'es sz\'or\'asn\'egyzet\'et,
melyre $P(\xi=k)=p^{k-1}(1-p)$, $k=1,2,\dots$.
\item{} {\it Megold\'as:}\/ Ha $\xi$ $(1,p)$ param\'eter\H{u} negativ
binomi\'alis eloszl\'as\'u val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o,
akkor
$$
E\xi=\sum_{k=1}^\infty k(1-p) p^{k-1}, \qquad
E\xi^2=\sum_{k=1}^\infty k^2(1-p) p^{k-1}.
$$
Ezen \"osszegek egyik lehets\'eges kisz\'amol\'asa:
$\summ_{k=0}^\infty x^k=\dfrac 1{1-x}$, ha $|x|<1$. K\'et egym\'as
ut\'ani deriv\'al\'assal kapjuk, hogy $\summ_{k=1}^\infty
kx^{k-1}=\dfrac 1{(1-x)^2}$ \'es $\summ_{k=2}^\infty
k(k-1)x^{k-2}=\dfrac 2{(1-x)^3}$. Innen $\summ_{k=1}^\infty
kp^{k-1}=\dfrac 1{(1-p)^2}$, $\summ_{k=1}^\infty k^2 p^{k-1}=
\summ_{k=1}^\infty k p^{k-1}+p\summ_{k=2}^\infty k(k-1) p^{k-2}=
\dfrac 1{(1-p)^2}+\dfrac {2p}{(1-p)^3}$, \'es $E\xi=\dfrac 1{1-p}$,
$E\xi^2=\dfrac 1{1-p}+\dfrac {2p}{(1-p)^2}$. Ez\'ert
$\Var\xi=E\xi^2-(E\xi)^2=\dfrac p{(1-p)^2}$.
\item{3.} Oldjuk meg a bevezet\'esben megfogalmazott feladatot.
L\'assuk be, hogy $n$ coupon eset\'en az \"osszes coupon
megszerz\'es\'ehez sz\"uks\'eges v\'as\'arl\'asok $\zeta$ sz\'am\'anak
v\'arhat\'o \'ert\'eke $E\zeta=\summ_{k=1}^n\dfrac n{n-k+1}$,
sz\'or\'asn\'egyzete pedig $\Var\zeta=\summ_{k=1}^n\dfrac
{n(k-1)}{(n-k+1)^2}$. Sz\'a\-mol\-juk ki ezen mennyis\'egek
aszimptotikus viselked\'es\'et nagy $n$ sz\'amokra.
\item{} {\it Megold\'as:}\/ L\'attuk, hogy
$\zeta=\summ_{k=1}^n\zeta_k$, ahol $\zeta_k$ f\"uggetlen
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok negat\'{\i}v binomi\'alis
eloszl\'assal $p_k=\dfrac{k-1}n$ param\'eterrel, $k=1,\dots,n$. Ez\'ert
$E\zeta=\summ_{k=1}^nE\zeta_k$, $\Var\zeta=\summ_{k=1}^n\Var\zeta_k$.
Tov\'abb\'a, az el\H{o}z\H{o} feladat alapj\'an
$E\zeta_k=\dfrac n{n-k+1}$,
$\Var\zeta_k=\dfrac {n(k-1)}{(n-k+1)^2}$ minden $k=1,\dots,n$ sz\'amra.
Innen k\"ovetkeznek a fel\'{\i}rt azonoss\'agok. Tov\'abb\'a nagy
$n$-re $E\zeta=\summ_{k=1}^n\dfrac n{n-k+1}\sim n \dsize\int_1^n
\frac1{n-u+1}\,du=n\log n$. Hasonl\'oan
$\Var\zeta\sim n\dsize \int_{1}^n\dfrac
{(u-1)}{(n-u+1)^2}\,du$. Tov\'abb\'a
$$\dsize\int_{1}^n\dfrac
{(u-1)}{(n-u+1)^2}\,du=-\int_1^n\dfrac
1{n-u+1}\,du+n\int_1^n\frac1{(n-u+1)^2}\,du\sim\int_1^\infty
\frac n{u^2}\,du.
$$
Ez\'ert $\Var\zeta\sim\dfrac{n^2}3$.
\item{4.} Sz\'amoljuk ki annak v\'arhat\'o \'ert\'ek\'et \'es
sz\'or\'asn\'egyzet\'et, hogy h\'any v\'as\'arl\'as sz\"uk\-s\'e\-ges
ahhoz, hogy a sz\"uks\'eges couponok $p$-ed r\'esz\'et megszerezz\"uk.
Sz\'amoljuk ki a v\'arhat\'o \'ert\'ek aszimptotik\'aj\'at nagy $n$
\'es r\"ogz\'{\i}tett $p$ sz\'amra.
\item{} {\it Megold\'as:}\/ Ezt a feladatot az el\"oz\H{o} feladathoz
hasonl\'oan oldhatjuk meg. Az egyetlen k\"ul\"onbs\'eg, hogy most
nem egyt\H{o}l $n$-ig, hanem $1$-t\H{o}l $pn$-ig kell \"osszegezni.
Ez\'ert a v\'arhat\'o \'ert\'ek $\summ_{k=1}^{np}\dfrac n{n-k+1}$,
a sz\'or\'asn\'egyzet pedig $\summ_{k=1}^{np}\dfrac
{n(k-1)}{(n-k+1)^2}$. Hasonl\'oan az el\H{o}z\H{o} feladat
sz\'amol\'as\'ahoz a v\'arhat\'o \'ert\'ek nagy $n$-re
k\"ozel\'{\i}t\H{o}leg
$$
\int_1^{pn}\frac n{n-u+1}\,du=n\int_{n-np+1}^{n}
\frac{\,du}u=n\log\frac n{n(1-p)+1}\sim n\log\dfrac1{1-p}.
$$
\item{} (Hasonl\'o sz\'amol\'as mutatja, hogy a sz\'or\'asn\'egyzet
is $n$-nel lesz ar\'anyos.)
 
 
\bye
 
 
 
