A Secretary problem. Optimális választás megtalálása.

A Szindbád problémának van egy szintén klasszikusnak tekinthető, talán természetesebb viszont nehezebb változata. Ez 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ának a várható értéké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ű indoklá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.

A ,,Secretary problem”-nak csak 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éke. 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, csak egy heurisztikus indoklást adok, mely felhasználja az optimális megoldás megadásához szükséges számsorozat néhány természetes, de bizonyításra szoruló tulajdonságát. Az érdeklődők a részleteket kidolgozó, teljes bizonyítást megtalálhatják 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 újságan megjelent cikkében.

A secretary problem sokban hasonlít a Szindbád problémához. Az ott tanultak nagyon hasznosak, és lényegében elegendő információt adnak az optimális stratégia kidolgozásához.

Legyen Z_{1}, …, Z_{n} az egymás után megjelenő jelöltek a megjelenés pillanatában ismeretlen rangja, és legyen ξ_{i} az i-ik jelült (megjelenése után megismert) relativ rangja az első i jelölt között. Ekkor, mint azt a Szindbád probléma megoldásában láttuk a

ξ_{1}, …, ξ_{n} valószínűségi változók függetlenek, és P (ξ_{i} = j) = \frac{1}{i} minden 1 ≤ j ≤ i számra. Továbbá ki tudjuk számolni annak feltételes valószínűségét, hogy a i-edik jelölt rangja egy adott k szám feltéve az első i megfigyelés értékét. Ez a

P (Z_{i} = k|ξ_{1} = j_{1}, …, ξ_{i−1} = j_{i−1}, ξ_{i} = j) = \begin{matrix}\binom{k − 1}{j − 1} & \binom{n − k}{i − j} \\ ( & {n \atop i} & ) \end{matrix}.  (1)

érték.

Ezt az azonosságot például a következőképp láthatjuk be:

P (ξ_{1} = j_{1}, …, ξ_{i−1} = j_{i−1}, ξ_{i} = j) = \frac{\binom{n}{i}(n − i)!}{n!},

aminek egyik lehetséges indoklása a következő: A jelöltek összesen n! sorrendben jelenhetnek meg, és minden sorrend egyformán valószínű. Az olyan sorrendek száma,

melyekre teljesülnek a ξ_{1} = j_{1}, …, ξ_{i−1} = j_{i−1}, ξ_{i} = j feltételek \binom{n}{i}(n − i)!, mert \binom{n}{i}

féle módon választhatjuk meg az első i lépésben megjelenő jelöltek halmazát, ezek belső sorrendjét egyértelműen meghatározza a ξ_{1} = j_{1}, …, ξ_{i−1} = j_{i−1}, ξ_{i} = j feltétel, és ezután a maradék n − i jelölt (n − i)! sorrendben jelenhet meg. Másrészt

P (Z_{i} = k, ξ_{1} = j_{1}, …, ξ_{i−1} = j_{i−1}, ξ_{i} = j) = \frac{\binom{k − 1}{j − 1}\binom{n − k}{i − j}(n − i)!}{n!}.

Ez az azonosság az előzőhöz hasonlóan indokolható. Azt kell megértenünk, hogy ekkor

a lehetséges megjelenési sorrendek száma \binom{k − 1}{j − 1}\binom{n − k}{i − j}(n − i)!. Ugyanis ekkor az

első i lépésben megjelenő jelöltek között ott lennie annak a jelöltnek, akinek a rangja k, és ennek a relativ rangja az első i jelölt között j kell, hogy legyen. Ez azt jelenti, hogy a legjobb k − 1 jelölt közül j − 1 és a legrosszabb n − k jelölt közül pedig i − j

résztvevő jelenik meg az első i lépésben. Ez \binom{k − 1}{j − 1}\binom{n − k}{j − i} módon lehetséges. Ezután

a Z_{i} = k, ξ_{1} = j_{1}, …, ξ_{i−1} = j_{i−1}, ξ_{i} = j feltétel egyértelműen meghatározza az első i jelölt belső sorrendjét, a maradék n − i jelölt pedig (n − i)! módon jelenhet meg.

Az (1) reláció speciálisan azt is jelenti, hogy

∑_{k=j}^{n} \binom{k − 1}{j − 1}\binom{n − k}{i − j} = \binom{n}{i}.  (2)

Ezért

\begin{matrix}E(Z_{i}|ξ_{1} = i_{1}, …, ξ_{i−1} = j_{i−1}, ξ_{i} = j) = ∑_{k=j}^{n} k \begin{matrix}\binom{k − 1}{j − 1} & \binom{n − k}{i − j} \\ ( & {n \atop i} & ) \end{matrix} \\ = \frac{1}{\binom{n}{i}} ∑_{k=j}^{n} j\binom{k}{j}\binom{(n + 1) − (k + 1)}{(i + 1) − (j + 1)} = j \begin{matrix}( & {n + 1 \atop i + 1} & ) \\ ( & {n \atop i} & ) \end{matrix} = j \frac{n + 1}{i + 1} \end{matrix}  (3)

a (2) reláció alapján (az n, i és j paraméterek helyett az n + 1, i + 1 és j + 1 paraméter választással.

Feladat: Adjunk a (2) azonosságra közvetlen kombinatorikus bizonyítást. Egy lehetőség: Számoljuk össze, hány olyan n + 1 hosszúságú fej-írás sorozat van, melyben az n + 1-ik tag az i + 1-ik fej. Számoljuk ezt össze úgy is, hogy előírjuk a sorozatban szereplő j-ik fejdobás helyét, majd összegezünk ennek a helynek a lehetséges értékeire.

Egy másik lehetséges indoklás: (A negatív binomiális eloszlásról tanultak alapján) írjuk át a (2) kifejezésben szereplő tagokat mint alkalmas (negatív számokat is megengedő) binomiális együtthatókat.

Például: \binom{n}{i} = \binom{n}{n − i} = (−1)^{n−i}\binom{−(i + 1)}{n − i}. Ezután alkalmazzuk az (1 −

x)^{α+β} = (1 − x)^{α}(1 − x)^{β} azonosságot, illletve annak következményét e függvények hatványsorainak együtthatóira alkalmas α és β választással.

A fenti eredmény, illetve a Szindbád probléma megoldásában tanultak alapján a Secretary problem ekvivalens a következő kérdéssel: Legyenek ξ_{1}, …, ξ_{n} független

valószínűségi változók, melyek eloszlását a P (ξ_{i} = j) = \frac{1}{i}. 1 ≤ j ≤ i, 1 ≤ i ≤ n képlet

adja meg. Vezessük be a v_{i}(j) = v_{i,n}(j) = j \frac{n + 1}{i + 1} költségfüggvényt. Keressük meg azt

az optimális τ megállási szabályt, mely minimalizálja a költségfüggvény Ev_{τ} (ξ_{τ}) várható értékét. Azt is megtárgyaltuk, hogyan kell ezt a feladatot megoldani. Definiáljuk a

\begin{aligned}c_{n−1} & = Ev_{n}(ξ_{n}) = \frac{1}{n} ∑_{j=1}^{n} j \frac{n + 1}{n + 1} = \frac{n + 1}{2} \\ c_{i−1} & = E (min (\frac{n + 1}{i + 1}ξ_{i}, c_{i})) = \frac{1}{i} ∑_{j=1}^{i} (min (\frac{n + 1}{i + 1}j, c_{i})) , i = n − 1, n − 2, …, 1 \end{aligned}

(4)

számsorozatot. Ekkor az optimális megállás az lesz, hogy a i-ik időpontban állok meg,

1 ≤ i ≤ n − 1, ha nem álltam meg előbb, és v_{i}(ξ_{i}) = \frac{n + 1}{i + 1}ξ_{i} ≥ c_{i}. Az n-ik lépésben

mindenképp megállok. A költség várható értéke pedig (az optimális stratégia esetén) c_{0}. Ezek után a feladat a (4) rekurzív eljárással megadott az n megengedett lépésszámtól is függő c_{i} = c_{i}^{(n)} sorozat kiszámolása és a C = lim_{n→∞} c_{0}^{(n)} határérték meghatározása (feltéve, hogy ez a határérték létezik).

A c_{i} sorozat vizsgálatában érdemes bevezetni a t_{i} = \frac{i + 1}{n + 1}c_{i}, 0 ≤ i ≤ n − 1, és

s_{i} = [t_{i}] mennyiségeket, ahol [x] jelöli az x szám egész részét. Ezekkel a jelölésekkel a (4) rekurziós formula némileg egyszerűbb formában írható fel:

c_{i−1} = \frac{1}{i} (\frac{n + 1}{i + 1}(1 + ⋯ + s_{i}) + (i − s_{i})c_{i}) = \frac{1}{i} (\frac{n + 1}{i + 1} \frac{s_{i}(s_{i} + 1)}{2} + (i − s_{i})c_{i}) ,

és t_{i} = s_{i} + α_{i}, 0 < α_{i} < 1 jelöléssel

t_{i−1} = \frac{s_{i}(s_{i} + 1) + 2t_{i}(i − s_{i})}{2(i + 1)},  (5a)

t_{i−1} = \frac{t_{i}(1 + 2i − t_{i})}{2(i + 1)} − \frac{α(1 − α)}{2(i + 1)}.  (5)

A t_{i} → t_{i−1} transzformáció viselkedésének jobb megértése érdekében vezessük be az annak a fő részét leíró

T (x) = T_{i}(x) = \frac{x(1 + 2i − x)}{2(i + 1)}

transzformációt. Egyszerű számolás adja, hogy

T′(x) = \frac{1 + 2i − 2x}{2(i + 1)} ≥ 0, ha x ≤ i + \frac{1}{2},

ezért T (x) monoton nő x ≤ i + \frac{1}{2} esetén. Továbbá (5) alapján

T (t_{i}) ≥ t_{i−1}.  (6)

A fentiek alapján bizonyítható a következő

Lemma.

t_{i} ≤ \frac{2n}{n − i + 3}.  (7)

A lemma bizonyítása előtt mutassuk meg annak egy érdekes következményét.

Következmény:

c_{0} < 8,

azaz a várható nyeremény optimális stratégia esetén bármely n számra kisebb mint 8.

A következmény bizonyítása. A c_{i} sorozat definiciójából kiolvasható, hogy az monoton nő. Ezért választva az i = [\frac{n}{2}] számot kapjuk a Lemma felhasználásával, hogy

c_{0} ≤ c_{i} = \frac{n + 1}{i + 1}t_{i} ≤ \frac{n + 1}{i + 1} \frac{2n}{n − i + 3} ≤ \frac{2n(n + 1)}{\frac{n}{2} (\frac{n}{2} + 3)} < 8.

A Lemma bizonyítása: A Lemma állítása érvényes i = n − 1-re, mert t_{n−1} = \frac{n}{2} = \frac{2n}{4}. Ezért elég belátni, hogy amennyiben az érvényes 1 ≤ i ≤ n − 1-re, akkor érvényes i − 1-re is. Ezt úgy bizonyítjuk, hogy felhasználjuk a (7)-es formulát a már bizonyított i paraméterrel, a (6) egyenlőtlenséget valamint azt, hogy a T (x) transzformáció monoton

nő t ≤ i + \frac{1}{2} esetben. Továbbá, mivel a c_{i} sorozat monoton nő, ezért

t_{i−1} = \frac{i}{n + 1}c_{i+1} ≤ \frac{i}{n + 1}c_{n−1} = \frac{i}{n + 1} \frac{n + 1}{2} = \frac{i}{2}.

Ez a becslés túl durva, mégis hasznos. Ugyanis vagy teljesül az \frac{i}{2} ≤ \frac{2n}{n − i + 4} azonosság,

és az indukciós feltevés teljesül i − 1-re is, (ez csak nagyon kis i indexre lehetséges) vagy

\frac{i}{2} > \frac{2n}{n − i + 4}, és ekkor i+ \frac{1}{2} ≥ \frac{2n}{n − i + 3}, ezért mind a t_{i} mind a \frac{2n}{n − i + 3} ≥ t_{i} számok

beleesnek abba az intervallumba, ahol T (·) monoton nő. Ezért

t_{i−1} ≤ T (t_{i}) ≤ T (\frac{2n}{n − i + 3}) = \frac{n\{(1 + 2i)(n − i + 3) − 2n\}}{(i + 1)(n − i + 3)^{2}} ≤ \frac{2n}{n − i + 4},

ami azt jelenti, hogy igaz az indukciós feltevés i − 1-re is. Az utolsó azonosság azért igaz, mert az ekvivalens a

(n − i + 3)^{2} + (2n − 2i − 10(n − i + 3) + 2n ≥ 0

egyenlőtlenséggel, ami nyílván érvényes n − i ≥ 1, azaz i ≤ n − 1 esetén.

A lim_{n→∞} c_{0}^{(n)} határérték meghatározása.

A részletek kidologzása nélkül.

Vezessük be az i_{k} = i_{k}^{(n)} mennyiségeket a következő módon:

i_{k} = A legkisebb j pozitív egész szám, melyre t_{j} ≥ k.

Az i_{k} mennyiségeket azért érdemes bevezetni, mert segítségükkel vizsgálható az optimális megállási szabály. Ez a következő: Az első i_{1} − 1 jelöltet mindenképpen elutasítjuk. Az i_{k} ≤ j < i_{k+1}-ik megjelent jelöltet akkor fogadjuk el, ha annak ξ_{k} relatív rangja kisebb vagy egyenlő mint k. A fenti megjegyzésből az is következik, hogy

c_{0} = c_{1} = ⋯ = c_{i_{1}−1}.

(Emlékeztetőül, a c_{j} mennyiség annak a várható értéke, hogy mekkora a költségfüggvényem, ha az első j lépésben nem állhatok meg, és ezen feltétel mellett az optimális stratégiát folytatom.)

Be lehet látni, hogy hogy léteznek az α_{k−1} = lim_{n→∞} \frac{i_{k}^{(n)}}{n} határértékek, α_{0} ≤ α_{1} ≤ ⋯,

α_{k} < 1 minden k = 0, 1, … számra, és lim_{k→∞} α_{k} = 1. Érdemes külön hangsúlyozni, hogy az α_{0} > 0 szigorú egyenlőtlenség érvényes.

Ezenkívül a t_{j} = t_{j}^{(n)} számok a j index megváltozásával keveset változnak. Pontosabban megfogalmazva, tetszőleges 0 < α < β < 1 számra

lim_{n→∞} sup_{αn≤j≤βn}(t_{j}^{(n)} − t_{j−1}^{(n)}) = 0.

A fenti reláció azt sugallja, hogy a t_{i_{k}} ∼ t_{i_{k}−1} ∼ k közelítéssel kis hibát követünk el. Speciálisan,

c_{0} = c_{1} = ⋯ = c_{i_{1}=1} = \frac{(n + 1)t_{i_{1}−1}}{i} ∼ \frac{n}{i_{1}} ,

ezért

lim_{n→∞} c_{0}^{(n)} = lim_{n→∞} \frac{n}{i_{1}^{(n)}} = \frac{1}{α_{0}} .  (8)

Ezért a feladat megoldása érdekében elég a lim_{n→∞} \frac{i_{k}^{(n)}}{n} = α_{k−1} mennyiségeket meghatározni. Azért, hogy ezeket a határértékeket kiszámoljuk vezessük be a

v_{i} = t_{i} − \frac{k}{2} , ha i_{k} ≤ i < i_{k+1} azaz k ≤ t_{i} < k + 1

mennyiségeket, és írjuk fel mit jelentenek a t_{i} mennyiségekre fennálló rekurziós formulák a v_{i} mennyiségekre. Azt kapjuk, hogy

v_{i−1} + \frac{k}{2} = \frac{k(k + 1) + 2(i − k) (v − \frac{k}{2} )}{2(i + 1)} = \frac{k}{2} + \frac{v_{i} − k}{i + 1} v_{i},

ahonnan

v_{i} = \frac{i + 1}{i − k} v_{i−1} ha i_{k} ≤ i < i_{k+1}.  (9)

(Hogyan lehet rájönni, hogy a fent definiált v_{i} mennyiségekre ilyen egyszerű rekurziós formula érvényes?)

Alkalmazva a (8) relációt szukcessziven a i_{k} ≤ i < i_{k+1} számokra azt kapjuk, hogy

\frac{v_{j}}{v_{i}} = \frac{(j + 1 − k) ⋯ (j + 1)}{(i + 1 − k) ⋯ (i + 1)}, ha i_{k} ≤ i ≤ j < i_{k+1}.  (10)

Alkalmazzuk a (10) formulát i = i_{k}, j = i_{k+1} választással. Azt kapjuk, hogy egyrészt

lim_{n→∞} \frac{v_{i_{k+1}^{(n)}}}{v_{i_{k}^{(n)}}} = lim_{n→∞} (\frac{i_{k+1}^{(n)}}{i_{k}^{(n)}} )^{k+1} = (\frac{α_{k}}{α_{k−1}} )^{k+1} ,

másrészt

lim_{n→∞} \frac{v_{i_{k+1}^{(n)}}}{v_{i_{k}^{(n)}}} lim_{n→∞} \frac{(t_{i_{k+1}^{(n)}} − \frac{k}{2} )}{(t_{i_{k}^{(n)}} − \frac{k}{2} )} = \frac{k + 1 − \frac{k}{2}}{k − \frac{k}{2}} = \frac{k + 2}{k}.

Innen

\frac{k + 2}{k} = (\frac{α_{k}}{α_{k−1}} )^{k+1} ,

ezért

\frac{α_{0}}{α_{k}} = ∏_{j=1}^{k} (\frac{j}{j + 2})^{j+1} ,

és k → ∞ határátmenettel (felhasználva, hogy lim_{k→∞} α_{k} = 1) kapjuk, hogy

lim_{n→∞} \frac{i_{1}^{(n)}}{n} = α_{0} = ∏_{j=1}^{∞} (\frac{j}{j + 2})^{j+1} .

Innen és a (8) formuából következik, hogy a keresett várható érték valóban a megadott szám.

A fenti heurisztikus érvelés pontossá tétele érdekéban néhány becslésre van szükség. Ezek közül a legfontosabb az, hogy a t_{j} mennyiségekre ne csak (viszonylag durva) felső becslést adjunk (ezt tettük meg a Lemmában), hanem megfelelő alsó becslést is bi-

zonyítsunk. Ez kell például ahhoz, hogy tudjuk: lim inf_{n→∞} \frac{i_{1}^{(n)}}{n} > 0.

A t_{j} mennyiségre adott felső becslés bizonyítása azon alapult, hogy az (5) formula segítségével viszonylag egyszerű, de jó t_{i−1} ≤ T (t_{i}) alakú becslést tudtunk adni. Hasonló elven egy alsó becslést is lehet bizonyítani. Be lehet látni, hogy

t_{i−1} ≥ \frac{t_{i}}{i + 1} (1 − \frac{t_{i}}{2(i + 1)}) ,

és ennek alapján

t_{i} ≥ \frac{3(i + 1)}{2(n − i + 2)}.

A bizonyítás részleteit elhagyjuk. Az megtalálható az említett cikkben.