Problem sekretarki

Problem sekretarki (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 dla tego ciągu.

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 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 $1\leqslant r<n$, 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 $r\approx n/e\approx 0,368n$, gdzie $e$ jest podstawą logarytmów naturalnych (liczbą 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:

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

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 ${\frac {r}{a}}$. Zatem, całkowita szansa na sukces wynosi ${\frac {r}{a}}$ 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$

$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 ${\frac {r}{n}}$ powyższego wyrażenia do zera otrzymujemy, że wartość ${\frac {r}{n}}={\frac {1}{e}}$ maksymalizuje prawdopodobieństwo wyboru najlepszej kandydatki.

Literatura

• R. Bartoszyński. "Reguły zatrzymywania", Wiadom. Mat. 18, 41–53, 1974.