Problem sekretarki

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ę ${\displaystyle 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 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 ${\displaystyle r,}$ ze zbioru ${\displaystyle 1\leqslant r<n,}$ taka, że optymalnie jest analizować pierwszych ${\displaystyle r}$ kandydatek i je odrzucać. Następnie, z pozostałych ${\displaystyle 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 ${\displaystyle r.}$ Optymalna wartość ${\displaystyle r}$ przy ${\displaystyle n}$ dążącym do nieskończoności jest równa ${\displaystyle 1/e.}$ Inaczej mówiąc, można pokazać, że ${\displaystyle r\approx n/e\approx 0{,}368n,}$ gdzie ${\displaystyle e}$ jest podstawą logarytmów naturalnych (liczbą Eulera). Przy takiej strategii prawdopodobieństwo wyboru najlepszej kandydatki, przy ${\displaystyle n}$ dążącym do nieskończoności, dąży do ${\displaystyle 1/e}$ (około 36,8%).

Przedstawiony problem ma wiele wariantów. Ważniejsze modyfikacje to:

1. mamy prawo wybrać dwa obiekty,
2. problem, gdy liczba możliwych obiektów, z których dokonujemy wyboru jest losowa,
3. znacząca liczba kandydatek jest nierozróżnialna,
4. można powracać do odrzuconych obiektów,
5. celem jest wybór najlepszego lub drugiego w klasyfikacji.

Załóżmy, że najlepsza kandydatka jest na pozycji ${\displaystyle a.}$ Jeśli ${\displaystyle a<r,}$ to proponowana strategia jej nie wybierze i w takim przypadku nie dokonamy wyboru najlepszej kandydatki. Jeśli ${\displaystyle a>r,}$ to przyjęty próg dzieli kandydatki na trzy grupy, ${\displaystyle [1,r],}$ ${\displaystyle [r,a]}$ oraz ${\displaystyle [a,n].}$ Jeśli nasza strategia ma przynieść sukces, to druga według naszego kryterium kandydatka w przedziale [1,a] powinna być przed progiem ${\displaystyle r,}$ tj. w przedziale [1,r]. Prawdopodobieństwo takiego zdarzenia wynosi ${\displaystyle {\frac {r}{a}}.}$ Zatem całkowita szansa na sukces wynosi ${\displaystyle {\frac {r}{a}}}$ pod warunkiem, że ${\displaystyle a>r.}$

Przy dużych liczbach kandydatek ${\displaystyle n}$ prawdopodobieństwo wyboru najlepszej jest bliskie całce po możliwych położeniach ${\displaystyle a}$

${\displaystyle P(\mathrm {success} )={\frac {1}{n}}\sum _{a=r}^{n}{\frac {r}{a}}\approx {\frac {1}{n}}\int \limits _{r}^{n}{\frac {r}{a}}da=-{\frac {r}{n}}\log \left({\frac {r}{n}}\right).}$

Przyrównując pochodną po ${\displaystyle {\frac {r}{n}}}$ powyższego wyrażenia do zera, otrzymujemy, że wartość ${\displaystyle {\frac {r}{n}}={\frac {1}{e}}}$ maksymalizuje prawdopodobieństwo wyboru najlepszej kandydatki^[3].