Problem sekretarki
Z Wikipedii
W statystyce, teorii decyzji i teorii gier, problem sekretarki (znany także jako problem wyboru najlepszego obiektu lub problem łowcy posagu) to zagadnienie optymalnej selekcji najlepszej propozycji ze skończonego zbioru takich propozycji, prezentowanych sekwencyjnie w losowej kolejności. Przyjmuje się przy tym, że propozycje są istotnie różne.
Klasyczny przykład takiego problemu to zagadnienie obsady stanowiska sekretarki. Na ogłoszenie o wolnym stanowisku sekretarki zgłosiło się N kandydatek. Z każdą z nich przeprowadza się wywiad oceniając jej przydatność i natychmiast po skończeniu wywiadu kandydatkę można bądź przyjąć (wówczas proces selekcji kończy się), bądź też odrzucić i przeprowadzić wywiad z następną. Nie wolno przy tym zmieniać decyzji w stosunku do odrzuconych kandydatek. Inny niefrasobliwy przykład, to wybór kandydatki na żonę z listy kandydatek przedstawianych w losowej kolejności. Celem jest maksymalizacja prawdopodobieństwa wyboru najlepszej kandydatki.
Przedstawiony problem ma bardzo proste rozwiązanie optymalne: istnieje liczba r, ze zbioru 
, taka, że optymalnie jest analizować pierwszych r kandydatek i je odrzucać. Następnie, z pozostałych n − r kandydatek, wybrać pierwszą, która jest lepsza od dotychczas przeglądanych. Metodami poszukiwania maksimum ciągu liczbowego można wyznaczyć optymalną wartość progu r. Optymalna wartość r przy n dążącym do nieskończoności jest równa 1 / e. Inaczej mówiąc, można pokazać, że 
, gdzie e jest podstawą logarytmów naturalnych (stałą Eulera). Przy takiej strategii prawdopodobieństwo wyboru najlepszej kandydatki, przy n dążącym do nieskończoności, dąży do 1 / e (około 36.8%).
Przedstawiony problem ma wiele wariantów. Ważniejsze modyfikacje to:
- mamy prawo wybrać dwa obiekty
- problem, gdy liczba możliwych obiektów, z których dokonujemy wyboru jest losowa
- znacząca liczba kandydatek jest nierozróżnialna
- można powracać do odrzuconych obiektów
- celem jest wybór najlepszego lub drugiego w klasyfikacji
[edytuj] Optymalne wyznaczanie progu r
Załóżmy, że najlepsza kandydatka jest na pozycji a. Jeśli a < r, to proponowana strategia jej nie wybierze i w takim przypadku nie dokonamy wyboru najlepszej kandydatki. Jeśli a > r, to przyjęty próg dzieli kandydatki na trzy grupy, [1,r], [r,a] oraz [a,n]. Jeśli nasza strategia ma przynieść sukces, to druga według naszego kryterium kandydatka w przedziale [1,a] powinna być przed progiem r, tj. w przedziale [1,r]. Prawdopodobieństwo takiego zdarzenia wynosi 
. Zatem, całkowita szansa na sukces wynosi pod warunkiem, że a > r.
Przy dużych liczbach kandydatek n prawdopodobieństwo wyboru najlepszej jest bliskie całce po możliwych położeniach a
Przyrównując pochodną po 
powyższego wyrażenia do zera otrzymujemy, że wartość 
maksymalizuje prawdopodobieństwo wyboru najlepszej kandydatki.
[edytuj] Literatura
- R. Bartoszynski. "Reguły zatrzymywania", Wiadom. Mat. 18, 41-53, 1974.
- T. S. Ferguson. "Who solved the secretary problem?", Statistical Science, volume 4, pp.282-296, 1989.
