]> Titkárnő probléma
  1. Virtuális laboratóriumok
  2. 11. Véges mintavételi modellek
  3. 1
  4. 2
  5. 3
  6. 4
  7. 5
  8. 6
  9. 7
  10. 8
  11. 9

9. Titkárnő probléma

Ebben a részben tanulmányozni fogunk egy szép problémát, ami többféle néven is ismert, mint pédául titkárnő probléma vagy házasodási probléma. Egyszerű megállapítani, hogy a problémát nem nehéz megoldani, de a megoldás érdekes és egy kicsit meglepő. A probléma egy kellemes bevezetést szolgáltat a statisztikai döntések általános területére.

A probléma állítása

Mint mindig, a probléma egy világos megfogalmazásával indulunk. Van n jelöltünk (talán pályázók egy munkára, vagy lehetséges házassági partnerek). Feltevéseink:

Ezek a feltevések természetesen a valós alkalmazásokban teljesen elfogadhatók. Az utolsó feltevés például, hogy n ismert, a titkárnő interpretációban helyénvalóbb, mint a házassági interpretációban.

Mi az optimális stratégia? Ezzel a stratégiával mekkora a ( legjobb ) választás valószínűsége? Mi történik a stratégiával, és a valószínűséggel, ha n ? Speciálisan, nagy n esetén,van remény a legjobb jelölt megtalálására?

Stratégiák

Játsszuk le a titkárnő játékot néhányszor n 10 jelölttel. Nézze meg, hogy van-e különbség a teljesítményben!

A titkárnőjáték néhényszori lejátszása után, világos lesz, hogy a stratégiának csak az a típusa elfogadható, amikor bizonyos számú, k 1 jelölt már elhaladt és ekkor kiválasztjuk az első jelöltet, aki jobb, mint az összes, eddigi jelölt (ha létezik ilyen). Ha nem létezik (azaz, ha nincs olyan jelölt, aki az összes eddigi jelöltnél jobb), akkor megállapodunk, hogy az utolsó jelöltet fogadjuk el, annak ellenére, hogy ez kudarcot jelent. A k paraméternek 1 és n között kell lennie; ha k 1 , akkor válasszuk az 1. jelöltet; ha k n , akkor válsszuk az utolsó jelöltet; k bármely más értéke esetén a jelöltet véletlenszerűen válasszuk ki, a k k 1 n halmazból. Erre az engedjünk el k 1 jelöltet módszerre, mint k stratégia-ként fogunk hivatkozni.

Így, nekünk ki kell számítanunk a p n k valószínűséget k stratégiát használva n jelölt esetén. Ekkor maximalizálni tudjuk a k feletti valószínűséget és meg tudjuk adni az optimális stratégiát, továbbá az n szerinti határértéket és tanulmányozni tudjuk az aszimptotikát.

Analízis (Elemzés)

Először végezzük el az alapszámításokat.

Az n 3 esetre listázzuk ki az 1 2 3 elemek permutációit és ellenőrizzük az alábbi táblában szereplő valószínűségeket. Megemlítjük, hogy k 2 az optimális.

k 1 2 3
p 3 k 13 12 13

Játsszuk le a titkárnő játékot néhányszor n 3 jelöltre felhasználva a következő stratégiákat. Nézze meg, hogy van-e különbség a teljesítményben!

  1. 1 stratégia
  2. 2 stratégia
  3. 3 stratégia

Az n 4 esetben listázza ki az 1 2 3 4 elemek permutációit és ellenőrizze a valószínűségeket az alábbi táblázatban. Vegye észre, hogy k 2 az optimális.

k 1 2 3 4
p 4 k 624 1124 1024 624

Játssza le a titkárnő játékot néhányszor n 4 jelölttel, felhasználva a következő startégiákat. Nézze meg, hogy van-e különbség a teljesítményben!

  1. 1 stratégia
  2. 2 stratégia
  3. 3 stratégia

Az n 5 esetre listázza ki az 1 2 3 4 5 elemek permutációit és ellenőrizze a valószínűségeket az alábbi táblázatban. Vegye észre, hogy k 3 az optimális.

k 1 2 3 4 5
p 5 k 24120 50120 52120 42120 24120

Játssza le a titkárnő játékot néhányszor n 5 jelöltre felhasználva a következő stratégiákat: lássa, ha különbséget észlel a véghezvitelben.

  1. 2 stratégia
  2. 3 stratégia
  3. 4 stratégia

Nos, világos, hogy nem akarjuk folytatni ezt. Nézzük, mennyiben tudunk találni egy általános elemzést. n jelölttel, jelölje X n a legjobb jelölt (érkezési sorrend szerint) számát, és jelölje S n k a k stratégia esetén a sikeres eseményt (azaz, hogy megtaláltuk a legjobb jelöltet).

Bizonyítsuk be, hogy mivel a jelöltek véletlenszerű sorrendben jönnek, X n egyenletes eloszlású a 1 2 n halmazon.

Bizonyítsuk be, hogy

  1. S n k X n j 0 ha j 1 2 k 1 . Ha a legjobb jelölt érkezési száma j k , akkor a k stratégia bizonyosan nem jár sikerrel.
  2. S n k X n j k 1 j 1 ha j k k 1 n . Ha a legjobb jelölt érkezési száma j k , akkor a k stratégia akkor és csak akkor lesz sikeres, ha az első k 1 jelölt között (vagyis az automatikusan elutasítottak között) van az első j 1 jelölt legjobbja.

A következőkben két esetet illusztrálunk. A nagy pont a legjobb jelöltet jelöli. A piros pontok azokat a jelölteket jelölik, akiket elutasítottunk, míg a kékek azokat, akiket megvizsgáltunk.

Image: Success1.png Image: Success2.png

Felhasználva az előző gyakorlat eredményeit és egy feltételes érvelést, mutassuk meg, hogy

p n k S n k j k n 1 n k 1 j 1 k 1 n j k n 1 j 1

A p n függvény értékeit ki tudjuk könnyen számolni kis n értékek esetén és számítógépes algebra rendszer segítségével közepesen nagy n számok esetén. A p 100 ábrája látható a következő ábrán. Megjegyezzük, hogy a gráf alulról konkáv alakú és k optimális értéke 38-nál van. Az optimális valószínűség 0.37104.

Image: Strategyk.png

Az optimális stratégia k n -re, a k n n hányados és a p n k n a legjobb jelölt megtalására vonatkozó optimális valószínűséget, mint n 3 4 20 függvényét a következő táblázatban adtuk meg:

Jelöltek n Optimális stratégia k n Hányados k n n Optimális valószínűség p n k n
3 2 0.6667 0.5000
4 2 0.5000 0.4853
5 3 0.6000 0.4333
6 3 0.5000 0.4278
7 3 0.4286 0.4143
8 4 0.5000 0.4098
9 4 0.4444 0.4060
10 4 0.4000 0.3987
11 5 0.4545 0.3984
12 5 0.4167 0.3955
13 6 0.4615 0.3923
14 6 0.4286 0.3917
15 6 0.4000 0.3894
16 7 0.4375 0.3881
17 7 0.4118 0.3873
18 7 0.3889 0.3854
19 8 0.4211 0.3850
20 8 0.4000 0.3842

Kétségtelenül, mint várható volt, a k n optimális stratégia növekszik és a p n k n csökken, amint n növekszik. Másrészt, az bíztató és egy kicsit meglepő, hogy az optimális valószínűség nem csökken 0-ig. Az talán legkevésbé világos, mi történik a hányadossal. A táblázatban néhány információ grafikus megjelenítése segíthet:

Segíthet-e, hogy a k n n hányados és a p n k n valószínűség mindegyike konvergál és emellett ugyanahhoz az értékhez? Először próbáljunk kimutatni a táblázatban megfigyelt bizonyos trendeket.

Mutassuk meg, hogy

  1. p n k 1 p n k akkor és csak akkor, ha j k n 1 j 1 1
  2. Minden n esetén a p n függvény előszőr növekszik, majd csökken.
  3. A maximum a legnagyobb olyan k -nál van, amelyre j k n 1 j 1 1 . Ez a k n optimális stratégia.
  4. Ha n növekszik, akkor k n növekszik

Adjunk valószínűségszámítási bizonyítást arra, hogy az optimális valószínűség p n k n csökken, ha n növekszik.

Aszimptotikus elemzés

Természetesen, minket érdekel a p n függvény aszimptotikus viselkedése és az optimális stratégia, ha n . A kulcs annak felismerése, hogy p n egy egyszerű integrál Riemann összege. (A Riemann összegek természetesen Georg Riemann-ról kapta a nevét.)

Mutassuk meg, hogy

p n k k 1 n j k n 1 n n j 1

Az előző gyakorlatban lévő összegnek, mint balodali Riemann összegnek a felismerése az f t 1 t esetén a k 1 n 1 intervallum olyan n k 1 részintervallumokra való bontása, melyek mindegyikének hossza 1 n : k 1 n k n k 1 n n 1 n 1

Az előző két gyakorlatból következik, hogy

p n k k 1 n k 1 n k n k n

Még szigorúbban tételezzük fel, hogy k n n -től függ és hogy k n n x ha n . Így x 0 1 azon jelöltek határhányadosa, akiket azonnal elutasítunk.

Mutassuk meg, hogy p n k n x x ha n .

A következő grafikon a p n k valódi valószínűségeket mutatja és a k n k n határértékeket, mint k függvényét n 100 esetén.

Image: Strategyk2.png

Könnyen maximalizálhatjuk a határfüggvényt.

Mutassuk meg, hogy x x maximuma x 1 értéknél van, és ez a maximum 1 -vel egyenlő.

Image: StrategyLimit.png

Így, az 1 0.36788 mágikus szám kétszer szerepel a problémában. Nagy n esetén:

Tom Ferguson a probléma egy érdekes történeti diszkusszióját adja a "Who Solved the Secretary Problem? (magyarul: Ki oldotta meg a titkárnő problémát?)" c. cikkében, amely elmélkedést tartalmaz arról, hogy Johann Kepler lehetséges, hogy alkalmazta az optimális stratégiát második felesége kiválasztásánál. A cikk a probléma néhány általánosítását is elemzi.