Problem sekretarki — reguła 37%
Rozszerzenie tematu prawdopodobieństwa i liczby e. By z największą szansą wybrać najlepszego kandydata widzianego pojedynczo (bez powrotu), należy odrzucić pierwsze ~37% (1/e), a potem wybrać pierwszego lepszego od wszystkich dotychczasowych. Próg optymalny dąży do 1/e, a szansa sukcesu też ~1/e. Problem spopularyzował Martin Gardner w 1960 r.
Dam Ci liczbę kandydatów do odrzucenia — ustaw suwak n tak, by optymalny próg round(n/e) dokładnie ją dał.
Co się właśnie stało?
Przeglądasz kandydatów pojedynczo, w losowej kolejności, i po każdym musisz od razu zdecydować „biorę” lub „odrzucam na zawsze” — bez możliwości powrotu. Chcesz wybrać najlepszego. Zaskakująco prosta i elegancka strategia optymalna: odrzuć pierwsze ~37% kandydatów, tylko ich obserwując i zapamiętując najlepszego jako „poprzeczkę”, a potem wybierz pierwszego, który przewyższy wszystkich dotychczasowych. Na scenie widać dwie fazy — obserwacji (odrzucania) i wyboru — rozdzielone progiem, oraz krzywą szansy sukcesu z wyraźnym maksimum przy 37%.
Optymalny próg odcięcia:
— odrzucasz pierwsze kandydatów (gdzie to liczba Eulera), co dla dużych daje próg zbieżny do 37%.
Szansa wybrania najlepszego:
Ta strategia daje ~37% szansy (dokładnie ) na trafienie w absolutnie najlepszego kandydata — niezależnie od tego, czy jest ich 10, 100 czy milion! To niezwykłe, bo naiwnie wydawałoby się, że przy widzeniu każdego tylko raz szansa powinna być znikoma ().
Dlaczego akurat 1/e? (niezmiennik)
Magiczna liczba (odwrotność liczby Eulera) pojawia się tu naturalnie z rachunku prawdopodobieństwa: maksymalizując po progu , otrzymujemy warunek, którego rozwiązanie dąży do . W tym punkcie także sama szansa sukcesu wynosi . Panel po prawej pokazuje oba te słupki przyklejone do linii — i to niezależnie od .
Historia i zastosowania
Problem sekretarki (znany też jako problem narzeczonej, problem sułtana czy „problem najlepszego wyboru”) to klasyczny problem optymalnego zatrzymania, spopularyzowany przez Martina Gardnera w 1960 r. Ma realne zastosowania w teorii decyzji, ekonomii, a nawet w życiowych wyborach (stąd żartobliwe „reguła 37%” dla randkowania — po obejrzeniu 37% opcji wybierz następną lepszą). To piękny przykład tego, jak matematyka daje konkretną, optymalną strategię w sytuacji pozornie beznadziejnej.
Po co Ci to na maturze:
To rozszerzenie tematu prawdopodobieństwa i liczby . Pokazuje, że nawet przy nieodwracalnych decyzjach „na żywo” prosta reguła progowa bije wybór losowy — i że stała wyskakuje w miejscach, gdzie zupełnie się jej nie spodziewamy.
Zapamiętaj: obserwuj i odrzucaj pierwsze , potem bierz pierwszego lepszego. Szansa na najlepszego: .
Teoria i wzory
Reguła 1/e
Kandydatów oglądamy pojedynczo, bez powrotu. Optymalna strategia: odrzuć pierwsze (około ), zapamiętując najlepszego, a potem wybierz pierwszego lepszego od wszystkich dotychczasowych.
Szansa sukcesu
Dla dużych próg i prawdopodobieństwo wybrania najlepszego dążą do:
Skąd e
Maksymalizacja szansy prowadzi do równania, którego rozwiązaniem jest próg — stąd stała w problemie optymalnego zatrzymania.
Oznaczenia: liczba kandydatów, .
Uczysz? Umieść ten eksperyment na swojej stronie.
Darmowy widget — wklej na stronę szkoły, bloga lub notatki. Linkuje do pełnej wersji.
Najczęstsze pytania
›Ile kandydatów odrzucić na początku?
Około 37% (dokładnie n/e), tylko ich obserwując, a potem wybrać pierwszego lepszego od wszystkich dotychczasowych.
›Jaka jest szansa wybrania najlepszego?
Około 1/e ≈ 37% — niezależnie od liczby kandydatów (dla dużych n).
›Skąd bierze się liczba 1/e w tym problemie?
Z rachunku prawdopodobieństwa optymalnego zatrzymania — optymalny próg i szansa sukcesu dążą do 1/e.