Problem sekretarki
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f5/Fotothek_df_roe-neg_0006196_004_Portr%C3%A4t_einer_Frau_an_einer_Schreibmaschine.jpg/220px-Fotothek_df_roe-neg_0006196_004_Portr%C3%A4t_einer_Frau_an_einer_Schreibmaschine.jpg)
Problem sekretarki[1] (znany także jako problem wyboru najlepszego obiektu lub problem łowcy posagu) – 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. Zagadnienie sprowadza się do optymalnego zatrzymania pewnego ciągu losowego, czyli wyboru optymalnego momentu zatrzymania[2] dla tego ciągu.
Klasyczny przykład takiego problemu to zagadnienie obsady stanowiska sekretarki[1][3]. Na ogłoszenie o wolnym stanowisku sekretarki zgłosiło się 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 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 ze zbioru taka, że optymalnie jest analizować pierwszych kandydatek i je odrzucać. Następnie, z pozostałych kandydatek, wybrać pierwszą, która jest lepsza od dotychczas przeglądanych. Metodami poszukiwania maksimum ciągu liczbowego można wyznaczyć optymalną wartość progu Optymalna wartość przy dążącym do nieskończoności jest równa Inaczej mówiąc, można pokazać, że gdzie jest podstawą logarytmów naturalnych (liczbą Eulera). Przy takiej strategii prawdopodobieństwo wyboru najlepszej kandydatki, przy dążącym do nieskończoności, dąży do (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.
Optymalne wyznaczanie progu
Załóżmy, że najlepsza kandydatka jest na pozycji Jeśli to proponowana strategia jej nie wybierze i w takim przypadku nie dokonamy wyboru najlepszej kandydatki. Jeśli to przyjęty próg dzieli kandydatki na trzy grupy, oraz Jeśli nasza strategia ma przynieść sukces, to druga według naszego kryterium kandydatka w przedziale [1,a] powinna być przed progiem tj. w przedziale [1,r]. Prawdopodobieństwo takiego zdarzenia wynosi Zatem całkowita szansa na sukces wynosi pod warunkiem, że
Przy dużych liczbach kandydatek prawdopodobieństwo wyboru najlepszej jest bliskie całce po możliwych położeniach
Przyrównując pochodną po powyższego wyrażenia do zera, otrzymujemy, że wartość maksymalizuje prawdopodobieństwo wyboru najlepszej kandydatki[3].
Przypisy
- ↑ a b Thomas S.T.S. Ferguson Thomas S.T.S., Who solved the secretary problem?, „Statistical Science”, 4 (3), sierpień 1989, s. 282–296, ISBN 3-540-74010-4, JSTOR: 2245639 .
- ↑ Tomasz Bojdecki: Martyngały z czasem dyskretnym. Zarys teorii i przykłady zastosowań. Wyd. Skrypt dla studentów III roku Instytutu Matematyki. Warszawa: Wydawnictwo Uniwersytetu Warszawskiego, 1977. ISBN 83-230-0426-9.
- ↑ a b RobertR. Bartoszyński RobertR., Reguły zatrzymywania (Stopping rules), „Roczniki Polskiego Towarzystwa Matematycznego. Seria II. Wiadomości Matematyczne”, 18, 1974, s. 41–53, ISSN 0373-8302 .
- LCCN: sh2007002577
- J9U: 987007554300205171