Rendkívül népszerű és egyben tanulságos a következő valószínűségi, optimalizációs probléma, mely Magyarországon Szindbád problémája néven vált ismertté. A következő történetet szokták hozzáfűzni:

Szindbád megmentette a kalifa életét, és ezért jutalmul feleségül veheti a kalifa egyik háremhölgyét. A háremhölgyek sorban elvonulnak Szindbád mellett, egyszerre csak egy háremhölgy jelenik meg. Szindbád minden háremhölgy szépségét össze tudja hasonlítani az elözőleg megjelentekével, és egyértelműen meg tudja állapítani, hogy az eddig látott háremhölgyek közül ki a legszebb. Egy éppen megjelent háremhölgyről megjelenése után azonnal el kell döntenie, hogy őt akarja-e feleségül venni, és ezt a döntést később nem változtathatja meg. Szindbád tudja, hogy a kalifának hány háremhölgye van, viszont semmit nem tud arról, hogy a még nem látott háremhölgyek milyen szépek. A háremhölgyek véletlen sorrendben jelennek meg, és minden sorrend egyforma valószínű. Szindbád szeretné a legszebb háremhölgyet választani. Milyen stratégiával tudja ezt a lehető legnagyobb valószínűséggel elérni, és mekkora ez a valószínűség?

Gondoljuk meg, mekkora a síker valószínűsége nagy számú feleségjelölt esetén. Ez a valószínűség nullához tart-e, ha a jelöltek száma végtelenhez tart, vagy például tetszőlegesen nagy szám esetén elérhető-e az, hogy a síker valószínűsége nagyobb, mint mondjuk \frac{1}{10}? A fenti problémát egy feladatsor segítségével fogjuk megoldani. Az itt előforduló gondolatmenet segít az idei Schweitzer verseny valószínűség feladatának a megoldásában is. Ezt a problémát is tárgyalni fogjuk.

Feladatok

Rögzítsünk egy pozitív egész N számot, és tekintsük az {1, …, N} halmaz összes lehetséges π = {π(1), …, π(N)} permutációját. Azt mondjuk, hogy egy permutációt véletlenül kiválasztunk egyenletes eloszlással, ha kiválasztjuk véletlenül az {1, …, N}

halmaz egy permutációját, és minden lehetséges permutációt \frac{1}{N!} valószínűséggel választunk.

Adva az {1, …, N} halmaznak egy π = {π(1), …, π(N)} permutációja és egy 1 ≤ L ≤ N egész szám, nevezzük a π permutáció L-ed rendű belső sorrendjének az {1, …, L} halmaznak azt a π̄ = π̄_{L} = {π̄_{L}(1), …, π̄_{L}(L)}} permutációját, mely a π(1), …, π(L) számok egymás közötti sorrendjét adja meg. Pontosabban, ha a {π(1), …, π(L)} számhalmaz elemeit nagyság szerint sorrendbe rakva a {j_{1}, …, j_{L}}, 1 ≤ j_{1} < j_{2} < ⋯ < j_{L} ≤ N, halmazt kapjuk, akkor π(s) = j_{r} esetén π̄_{L}(s) = r, 1 ≤ s ≤ L.

1. Válasszuk az {1, …, N} halmaz egy véletlen π permutációját egyenletes eloszlással. Legyen ξ_{L} az {π(1), …, π(L)} számok közül az utolsónak a belső sorrend szerinti indexe, azaz ξ_{L} = π̄_{L}(L), 1 ≤ L ≤ N. Ekkor a ξ_{L} valószínűségi változók függetlenek,

és P (ξ_{L} = k) = \frac{1}{L}, ha 1 ≤ k ≤ L minden 1 ≤ L ≤ N-re.

1a.) Annak feltételes valószínűsége, hogy π(L) a legkisebb az összes π(j), 1 ≤ j ≤ N, között, azaz π(L) = 1 azon feltétel mellett, hogy π(L) a legkisebb az összes π(j),

1 ≤ j ≤ L, szám között ∏_{j=L+1}^{N} \frac{j − 1}{j} = \frac{L}{N}. Más szóval

P (π(L) = 1|π̄_{L}(1) = j_{1}, π̄_{L}(2) = j_{2}, …, π̄_{L}(L) = j_{L}) = \frac{L}{N}

az 1, 2, …, L számoknak minden olyan j_{1}, j_{2}, …, j_{L} permutációjára, melyre

j_{L} = 1.

Legyen adva valószínűségi változóknak egy véges ξ_{1}, …, ξ_{N} sorozata, mely valószínűségi változók mindegyike véges sok értéket vesz fel, és legyen adva minden k-ra egy g_{k}(ξ_{1}, …, ξ_{k}) (véletlen) nyereményfüggvény. Ez a nyereményünk, ha a k-ik lépésben állunk meg. Szeretnénk olyan megállási stratégiát találni, mely optimalizálja várható nyereségünket. A következő feladatban megfogalmazunk egy egyszerű és természetes elvet az optimális stratégia megtalálására, és megmutatjuk, hogy Szindbád problémája is tárgyalható és megoldható ennek az elvnek a segítségével.

Először megfogalmazzuk pontosan a megállási stratégia fogalmát. Azt mondjuk, hogy a τ 0, 1, …, N értékeket felvevő valószínűségi változó (N lépésben befejezendő) megállási szabály, ha P (τ ≤ N) = 1, és tetszőleges 1 ≤ k ≤ N-re azt, hogy τ = k teljesül-e a ξ_{1}, …, ξ_{k} valószínűségi változók értékei alapján el tudjuk dönteni. (Azaz azt, hogy a k-ik lépésben megállunk-e vagy nem a k-ik időpontig szerzett információ alapján el tudjuk dönteni.)

Vezessük be a következő jelöléseket. Legyen Θ_{k} az olyan megállási szabályok halmaza, melyekre P (τ ≥ k) = 1, minden τ ∈ Θ_{k}-ra. Legyen

v_{k}(ξ_{1}, …, ξ_{k}) = sup_{τ∈Θ_{k}} E(g_{τ} (ξ_{1}, …, ξ_{τ})|ξ_{1}, …, ξ_{k}),

a feltételes optimális várható nyeremény, ha csak olyan megállási stratégiákat tekintünk, melyekben először a k-ik lépésben állhatunk meg, feltéve az első k lépésben bekövetkezett ξ_{1}, …, ξ_{k} értékeket.

(Megjegyzem, hogy az itt szereplő fogalmakat és későbbi eredményeket minden nehézség nélkül lehet általánosítani tetszőleges nem feltétlenül diszkrét valószínűségi változók esetére. De erre az általánosításra az itt vizsgált probléma megoldásához nincs szükségünk, és az általánosításhoz szükség van néhány csak a felső években tanított mértékelméleti eredményre is.)

2. A következő rekurziós formula érvényes:

v_{N}(ξ_{1}, …, ξ_{N}) = g_{N}(ξ_{1}, …, ξ_{N})
v_{k}(ξ_{1}, …, ξ_{k}) = max{g_{k}(ξ_{1}, …, ξ_{k}), E (v_{k+1}(ξ_{1}, …, ξ_{k+1})|ξ_{1}, …, ξ_{k})},
1 ≤ k ≤ N − 1

A következő módon kaphatunk optimális megállási stratégiát. Ha a k-ik lépés előtt nem állunk meg, akkor a k-ik lépésben megállunk, ha

g_{k}(ξ_{1}, …, ξ_{k}) ≥ E (v_{k+1}(ξ_{1}, …, ξ_{k+1})|ξ_{1}, …, ξ_{k}) ,

ellenkező esetben pedig nem állunk meg a k-ik lépésben, 1 ≤ k ≤ N − 1.

Ha a ξ_{1}, …, ξ_{N} valószínűségi változók függetlenek, és g_{k}(ξ_{1} …, ξ_{k}) = g_{k}(ξ_{k}), akkor a fenti rekurzió egyszerűbb. Nevezetesen, ebben az esetben v_{k}(ξ_{1}, …, ξ_{k}) = v_{k}(ξ_{k}), és legyen V_{k} = Ev_{k}(ξ_{k}) jelöléssel

v_{N}(ξ_{N}) = g_{N}(ξ_{N}), v_{k}(ξ_{k}) = max{g_{k}(ξ_{k}), V_{k+1}}

2a.) A Szindbád problémájaként megfogalmazott feladat ilyen tipusú feladatra vezethető vissza a következő választással: ξ_{1}, …, ξ_{N} független valószínűségi vál-

tozók, P (ξ_{L} = j) = \frac{1}{L}, 1 ≤ j ≤ L, g_{L}(ξ_{L}) = \frac{L}{N}, ha ξ_{L} = 1, és g_{L}(ξ_{L}) = 0, ha ξ_{L} ≠ 1, 1 ≤ L ≤ N.

3. Oldjuk meg a 2a.) pontban megfogalmazott feladatot. Mutassuk meg, hogy ebben az esetben

V_{N} = \frac{1}{N} , V_{L} = \frac{L − 1}{L}V_{L+1} + \frac{1}{L} max \{\frac{L}{N} , V_{L+1}\} , ha 1 ≤ L ≤ N − 1,

ahol V_{L} = Ev_{L}(ξ_{L}).

Legyen P (L) = \frac{1}{N} ∑_{k=L}^{N} \frac{L − 1}{k − 1}, és L^{∗} a legkisebb olyan L szám, melyre P (L+1) ≥ \frac{L}{N},

azaz ∑_{k=L}^{N} \frac{1}{k − 1} ≥ 1. Ekkor V_{L} = P (L), ha L ≥ L^{∗}, és V_{L} = P (L^{∗}), ha L < L^{∗}. Az

optimális τ stratégia a következő: τ = min{k: k ≥ L^{∗}, ξ_{k} = 1}, és τ = N, ha ilyen

k szám nincsen. A nyeremény értéke P (L^{∗}) = \frac{L^{∗} − 1}{N} ∑_{k=L^{∗}}^{N} \frac{1}{k − 1}.

Lássuk be, hogy az előbb definiált P (L) szám annak a valószínűsége, hogy az L időpont után megjelenik egy (első) lokális minimum, azaz olyan k, k ≥ L, melyre ξ_{k} = 1 és ez egyben a minimum is. Mi a fenti formulák szemléletes tartalma?

4. Nagy N-re L^{∗} ∼ \frac{N}{e}, és az optimális stratégia nyeresége (annak valószínűsége, hogy

Szindbádnak síkerül a legszebb hölgyet kiválasztani) körülbelül e^{−1}.

Az idei Schweitzer verseny valószínűségszámítási feladatát kissé másképp fogalmazzuk meg, és valójában egy élesebb eredményt bizonyítunk be.

Az n dimenziós egységkocka minden csúcspontjához hozzá van rendelve egy standard normális valószínűségi változó, és ezek a valószínűségi változók függetlenek. A következő véletlen algoritmus segítségével keressük e valószínűségi változók maximumának egy jó közelítését:

a.) Az első lépésben kiválasztunk véletlenül egy pontot az n dimenziós kocka csúcsai közül, minden pontot egyforma valószínűséggel választva.

b.) A k-ik lépésben tekintjük az k − 1-ik lépésben kiválasztott csúcspont szomszédait. Ha ezek mindegyikéhez kisebb szám van hozzárendelve, mint ehhez a ponthoz, akkor az algoritmust befejezzük. Ha vannak olyan szomszédos pontok, melyekhez nagyobb érték van hozzárendelve, akkor ezek közül egyforma valószínűséggel az eddig történtektől függetlenül kiválasztjuk az egyiket.

Jelölje λ(n) az algoritmus lépésszámát. Bizonyítsuk be, hogy \frac{λ(n) − log n}{\sqrt{log n}} eloszlásban

konvergál a standard normális eloszláshoz, ha n → ∞.

1′.) Bizonyítsuk be, hogy a Schweitzer feladat állítása következik a következő feladat eredményéből: Legyen x_{1}, …, x_{2^{n}} 2^{n} különböző valós szám. Sorsoljuk ki ezeket a számokat egy n dimenziós kocka csúcspontjai között úgy, hogy minden lehetséges elhelyezés valószínűsége \frac{1}{(2^{n})!}. Alkalmazzuk a következő algoritmust. Első lépésben kiválasztunk és megnézünk véletlenül egy csúcspontot, és ez az algoritmus által (a maximumhelyre) adott becslés az első lépésben. A k-ik lépésben véletlen módon megnézzük a k − 1-ik lépésben adott becslő csúcspont egyik még nem látott szomszédját. Minden lehetséges pontot egyforma valószínűséggel választunk, feltéve hogy ilyen pont létezik. Ha az ehhez a ponthoz rendelt szám kisebb mint a k − 1-ik lépésben adott becslés, akkor az algoritmus k-ik és k −1-ik lépésében adott becslések megegyeznek. Ha az új ponthoz rendelt szám nagyobb, mint a k − 1-ik lépésben adott becslés, akkor ez az új pont lesz a becslés az algoritmus k-ik lépésében. Ha a k − 1-ik lépésben kijelölt becslő pontnak már minden pontját láttuk, akkor az algoritmust befejezzük. Jelölje λ̄(n) az algoritmus különböző lépéseiben adott becslő pontok

számát. Ekkor a \frac{λ̄(n) − log n}{\sqrt{log n}} valószínűségi változó eloszlása konvergál a standard

normális eloszláshoz, ha n → ∞.

Az 1′.) feladat állítását fogjuk bebizonyítani. Ehhez lássuk be először, hogy

2′.) Az algoritmus befejezése előtt nem fordulhat elő, hogy n egymás utáni lépésben nem változtattuk meg a becslő pontot. Másrészt, addig az időpontig, amíg a d − 1-ik és d-ik becslőpont kiválasztása között kevesebb, mint n − 2d lépés történik minden d számra, az algoritmus nem fejeződik be.

Legyen π(k) a k-ik időpontban megfigyelt pontbeli érték relatív sorrendje az addig megfigyeltek között. Be fogjuk látni, hogy a teljesen véletlen sorrend miatt ez a lehetséges 1, …, k értékek mindegyikét \frac{1}{k} valószínűséggel veszi fel, a múlttól függetlenül. Ennek az állításnak és a 2.) feladatnak a segítségével nem nehéz a kívánt állítást a centrális határeloszlástételből levezetni.

Soroljuk fel az n dimenziós kocka N = 2^{n} csúcspontjait valamilyen rögzített sorrendben, és jelöljük meg azt, hogy az j számnak, 1 ≤ j ≤ N pontnak megfelelő csúcspont szomszédainak mely számok felelnek meg. Definiáljuk a következő véletlen π = π_{0} = {π(1), π(2), …, π(N)} permutációt az {1, 2, …, N} halmazon: Ha a j pontnak megfelelő csúcshoz az x_{j} pont van hozzárendelve, akkor legyen π(j) az x_{j} szám nagyság szerinti sorrendje az x_{1}, …, x_{N} számok között. Ez az {1, 2, …, N} halmaznak egyenletes eloszlású permutációja. Az algoritmus k-ik lépésében definiáljuk az {1, …, N} számok egy véletlen átrendezését és egy π_{k} permutációt a következő módon. Tekintjük az {1, …, N} számok átrendezését a k − 1-ik lépésben (a 0-ik átrendezés a számok eredeti sorrendje), és a k-ik lépésben megnézett csúcspontot a k−1-ik átrendezés k-ik helyére tesszük. Ez a k-ik átrendezés. Legyen π_{k}(j) a k-ik átrendezéseben a j ponthoz rendelt csúcsban ülő szám nagyság szerinti sorrendje.

3′.) Legyen π az {1, …, N} halmaz véletlen permutációja, és L, 1 ≤ L ≤ N, tetszőleges rögzített egész szám. Lássuk be, hogy a π permutáció akkor és csak akkor egyenletes eloszlású, ha az {1, …, L} számok {π(1), …, π(L)} által megadott {π̄(1), …, π̄(L)} belső permutációja egyenletes eloszlású, (e fogalom definicióját lásd a Szindbád probléma elején), ez független a (π(L+1), …, π(N)) véletlen vektortól, és ez utóbbi

vektor minden lehetséges értéket \frac{1}{L + 1} ⋯ \frac{1}{N} valószínűséggel vesz fel.

a.) Legyen adva egy ξ valószínűségi változó úgy, hogy a {π̄(1), …, π̄(L)} belső permutáció és a ξ valószínűségi változó által képzett vektor független a {π(L + 1), …, π(N)} vektortól. Legyen P = P (ξ, {π̄(1), …, π̄(L)}) az {L + 1, …, N} halmaznak a ξ valószínűségi változótól és a π̄ belső permutációtól függő átrendezése. Definiáljuk a π̃ = {π̃(1), …, π̃(N)} permutációt a következő módon: π̃(j) = π(j), ha 1 ≤ j ≤ L, és π̃(j) = π(P (j)), ha L + 1 ≤ j ≤ N. Bizonyítsuk be, hogy a π̃ permutáció egyenletes eloszlású.

b.) A feladat előtt definiált π_{k} véletlen permutáció egyenletes eloszlású.

4′.) Lássuk be, hogy minden ε > 0 számhoz létezik olyan C = C(ε) szám, hogy amenynyiben a Cn-ik lépésben az 1′.) feladatban leírt algoritmus nem fejeződik be, akkor feltéve az első Cn lépésben megfigyelt belső sorrendet, annak feltételes valószínűsége (bármely lehetséges sorrend esetén), hogy az algoritmus Cn+n lépésben befejeződik nagyobb mint 1 − ε. Definiáljuk a ξ_{k}, k = 1, …, N, valószínűségi változókat a következő módon. Legyen ξ_{k} = 1, ha az 1′.) feladat megoldása érdekében definiált átrendezések közötti utolsó átrendezés szerint a k-ik ponthoz rendelt csúcsban ülő szám nagyobb, mint a megelőző pontokhoz rendelt csúcsokban ülő szám. Ellenkező esetben legyen ξ_{k} = 0. Ekkor ξ_{1}, …, ξ_{N} független valószínűségi változók, és P (ξ_{k} = 1) = 1 − P (ξ_{k} = 0) = \frac{1}{k}. Minden ε > 0-hoz létezik olyan C = C(ε) szám, hogy elég nagy n-re

P (∑_{k=1}^{n/3} ξ_{k} < x) ≥ P (λ̄(n) < x) ≥ P (∑_{k=1}^{Cn} ξ_{k} < x) − ε

minden x számra. Bizonyítsuk be az 1′.) feladat állítását.