A Secretary problem.




E jegyzetben a következõ optimalizációs problémával foglalkozunk. Egy titkárnõi állásra n jelentkezõ van. Legyen a legjobb jelölt jósági indexe 1, a második legjobbé 2, és így tovább. Ismerjük a jelöltek számát, de egyébként semmit nem tudunk róluk. Véletlen sorrendben megjelennek a jelöltek, minden sorrend egyforma valószínû. Szeretnénk a kiválaszott jelölt jósági indexének a várható értékét minimalizálni. Mi az optimális stratégia, és mennyi a keresett várható érték optimális stratégia esetén? Mi e várható érték határértéke, ha a jelöltek n száma tart a végtelenhez? (Egyébként ez a határérték egy 8-nél kisebb számhoz tart.) E kérdésekkel foglalkozunk. Elmagyarázzuk a megoldás legfontosabb gondolatait, bár nem dolgozunk ki minden részletet. A részletes bizonyítás megtalálható Y. S. Chow, S. Moriguti, H. Robbins és M. Samuels Optimal Selection Based On Relative Ranks,``the Secretary Problem" címû cikkében az Israel Journal of Mathematics (1964) 81--90 újságban.


7 oldal