\magnification=\magstep1
\input amstex
\hsize=16truecm
\parskip=4pt
\parindent=18pt
\TagsOnRight
 
\define\({\left(}
\define\){\right)}
\define\e{\varepsilon}
 
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 s\'{\i}ker 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}$? A fenti probl\'em\'at egy feladatsor
seg\'{\i}ts\'eg\'evel fogjuk megoldani. Az itt el\H{o}fordul\'o
gondolatmenet seg\'{\i}t az idei Schweitzer verseny
val\'osz\'{\i}n\H{u}s\'eg feladat\'anak a
megold\'as\'aban is. Ezt a probl\'em\'at is t\'argyalni fogjuk.
\bigskip
\centerline{\bf Feladatok}
R\"ogz\'{\i}ts\"unk egy pozit\'{\i}v eg\'esz $N$ sz\'amot, \'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.
 
Adva az $\{1,\dots,N\}$ halmaznak egy $\pi=\{\pi(1),\dots,\pi(N)\}$
permut\'aci\'oja \'es egy $1\le L\le N$ eg\'esz sz\'am, nevezz\"uk a
$\pi$ permut\'aci\'o $L$-ed rend\H{u} bels\H{o} sorrendj\'enek
az $\{1,\dots,L\}$ halmaznak azt a
$\bar\pi=\bar\pi_L=\{\bar\pi_L(1),\dots,\bar\pi_L(L)\}\}$
permut\'aci\'oj\'at,
mely a $\pi(1),\dots,\pi(L)$ sz\'a\-mok egym\'as k\"oz\"otti
sorrendj\'et adja meg. Pontosabban, ha a $\{\pi(1),\dots,\pi(L)\}$
sz\'am\-hal\-maz elemeit nagys\'ag szerint sorrendbe rakva a
$\{j_1,\dots,j_L\}$, $1\le j_1<j_2<\cdots<j_L\le
N$, halmazt kapjuk, akkor $\pi(s)=j_r$ eset\'en $\bar\pi_L(s)=r$,
$1\le s\le L$. \smallskip
\item{1.} V\'alasszuk az $\{1,\dots,N\}$ halmaz egy v\'eletlen $\pi$
permut\'aci\'oj\'at egyenletes eloszl\'assal. Legyen $\xi_L$ az
$\{\pi(1),\dots,\pi(L)\}$ sz\'amok k\"oz\"ul az utols\'onak a
bels\H{o} sorrend szerinti indexe, azaz $\xi_L=\bar\pi_L(L)$, $1\le
L\le N$. Ekkor a $\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.)} Annak felt\'eteles val\'osz\'{\i}n\H{u}s\'ege, hogy
$\pi(L)$ a legkisebb az \"osszes $\pi(j)$, $1\le j\le N$, k\"oz\"ott,
azaz $\pi(L)=1$ azon felt\'etel mellett, hogy  $\pi(L)$ a legkisebb az
\"osszes $\pi(j)$, $1\le j\le L$, sz\'am k\"oz\"ott
$\prod\limits_{j=L+1}^N\dfrac {j-1}j=\dfrac LN$. M\'as sz\'oval
$$
P\(\pi(L)=1|\bar\pi_L(1)=j_1,\bar\pi_L(2)=j_2,\dots,\bar\pi_L(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$.
\medskip
Legyen adva val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'oknak egy v\'eges
$\xi_1,\dots,\xi_N$ sorozata, mely val\'o\-sz\'{\i}\-n\H{u}\-s\'egi
v\'altoz\'ok mindegyike v\'eges sok \'ert\'eket vesz fel, \'es legyen
adva minden $k$-ra egy $g_k(\xi_1,\dots,\xi_k)$ (v\'eletlen)
nyerem\'enyf\"uggv\'eny. Ez a nyerem\'eny\"unk, ha a $k$-ik l\'ep\'esben
\'allunk meg. Szeretn\'enk olyan meg\'all\'asi
strat\'egi\'at tal\'alni, mely optimaliz\'alja v\'arhat\'o
nyeres\'eg\"unket. 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\'argyalhat\'o
\'es megoldhat\'o ennek az elvnek a seg\'{\i}ts\'eg\'evel.
 
El\H{o}sz\"or megfogalmazzuk pontosan a meg\'all\'asi strat\'egia
fogalm\'at. Azt mondjuk, hogy a $\tau$ 0, 1, \dots, $N$ \'ert\'ekeket
felvev\H{o} val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'o ($N$ l\'ep\'esben
befejezend\H{o}) meg\'all\'asi szab\'aly,  ha $P(\tau\le N)=1$, \'es
tetsz\H{o}leges $1\le k\le N$-re azt, hogy $\tau=k$ teljes\"ul-e a
$\xi_1,\dots, \xi_k$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
\'ert\'ekei alapj\'an el tudjuk d\"onteni. (Azaz azt, hogy a $k$-ik
l\'ep\'esben meg\'allunk-e vagy nem a $k$-ik id\H{o}pontig szerzett
inform\'aci\'o alapj\'an el tudjuk d\"onteni.)
 
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(\xi_1,\dots,\xi_k)=\sup\limits_{\tau\in
\Theta_k}E(g_\tau(\xi_1,\dots,\xi_\tau)|\xi_1,\dots,\xi_k),
$$
a felt\'eteles 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, felt\'eve az els\H{o} $k$
l\'ep\'esben be\-k\"o\-vet\-ke\-zett $\xi_1,\dots,\xi_k$ \'ert\'ekeket.
 
(Megjegyzem, hogy az itt szerepl\H{o} fogalmakat \'es k\'es\H{o}bbi
eredm\'enyeket minden neh\'ezs\'eg n\'elk\"ul lehet
\'altal\'anos\'{\i}tani tetsz\H{o}leges nem felt\'etlen\"ul
diszkr\'et val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok eset\'ere. De erre
az \'altal\'anos\'{\i}t\'asra az itt vizsg\'alt probl\'ema
megold\'as\'ahoz nincs sz\"uks\'eg\"unk, \'es az
\'altal\'anos\'{\i}t\'ashoz sz\"uks\'eg van n\'eh\'any csak a
fels\H{o} \'evekben tan\'{\i}tott m\'ert\'ekelm\'eleti eredm\'enyre is.)
\medskip
\item{2.} A k\"ovetkez\H{o} rekurzi\'os formula \'erv\'enyes:
$$
\align
v_N(\xi_1,\dots,\xi_N)&=g_N(\xi_1,\dots,\xi_N)\\
v_k(\xi_1,\dots,\xi_k)&=\max\{g_k(\xi_1,\dots,\xi_k),E\(v_{k+1}
(\xi_1,\dots,\xi_{k+1})|\xi_1,\dots,\xi_k\)\}, \\
&\qquad\qquad\qquad 1\le k\le N-1
\endalign
$$
A k\"ovetkez\H{o} m\'odon kaphatunk optim\'alis meg\'all\'asi
strat\'egi\'at. Ha a $k$-ik l\'ep\'es el\H{o}tt nem \'allunk meg, akkor
a $k$-ik l\'ep\'esben meg\'allunk, ha
$$
g_k(\xi_1,\dots,\xi_k)\ge E\(v_{k+1}
(\xi_1,\dots,\xi_{k+1})|\xi_1,\dots,\xi_k\),
$$
ellenkez\H{o} esetben pedig nem \'allunk meg a $k$-ik l\'ep\'esben,
$1\le k\le N-1$.
\item{} Ha a $\xi_1,\dots,\xi_N$ val\'osz\'{\i}n\H{u}s\'egi v\'altoz\'ok
f\"uggetlenek, \'es $g_k(\xi_1\dots,\xi_k)=g_k(\xi_k)$, akkor a fenti
rekurzi\'o egyszer\H{u}bb. Nevezetesen, ebben az esetben
$v_k(\xi_1,\dots,\xi_k)=v_k(\xi_k)$, \'es legyen $V_k=Ev_k(\xi_k)$
jel\"ol\'essel
$$
v_N(\xi_N)=g_N(\xi_N),\quad v_k(\xi_k)=\max\{g_k(\xi_k), V_{k+1}\}
$$
\itemitem{2a.)} A Szindb\'ad probl\'em\'ajak\'ent megfogalmazott
feladat ilyen tipus\'u feladatra ve\-zet\-het\H{o} vissza a
k\"ovetkez\H{o} v\'alaszt\'assal: $\xi_1,\dots,\xi_N$ f\"uggetlen
val\'osz\'{\i}n\H{u}s\'egi v\'al\-to\-z\'ok, $P(\xi_L=j)=\dfrac1L$,
$1\le
j\le L$, $g_L(\xi_L)=\dfrac LN$, ha $\xi_L=1$, \'es $g_L(\xi_L)=0$, ha
$\xi_L\neq1$, $1\le L\le N$.
\item{3.} Oldjuk meg a 2a.) pontban megfogalmazott feladatot. Mutassuk
meg, hogy ebben az esetben
$$
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=Ev_L(\xi_L)$.
\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 $V_L=P(L^*)$, ha $L<L^*$. 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 \'ert\'eke
$P(L^*)=\dfrac{L^*-1}N\sum\limits_{k=L^*}^N \dfrac1{k-1}$.
\item{} L\'assuk be, hogy az el\H{o}bb defini\'alt $P(L)$ sz\'am annak
a val\'osz\'{\i}n\H{u}s\'ege, hogy az $L$ id\H{o}pont ut\'an megjelenik
egy (els\H{o}) lok\'alis minimum, azaz olyan $k$, $k\ge L$, melyre
$\xi_k=1$ \'es ez egyben a minimum is. Mi a fenti formul\'ak
szeml\'eletes tartalma?
\item{4.} 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}$.
\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