 
\magnification=\magstep1
\input amstex
\hsize=16truecm
\parskip=4pt
\parindent=18pt
\TagsOnRight
 
\define\({\left(}
\define\){\right)}
\define\e{\varepsilon}
 
\centerline{\bf A Szindb\'ad probl\'ema. Optim\'alis v\'alaszt\'as
megtal\'al\'asa.} \medskip
Rendk\'{\i}v\"ul n\'epszer\H{u} \'es egyben tanuls\'agos a
k\"ovetkez\H{o} val\'osz\'{\i}n\H{u}s\'egi, optimaliz\'aci\'os
probl\'ema, mely Magyarorsz\'agon Szindb\'ad probl\'em\'aja n\'even
v\'alt ismertt\'e. A k\"ovetkez\H{o} t\"ort\'enetet szokt\'ak
hozz\'af\H{u}zni: \medskip
{\narrower{\narrower\noindent Szindb\'ad megmentette a kalifa
\'elet\'et, \'es ez\'ert jutalmul feles\'eg\"ul veheti a kalifa egyik
h\'aremh\"olgy\'et. A h\'aremh\"olgyek sorban elvonulnak Szindb\'ad
mellett, egyszerre csak egy h\'aremh\"olgy jelenik meg. Szindb\'ad
minden h\'aremh\"olgy sz\'eps\'eg\'et \"ossze tudja hasonl\'{\i}tani
az el\"oz\H{o}leg megjelentek\'evel, \'es egy\'ertelm\H{u}en meg tudja
\'allap\'{\i}tani, hogy az eddig l\'atott h\'aremh\"olgyek k\"oz\"ul ki
a legszebb. Egy \'eppen megjelent h\'aremh\"olgyr\H{o}l megjelen\'ese
ut\'an azonnal el kell d\"ontenie, hogy \H{o}t akarja-e feles\'eg\"ul
venni, \'es ezt a d\"ont\'est k\'es\H{o}bb nem v\'altoztathatja meg.
Szindb\'ad tudja, hogy a kalif\'anak h\'any h\'aremh\"olgye van,
viszont semmit nem tud arr\'ol, hogy a m\'eg nem l\'atott
h\'aremh\"olgyek milyen sz\'epek. A h\'aremh\"olgyek
v\'eletlen sorrendben jelennek meg, \'es minden sorrend egyforma
va\-l\'o\-sz\'{\i}\-n\H{u}. Szindb\'ad szeretn\'e a legszebb
h\'aremh\"olgyet v\'alasztani. Milyen stra\-t\'e\-gi\'a\-val tudja
ezt a lehet\H{o} legnagyobb val\'osz\'{\i}n\H{u}s\'eggel
el\'erni, \'es mekkora ez a val\'osz\'{\i}n\H{u}s\'eg?\par}  \par}
\medskip
Gondoljuk meg, mekkora a siker val\'osz\'{\i}n\H{u}s\'ege nagy
sz\'am\'u feles\'egjel\"olt eset\'en. Ez a val\'osz\'{\i}n\H{u}s\'eg
null\'ahoz tart-e, ha a jel\"oltek sz\'ama v\'egtelenhez tart, vagy
p\'eld\'aul tetsz\H{o}legesen nagy sz\'am eset\'en el\'erhet\H{o}-e
az, hogy a s\'{\i}ker val\'osz\'{\i}n\H{u}s\'ege nagyobb, mint mondjuk
$\frac1{10}$?
 
Tekints\"uk a k\"ovetkez\H{o} strat\'egi\'at. Szindb\'ad az els\H{o}
$\dfrac n2$ h\'aremh\"olgyet hagyja elmenni, majd azt figyeli,
jelent-e meg az \"osszes eddigi h\'aremh\"olgyn\'el szebb. Ha egy
ilyen h\"olgy megjelenik, akkor azt v\'alasztja, ha ilyen h\"olgy nem
jelenik meg akkor mindenkit tov\'abbenged, \'es az utols\'o
h\'aremh\"olgyet v\'alasztja. Amennyiben a m\'asodik legszebb
h\'aremh\"olgy a megjelentek els\H{o}, a legszebb h\'aremh\"olgy
pedig a m\'asodik fel\'eben van, aminek val\'osz\'{\i}n\H{u}s\'ege
$\dfrac14$, akkor Szindb\'adnak ezzel a strat\'egi\'aval siker\"ul
kiv\'alasztani a legszebb h\'aremh\"olgyet. Ez azt
jelenti, hogy nagyon nagy $n$ sz\'amra is Szindb\'ad legal\'abb
$\dfrac14$ val\'osz\'{\i}n\H{u}s\'eggel sikerrel j\'ar. R\'aad\'asul,
lehets\'eges hogy van enn\'el jobb strat\'egia is.
 
Jegyezz\"uk meg, hogy Szindb\'ad c\'elja, az hogy min\'el nagyobb
val\'osz\'{\i}n\H{u}s\'eggel a legszebb h\"olgyet v\'alassza
term\'eszetes, de nem ez az egyetlen lehets\'eges term\'eszetes c\'el.
Vegy\"uk \'eszre, hogy amennyiben Szindb\'ad az el\H{o}bb javasolt
strat\'egi\'at v\'alasztja, akkor viszonylag nagy
val\'osz\'{\i}n\H{u}s\'eggel meglehet\H{o}sen rossz v\'alaszt\'ast is
tehet. Val\'oban, annak a val\'osz\'{\i}n\H{u}s\'ege, hogy a legszebb
h\'aremh\"olgy a megjelentek els\H{o} fel\'eben jelenik meg, \'es az
utols\'o h\'aremh\"olgy a megjelentek sz\'eps\'eg szempontj\'ab\'ol
m\'asodik, rosszabb fel\'eben van k\"or\"ulbel\"ul $\frac14$. Ebben
az esetben Szindb\'ad a fenti strat\'egi\'aval az utols\'o
h\'aremh\"olgyet v\'alasztja, azaz meglehet\H{o}sen rossz v\'alaszt\'ast
tesz. \'Erezhet\H{o}, hogy amennyiben Szindb\'ad p\'eld\'aul  a k\'et
legszebb  h\'aremh\"olgy valamelyik\'et akarja min\'el nagyobb
val\'osz\'{\i}n\H{u}s\'eggel v\'alasztani, akkor a siker
val\'osz\'{\i}n\H{u}s\'ege nagyobb, \'es kisebb
val\'osz\'{\i}n\H{u}s\'eggel fog nagyon rossz v\'alaszt\'ast tenni.
 
A feladatnak egy klasszikus az el\H{o}bb megfogalmazottn\'al
nehezebb, de szint\'en meg\-old\-hat\'o v\'altozata a k\"ovetkez\H{o}
,,Secretary problem"-nak nevezett k\'erd\'es: Egy \'all\'asra ismert
$n$ sz\'am\'u jel\"olt jelentkezik, akik v\'eletlen sorrendben jelennek
meg a felv\'eteli interj\'ura, \'es minden lehets\'eges sorrend
egyforma val\'osz\'{\i}n\H{u}. Legyen a legjobb jel\"olt rangja 1,
a m\'asodik legjobb jel\"olt rangja 2, \'es a $k$-ik legjobb jel\"olt
rangja $k$, $k=1,2,\dots,n$. A felv\'eteli interj\'u sor\'an az \'eppen
jelentkez\H{o} felv\'eteliz\H{o} j\'os\'ag\'at \"ossze tudjuk
hasonl\'{\i}tani az addig megjelentekkel, azaz meg tudjuk mondani az
addig megjelentek k\"oz\"otti relativ rangj\'at. Ezut\'an
eld\"ontj\"uk, hogy a jel\"oltet elfogadjuk vagy elbocs\'ajtjuk, \'es
ezt a d\"ont\'est k\'es\H{o}bb nem v\'altoztathatjuk meg. C\'elunk az,
hogy minimaliz\'aljuk a kiv\'alasztott jel\"olt rangj\'at. K\'erd\'es,
hogy ez a rang optim\'alis v\'alaszt\'as eset\'en v\'egtelenhez
tart-e, ha a jel\"oltek $n$ sz\'ama tart a v\'egtelenhez. Be lehet
l\'atni, hogy optim\'alis v\'alaszt\'as eset\'en l\'etezik v\'eges
hat\'ar\'ert\'ek, \'es annak \'ert\'eke is ismert. Ez a
$$
\prod_{j=1}^\infty\(\frac{j+2}j\)^{1/(j+1)}\sim 3.8695
$$
sz\'am. Ennek a t\'enynek azonban nincs olyan egyszer\H{u} indok\'asa
mint annak, hogy Szindb\'ad probl\'em\'aj\'aban a sikeres v\'alaszt\'as
val\'osz\'{\i}n\H{u}s\'ege j\'o strat\'egia eset\'en nem tart
null\'ahoz $n\to\infty$ eset\'en sem.
 
Az al\'abbiakban Szindb\'ad probl\'em\'aj\'aank ismertetem a teljes
megold\'as\'at. A ,,Secretary problem"-nak viszont csak egy
r\'eszleges megold\'as\'at \'{\i}rom le. Megadom minden
r\"ogz\'{\i}tett $n$-re az optim\'alis strat\'egi\'at, illetve azt a
rekurzi\'ot, melynek seg\'{\i}ts\'eg\'evel kisz\'am\'{\i}that\'o az
optim\'alis strat\'egia eset\'en a kiv\'alasztott jel\"olt rangj\'anak
a v\'arhat\'o \'ert\'ek\'et. Ennek seg\'{\i}ts\'eg\'evel megmutatom,
hogy ennek a v\'arhat\'o \'ert\'eknek az \'ert\'eke minden
$n$ sz\'amra kisebb mint 8. Annak bizony\'{\i}t\'asa, hogy l\'etezik
a fent megadott hat\'ar\'ert\'ek a rekurzi\'o alaposabb vizsg\'alat\'at
ig\'enyli. Ez meglehet\H{o}sen f\'araszt\'o, a
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'eg\-sz\'a\-m\'{\i}\-t\'as\-hoz
k\"ozvetlen\"ul
nem kapcsol\'od\'o probl\'ema. Ez\'ert ennek r\'eszleteit nem
t\'argyalom. Az \'erdekl\H{o}d\H{o}k ezt megtal\'alhatj\'ak azt Y. S.
Chow, S. Moriguti, H. Robbins \'es M. Samuels {\it Optimal Selection
Based On Relative Ranks}\/ (``the Secretary Problem") c\'{\i}m\H{u}
az Israel Journal of Mathematics (1964) 81--90 c\'{\i}n\H{u}
cikk\'eben.
 
A t\'argyalt probl\'em\'ak nemcsak \"onmaguk miatt \'erdekesek. Ezek
megold\'as\'aban olyan gondolatok jelennek meg, melyek egy\'eb
feladatok vizsg\'alat\'aban is fontos szerepet j\'atszanak. Erre
k\'es\H{o}bb visszat\'er\"unk.
 
\bigskip
\centerline{\bf A Szindb\'ad probl\'ema megold\'asa}
\medskip
Jel0lje az pozit\'{\i}v eg\'esz $N$ sz\'am a v\'alaszthat\'o
(h\'arem)h\"olgyek sz\'am\'at,
\'es tekints\"uk az $\{1,\dots,N\}$ halmaz \"osszes lehets\'eges
$\pi=\{\pi(1),\dots,\pi(N)\}$ permut\'aci\'oj\'at. Azt mondjuk, hogy
egy permut\'aci\'ot v\'eletlen\"ul kiv\'alasztunk egyenletes
eloszl\'assal, ha kiv\'alasztjuk v\'eletlen\"ul az $\{1,\dots,N\}$
halmaz  egy per\-mu\-t\'a\-ci\'o\-j\'at, \'es minden
lehets\'eges permut\'aci\'ot $\dfrac1{N!}$
val\'osz\'{\i}n\H{u}s\'eggel v\'a\-lasz\-tunk.
 
Jel\"olje $Z(j)$, $1\le j\le N$, a $j$-ik jel\"olt sorrendj\'et,
azaz legyen $Z(j)=l$, ha $j$-ik megjelen\H{o} jel\"olt az $l$-ik
legszebb h\"olgy. Vezess\"uk be ezenk\'{\i}v\"ul a $j$-ik jel\"olt
$\xi(j)$ relat\'{\i}v sorrendj\'et, ami azt jel\"oli, hogy a $j$-ik
megjelen\H{o} jel\"olt, hanyadik legszebb az addig megjelentek
k\"oz\"ott. Azt a jel\"oltet szeretn\'enk min\'el nagyobb
val\'osz\'{\i}n\H{u}s\'eggel kiv\'alasztani, melynek $Z(\cdot)$
sorrendje 1, viszont a d\"ont\'es sor\'an csak a jel\"oltek $\xi(j)$
relativ sorrendj\'et tudjuk megfigyelni. Tudjuk, hogy az \"osszes
lehets\'eges $(Z(1),\dots,Z(N))$ sorozat val\'osz\'{\i}n\H{u}s\'ege
$\dfrac1{N!}$. Annak \'erdek\'eben, hogy a feladatot meg tudjuk
oldani tegy\"uk el\H{o}sz\"or a k\"ovetkez\H{o} \'eszrev\'etelt,
amelyik le\'{\i}rja $(\xi(1),\dots,\xi(N))$ v\'eletlen sorozat
eloszl\'as\'at.
 
\medskip
\item{1.} V\'alasszuk az $\{1,\dots,N\}$ halmaz egy v\'eletlen $\pi$
permut\'aci\'oj\'at egyenletes eloszl\'assal.
Ekkor a fent defini\'alt $\xi(L)$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'ok f\"uggetlenek, \'es $P(\xi(L)=k)=\dfrac1L$, ha $1\le k\le
L$ minden $1\le L\le N$-re.
\itemitem{1a.)}  Tekints\"unk egy $1\le L\le N$ sz\'amot. Annak
felt\'eteles val\'osz\'{\i}n\H{u}s\'ege, hogy
$\xi(L)$ a legkisebb az \"osszes $\xi(j)$, $1\le j\le N$, k\"oz\"ott,
azaz $Z(L)=1$ azon felt\'etel mellett, hogy  $\xi(L)$ a legkisebb az
\"osszes $\xi(j)$, $1\le j\le L$, sz\'am k\"oz\"ott
$\prod\limits_{j=L+1}^N\dfrac {j-1}j=\dfrac LN$. \'Altal\'anosabban,
$$
P\(Z(L)=1|\xi(1)=j_1,\xi(2)=j_2,\dots,\xi(L)=j_L\)=\frac LN
$$
az $1,2,\dots,L$ sz\'amoknak minden olyan $j_1,j_2,\dots,j_L$
permut\'aci\'oj\'ara, melyre $j_L=1$ \'es $1\le j_s\le s$ minden $1\le
s\le L-1$ sz\'amra.
\itemitem{} Tov\'abb\'a, term\'eszetesen
$$
P\(Z(L)=1|\xi(1)=j_1,\xi(2)=j_2,\dots,\xi(L)=j_L\)=0,
$$
ha $j_L\ge2$.
\medskip
\item{} {\it Indokl\'as:}\/
A f\H{o} r\'esz \'all\'{\i}t\'as\'anak
bizony\'{\i}t\'as\'ahoz el\'eg bel\'atni, hogy a
$$
\{Z(1)=k_1,\dots,Z(N)=k_N\}
$$
esem\'enyek, $k_1,\dots,k_N$ az $1,\dots,N$ sz\'amok permut\'aci\'oi
\'es a
$$
\{\xi(1)=j_1,\dots,\xi(N)=j_N\}, \quad 1\le j_L\le L,\quad
1\le L\le N,
$$
esem\'enyek k\"oz\"ott k\"olcs\"on\"osen egy\'ertelm\H{u}
megfeleltet\'es van. Ez ugyanis azt jelenti, hogy
$P(\xi(1)=j_1,\dots,\xi(N)=j_N)=\dfrac1{N!}$, $1\le j_L\le L$, $1\le
L\le N$. Ez az \'all\'{\i}t\'as viszont k\"onnyen l\'athat\'o, mert
minden $\{Z(1)=k_1,\dots,Z(N)=k_N\}$ esem\'enynek megfelel egy
$\{\xi(1)=j_1,\dots,\xi(N)=j_N\}$, $1\le j_L\le L$, $1\le L\le N$,
esem\'eny, \'es megford\'{\i}tva minden
$\{\xi(1)=j_1,\dots,\xi(N)=j_N\}$, $1\le j_L\le L$, $1\le L\le N$,
esem\'enyre megadhat\'o, hogy melyik
$\{Z(1)=k_1,\dots,Z(N)=k_N\}$ esem\'enynek felel meg. Val\'oban,
$\xi(N)=Z(N)$, ezut\'an $\xi(N-1)$ illetve annak ismeret\'eben, hogy
az $N$-ik \'es $N-1$-ik jel\"olt k\"oz\"ul melyik a nagyobb, ismerj\"uk
a $Z(N-1)$ \'ert\'ek\'et is. \'Igy szukcesszive meg tudjuk hat\'arozni
a $Z(k)$ \'ert\'eket a m\'ar meghat\'arozott $Z(j)$ \'ert\'ekek
seg\'{\i}ts\'eg\'evel.
\item{} Az 1a r\'esz bizony\'{\i}t\'as\'ahoz vegy\"uk \'eszre, hogy
az $L$-ik l\'ep\'esben megjelen\H{o} az \"osszes addig megjelent
jel\"oltn\'el szebb h\"olgy akkor \'es csak akkor a legszebb az
\"osszes jel\"olt k\"oz\"ott, ha nem jelenik meg a k\'es\H{o}bbiekben
minden kor\'abbin\'al szebb h\"olgy, azaz a $\xi(L)=1$ esem\'enyb\H{o}l
akkor k\"ovetkezik a $Z(L)=1$ esem\'eny, ha $\xi(k)\ge2$ minden $L+1\le
k\le N$ indexre. Ez\'ert
$$
\align
&P\(Z(L)=1|\xi(1)=j_1,\xi(2)=j_2,\dots,\xi(L)=1\) \\
&\qquad=P\(\xi(L+1)\ge2,\dots,\xi(N)\ge2|\xi(1)=j_1,\xi(2)=j_2,
\dots,\xi(L)=1\)\\
&\qquad=P\(\xi(L+1)\ge2,\dots,\xi(N)\ge2\)=\prod_{j=L+1}^N
P(\xi(j)\ge2) =\prod_{j=L+1}^N \frac{j-1}j=\frac LN
\endalign
$$
 
A feladat megold\'asa \'erdek\'eben \'erdemes bevezetni a
meg\'all\'asi szab\'aly fogalm\'at \'es a feladatot form\'alis
szempontb\'ol precizen megfogalmazni. \medskip\noindent
{\bf Meg\'all\'asi szab\'aly fogalma.} {\it Legyen adva
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok $\xi(1),\xi(2),\dots$,
so\-ro\-za\-ta. Azt mondjuk, hogy egy $\tau$ pozit\'{\i}v
eg\'esz \'ert\'ekeket felvev\H{o} val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o meg\'all\'asi szab\'aly ezekre a $\xi(1),\xi(2),\dots$,
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okra n\'ezve, ha
$P(\tau<\infty)=1$, \'es minden $n=1,2,\dots$ sz\'amra megadhat\'o az
$n$ dimenzi\'os t\'er olyan $A_n$ halmaza, hogy a $\{\tau=n\}$
esem\'eny akkor \'es csak akkork\"ovetkezik be, ha
$\{\xi(1),\dots,\xi(n)\}\in A_n$.} \medskip
A meg\'all\'asi szab\'aly szeml\'eletes tartalma az, hogy az $n$-ik
id\H{o}pntban annak el\-d\"on\-t\'e\-s\'et, hogy meg\'alljunk-e ekkor
vagy sem az $n$-ik id\H{o}pontban \"osszegy\"ujt\"ott inform\'aci\'o
alapj\'an d\"ontj\"uk el. Val\'oj\'aban a definici\'o
\'altal\'anosabb. A szok\'asos definici\'o a k\"ovetkez\H{o}: Egy
$(\Omega,\Cal A,P)$ val\'osz\'{\i}n\H{u}s\'egi mez\H{o}n adott
egym\'asba skatuly\'azott $\Cal F_1\subset \Cal F_2\subset\cdots
\subset \Cal A$ $\sigma$-algebr\'ak sorozata. Azt mondjuk, hogy egy
$\tau$, $P(\tau<\infty)=1$, val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
meg\'all\'asi szab\'aly, ha $\{\tau=n\}\in \Cal F_n$.
Ennek a definici\'onak szeml\'eletes tartalma az, hogy $\Cal F_n$
az $n$-ik id\H{o}pontig \"osszegy\"ujt\"ott inform\'aci\'okat
tartalmaz\'o $\sigma$-algebra, \'es azt hogy az $n$-ik l\'ep\'esben
meg\'allunk-e vagy sem azt az $n$-ik l\'ep\'esben
\"osszegy\"ujt\"ott inform\'aci\'ok alapj\'an d\"ontj\"uk el.
 
Eset\"unkben az $\Cal F_n$ $\sigma$-algebr\'at mint a
$\xi_1,\dots,\xi_n$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok \'altal
gener\'alt $\sigma$-algebr\'at defini\'aljuk. Bizonyos
m\'ert\'ekelm\'eleti ismeretek seg\'{\i}ts\'eg\'evel be lehet
l\'atni, hogy ebben az esetben az \'altalunk megadott, illetve az
\'altal\'anos definici\'o megegyezik. Erre azonban nem lesz
sz\"uks\'eg\"unk. Az \'altalunk tekintett feladatban elegend\H{o}
diszkr\'et \'ert\'ek\H{u} val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okkal
dolgozni, amikor nem mer\"ulnek fel komoly
m\'er\-t\'ek\-el\-m\'e\-le\-ti probl\'em\'ak. Ugyanakkor az
\'altal\'anos eset vizsg\'alat\'aban,
b\'ar sz\"uks\'eg van bizonyos nem trivi\'alis
m\'ert\'ekelm\'eleti eredm\'enyekre, nem mer\"ulnek fel komoly \'uj
elvi neh\'ezs\'egek.
 
Minket a fenti definici\'o \'es a kor\'abbi jel\"ol\'esek
felhaszn\'al\'as\'aval a k\"ovetkez\H{o} feladat megold\'asa \'erdekel:
Adott $\xi(1),\dots,\xi(N)$ (f\"uggetlen) ismert egy\"uttes
eloszl\'as\'u va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-gi v\'altoz\'ok
sorozata. (L\'asd az els\H{o} feladatot.) Ezenk\'{\i}v\"ul
tekintett\"unk olyan $Z(k)$, $k=1,2,\dots,N$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'okat, melyek ezen $\xi(j)$ v\'altoz\'ok
f\"uggv\'enyeik\'ent kifejezhet\H{o}ek, \'es tekintett\"unk
valamilyen $g_k(Z(1),\dots,Z(N))$ nyerem\'enyf\"uggv\'enyeket, melyek
azt fejezik, ki mennyi a nyerem\'eny\"unk, ha a $k$-ik l\'ep\'esben
meg\'allunk. Ese\-t\"unk\-ben $Z(k)$ fejezi ki azt, hogy a $k$-ik
megjelent h\'aremh\"olgy hanyadik a sz\'eps\'egi sorrendben, \'es
$g_k(u_1,\dots,u_n))=1$, ha $u_k=1$, \'es $g_k(u_1,\dots,u_N)=0$,
ha $u_k\ge2$. Hangs\'ulyozzuk, hogy p\'eld\'aul a $Z(1)$
ismeret\'ehez sz\"uks\'eg\"unk van az \"osszes $\xi(k)$,
$k=1,\dots,N$, ismeret\'ere. Ekkor megadhat\'oak olyan
$f_k(x_1,\dots,x_n)$ f\"uggv\'enyek,
melyekre $f_k(\xi(1),\dots,\xi(N)=1$, ha $Z(k)=1$, \'es
$f_k(\xi(1),\dots,\xi(N)=0$, ha $Z(k)\ge2$, $1\le k\le N$.
Feladatunk ezek ut\'an a k\"ovetkez\H{o}k\'epp fogalmazhat\'o meg.
Tekints\"uk az \"osszes lehets\'eges $\tau$ meg\'all\'asi szab\'alyt
a $\xi(1),\dots,\xi(N)$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okra
n\'ezve, (feltessz\"uk, hogy $P(\tau\le N)=1$), \'es keress\"uk meg
ezek k\"oz\"ul azt, melyre $Ef_\tau(\xi(1),\dots,\xi(N))$ a
mini\-m\'a\-lis.
 
Az el\"obb megfogalmazott probl\'em\'at lehet egyszer\H{u}bben, \'es
konkr\'etabban megfogalmazni a k\"ovetkez\H{o} \'all\'{\i}t\'as
seg\'{\i}ts\'eg\'evel. Ebben olyan nyerem\'enyf\"uggv\'enyek eset\'eben
vett optimaliz\'aci\'os feladatot tekintj\"uk, melyeknek a $k$
id\H{o}pontban felvett $h_k(\xi(1),\dots,\xi(k))$ \'ert\'ek\"uk
csak a $k$-ik id\H{o}pontig megfigyelt $\xi(1),\dots,\xi(k)$
\'ert\'ekekt\H{o}l f\"ugg.
\medskip
\item{2.} Legyen adva $\xi(1),\dots,\xi(N)$ (diszkr\'et)
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok  \'es $h_k(x_1,\dots,x_N)$
nye\-re\-m\'eny\-f\"uggv\'enyek sorozata. Vezess\"uk be az
$$
u_k(x_1,\dots,x_k)=
E(h_k(\xi(1),\dots,\xi(N)|\xi(1)=x_1,\dots,\xi(k)=x_k)
$$
f\"uggv\'enyeket. Ekkor minden $\tau$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'ora, amelyik $\tau$ meg\'all\'asi szab\'aly a
$\xi(1),\dots,\xi(N)$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'okra
n\'ezve
$$
E(u_\tau(\xi(1),\dots,\xi(\tau))=E(h_k(\xi(1),\dots,\xi(N)).
$$
Ez az eredm\'eny speci\'alisan azt jelenti, hogy Szindb\'ad
probl\'em\'aja (felhaszn\'alva az els\H{o} feladat eredm\'eny\'et)
ekvivalens a k\"ovetkez\H{o} feladattal: Adott f\"uggetlen
$\xi(1),\dots,\xi(N)$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
sorozata, melyekre $P(\xi(k)=j)=\dfrac1k$, $1\le j\le k$, $1\le k\le
N$, valamint az $u_k(x)=\dfrac kN$, ha $x=1$, $u_k(x)=0$, ha $x\neq
1$, $1\le k\le N$ f\"uggv\'enyek sorozata. Keress\"uk meg az
optim\'alis $\tau$ meg\'all\'asi szab\'alyt, melyre az
$Eu_\tau(\xi_\tau)$ v\'arhat\'o \'ert\'ek felveszi a minim\'at, \'es
hat\'arozzuk meg az $Eu_\tau(\xi_\tau)$ v\'arhat\'o \'ert\'eket.
\medskip
\item{} {\it Megold\'as:}\/ Azt kell bel\'atni, hogy
$$
\int I(\{\tau=k\}) h_k(\xi(1),\dots,\xi(N))dP=
\int I(\{\tau=k\})(u_k(\xi(1),\dots,\xi(k))dP.
$$
Itt \'es a tov\'abbiakban $I(A)$ fogja jel\"olni egy $A$ halmaz
indik\'atorf\"uggv\'eny\'et. A $\{\tau=k\}$
esem\'eny bizonyos $A(j_1,\dots,j_k)=\{\xi(1)=j_1,\dots,\xi(k)=j_k\}$
alak\'u esem\'enyek uni\'oja. Ez\'ert el\'eg bel\'atni, hogy
$$
\int I(A(j_1,\dots,j_k)) h_k(\xi(1),\dots,\xi(N))dP=
\int I(A(j_1,\dots,j_k))u_k(\xi(1),\dots,\xi(k))dP.
$$
Ez az azonoss\'ag viszont a felt\'eteles v\'arhat\'o \'ert\'ek
fogalm\'anak a k\"ovetkezm\'enye.
\item{} A feladat m\'asodik \'all\'{\i}t\'asa
k\"ovetkezm\'enye az els\H{o} feladatnak. Jegyezz\"uk meg, hogy e
feladat 1a) r\'esze alapj\'an a nyerem\'enyf\"uggv\'eny \'ert\'eke
az $u_k(x_1,\dots,x_k)=u_k(x_k)$,
$u_k(x)=\dfrac kN$, ha $x=1$, $u_k(x)=0$, ha $x\neq
1$, $1\le k\le N$ f\"uggv\'eny.
 
A k\"ovetkez\H{o} feladatban megfogalmazunk egy egyszer\H{u} \'es
term\'eszetes elvet az optim\'alis strat\'egia megtal\'al\'as\'ara,
\'es megmutatjuk, hogy Szindb\'ad probl\'em\'aja is
t\'ar\-gyal\-ha\-t\'o \'es megoldhat\'o ennek az elvnek a
seg\'{\i}ts\'eg\'evel. Ezt a feladatot nem fogalmazzuk meg az
\'altal\'anos esetben. Bizonyos speci\'alis megszor\'{\i}t\'asokat
tesz\"unk, mert a minket \'erdekl\H{o} feladatban ez nem okoz
probl\'em\'at \'es nem k\'{\i}v\'anjuk haszn\'alni az \'altal\'anos
(nulla va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'e\-g\H{u} felt\'eteleket is
megenged\H{o}) felt\'eteles v\'arhat\'o \'ert\'ek meglehet\H{o}sen
m\'ely ismereteket ig\'enyl\H{o} fogalm\'at. Ez a megjegyz\'es
egy\'ebk\'ent \'erv\'enyes az el\H{o}z\H{o} feladatra is.
Az al\'abbiakban csak olyan nyerem\'enyf\"uggv\'enyeket fogunk
tekinteni, melyekre $v_k(x_1,\dots,x_k)=v_k(x_k)$, \'es a
$\xi(1),\dots,\xi_k)$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
f\"uggetlenek. Ezekt\H{o}l a megszor\'{\i}t\'asokt\'ol nem lenne
neh\'ez megszabadulni.
 
Vezess\"uk be a k\"ovetkez\H{o} jel\"ol\'eseket. Legyen $\Theta_k$ az
olyan meg\'all\'asi szab\'alyok halmaza, melyekre $P(\tau\ge k)=1$,
minden $\tau\in \Theta_k$-ra. Legyen
$$
V_k=\sup\limits_{\tau\in
\Theta_k}E(v_\tau(\xi_\tau)), \tag $*$
$$
az optim\'alis v\'arhat\'o nyerem\'eny, ha csak olyan
meg\'all\'asi strat\'egi\'akat tekint\"unk, melyekben el\H{o}sz\"or a
$k$-ik l\'ep\'esben \'allhatunk meg.
\medskip
\item{3.} Tegy\"uk fel, hogy a $\xi_1,\dots,\xi_N$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok f\"uggetlenek, \'es
$v_k(\xi_1,\dots,\xi_k)=v_k(\xi_k)$. Ekkor a
$ V_k=\sup\limits_{\tau\in \Theta_k}E(v_\tau(\xi_\tau))$,
mennyis\'egek seg\'{\i}ts\'eg\'evel a k\"ovetkez\H{o}
re\-kur\-zi\-\'os formul\'at \'{\i}rhatjuk fel az al\'abb defini\'alt
$V_k$ \'es $U_k(x)$, $k=N,\dots,1$ mennyis\'egekre:
$$
\align
U_N(x)&=v_N(x),\quad V_N=EU_N(\xi(N)), \\
U_k(x)&=\max\{v_k(x),V_{k+1}\},\quad V_k=EU_k(\xi(k)).
\endalign
$$
A $V_k$ mennyis\'eg megadja a lehets\'eges maxim\'alis nyerem\'enyt,
ha a $k$-ik l\'ep\'esben vagy azut\'an \'allhatok meg, az $U_k(x)$ a
felt\'eteles v\'arhat\'o \'ert\'ek\'et ennek a maxim\'alis
nyerem\'enynek, felt\'eve hogy a $k$-ik l\'ep\'esben a $\xi(k)=x$
esem\'eny k\"ovetkezett be.
\item{} Megadhat\'o az optim\'alis strat\'egia is a
k\"ovetkez\H{o} m\'odon: Kisz\'amoljuk a fenti $V_k$, $k=1,2,\dots$,
mennyis\'egeket. A  $\Theta_k$ oszt\'alyban az optim\'alis $V_k$
v\'arhat\'o \'ert\'ek\H{u} nyerem\'enyt biztos\'{\i}t\'o
meg\'all\'asi szab\'aly a k\"ovetkez\H{o}: Az els\H{o} $k-1$
l\'ep\'esben nem \'allunk meg. A $k$-ik l\'ep\'esben akkor \'allunk
meg, ha $v(\xi_k)\ge V_{k+1}$, ellenkez\H{o} esetben tov\'abb
megy\"unk. Az $m$-ik l\'ep\'esben, $N>m\ge k$, akkor \'allunk meg, ha
nem \'alltunk meg el\H{o}bb, \'es $v(\xi_m)\ge V_{m+1}$. Az $N$-ik
l\'ep\'esben mindenk\'epp meg\'allunk. A fent defini\'alt $V_k$
mennyis\'egek megegyeznek a $(*)$ formul\'aban szerepl\H{o} $V_k$
mennyis\'egekkel. Mi a fenti formul\'ak szeml\'eletes tartalma? \medskip
\item{} {\it Megold\'as:}\/ Bel\'atjuk $k$-ra alkalmazott ``backward"
indukci\'oval, hogy $\tau\in \Theta_k$ eset\'eben a v\'arhat\'o
optim\'alis nyerem\'eny $V_k$, \'es a fent le\'{\i}rt strat\'egia
optim\'alis. A $k=N$ esetben az egyetlen lehets\'eges strat\'egia
optim\'alis, \'es annak nyerem\'enye $V_N$. Tegy\"uk fel, hogy az
\'all\'{\i}t\'ast m\'ar tudjuk $k+1$-re \'es l\'assuk be $k$-ra. A
bizony\'{\i}t\'asban felhaszn\'aljuk azt, hogy mivel a
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok f\"uggetlenek \'es a
nyerem\'eny csak a meg\'all\'asi id\H{o}ponttal indexezett
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o \'ert\'ek\'et\H{o}l f\"ugg,
ez\'ert ha a $k$-ik l\'ep\'esben nem \'allok meg, akkor a
nyerem\'enyem el\'erhet\H{o} felt\'eteles v\'arhat\'o \'ert\'eke
felt\'eve az els\H{o} $k$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
\'ert\'ekeit, ez a felt\'eteles v\'arhat\'o \'ert\'ek
nem f\"ugg a felt\'etelt\H{o}l. Val\'oban semmilyen
strat\'egi\'aval \'es semmilyen $\xi(1)=j_1$,\dots, $\xi(k)=j_k$
felt\'etel teljes\"ul\'ese eset\'en nem tudom el\'erni, hogy ez
a felt\'eteles v\'arhat\'o \'ert\'ek nagyobb legyen mint $V_{k+1}$,
azt viszont el tudom \'erni, hogy ez $V_{k+1}$
legyen. Val\'oban, ha valamilyen strat\'egi\'aval el tudn\'am \'erni,
hogy a felt\'eteles v\'arhat\'o \'ert\'ek hat\'arozottan nagyobb
legyen mint $V_{k+1}$, ami azt jelenten\'e, hogy minden lehets\'eges
$\xi(1)=j_1,\dots,\xi(k)=j_k,\xi(k+1)=j_{k+1}\dots,\xi(N)=j_N$
eset\'en megmondva, hogy hol \'alljak meg el\'erhet\H{o}, hogy a felt\'eteles
v\'arhat\'o \'ert\'ek nagyobb legyen mint $V_{k+1}$, akkor alkalmazva
azt a
meg\'all\'asi szab\'alyt, mely szerint ugyanott \'allok meg egy olyan
$j_1',\dots,j_k',\dots, j_N$ megfigyelt sorozat eset\'en, melyben az
els\H{o} $k$ megfigyelt \'ert\'ek k\"ul\"onb\"ozhet az el\H{o}z\H{o}
sorozatt\'ol, de a k\'es\H{o}bbiek nem, el\'erhetem hogy egy az
optim\'alisn\'al jobb strat\'egia $V_{k+1}$ nyerem\'eny\'en\'el
el\H{o}ny\"osebb meg\'all\'asi szab\'alyt tal\'aljak a $\Theta_{k+1}$
halmazban, ami ellentmond\'as. A $V_{k+1}$ felt\'eteles v\'arhat\'o
\'ert\'eket viszont el tudom \'erni, ha alkalmazom a $V_{k+1}$
optim\'alis nyerem\'enyt ny\'ujt\'o $\tau\in \Theta_{k+1}$
strat\'egi\'at f\"uggetlen\"ul a $\xi(1)=j_1,\dots,\xi(k)=j_k$
\'ert\'ekekt\H{o}l.
\item{} Ez azt jelenti, hogy a $\tau\in\Theta_k$ meg\'all\'asi
szab\'alyok k\"oz\"ott az optimumot keresve el\'eg csak azokat
figyelembe venni, melyekben minden
$\xi(1)=j_1,\dots,\xi(k)=j_k,\xi(k+1)=j_{k+1}\dots,\xi(N)=j_N$
esem\'eny eset\'en vagy meg\'allunk a $k$-ik id\H{o}pontban vagy
tov\'abbl\'ep\"unk \'es ezut\'an
az optim\'alis $\tau\in\Theta_{k+1}$ meg\'all\'asi strat\'egi\'at
folytatjuk.
Az els\H{o} esetben $v_k(\xi_k)$ a m\'asodik esetben pedig $V_{k+1}$
lesz a felt\'eteles nyerem\'eny\"unk. Ez\'ert $v_k(\xi_k)\ge V_{k+1}$
eset\'eben \'erdemes meg\'allni, m\'{\i}g $v_k(\xi_k)< V_{k+1}$
esetben \'erdemes nem meg\'allni a $k$-ig l\'ep\'esben. A
feladatban ezt a rekurzi\'ot \'{\i}rtam le \'es ennek nyerem\'eny\'et
adtam meg. A feladat szeml\'eletes tartalma az, hogy minden egyes
l\'ep\'esben a k\'et lehets\'eges v\'alaszt\'as k\"oz\"ul
(tov\'abbmenni vagy meg\'allni) az el\H{o}\-ny\"o\-seb\-bet
v\'alasztjuk. \medskip
\item{4.} Oldjuk meg a 2. pontban megfogalmazott feladatot a 3.
feladat eredm\'eny\'enek a seg\'{\i}ts\'eg\'evel.
\item{}{\it Megold\'as:}\/ Ebben az esetben $v_k(x)=\dfrac kN$, ha
$x=1$, $v_k(x)=0$, ha $x\neq1$, \'es a 3. feladat rekurziv formul\'aja
alapj\'an
$$
V_N=\frac1N,\quad V_L=\frac{L-1}L V_{L+1}+\frac1L\max\left\{\frac LN,
V_{L+1}\right\},\; \text{ ha } 1\le L\le N-1,
$$
ahol $V_L=EU_L(\xi_L)$, a maxim\'alis nyerem\'eny \'ert\'eke azon
meg\'all\'asi szab\'alyok k\"oz\"ott, melyekben az els\H{o} $L$
l\'ep\'esben nem szabad meg\'allni.
\item{} Legyen $P(L)=\dfrac1N\sum\limits_{k=L}^N\dfrac{L-1}{k-1}$,
\'es $L^*$ a legkisebb olyan $L$ sz\'am, melyre $P(L+1)\ge \dfrac LN$,
azaz $\sum\limits_{k=L}^N\dfrac 1{k-1}\ge1$. Ekkor $V_L=P(L)$, ha $L\ge
L^*$, \'es azt \'all\'{\i}tjuk, hogy $V_L=P(L^*)$, ha $L<L^*$. Ennek
\'erdek\'eben vegy\"uk \'eszre, hogy a $P(L)$ sz\'amsorozat
teljes\'{\i}ti a $P(L)=\dfrac{L-1}L P(L-1)+\dfrac1L\dfrac LN$
rekurzi\'os formul\'at. Val\'oban, $\dfrac{L-1}L
P(L+1)=\dfrac1N\sum\limits_{k=L+1}^N
\dfrac{L-1}{k-1}$, \'es $\dfrac 1L\dfrac LN=\dfrac 1N\dfrac{L-1}{L-1}$.
Ezeket az azonoss\'agokat \"osszeadva megkapjuk a k\'{\i}v\'ant
formul\'at. Mivel $L\ge L^*$ eset\'en a $V_L$ sz\'amok ugyanezt a
rel\'aci\'{\i}\'ot teljes\'{\i}tik, \'es $P(N)=V_N$. Innen $P(L)=V_L$,
ha $N\ge L\ge L^*$. M\'asr\'eszt $L<L^*$ eset\'eben a $V_L$ sorozatra
adott rekurzi\'os formula $V_L=\dfrac{L-1}L V_{L+1}+\dfrac1L
V_{L+1}=V_{L+1}$ alak\'u, azaz $V(L)=V(L+1)$, mert ebben az esetben
$\max\left\{\dfrac LN, V_{L+1}\right\}=V_{L+1}$. Innen $V_L=V_{L^*}$,
ha $L\le L^*$.
\item{} Ennek alapj\'an az optim\'alis $\tau$ strat\'egia
a k\"ovetkez\H{o}: $\tau=\min\{k\: k\ge L^*, \xi(k)=1\}$, \'es
$\tau=N$, ha ilyen $k$ sz\'am nincsen. A nyerem\'eny v\'arhat\'o
\'ert\'eke pedig $P(L^*)=\dfrac{L^*-1}N\sum\limits_{k=L^*}^N
\dfrac1{k-1}$.
\item{5.} Nagy $N$-re $L^*\sim\dfrac Ne$, \'es az optim\'alis
strat\'egia nyeres\'ege (annak val\'osz\'{\i}n\H{u}s\'ege, hogy
Szindb\'adnak s\'{\i}ker\"ul a legszebb h\"olgyet kiv\'alasztani)
k\"or\"ulbel\"ul $e^{-1}$.
\item{} {\it Megold\'as:}\/ Az $L^*=L^*(N)$ sz\'amot \'ugy hat\'aroztuk
meg mint a legkisebb olyan $L$ sz\'am, melyre $P(L+1)\ge \dfrac LN$,
$P(L)=\dfrac{L-1}N\sum\limits_{k=L}^N\dfrac1{k-1}$. Viszont
$P(L+1)\sim\dfrac LN\log\(\dfrac NL\)$, ahonnan
$\log\(\dfrac{N}{L^*}\)\sim 1$, azaz $L^*\sim\dfrac Ne$, \'es a
nyerem\'eny \'ert\'eke k\"o\-r\"ul\-be\-l\"ul $P(L^*)\sim\dfrac 1e$.
 
\bye
 
\vfill\eject
 
 
\bigskip
Az idei Schweitzer verseny val\'osz\'{\i}n\H{u}s\'egsz\'am\'{\i}t\'asi
feladat\'at kiss\'e m\'ask\'epp fogalmazzuk meg, \'es val\'oj\'aban egy
\'elesebb eredm\'enyt bizony\'{\i}tunk be. \smallskip \noindent
Az $n$ dimenzi\'os egys\'egkocka minden cs\'ucspontj\'ahoz hozz\'a van
rendelve egy standard norm\'alis
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o, \'es ezek a
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok f\"uggetlenek. A
k\"ovetkez\H{o} v\'eletlen algoritmus seg\'{\i}ts\'eg\'evel keress\"uk
e val\'osz\'{\i}n\H{u}s\'egi v\'al\-to\-z\'ok maximum\'anak egy j\'o
k\"ozel\'{\i}t\'es\'et:
\item{a.)} Az els\H{o} l\'ep\'esben kiv\'alasztunk v\'eletlen\"ul egy
pontot az $n$ dimenzi\'os kocka cs\'ucsai k\"oz\"ul, minden pontot
egyforma val\'osz\'{\i}n\H{u}s\'eggel v\'alasztva.
\item{b.)} A $k$-ik l\'ep\'esben tekintj\"uk az $k-1$-ik l\'ep\'esben
kiv\'alasztott cs\'ucspont szomsz\'edait. Ha ezek mindegyik\'ehez
kisebb sz\'am van hozz\'arendelve, mint ehhez a ponthoz, akkor az
algoritmust befejezz\"uk. Ha vannak olyan szomsz\'edos pontok,
melyekhez na\-gyobb \'ert\'ek van hozz\'arendelve, akkor ezek k\"oz\"ul
egyforma val\'osz\'{\i}n\H{u}s\'eggel az eddig t\"ort\'entekt\H{o}l
f\"uggetlen\"ul kiv\'alasztjuk az egyiket.
 
\noindent
Jel\"olje $\lambda(n)$ az algoritmus l\'ep\'essz\'am\'at.
Bizony\'{\i}tsuk be, hogy $\dfrac{\lambda(n)-\log n}{\sqrt{\log n}}$
eloszl\'asban konverg\'al a standard norm\'alis eloszl\'ashoz, ha
$n\to\infty$. \bigskip\noindent
\item{$1'.)$} Bizony\'{\i}tsuk be, hogy a Schweitzer feladat
\'all\'{\i}t\'asa k\"ovetkezik a k\"ovetkez\H{o} feladat
eredm\'eny\'eb\H{o}l:\hfill\break
Legyen $x_1,\dots,x_{2^n}$ $2^n$ k\"ul\"onb\"oz\H{o} val\'os sz\'am.
Sorsoljuk ki ezeket a sz\'amokat egy $n$ dimenzi\'os kocka
cs\'ucspontjai k\"oz\"ott  \'ugy, hogy minden lehets\'eges elhelyez\'es
va\-l\'o\-sz\'{\i}\-n\H{u}\-s\'ege $\frac1{(2^n)!}$. Alkalmazzuk a
k\"ovetkez\H{o} algoritmust. Els\H{o} l\'ep\'esben kiv\'alasztunk \'es
megn\'ez\"unk v\'eletlen\"ul egy cs\'ucspontot, \'es ez az algoritmus
\'altal (a maximum\-hely\-re) adott becsl\'es az els\H{o} l\'ep\'esben.
A $k$-ik l\'ep\'esben v\'eletlen m\'odon megn\'ezz\"uk a $k-1$-ik
l\'ep\'esben adott becsl\H{o} cs\'ucspont egyik m\'eg nem l\'atott
szomsz\'edj\'at. Minden lehets\'eges pontot egyforma
val\'osz\'{\i}n\H{u}s\'eggel v\'alasztunk, felt\'eve hogy ilyen
pont l\'etezik. Ha az ehhez a ponthoz rendelt sz\'am kisebb mint a
$k-1$-ik l\'ep\'esben adott becsl\'es, akkor az algoritmus $k$-ik \'es
$k-1$-ik l\'ep\'es\'eben adott becsl\'esek megegyeznek. Ha az \'uj
ponthoz rendelt sz\'am nagyobb, mint a $k-1$-ik l\'ep\'esben adott
becsl\'es, akkor ez az \'uj pont lesz a becsl\'es az algoritmus $k$-ik
l\'ep\'es\'eben. Ha a $k-1$-ik l\'ep\'esben kijel\"olt becsl\H{o}
pontnak m\'ar minden pontj\'at l\'attuk, akkor az algoritmust
befejezz\"uk. Jel\"olje $\bar \lambda(n)$ az algoritmus
k\"ul\"onb\"oz\H{o} l\'ep\'eseiben adott becsl\H{o} pontok sz\'am\'at.
Ekkor a $\dfrac {\bar \lambda(n)-\log n}{\sqrt{\log n}}$
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o eloszl\'asa konverg\'al a
standard norm\'alis eloszl\'ashoz, ha $n\to\infty$.
\medskip
Az $1'.)$  feladat \'all\'{\i}t\'as\'at fogjuk bebizony\'{\i}tani.
Ehhez l\'assuk be el\H{o}sz\"or, hogy
\medskip
\item{$2'.$)} Az algoritmus befejez\'ese el\H{o}tt nem fordulhat
el\H{o}, hogy $n$ egym\'as ut\'ani l\'ep\'esben nem v\'altoztattuk meg
a becsl\H{o} pontot. M\'asr\'eszt, addig az id\H{o}pontig, am\'{\i}g a
$d-1$-ik \'es $d$-ik becsl\H{o}pont kiv\'alaszt\'asa k\"oz\"ott
kevesebb, mint $n-2d$ l\'ep\'es t\"ort\'enik minden $d$ sz\'amra, az
algoritmus nem fejez\H{o}dik be.
\medskip Legyen $\pi(k)$ a $k$-ik id\H{o}pontban megfigyelt pontbeli
\'ert\'ek relat\'{\i}v sorrendje az addig megfigyeltek k\"oz\"ott. Be
fogjuk l\'atni, hogy a teljesen v\'eletlen sorrend miatt ez a
lehets\'eges $1,\dots,k$ \'ert\'ekek mindegyik\'et $\frac1k$
val\'osz\'{\i}n\H{u}s\'eggel veszi fel, a m\'ultt\'ol f\"uggetlen\"ul.
Ennek az \'all\'{\i}t\'asnak \'es a 2.) feladatnak a
seg\'{\i}ts\'eg\'evel nem neh\'ez a k\'{\i}v\'ant
\'all\'{\i}t\'ast a centr\'alis hat\'areloszl\'ast\'etelb\H{o}l
levezetni.
 
Soroljuk fel az $n$ dimenzi\'os kocka $N=2^n$ cs\'ucspontjait
valamilyen r\"ogz\'{\i}tett sorrendben, \'es jel\"olj\"uk meg azt, hogy
az $j$ sz\'amnak, $1\le j\le N$ pontnak megfelel\H{o} cs\'ucspont
szomsz\'edainak mely sz\'amok felelnek meg. Defini\'aljuk a
k\"ovetkez\H{o} v\'eletlen $\pi=\pi_0=\{\pi(1),\pi(2),\dots,\pi(N)\}$
permut\'aci\'ot az $\{1,2,\dots,N\}$ halmazon:  Ha a $j$ pontnak
megfelel\H{o} cs\'ucshoz az $x_j$ pont van hozz\'arendelve, akkor
legyen $\pi(j)$ az $x_j$ sz\'am nagys\'ag szerinti sorrendje az
$x_1,\dots,x_N$ sz\'amok k\"oz\"ott. Ez az $\{1,2,\dots,N\}$ halmaznak
egyenletes eloszl\'as\'u permut\'aci\'oja. Az algoritmus $k$-ik
l\'ep\'es\'eben defini\'aljuk az $\{1,\dots,N\}$ sz\'amok egy
v\'eletlen \'atrendez\'es\'et \'es egy $\pi_k$ permut\'aci\'ot a
k\"ovetkez\H{o} m\'odon. Tekintj\"uk az $\{1,\dots,N\}$ sz\'amok
\'atrendez\'es\'et a $k-1$-ik l\'ep\'esben (a 0-ik \'atrendez\'es a
sz\'amok eredeti sorrendje), \'es a $k$-ik l\'ep\'esben megn\'ezett
cs\'ucspontot a $k-1$-ik \'atrendez\'es $k$-ik hely\'ere tessz\"uk.
Ez a $k$-ik \'atrendez\'es. Legyen $\pi_k(j)$ a $k$-ik
\'atrendez\'eseben a $j$ pont\-hoz rendelt cs\'ucsban \"ul\H{o} sz\'am
nagys\'ag szerinti sorrendje.
\item{$3'.$)} Legyen $\pi$ az $\{1,\dots,N\}$ halmaz v\'eletlen
permut\'aci\'oja, \'es $L$, $1\le L\le N$, tetsz\H{o}leges
r\"ogz\'{\i}tett eg\'esz sz\'am. L\'assuk be, hogy a $\pi$
permut\'aci\'o akkor \'es csak akkor egyenletes eloszl\'as\'u, ha
az $\{1,\dots,L\}$ sz\'amok $\{\pi(1),\dots,\pi(L)\}$ \'altal megadott
$\{\bar\pi(1),\dots,\bar\pi(L)\}$ bels\H{o} permut\'aci\'oja egyenletes
eloszl\'as\'u, (e fogalom definici\'oj\'at l\'asd a Szindb\'ad
probl\'ema elej\'en), ez f\"uggetlen a $(\pi(L+1),\dots,\pi(N))$
v\'eletlen vektort\'ol, \'es ez ut\'obbi vektor minden lehets\'eges
\'ert\'eket $\dfrac1{L+1}\cdots\dfrac1N$ val\'osz\'{\i}n\H{u}s\'eggel
vesz fel.
\itemitem{a.)} Legyen adva egy $\xi$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'o \'ugy, hogy a $\{\bar\pi(1),\dots,\bar\pi(L)\}$ bels\H{o}
permut\'aci\'o \'es a $\xi$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o
\'altal k\'epzett vektor f\"uggetlen a $\{\pi(L+1),\dots,\pi(N)\}$
vektort\'ol. Legyen $P=P(\xi,\{\bar\pi(1),\dots,\bar\pi(L)\})$ az
$\{L+1,\dots,N\}$ halmaznak a $\xi$ val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'ot\'ol \'es a $\bar \pi$ bels\H{o} permut\'aci\'ot\'ol
f\"ugg\H{o} \'at\-ren\-de\-z\'e\-se. Defini\'aljuk a
$\tilde\pi=\{\tilde\pi(1),\dots,\tilde\pi(N)\}$ permut\'aci\'ot a
k\"ovetkez\H{o} m\'odon: $\tilde\pi(j)=\pi(j)$, ha $1\le j\le L$,
\'es $\tilde\pi(j)=\pi(P(j))$, ha $L+1\le j\le N$. Bizony\'{\i}tsuk be,
hogy a $\tilde\pi$ permut\'aci\'o egyenletes eloszl\'as\'u.
\itemitem{b.)} A feladat el\H{o}tt defini\'alt $\pi_k$ v\'eletlen
permut\'aci\'o egyenletes eloszl\'as\'u.
\item{$4'.)$} L\'assuk be, hogy minden $\e>0$ sz\'amhoz l\'etezik olyan
$C=C(\e)$ sz\'am, hogy ameny\-nyiben a $Cn$-ik l\'ep\'esben az $1'.)$
feladatban le\'{\i}rt algoritmus nem fejez\H{o}dik be, akkor felt\'eve
az els\H{o} $Cn$ l\'ep\'esben megfigyelt bels\H{o} sorrendet, annak
felt\'eteles val\'osz\'{\i}n\H{u}s\'ege (b\'armely lehets\'eges sorrend
eset\'en), hogy az algoritmus $Cn+n$ l\'ep\'esben befejez\H{o}dik
nagyobb mint $1-\e$.\hfill\break
Defini\'aljuk a $\xi_k$, $k=1,\dots,N$, val\'osz\'{\i}n\H{u}s\'egi
v\'altoz\'okat a k\"ovetkez\H{o} m\'odon. Legyen $\xi_k=1$, ha az $1'.)$
feladat megold\'asa \'erdek\'eben defini\'alt \'atrendez\'esek
k\"oz\"otti utols\'o \'atrendez\'es szerint a $k$-ik ponthoz rendelt
cs\'ucsban \"ul\H{o} sz\'am nagyobb, mint a meg\-el\H{o}\-z\H{o}
pontokhoz rendelt cs\'ucsokban \"ul\H{o} sz\'am. Ellenkez\H{o} esetben
legyen $\xi_k=0$.  Ekkor $\xi_1,\dots,\xi_N$  f\"uggetlen
val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok, \'es
$P(\xi_k=1)=1-P(\xi_k=0)=\frac1k$. Minden $\e>0$-hoz
l\'etezik olyan $C=C(\e)$ sz\'am, hogy el\'eg nagy $n$-re
$$
P\(\sum_{k=1}^{n/3} \xi_k<x\)\ge P\(\bar\lambda(n)<x\)\ge
P\(\sum_{k=1}^{Cn} \xi_k<x\)-\e
$$
minden $x$ sz\'amra. Bizony\'{\i}tsuk be az $1'.)$ feladat
\'all\'{\i}t\'as\'at.
 
 
 \bye
