Problem sekretarki

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

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.

Przedstwiony problem ma bardzo proste rozwiązanie optymalne: istnieje liczba $r$ , ze zbioru $1\leq 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 (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 $\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.