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.
[1] Ha az első vagy az utolsó jelöltet választjuk, annak \(1/4\) az esélye, ha 2 jelölt után választjuk a legjobbat, annak \(5/12\), ha viszont 1 után, annak \(11/24\); ez az optimális.
[2] Vegyük észre, hogy ha a legjobb jelölt az (\(r + 1\))-edik a sorban, és az első \(r\) jelentkező meghallgatása után fogunk csak választani, akkor biztos, hogy a legjobbat kapjuk, de ez csak \(1/N\) valószínűséggel következik be. Ha a legjobb jelölt az (\(r + 2\))-edik, \(1/N\cdot r/(r + 1)\) eséllyel választjuk ki (hiszen \(r/(r + 1)\) az esélye annak, hogy az első \(r+1\) jelölt közötti legjobb beleesik az első \(r\)-be; a nekünk rossz eset pont ennek komplemetere, amikoris az (\(r+1\))-edik jelölt a legjobb az első \(r+1\) közül, ezért őt kiválasztjuk, holott a ténylegesen legjobb jelölt csak az \(r+2\)-edik helyen jönne). Ha ezt a gondolatmenetet továbbvisszük a sorban később következő jelöltekre, azt kapjuk, hogy a sikerességünk esélye ezen mennyiségek összege, vagyis \[\begin{align}P(N, r)&=\dfrac{1}{N}\cdot\left(1+\dfrac{r}{r+1}+\dfrac{r}{r+2}+\dfrac{r}{r+3}+\dfrac{r}{r+4}+\dfrac{r}{r+5}+\ldots +\dfrac{r}{N-1}\right)\\&≈\dfrac{1}{N}\cdot\left(1+r\ln\left(\dfrac{N – 1}{r}\right)\right).\end{align}\] Ez utóbbi mennyiség, amely felé a sor tart \(N\) növekedésével, maximális értékét akkor éri el, amikor \((N – 1)/r≈e\), vagyis \(e ≈(N – 1)/r ≈ N/r\), ha \(N\) elég nagy. Így \(P(N, r)\) maximuma \(P ≈(r/N)\cdot\ln(N/r)≈1/e≈ 0{,}37\).
[3] Pontosabban, ha az első \(N/e\) jelentkező meghallgatása után választunk a következőkből, akkor annak esélye, hogy a legjobbat találjuk meg, \(N\) növekedésével közelít \(1/e\) értékéhez, ahol \(e ≈ 2{,}7182\ldots ≈1/0{,}37\) állandó a természetes logaritmus alapszáma.
