A Szindbád probléma. Optimális választás megtalálása.

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 siker 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}?

Tekintsük a következő stratégiát. Szindbád az első \frac{n}{2} háremhölgyet hagyja elmenni, majd azt figyeli, jelent-e meg az összes eddigi háremhölgynél szebb. Ha egy ilyen hölgy megjelenik, akkor azt választja, ha ilyen hölgy nem jelenik meg akkor mindenkit továbbenged, és az utolsó háremhölgyet választja. Amennyiben a második legszebb háremhölgy a megjelentek első, a legszebb háremhölgy pedig a második felében van,

aminek valószínűsége \frac{1}{4}, akkor Szindbádnak ezzel a stratégiával sikerül kiválasztani a legszebb háremhölgyet. Ez azt jelenti, hogy nagyon nagy n számra is Szindbád legalább

\frac{1}{4} valószínűséggel sikerrel jár. Ráadásul, lehetséges hogy van ennél jobb stratégia is.

Jegyezzük meg, hogy Szindbád célja, az hogy minél nagyobb valószínűséggel a legszebb hölgyet válassza természetes, de nem ez az egyetlen lehetséges természetes cél. Vegyük észre, hogy amennyiben Szindbád az előbb javasolt stratégiát választja, akkor viszonylag nagy valószínűséggel meglehetősen rossz választást is tehet. Valóban, annak a valószínűsége, hogy a legszebb háremhölgy a megjelentek első felében jelenik meg, és az utolsó háremhölgy a megjelentek szépség szempontjából második, rosszabb felében van körülbelül \frac{1}{4}. Ebben az esetben Szindbád a fenti stratégiával az utolsó háremhölgyet választja, azaz meglehetősen rossz választást tesz. Érezhető, hogy amennyiben Szindbád például a két legszebb háremhölgy valamelyikét akarja minél nagyobb valószínűséggel választani, akkor a siker valószínűsége nagyobb, és kisebb valószínűséggel fog nagyon rossz választást tenni.

A feladatnak egy klasszikus az előbb megfogalmazottnál nehezebb, de szintén megoldható változata a következő ,,Secretary problem”-nak nevezett kérdés: Egy állásra ismert n számú jelölt jelentkezik, akik véletlen sorrendben jelennek meg a felvételi interjúra, és minden lehetséges sorrend egyforma valószínű. Legyen a legjobb jelölt rangja 1, a második legjobb jelölt rangja 2, és a k-ik legjobb jelölt rangja k, k = 1, 2, …, n. A felvételi interjú során az éppen jelentkező felvételiző jóságát össze tudjuk hasonlítani az addig megjelentekkel, azaz meg tudjuk mondani az addig megjelentek közötti relativ rangját. Ezután eldöntjük, hogy a jelöltet elfogadjuk vagy elbocsájtjuk, és ezt a döntést később nem változtathatjuk meg. Célunk az, hogy minimalizáljuk a kiválasztott jelölt rangját. Kérdés, hogy ez a rang optimális választás esetén végtelenhez tart-e, ha a jelöltek n száma tart a végtelenhez. Be lehet látni, hogy optimális választás esetén létezik véges határérték, és annak értéke is ismert. Ez a

∏_{j=1}^{∞} (\frac{j + 2}{j})^{1/(j+1)} ∼ 3.8695

szám. Ennek a ténynek azonban nincs olyan egyszerű indokása mint annak, hogy Szindbád problémájában a sikeres választás valószínűsége jó stratégia esetén nem tart nullához n → ∞ esetén sem.

Az alábbiakban Szindbád problémájáank ismertetem a teljes megoldását. A ,,Secretary problem”-nak viszont csak egy részleges megoldását írom le. Megadom minden rögzített n-re az optimális stratégiát, illetve azt a rekurziót, melynek segítségével kiszámítható az optimális stratégia esetén a kiválasztott jelölt rangjának a várható értékét. Ennek segítségével megmutatom, hogy ennek a várható értéknek az értéke minden n számra kisebb mint 8. Annak bizonyítása, hogy létezik a fent megadott határérték a rekurzió alaposabb vizsgálatát igényli. Ez meglehetősen fárasztó, a valószínűségszámításhoz közvetlenül nem kapcsolódó probléma. Ezért ennek részleteit nem tárgyalom. Az érdeklődők ezt megtalálhatják azt Y. S. Chow, S. Moriguti, H. Robbins és M. Samuels Optimal Selection Based On Relative Ranks (“the Secretary Problem”) című az Israel Journal of Mathematics (1964) 81–90 cínű cikkében.

A tárgyalt problémák nemcsak önmaguk miatt érdekesek. Ezek megoldásában olyan gondolatok jelennek meg, melyek egyéb feladatok vizsgálatában is fontos szerepet játszanak. Erre később visszatérünk.

A Szindbád probléma megoldása

Jel0lje az pozitív egész N szám a választható (hárem)hölgyek számát, é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.

Jelölje Z(j), 1 ≤ j ≤ N, a j-ik jelölt sorrendjét, azaz legyen Z(j) = l, ha jik megjelenő jelölt az l-ik legszebb hölgy. Vezessük be ezenkívül a j-ik jelölt ξ(j) relatív sorrendjét, ami azt jelöli, hogy a j-ik megjelenő jelölt, hanyadik legszebb az addig megjelentek között. Azt a jelöltet szeretnénk minél nagyobb valószínűséggel kiválasztani, melynek Z(·) sorrendje 1, viszont a döntés során csak a jelöltek ξ(j) relativ sorrendjét tudjuk megfigyelni. Tudjuk, hogy az összes lehetséges (Z(1), …, Z(N))

sorozat valószínűsége \frac{1}{N!}. Annak érdekében, hogy a feladatot meg tudjuk oldani tegyük először a következő észrevételt, amelyik leírja (ξ(1), …, ξ(N)) véletlen sorozat eloszlását.

1. Válasszuk az {1, …, N} halmaz egy véletlen π permutációját egyenletes eloszlással.

Ekkor a fent definiált ξ(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.) Tekintsünk egy 1 ≤ L ≤ N számot. Annak feltételes valószínűsége, hogy ξ(L) a legkisebb az összes ξ(j), 1 ≤ j ≤ N, között, azaz Z(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}.

Általánosabban,

P (Z(L) = 1|ξ(1) = j_{1}, ξ(2) = j_{2}, …, ξ(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 és 1 ≤ j_{s} ≤ s minden 1 ≤ s ≤ L − 1 számra.

Továbbá, természetesen

P (Z(L) = 1|ξ(1) = j_{1}, ξ(2) = j_{2}, …, ξ(L) = j_{L}) = 0,

ha j_{L} ≥ 2.

Indoklás: A fő rész állításának bizonyításához elég belátni, hogy a

{Z(1) = k_{1}, …, Z(N) = k_{N}}

események, k_{1}, …, k_{N} az 1, …, N számok permutációi és a

{ξ(1) = j_{1}, …, ξ(N) = j_{N}}, 1 ≤ j_{L} ≤ L, 1 ≤ L ≤ N,

események között kölcsönösen egyértelmű megfeleltetés van. Ez ugyanis azt jelenti,

hogy P (ξ(1) = j_{1}, …, ξ(N) = j_{N}) = \frac{1}{N!}, 1 ≤ j_{L} ≤ L, 1 ≤ L ≤ N. Ez az állítás viszont könnyen látható, mert minden {Z(1) = k_{1}, …, Z(N) = k_{N}} eseménynek megfelel egy {ξ(1) = j_{1}, …, ξ(N) = j_{N}}, 1 ≤ j_{L} ≤ L, 1 ≤ L ≤ N, esemény, és megfordítva minden {ξ(1) = j_{1}, …, ξ(N) = j_{N}}, 1 ≤ j_{L} ≤ L, 1 ≤ L ≤ N, eseményre megadható, hogy melyik {Z(1) = k_{1}, …, Z(N) = k_{N}} eseménynek felel meg. Valóban, ξ(N) = Z(N), ezután ξ(N − 1) illetve annak ismeretében, hogy az N-ik és N − 1-ik jelölt közül melyik a nagyobb, ismerjük a Z(N − 1) értékét is. Így szukcesszive meg tudjuk határozni a Z(k) értéket a már meghatározott Z(j) értékek segítségével.

Az 1a rész bizonyításához vegyük észre, hogy az L-ik lépésben megjelenő az összes addig megjelent jelöltnél szebb hölgy akkor és csak akkor a legszebb az összes jelölt között, ha nem jelenik meg a későbbiekben minden korábbinál szebb hölgy, azaz a ξ(L) = 1 eseményből akkor következik a Z(L) = 1 esemény, ha ξ(k) ≥ 2 minden L + 1 ≤ k ≤ N indexre. Ezért

P (Z(L) = 1|ξ(1) = j_{1}, ξ(2) = j_{2}, …, ξ(L) = 1) = P (ξ(L + 1) ≥ 2, …, ξ(N) ≥ 2|ξ(1) = j_{1}, ξ(2) = j_{2}, …, ξ(L) = 1)

= P (ξ(L + 1) ≥ 2, …, ξ(N) ≥ 2) = ∏_{j=L+1}^{N} P (ξ(j) ≥ 2) = ∏_{j=L+1}^{N} \frac{j − 1}{j} = \frac{L}{N}

A feladat megoldása érdekében érdemes bevezetni a megállási szabály fogalmát és a feladatot formális szempontból precizen megfogalmazni.

Megállási szabály fogalma. Legyen adva valószínűségi változók ξ(1), ξ(2), …, sorozata. Azt mondjuk, hogy egy τ pozitív egész értékeket felvevő valószínűségi változó megállási szabály ezekre a ξ(1), ξ(2), …, valószínűségi változókra nézve, ha P (τ < ∞) = 1, és minden n = 1, 2, … számra megadható az n dimenziós tér olyan A_{n} halmaza, hogy a {τ = n} esemény akkor és csak akkorkövetkezik be, ha {ξ(1), …, ξ(n)} ∈ A_{n}.

A megállási szabály szemléletes tartalma az, hogy az n-ik időpntban annak eldöntését, hogy megálljunk-e ekkor vagy sem az n-ik időpontban összegyüjtött információ alapján döntjük el. Valójában a definició általánosabb. A szokásos definició a következő: Egy (Ω, A, P) valószínűségi mezőn adott egymásba skatulyázott F_{1} ⊂ F_{2} ⊂ ⋯ ⊂ A σ-algebrák sorozata. Azt mondjuk, hogy egy τ, P (τ < ∞) = 1, valószínűségi változó megállási szabály, ha {τ = n} ∈ F_{n}. Ennek a definiciónak szemléletes tartalma az, hogy F_{n} az n-ik időpontig összegyüjtött információkat tartalmazó σ-algebra, és azt hogy az nik lépésben megállunk-e vagy sem azt az n-ik lépésben összegyüjtött információk alapján döntjük el.

Esetünkben az F_{n} σ-algebrát mint a ξ_{1}, …, ξ_{n} valószínűségi változók által generált σ-algebrát definiáljuk. Bizonyos mértékelméleti ismeretek segítségével be lehet látni, hogy ebben az esetben az általunk megadott, illetve az általános definició megegyezik. Erre azonban nem lesz szükségünk. Az általunk tekintett feladatban elegendő diszkrét értékű valószínűségi változókkal dolgozni, amikor nem merülnek fel komoly mértékelméleti problémák. Ugyanakkor az általános eset vizsgálatában, bár szükség van bizonyos nem triviális mértékelméleti eredményekre, nem merülnek fel komoly új elvi nehézségek.

Minket a fenti definició és a korábbi jelölések felhasználásával a következő feladat megoldása érdekel: Adott ξ(1), …, ξ(N) (független) ismert együttes eloszlású valószínűségi változók sorozata. (Lásd az első feladatot.) Ezenkívül tekintettünk olyan Z(k), k = 1, 2, …, N valószínűségi változókat, melyek ezen ξ(j) változók függvényeiként kifejezhetőek, és tekintettünk valamilyen g_{k}(Z(1), …, Z(N)) nyereményfüggvényeket, melyek azt fejezik, ki mennyi a nyereményünk, ha a k-ik lépésben megállunk. Esetünkben Z(k) fejezi ki azt, hogy a k-ik megjelent háremhölgy hanyadik a szépségi sorrendben, és g_{k}(u_{1}, …, u_{n})) = 1, ha u_{k} = 1, és g_{k}(u_{1}, …, u_{N}) = 0, ha u_{k} ≥ 2. Hangsúlyozzuk, hogy például a Z(1) ismeretéhez szükségünk van az összes ξ(k), k = 1, …, N, ismeretére. Ekkor megadhatóak olyan f_{k}(x_{1}, …, x_{n}) függvények, melyekre f_{k}(ξ(1), …, ξ(N) = 1, ha Z(k) = 1, és f_{k}(ξ(1), …, ξ(N) = 0, ha Z(k) ≥ 2, 1 ≤ k ≤ N. Feladatunk ezek után a következőképp fogalmazható meg. Tekintsük az összes lehetséges τ megállási szabályt a ξ(1), …, ξ(N) valószínűségi változókra nézve, (feltesszük, hogy P (τ ≤ N) = 1), és keressük meg ezek közül azt, melyre Ef_{τ} (ξ(1), …, ξ(N)) a minimális.

Az elöbb megfogalmazott problémát lehet egyszerűbben, és konkrétabban megfogalmazni a következő állítás segítségével. Ebben olyan nyereményfüggvények esetében vett optimalizációs feladatot tekintjük, melyeknek a k időpontban felvett h_{k}(ξ(1), …, ξ(k)) értékük csak a k-ik időpontig megfigyelt ξ(1), …, ξ(k) értékektől függ.

2. Legyen adva ξ(1), …, ξ(N) (diszkrét) valószínűségi változók és h_{k}(x_{1}, …, x_{N}) nyereményfüggvények sorozata. Vezessük be az

u_{k}(x_{1}, …, x_{k}) = E(h_{k}(ξ(1), …, ξ(N)|ξ(1) = x_{1}, …, ξ(k) = x_{k})

függvényeket. Ekkor minden τ valószínűségi változóra, amelyik τ megállási szabály a ξ(1), …, ξ(N) valószínűségi változókra nézve

E(u_{τ} (ξ(1), …, ξ(τ)) = E(h_{k}(ξ(1), …, ξ(N)).

Ez az eredmény speciálisan azt jelenti, hogy Szindbád problémája (felhasználva az első feladat eredményét) ekvivalens a következő feladattal: Adott független

ξ(1), …, ξ(N) valószínűségi változók sorozata, melyekre P (ξ(k) = j) = \frac{1}{k}, 1 ≤

j ≤ k, 1 ≤ k ≤ N, valamint az u_{k}(x) = \frac{k}{N}, ha x = 1, u_{k}(x) = 0, ha x ≠ 1, 1 ≤ k ≤ N függvények sorozata. Keressük meg az optimális τ megállási szabályt, melyre az Eu_{τ} (ξ_{τ}) várható érték felveszi a minimát, és határozzuk meg az Eu_{τ} (ξ_{τ}) várható értéket.

Megoldás: Azt kell belátni, hogy

∫ I({τ = k})h_{k}(ξ(1), …, ξ(N))dP = ∫ I({τ = k})(u_{k}(ξ(1), …, ξ(k))dP.

Itt és a továbbiakban I(A) fogja jelölni egy A halmaz indikátorfüggvényét. A {τ = k} esemény bizonyos A(j_{1}, …, j_{k}) = {ξ(1) = j_{1}, …, ξ(k) = j_{k}} alakú események uniója. Ezért elég belátni, hogy

∫ I(A(j_{1}, …, j_{k}))h_{k}(ξ(1), …, ξ(N))dP = ∫ I(A(j_{1}, …, j_{k}))u_{k}(ξ(1), …, ξ(k))dP.

Ez az azonosság viszont a feltételes várható érték fogalmának a következménye.

A feladat második állítása következménye az első feladatnak. Jegyezzük meg, hogy e feladat 1a) része alapján a nyereményfüggvény értéke az u_{k}(x_{1}, …, x_{k}) = u_{k}(x_{k}),

u_{k}(x) = \frac{k}{N}, ha x = 1, u_{k}(x) = 0, ha x ≠ 1, 1 ≤ k ≤ N függvény.

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. Ezt a feladatot nem fogalmazzuk meg az általános esetben. Bizonyos speciális megszorításokat teszünk, mert a minket érdeklő feladatban ez nem okoz problémát és nem kívánjuk használni az általános (nulla valószínűségű feltételeket is megengedő) feltételes várható érték meglehetősen mély ismereteket igénylő fogalmát. Ez a megjegyzés egyébként érvényes az előző feladatra is. Az alábbiakban csak olyan nyereményfüggvényeket fogunk tekinteni, melyekre v_{k}(x_{1}, …, x_{k}) = v_{k}(x_{k}), és a ξ(1), …, ξ_{k}) valószínűségi változók függetlenek. Ezektől a megszorításoktól nem lenne nehéz megszabadulni.

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} = sup_{τ∈Θ_{k}} E(v_{τ} (ξ_{τ})),  (∗)

az 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.

3. Tegyük fel, hogy a ξ_{1}, …, ξ_{N} valószínűségi változók függetlenek, és v_{k}(ξ_{1}, …, ξ_{k}) = v_{k}(ξ_{k}). Ekkor a V_{k} = sup_{τ∈Θ_{k}} E(v_{τ} (ξ_{τ})), mennyiségek segítségével a következő rekurzi-

ós formulát írhatjuk fel az alább definiált V_{k} és U_{k}(x), k = N, …, 1 mennyiségekre:

U_{N}(x) = v_{N}(x), V_{N} = EU_{N}(ξ(N)),
U_{k}(x) = max{v_{k}(x), V_{k+1}}, V_{k} = EU_{k}(ξ(k)).

A V_{k} mennyiség megadja a lehetséges maximális nyereményt, ha a k-ik lépésben vagy azután állhatok meg, az U_{k}(x) a feltételes várható értékét ennek a maximális nyereménynek, feltéve hogy a k-ik lépésben a ξ(k) = x esemény következett be.

Megadható az optimális stratégia is a következő módon: Kiszámoljuk a fenti V_{k}, k = 1, 2, …, mennyiségeket. A Θ_{k} osztályban az optimális V_{k} várható értékű nyereményt biztosító megállási szabály a következő: Az első k − 1 lépésben nem állunk meg. A k-ik lépésben akkor állunk meg, ha v(ξ_{k}) ≥ V_{k+1}, ellenkező esetben tovább megyünk. Az m-ik lépésben, N > m ≥ k, akkor állunk meg, ha nem álltunk meg előbb, és v(ξ_{m}) ≥ V_{m+1}. Az N-ik lépésben mindenképp megállunk. A fent definiált V_{k} mennyiségek megegyeznek a (∗) formulában szereplő V_{k} mennyiségekkel. Mi a fenti formulák szemléletes tartalma?

Megoldás: Belátjuk k-ra alkalmazott “backward” indukcióval, hogy τ ∈ Θ_{k} esetében a várható optimális nyeremény V_{k}, és a fent leírt stratégia optimális. A k = N esetben az egyetlen lehetséges stratégia optimális, és annak nyereménye V_{N}. Tegyük fel, hogy az állítást már tudjuk k + 1-re és lássuk be k-ra. A bizonyításban felhasználjuk azt, hogy mivel a valószínűségi változók függetlenek és a nyeremény csak a megállási időponttal indexezett valószínűségi változó értékétől függ, ezért ha a k-ik lépésben nem állok meg, akkor a nyereményem elérhető feltételes várható értéke feltéve az első k valószínűségi változó értékeit, ez a feltételes várható érték nem függ a feltételtől. Valóban semmilyen stratégiával és semmilyen ξ(1) = j_{1}, …, ξ(k) = j_{k} feltétel teljesülése esetén nem tudom elérni, hogy ez a feltételes várható érték nagyobb legyen mint V_{k+1}, azt viszont el tudom érni, hogy ez V_{k+1} legyen. Valóban, ha valamilyen stratégiával el tudnám érni, hogy a feltételes várható érték határozottan nagyobb legyen mint V_{k+1}, ami azt jelentené, hogy minden lehetséges ξ(1) = j_{1}, …, ξ(k) = j_{k}, ξ(k + 1) = j_{k+1} …, ξ(N) = j_{N} esetén megmondva, hogy hol álljak meg elérhető, hogy a feltételes várható érték nagyobb legyen mint V_{k+1}, akkor alkalmazva azt a megállási szabályt, mely szerint ugyanott állok meg egy olyan j′_{1}, …, j′_{k}, …, j_{N} megfigyelt sorozat esetén, melyben az első k megfigyelt érték különbözhet az előző sorozattól, de a későbbiek nem, elérhetem hogy egy az optimálisnál jobb stratégia V_{k+1} nyereményénél előnyösebb megállási szabályt találjak a Θ_{k+1} halmazban, ami ellentmondás. A V_{k+1} feltételes várható értéket viszont el tudom érni, ha alkalmazom a V_{k+1} optimális nyereményt nyújtó τ ∈ Θ_{k+1} stratégiát függetlenül a ξ(1) = j_{1}, …, ξ(k) = j_{k} értékektől.

Ez azt jelenti, hogy a τ ∈ Θ_{k} megállási szabályok között az optimumot keresve elég csak azokat figyelembe venni, melyekben minden ξ(1) = j_{1}, …, ξ(k) = j_{k}, ξ(k + 1) = j_{k+1} …, ξ(N) = j_{N} esemény esetén vagy megállunk a k-ik időpontban vagy továbblépünk és ezután az optimális τ ∈ Θ_{k+1} megállási stratégiát folytatjuk. Az első esetben v_{k}(ξ_{k}) a második esetben pedig V_{k+1} lesz a feltételes nyereményünk. Ezért v_{k}(ξ_{k}) ≥ V_{k+1} esetében érdemes megállni, míg v_{k}(ξ_{k}) < V_{k+1} esetben érdemes nem megállni a k-ig lépésben. A feladatban ezt a rekurziót írtam le és ennek nyereményét adtam meg. A feladat szemléletes tartalma az, hogy minden egyes lépésben a két lehetséges választás közül (továbbmenni vagy megállni) az előnyösebbet választjuk.

4. Oldjuk meg a 2. pontban megfogalmazott feladatot a 3. feladat eredményének a segítségével.

Megoldás: Ebben az esetben v_{k}(x) = \frac{k}{N}, ha x = 1, v_{k}(x) = 0, ha x ≠ 1, és a 3. feladat rekurziv formulája alapján

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} = EU_{L}(ξ_{L}), a maximális nyeremény értéke azon megállási szabályok között, melyekben az első L lépésben nem szabad megállni.

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 azt állítjuk, hogy V_{L} = P (L^{∗}), ha L < L^{∗}. Ennek érdekében vegyük észre, hogy a P (L) számsorozat teljesíti a P (L) = \frac{L − 1}{L}P (L − 1) + \frac{1}{L} \frac{L}{N} rekurziós formulát. Valóban, \frac{L − 1}{L}P (L + 1) = \frac{1}{N} ∑_{k=L+1}^{N} \frac{L − 1}{k − 1}, és \frac{1}{L} \frac{L}{N} = \frac{1}{N} \frac{L − 1}{L − 1}. Ezeket az azonosságokat összeadva megkapjuk a kívánt formulát. Mivel L ≥ L^{∗} esetén a V_{L} számok ugyanezt a reláciíót teljesítik, és P (N) = V_{N}. Innen P (L) = V_{L}, ha N ≥ L ≥ L^{∗}. Másrészt L < L^{∗} esetében a V_{L} sorozatra adott rekurziós formula V_{L} = \frac{L − 1}{L}V_{L+1} + \frac{1}{L}V_{L+1} = V_{L+1} alakú, azaz V (L) = V (L + 1), mert ebben az esetben max \{\frac{L}{N} , V_{L+1}\} = V_{L+1}. Innen V_{L} = V_{L^{∗}}, ha L ≤ L^{∗}. Ennek alapján 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 várható értéke pedig P (L^{∗}) =

\frac{L^{∗} − 1}{N} ∑_{k=L^{∗}}^{N} \frac{1}{k − 1}.

5. 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}. Megoldás: Az L^{∗} = L^{∗}(N) számot úgy határoztuk meg mint a legkisebb olyan L szám, melyre P (L + 1) ≥ \frac{L}{N}, P (L) = \frac{L − 1}{N} ∑_{k=L}^{N} \frac{1}{k − 1}. Viszont P (L + 1) ∼

\frac{L}{N} log (\frac{N}{L} ), ahonnan log (\frac{N}{L^{∗}} ) ∼ 1, azaz L^{∗} ∼ \frac{N}{e}, és a nyeremény értéke körül-

belül P (L^{∗}) ∼ \frac{1}{e}.