A titkárnőprobléma

John D. Barrow 100 alapvető dolog, amiről nem tudtuk, hogy nem tudjuk című könyvének mottója Neumann Jánostól származik:  „Ha valaki nem hiszi, hogy a matematika egyszerű, az azért van, mert még nem jött rá, hogy milyen bonyolult az élet”.

A problémák elsődleges okai a megoldások.

 Sevareid-szabály

Régi probléma, hogyan válasszunk sok jelentkező közül, például ha egy igazgató mellé 500-an jelentkeznek titkárnőnek, vagy ha egy királynak feleséget kell választania országa összes hajadonja közül, vagy amikor egy egyetem csak a legjobb diákot akarja felvenni a sok jelentkező közül. Amikor nincs túl sok jelölt, mindegyikükkel el lehet beszélgetni, össze lehet őket hasonlítani, esetleg újra meg lehet hallgatni, akiről többet akarunk tudni, majd végül ki lehet választani a legalkalmasabbat. Ha viszont sok a jelentkező, ez a módszer gyakorlati akadályokba ütközhet. Ha véletlenszerűen választunk egyvalakit N ember közül, annak az esélye, hogy éppen ő a legjobb, mindössze 1/N, és ha N nagy, ez bizony nem túl sok – 100 vagy még több jelentkező esetén kevesebb, mint 1%. A legjobb jelölt kiválasztására az első módszer, amikor mindenkivel személyesen találkoztunk, időigényes volt, viszont megbízható, a véletlenszerű választás viszont gyors, de megbízhatatlan. Vajon van valamiféle „legjobb” módszer a kettő között, amelynek alkalmazásával elég jó eséllyel ki tudjuk választani a legjobb jelöltet anélkül, hogy aránytalanul sok időt emésztene fel a folyamat?

Van, méghozzá meglepően egyszerű és hatékony, mint látni fogjuk. Van tehát N jelentkező egy állásra, akiket valamiféle véletlenszerű sorrendben fogunk elbírálni. Tegyük fel, hogy van egy módszerünk, amellyel egy-egy jelölt megismerése után el tudjuk dönteni, hogy ő milyen az eddig látott többihez képest, bár valójában mindig csak az a fontos, hogy tudjuk, ki volt a legjobb az adott pillanatig megismertek közül. Amikor egy jelöltet elbíráltunk, már nem hívjuk vissza. És csak akkor sikeres a módszerünk, ha megtaláljuk a legjobb jelöltet; az összes többi próbálkozásunk kudarcnak számít. Így amikor befejezzük a beszélgetést egy-egy jelentkezővel, csak annyit kell feljegyeznünk, hogy ki a legjobb az eddig megismertek közül (beleértve a legutóbbit is). Vajon az N jelölt közül hányat kell meghallgatnunk, hogy legjobb eséllyel válasszuk ki a legjobbat, és mi legyen a stratégiánk?

Stratégiánk a következő lesz. Az N jelölt közül C-vel elbeszélgetünk (N > C), és az lesz a befutó, aki a megmaradt jelöltek közül jobb mind a C jelöltnél. A nagy kérdés, hogy C mekkora legyen?

Tegyük fel, hogy három jelöltünk van: 1, 2 és 3, ahol 3 jobb 2-nél és 2 jobb 1-nél. Ekkor hat lehetséges meghallgatási sorrend képzelhető el:

123, 132, 213, 231, 312, 321

Ha az lenne a módszerünk, hogy mindig az elsőként meghallgatott jelentkezőt választjuk, akkor a legjobbat (a 3. jelöltet) a hat sorrend közül csak kettőben választanánk, azaz 2/6 = 1/3 valószínűséggel. Ha az a módszerünk, hogy az első jelentkező meghallgatása után azt választjuk, aki először mutatkozik nála jobbnak, akkor csak a második (132), harmadik (213) és negyedik (231) esetben találnánk meg a legjobb jelöltet, vagyis ennek esélye 3/6 = 1/2. Ha viszont az első kettő meghallgatása után választunk a maradékból, az csak az első (123) és a harmadik (213) esetben vezet jó eredményre, megint csak 1/3 valószínűséggel. Tehát amikor három jelentkező van, a megfelelő stratégia a legjobb kiválasztására, hogy egyet menni hagyunk, majd kiválasztjuk a következőt, aki nála jobb.

Ugyanezzel a gondolatmenettel végig lehet nézni, hogy mi a helyzet, amikor a jelentkezők száma (N) nagyobb 3-nál. 4 jelölt esetében 24 lehetséges sorrend képzelhető el. Ha ezt mind végiggondoljuk, kiderül, hogy még mindig az a legjobb esélyünk, ha az elsőtől elbúcsúzunk, és azt választjuk, aki először lesz jobb nála; a siker valószínűsége[1] ekkor 11/24. Bármekkora N-re ki lehet számolni ezt az értéket, és érdekes megfigyelni, hogyan változik C értéke a stratégiánk alkalmazásakor.

Ahogy nő a jelöltek száma, stratégiánk, illetve annak eredménye egyre jobban közelít az optimálishoz. vegyük például azt az esetet, amikor 100 jelölt van. Az optimális stratégia:[2] meghallgatni az első 37-et, majd azt választani, aki a többiek közül először lesz jobb az első 37-nél, és a többiekkel nem foglalkozni. Ennek eredményeképpen mintegy 37,1% valószínűséggel választjuk a legalkalmasabb jelentkezőt – ez egész jó az 1%-hoz képest, ami a véletlenszerű kiválasztásnál adódik.[3]

Vajon alkalmazható-e ez a stratégia a gyakorlatban? Persze szép és jó azt mondani, hogy ha meghirdetünk egy állást, meg kell hallgatnunk az összes jelentkezőt, de vajon ugyanez igaz a cégvezetők kiválasztásakor, amikor feleséget keresünk, vagy ki akarjuk választani az új sikerkönyv témáját vagy a tökéletes lakóhelyet? Végül is nem tölthetjük egész életünket keresgéléssel. Vajon mikor kell abbahagyni a válogatást és választani? Vagy kevésbé életbevágó helyzetekben, amikor szállodát vagy vendéglőt keresünk, a legjobb ár/érték arányú nyaralás után kutatunk az interneten, vagy megpróbáljuk megtalálni azt a benzinkutat, ahol a legolcsóbb a benzin, hány lehetőséget vizsgáljunk meg, mielőtt döntenénk? Ezek mind szekvenciális kiválasztási problémák, csakúgy, mint a titkárnők kérdése, amihez megkerestük az optimális stratégiát. A gyakorlati tapasztalatok alapján valószínűnek látszik, hogy nem keresgélünk elég sokáig a végső döntés meghozása előtt. A pszichológiai nyomás vagy egyszerűen a türelmetlenség (akár a sajátunk, akár a másoké) miatt sokkal hamarabb döntést hozunk, mintha végignéznénk a lehetőségek kritikus hányadát, mintegy 37%-át.

John D. Barrow: 100 alapvető dolog, amiről nem tudtuk, hogy nem tudjuk (Akkord Kiadó, Budapest, 2013

A szerző a Cambridge-i Egyetemen folyó Millenniumi Matematika Projekt vezetője, matematikaprofesszor, a Royal Society tagja. Az Akkord Kiadónál korábban megjelentek tőle A semmi könyve, A végtelen könyve és az Univerzumok könyve.