A Secretary problem. Optim´ alis v´ alaszt´ as megtal´ al´ asa. A Szindb´ ad probl´em´anak van egy szint´en klasszikusnak tekinthet˝ o, tal´ an term´eszetesebb viszont nehezebb v´ altozata. Ez a k¨ ovetkez˝ 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´ın˝ 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, . . . , n. A felv´eteli interj´ u sor´ an az ´eppen jelentkez˝ o felv´eteliz˝ o j´ os´ag´ at ossze tudjuk hasonl´ı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˝obb nem v´ altoztathatjuk meg. C´elunk az, hogy minimaliz´ aljuk a kiv´alasztott jel¨olt rangj´ anak a v´ arhat´ o ´ert´ek´et. 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 1/(j+1) ∞ Y j+2 ∼ 3.8695 j j=1 sz´am. Ennek a t´enynek azonban nincs olyan egyszer˝ u indokl´ asa mint annak, hogy Szindb´ ad probl´em´aj´aban a sikeres v´ alaszt´ as val´ osz´ın˝ us´ege j´ o strat´egia eset´en nem tart null´ ahoz n → ∞ eset´en. A ,,Secretary problem”-nak csak r´eszleges megold´ as´at ´ırom le. Megadom minden r¨ogz´ıtett n-re az optim´alis strat´egi´at, illetve azt a rekurzi´ ot, melynek seg´ıts´eg´evel kisz´ am´ıthat´ o az optim´alis strat´egia eset´en a kiv´alasztott jel¨olt rangj´ anak a v´ arhat´ o ´ert´eke. Ennek seg´ıts´eg´evel megmutatom, hogy ennek a v´ arhat´ o ´ert´eknek az ´ert´eke minden n sz´amra kisebb mint 8. Annak bizony´ıt´ asa, hogy l´etezik a fent megadott hat´ar´ert´ek a rekurzi´ o alaposabb vizsg´alat´at ig´enyli. Ez meglehet˝osen f´ araszt´ o, a val´ osz´ın˝ us´egsz´am´ıt´ ashoz k¨ ozvetlen¨ ul nem kapcsol´od´ o probl´ema. Ez´ert ennek r´eszleteit nem t´argyalom, csak egy heurisztikus indokl´ ast adok, mely felhaszn´alja az optim´alis megold´ as megad´as´ahoz sz¨ uks´eges sz´amsorozat n´eh´ any term´eszetes, de bizony´ıt´ asra szorul´ o tulajdons´ag´ at. Az ´erdekl˝ od˝ ok a r´eszleteket kidolgoz´ o, teljes bizony´ıt´ ast megtal´ alhatj´ ak Y. S. Chow, S. Moriguti, H. Robbins ´es M. Samuels Optimal Selection Based On Relative Ranks (“the Secretary Problem”) c´ım˝ u az Israel Journal of Mathematics (1964) 81–90 u ´js´agan megjelent cikk´eben. A secretary problem sokban hasonl´ıt a Szindb´ ad probl´em´ahoz. Az ott tanultak nagyon hasznosak, ´es l´enyeg´eben elegend˝ o inform´ aci´ot adnak az optim´alis strat´egia kidolgoz´ as´ahoz. Legyen Z1 , . . . , Zn az egym´ as ut´ an megjelen˝o jel¨oltek a megjelen´es pillanat´ aban ismeretlen rangja, ´es legyen ξi az i-ik jel¨ ult (megjelen´ese ut´ an megismert) relativ rangja az els˝ o i jel¨olt k¨ oz¨ ott. Ekkor, mint azt a Szindb´ ad probl´ema megold´ as´aban l´attuk a 1 minden 1 ≤ j ≤ i ξ1 , . . . , ξn val´ osz´ın˝ us´egi v´ altoz´ ok f¨ uggetlenek, ´es P (ξi = j) = i sz´amra. Tov´ abb´a ki tudjuk sz´amolni annak felt´eteles val´ osz´ın˝ us´eg´et, hogy a i-edik jel¨olt 1
rangja egy adott k sz´am felt´eve az els˝ o i megfigyel´es ´ert´ek´et. Ez a
P (Zi = k|ξ1 = j1 , . . . , ξi−1 = ji−1 , ξi = j) =
k−1 n−k j−1 i−j . n i
(1)
´ert´ek. Ezt az azonoss´agot p´eld´aul a k¨ ovetkez˝ ok´epp l´athatjuk be:
P (ξ1 = j1 , . . . , ξi−1
n (n − i)! i , = ji−1 , ξi = j) = n!
aminek egyik lehets´eges indokl´ asa a k¨ ovetkez˝ o: A jel¨oltek ¨ osszesen n! sorrendben jelenhetnek meg, ´es minden sorrend egyform´ an val´ osz´ın˝ u. Az olyan sorrendek sz´ama, n n melyekre teljes¨ ulnek a ξ1 = j1 , . . . , ξi−1 = ji−1 , ξi = j felt´etelek (n − i)!, mert i i f´ele m´ odon v´ alaszthatjuk meg az els˝ o i l´ep´esben megjelen˝o jel¨oltek halmaz´ at, ezek bels˝ o sorrendj´et egy´ertelm˝ uen meghat´ arozza a ξ1 = j1 , . . . , ξi−1 = ji−1 , ξi = j felt´etel, ´es ezut´ an a marad´ek n − i jel¨olt (n − i)! sorrendben jelenhet meg. M´asr´eszt
P (Zi = k, ξ1 = j1 , . . . , ξi−1
k−1 n−k (n − i)! j−1 i−j . = ji−1 , ξi = j) = n!
Ez az azonoss´ag az el˝ oz˝ oh¨ oz hasonl´oan indokolhat´ o. Azt kell unk, hogy ekkor meg´erten¨ k−1 n−k (n − i)!. Ugyanis ekkor az a lehets´eges megjelen´esi sorrendek sz´ama i−j j−1 els˝ o i l´ep´esben megjelen˝o jel¨oltek k¨ oz¨ ott ott lennie annak a jel¨oltnek, akinek a rangja k, ´es ennek a relativ rangja az els˝ o i jel¨olt k¨ oz¨ ott j kell, hogy legyen. Ez azt jelenti, hogy a legjobb k − 1 jel¨olt k¨ oz¨ ul j − 1 ´es a legrosszabb n − k jel¨olt k¨ oz¨ ul pedig i − j k−1 n−k m´ odon lehets´eges. Ezut´ an r´esztvev˝o jelenik meg az els˝ o i l´ep´esben. Ez j−i j−1 a Zi = k, ξ1 = j1 , . . . , ξi−1 = ji−1 , ξi = j felt´etel egy´ertelm˝ uen meghat´ arozza az els˝ oi jel¨olt bels˝ o sorrendj´et, a marad´ek n − i jel¨olt pedig (n − i)! m´ odon jelenhet meg. Az (1) rel´ aci´o speci´ alisan azt is jelenti, hogy n X k−1 n−k k=j
j−1
i−j
2
n . = i
(2)
Ez´ert
k−1 n−k n X j−1 i−j E(Zi |ξ1 = i1 , . . . , ξi−1 = ji−1 , ξi = j) = k n k=j i n+1 n 1 X k (n + 1) − (k + 1) n+1 i+1 =j =j = j n n (i + 1) − (j + 1) j i+1 k=j i i
(3)
a (2) rel´ aci´o alapj´ an (az n, i ´es j param´eterek helyett az n + 1, i + 1 ´es j + 1 param´eter v´ alaszt´ assal. Feladat: Adjunk a (2) azonoss´agra k¨ ozvetlen kombinatorikus bizony´ıt´ ast. Egy lehet˝ os´eg: Sz´ amoljuk ¨ ossze, h´any olyan n + 1 hossz´ us´ ag´ u fej-´ır´as sorozat van, melyben az n + 1-ik tag az i + 1-ik fej. Sz´ amoljuk ezt ¨ ossze u ´gy is, hogy el˝ o´ırjuk a sorozatban szerepl˝o j-ik fejdob´as hely´et, majd ¨ osszegez¨ unk ennek a helynek a lehets´eges ´ert´ekeire. Egy m´ asik lehets´eges indokl´ as: (A negat´ıv binomi´ alis eloszl´ asr´ ol tanultak alapj´ an) ´ırjuk ´ at a (2) kifejez´esben szerepl˝o tagokat mint alkalmas (negat´ıv sz´ amokat is megenged˝o) binomi´ alis egy¨ utthat´okat. n n n−i −(i + 1) P´eld´aul: = = (−1) . Ezut´an alkalmazzuk az (1 − i n−i n−i x)α+β = (1 − x)α (1 − x)β azonoss´agot, illletve annak k¨ ovetkezm´eny´et e f¨ uggv´enyek hatv´anysorainak egy¨ utthat´oira alkalmas α ´es β v´ alaszt´ assal. A fenti eredm´eny, illetve a Szindb´ ad probl´ema megold´ as´aban tanultak alapj´ an a Secretary problem ekvivalens a k¨ ovetkez˝ o k´erd´essel: Legyenek ξ1 , . . . , ξn f¨ uggetlen 1 val´ osz´ın˝ us´egi v´ altoz´ ok, melyek eloszl´ as´at a P (ξi = j) = . 1 ≤ j ≤ i, 1 ≤ i ≤ n k´eplet i n+1 adja meg. Vezess¨ uk be a vi (j) = vi,n (j) = j k¨ olts´egf¨ uggv´enyt. Keress¨ uk meg azt i+1 az optim´alis τ meg´ all´ asi szab´alyt, mely minimaliz´ alja a k¨ olts´egf¨ uggv´eny Evτ (ξτ ) v´ arhat´ o ´ert´ek´et. Azt is megt´ argyaltuk, hogyan kell ezt a feladatot megoldani. Defini´ aljuk a n
cn−1 = Evn (ξn ) =
ci−1 = E min
n+1 1 X n+1 j = n j=1 n + 1 2
n+1 ξi , ci i+1
i n+1 1X min j, ci = , i j=1 i+1
i = n − 1, n − 2, . . . , 1
(4) sz´amsorozatot. Ekkor az optim´alis meg´ all´ as az lesz, hogy a i-ik id˝ opontban a´llok meg, n+1 ξi ≥ ci . Az n-ik l´ep´esben 1 ≤ i ≤ n − 1, ha nem ´ alltam meg el˝ obb, ´es vi (ξi ) = i+1 mindenk´epp meg´ allok. A k¨ olts´eg v´ arhat´ o ´ert´eke pedig (az optim´alis strat´egia eset´en) c0 . Ezek ut´ an a feladat a (4) rekurz´ıv elj´ar´ assal megadott az n megengedett l´ep´essz´ amt´ol 3
(n)
is f¨ ugg˝o ci = ci
(n)
sorozat kisz´ amol´ asa ´es a C = lim c0 n→∞
hat´ar´ert´ek meghat´ aroz´asa
(felt´eve, hogy ez a hat´ar´ert´ek l´etezik). i+1 ci , 0 ≤ i ≤ n − 1, ´es n+1 si = [ti ] mennyis´egeket, ahol [x] jel¨oli az x sz´am eg´esz r´esz´et. Ezekkel a jel¨ol´esekkel a (4) rekurzi´ os formula n´emileg egyszer˝ ubb form´aban ´ırhat´ o fel: A ci sorozat vizsg´alat´aban ´erdemes bevezetni a ti =
ci−1
1 = i
n+1 (1 + · · · + si ) + (i − si )ci i+1
1 = i
n + 1 si (si + 1) + (i − si )ci , i+1 2
´es ti = si + αi , 0 < αi < 1 jel¨ol´essel si (si + 1) + 2ti (i − si ) , 2(i + 1)
(5a)
ti (1 + 2i − ti ) α(1 − α) − . 2(i + 1) 2(i + 1)
(5)
ti−1 =
ti−1 =
A ti → ti−1 transzform´ aci´o viselked´es´enek jobb meg´ert´ese ´erdek´eben vezess¨ uk be az annak a f˝ o r´esz´et le´ır´o x(1 + 2i − x) T (x) = Ti (x) = 2(i + 1) transzform´ aci´ot. Egyszer˝ u sz´amol´ as adja, hogy T ′ (x) =
ez´ert T (x) monoton n˝o x ≤ i +
1 + 2i − 2x ≥ 0, 2(i + 1)
1 ha x ≤ i + , 2
1 eset´en. Tov´ abb´a (5) alapj´ an 2 T (ti ) ≥ ti−1 .
(6)
A fentiek alapj´ an bizony´ıthat´ o a k¨ ovetkez˝ o Lemma. ti ≤
2n . n−i+3
(7)
A lemma bizony´ıt´ asa el˝ ott mutassuk meg annak egy ´erdekes k¨ ovetkezm´eny´et. K¨ ovetkezm´ eny: c0 < 8, azaz a v´ arhat´ o nyerem´eny optim´ alis strat´egia eset´en b´ armely n sz´ amra kisebb mint 8. 4
A k¨ ovetkezm´eny bizony´ıt´ asa. oj´ab´ ol kiolvashat´ o, hogy az monoton h nA i ci sorozat definici´ n˝o. Ez´ert v´ alasztva az i = sz´amot kapjuk a Lemma felhaszn´al´ as´aval, hogy 2 c0 ≤ ci =
n+1 2n(n + 1) n+1 2n < 8. ti ≤ ≤ n n i+1 i+1 n−i+3 + 3 2 2
n 2n A Lemma bizony´ıt´ asa: A Lemma ´ all´ıt´ asa ´erv´enyes i = n − 1-re, mert tn−1 = = . 2 4 Ez´ert el´eg bel´ atni, hogy amennyiben az ´erv´enyes 1 ≤ i ≤ n − 1-re, akkor ´erv´enyes i − 1-re is. Ezt u ´gy bizony´ıtjuk, hogy felhaszn´aljuk a (7)-es formul´ at a m´ ar bizony´ıtott i param´eterrel, a (6) egyenl˝otlens´eget valamint azt, hogy a T (x) transzform´ aci´o monoton 1 n˝o t ≤ i + esetben. Tov´ abb´a, mivel a ci sorozat monoton n˝o, ez´ert 2 ti−1 =
i i i n+1 i ci+1 ≤ cn−1 = = . n+1 n+1 n+1 2 2
2n i ≤ azonoss´ag, 2 n−i+4 ´es az indukci´ os feltev´es teljes¨ ul i − 1-re is, (ez csak nagyon kis i indexre lehets´eges) vagy i 2n 1 2n 2n > , ´es ekkor i+ ≥ , ez´ert mind a ti mind a ≥ ti sz´amok 2 n−i+4 2 n−i+3 n−i+3 beleesnek abba az intervallumba, ahol T (·) monoton n˝o. Ez´ert n{(1 + 2i)(n − i + 3) − 2n} 2n 2n ti−1 ≤ T (ti ) ≤ T = ≤ , 2 n−i+3 (i + 1)(n − i + 3) n−i+4 Ez a becsl´es t´ ul durva, m´egis hasznos. Ugyanis vagy teljes¨ ul az
ami azt jelenti, hogy igaz az indukci´ os feltev´es i − 1-re is. Az utols´ o azonoss´ag az´ert igaz, mert az ekvivalens a (n − i + 3)2 + (2n − 2i − 10(n − i + 3) + 2n ≥ 0 egyenl˝otlens´eggel, ami ny´ılv´an ´erv´enyes n − i ≥ 1, azaz i ≤ n − 1 eset´en. (n)
ar´ ert´ ek meghat´ aroz´ asa. A lim c0 hat´ n→∞ A r´eszletek kidologz´ asa n´elk¨ ul. (n)
Vezess¨ uk be az ik = ik
mennyis´egeket a k¨ ovetkez˝ o m´ odon:
ik = A legkisebb j pozit´ıv eg´esz sz´am, melyre tj ≥ k. Az ik mennyis´egeket az´ert ´erdemes bevezetni, mert seg´ıts´eg¨ ukkel vizsg´alhat´ o az optim´alis meg´ all´ asi szab´aly. Ez a k¨ ovetkez˝ o: Az els˝ o i1 − 1 jel¨oltet mindenk´eppen elutas´ıtjuk. Az ik ≤ j < ik+1 -ik megjelent jel¨oltet akkor fogadjuk el, ha annak ξk relat´ıv rangja kisebb vagy egyenl˝o mint k. A fenti megjegyz´esb˝ ol az is k¨ ovetkezik, hogy c0 = c1 = · · · = ci1 −1 . 5
(Eml´ekeztet˝ ou ¨l, a cj mennyis´eg annak a v´ arhat´ o ´ert´eke, hogy mekkora a k¨ olts´egf¨ uggv´enyem, ha az els˝ o j l´ep´esben nem ´ allhatok meg, ´es ezen felt´etel mellett az optim´alis strat´egi´at folytatom.) (n)
ik hat´ar´ert´ekek, α0 ≤ α1 ≤ · · · , n→∞ n ´ k¨ ul¨ on hangs´ ulyozni, hogy αk < 1 minden k = 0, 1, . . . sz´amra, ´es lim αk = 1. Erdemes Be lehet l´atni, hogy hogy l´eteznek az αk−1 = lim k→∞
az α0 > 0 szigor´ u egyenl˝otlens´eg ´erv´enyes. (n)
altoz´ as´aval keveset v´ altoznak. PonEzenk´ıv¨ ul a tj = tj sz´amok a j index megv´ tosabban megfogalmazva, tetsz˝oleges 0 < α < β < 1 sz´amra lim
sup
(n)
(tj
n→∞ αn≤j≤βn
(n)
− tj−1 ) = 0.
A fenti rel´ aci´o azt sugallja, hogy a tik ∼ tik −1 ∼ k k¨ ozel´ıt´essel kis hib´at k¨ ovet¨ unk el. Speci´alisan, (n + 1)ti1 −1 n c0 = c1 = · · · = ci1 =1 = ∼ , i i1 ez´ert (n)
lim c0
n→∞
= lim
n
=
n→∞ i(n) 1 i
1 . α0
(8)
(n)
aEz´ert a feladat megold´ asa ´erdek´eben el´eg a lim kn = αk−1 mennyis´egeket meghat´ n→∞ rozni. Az´ert, hogy ezeket a hat´ar´ert´ekeket kisz´ amoljuk vezess¨ uk be a vi = ti −
k , 2
ha ik ≤ i < ik+1
azaz k ≤ ti < k + 1
mennyis´egeket, ´es ´ırjuk fel mit jelentenek a ti mennyis´egekre fenn´all´ o rekurzi´ os formul´ ak a vi mennyis´egekre. Azt kapjuk, hogy k(k + 1) + 2(i − k) v − k vi−1 + = 2 2(i + 1) ahonnan vi =
i+1 vi−1 i−k
k 2
=
k vi − k + vi , 2 i+1
ha ik ≤ i < ik+1 .
(9)
(Hogyan lehet r´aj¨onni, hogy a fent defini´alt vi mennyis´egekre ilyen egyszer˝ u rekurzi´ os formula ´erv´enyes?) Alkalmazva a (8) rel´ aci´ot szukcessziven a ik ≤ i < ik+1 sz´amokra azt kapjuk, hogy (j + 1 − k) · · · (j + 1) vj , = vi (i + 1 − k) · · · (i + 1) 6
ha ik ≤ i ≤ j < ik+1 .
(10)
Alkalmazzuk a (10) formul´ at i = ik , j = ik+1 v´ alaszt´ assal. Azt kapjuk, hogy egyr´eszt
lim
n→∞
vi(n)
k+1
vi(n)
(n)
ik+1
= lim
(n)
n→∞
ik
k
m´ asr´eszt lim
n→∞
vi(n)
k+1
vi(n) k
!k+1
=
αk αk−1
ti(n) − k2 k+1− = lim k+1 n→∞ k − k2 ti(n) − k2
k 2
k+1
=
,
k+2 . k
k
Innen
k+2 = k ez´ert
αk αk−1
k+1
,
j+1 k Y α0 j , = αk j + 2 j=1
´es k → ∞ hat´ar´ atmenettel (felhaszn´ alva, hogy lim αk = 1) kapjuk, hogy k→∞
j+1 ∞ (n) Y j i1 = α0 = lim . n→∞ n j+2 j=1 Innen ´es a (8) formu´ab´ ol k¨ ovetkezik, hogy a keresett v´ arhat´ o ´ert´ek val´ oban a megadott sz´am. A fenti heurisztikus ´ervel´es pontoss´ a t´etele ´erdek´eban n´eh´ any becsl´esre van sz¨ uks´eg. Ezek k¨ oz¨ ul a legfontosabb az, hogy a tj mennyis´egekre ne csak (viszonylag durva) fels˝o becsl´est adjunk (ezt tett¨ uk meg a Lemm´ aban), hanem megfelel˝ o als´ o becsl´est is bi(n) i zony´ıtsunk. Ez kell p´eld´aul ahhoz, hogy tudjuk: lim inf 1 > 0. n→∞ n A tj mennyis´egre adott fels˝o becsl´es bizony´ıt´ asa azon alapult, hogy az (5) formula seg´ıts´eg´evel viszonylag egyszer˝ u, de j´ o ti−1 ≤ T (ti ) alak´ u becsl´est tudtunk adni. Hasonl´ o elven egy als´ o becsl´est is lehet bizony´ıtani. Be lehet l´atni, hogy ti−1
ti ≥ i+1
ti 1− 2(i + 1)
,
´es ennek alapj´ an ti ≥
3(i + 1) . 2(n − i + 2)
A bizony´ıt´ as r´eszleteit elhagyjuk. Az megtal´ alhat´ o az eml´ıtett cikkben. 7
