12.9: Проблема секретаря
- Page ID
- 99112
У цьому розділі ми вивчимо приємну проблему, відому по-різному як проблема секретаря або проблема шлюбу. Це просто констатувати і не важко вирішити, але рішення цікаве і трохи дивовижне. Також проблема служить приємним введенням в загальну область прийняття статистичних рішень.
Постановка проблеми
Як завжди, починати треба з чіткої постановки проблеми.
У нас є\(n\) кандидати (можливо, претенденти на роботу або можливі партнери по шлюбу). Припущення є
- Кандидати повністю замовлені від кращого до гіршого без зв'язків.
- Кандидати прибувають послідовно в довільному порядку.
- Ми можемо лише визначити відносні ряди кандидатів у міру їх прибуття. Ми не можемо спостерігати абсолютні ряди.
- Наша мета - вибрати найкращого кандидата, ніхто менше не зробить.
- Після того, як кандидат відхилений, вона зникне назавжди і не може бути відкликана.
- Кількість кандидатів\(n\) відома.
Припущення, звичайно, не зовсім розумні в реальних додатках. Останнє припущення, наприклад, яке\(n\) відомо, більше підходить для тлумачення секретаря, ніж для шлюбного тлумачення.
Що таке оптимальна стратегія? Яка ймовірність успіху з цією стратегією? Що відбувається зі стратегією і ймовірність успіху у міру\(n\) збільшення? Зокрема, коли\(n\) великий, чи є розумна надія знайти найкращого кандидата?
Стратегії
Грайте в гру секретаря кілька разів з\(n = 10\) кандидатами. Подивіться, чи зможете ви знайти хорошу стратегію просто методом проб і помилок.
Після гри секретаря кілька разів, повинно бути зрозуміло, що єдиний розумний тип стратегії - це дозволити певній кількості кандидатів пройти\(k - 1\) повз, а потім вибрати першого кандидата, який ми бачимо, хто кращий за всіх попередніх кандидатів (якщо вона існує). Якщо її не буде (тобто якщо немає кандидата краще за всіх попередніх кандидатів), ми погодимося прийняти останнього кандидата, хоча це означає невдачу. Параметр\(k\) повинен бути між 1 і\(n\); якщо\(k = 1\), ми вибираємо першого кандидата; якщо\(k = n\), ми вибираємо останнього кандидата; для будь-якого іншого значення\(k\), обраний кандидат є випадковим, розподіляється на\(\{k, k + 1, \ldots, n\}\). Ми будемо називати цю \(k - 1\)відпущену
стратегію як стратегію\(k\).
Таким чином, потрібно обчислити ймовірність успіху,\(p_n(k)\) використовуючи стратегію\(k\) з\(n\) кандидатами. Тоді ми можемо максимізувати ймовірність,\(k\) щоб знайти оптимальну стратегію, а потім взяти межу,\(n\) щоб вивчити асимптотичну поведінку.
Аналіз
По-перше, давайте зробимо деякі основні обчислення.
Для\(n = 3\) випадку перерахуйте 6 перестановок\(\{1, 2, 3\}\) та перевірте ймовірності в таблиці нижче. Зверніть увагу, що\(k = 2\) є оптимальним.
| \(k\) | 1 | 2 | 3 |
|---|---|---|---|
| \(p_3(k)\) | \(\frac{2}{6}\) | \(\frac{3}{6}\) | \(\frac{2}{6}\) |
Відповідь
У наступній таблиці наведено\( 3! = 6 \) перестановки кандидатів та кандидата\( (1, 2, 3) \), обраного кожною стратегією. Останній ряд дає загальну кількість успіхів для кожної стратегії.
| Перестановка | \(k = 1\) | \(k = 2\) | \(k = 3\) |
|---|---|---|---|
| \((1, 2, 3)\) | 1 | 3 | 3 |
| \((1, 3, 2)\) | 1 | 2 | 2 |
| \((2, 1, 3)\) | 2 | 1 | 3 |
| \((2, 3, 1)\) | 2 | 1 | 1 |
| \((3, 1, 2)\) | 3 | 1 | 2 |
| \((3, 2, 1)\) | 3 | 2 | 1 |
| Всього | 2 | 3 | 2 |
В експерименті секретаря встановіть кількість кандидатів на\(n = 3\). Проведіть експеримент 1000 разів з кожною стратегією\( k \in \{1, 2, 3\} \)
Для\(n = 4\) випадку перерахуйте 24 перестановки\(\{1, 2, 3, 4\}\) та перевірте ймовірності в таблиці нижче. Зверніть увагу, що\(k = 2\) є оптимальним. Останній ряд дає загальну кількість успіхів для кожної стратегії.
| \(k\) | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| \(p_4(k)\) | \(\frac{6}{24}\) | \(\frac{11}{24}\) | \(\frac{10}{24}\) | \(\frac{6}{24}\) |
Відповідь
У наступній таблиці наведено\(4! = 24\) перестановки кандидатів та кандидата\((1, 2, 3, 4)\), обраного кожною стратегією.
| Перестановка | \(k = 1\) | \(k = 2\) | \(k = 3\) | \(k = 4\) |
|---|---|---|---|---|
| \((1, 2, 3, 4)\) | 1 | 4 | 4 | 4 |
| \((1, 2, 4, 3)\) | 1 | 3 | 3 | 3 |
| \((1, 3, 2, 4)\) | 1 | 4 | 4 | 4 |
| \((1, 3, 4, 2)\) | 1 | 3 | 2 | 2 |
| \((1, 4, 2, 3)\) | 1 | 3 | 3 | 3 |
| \((1, 4, 3, 2)\) | 1 | 2 | 2 | 2 |
| \((2, 1, 3, 4)\) | 2 | 1 | 4 | 4 |
| \((2, 1, 4, 3)\) | 2 | 1 | 3 | 3 |
| \((2, 3, 1, 4)\) | 2 | 1 | 1 | 4 |
| \((2, 3, 4, 1)\) | 2 | 1 | 1 | 1 |
| \((2, 4, 1, 3)\) | 2 | 1 | 1 | 3 |
| \((2, 4, 3, 1)\) | 2 | 1 | 1 | 1 |
| \((3, 1, 2, 4)\) | 3 | 1 | 4 | 4 |
| \((3, 1, 4, 2)\) | 3 | 1 | 2 | 2 |
| \((3, 2, 1, 4)\) | 3 | 2 | 1 | 4 |
| \((3, 2, 4, 1)\) | 3 | 2 | 1 | 1 |
| \((3, 4, 1, 2)\) | 3 | 1 | 1 | 2 |
| \((3, 4, 2, 1)\) | 3 | 2 | 2 | 1 |
| \((4, 1, 2, 3)\) | 4 | 1 | 3 | 3 |
| \((4, 1, 3, 2)\) | 4 | 1 | 2 | 2 |
| \((4, 2, 1, 3)\) | 4 | 2 | 1 | 3 |
| \((4, 2, 3, 1)\) | 4 | 2 | 1 | 1 |
| \((4, 3, 1, 2)\) | 4 | 3 | 1 | 2 |
| \((4, 3, 2, 1)\) | 4 | 3 | 2 | 1 |
| Всього | 6 | 11 | 10 | 6 |
В експерименті секретаря встановіть кількість кандидатів на\(n = 4\). Проведіть експеримент 1000 разів з кожною стратегією\( k \in \{1, 2, 3, 4\} \)
Для цього\(n = 5\) випадку перерахуйте 120 перестановок\(\{1, 2, 3, 4, 5\}\) та перевірте ймовірності в таблиці нижче. Зверніть увагу, що\(k = 3\) є оптимальним.
| \(k\) | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| \(p_5(k)\) | \(\frac{24}{120}\) | \(\frac{50}{120}\) | \(\frac{52}{120}\) | \(\frac{42}{120}\) | \(\frac{24}{120}\) |
В експерименті секретаря встановіть кількість кандидатів на\(n = 5\). Проведіть експеримент 1000 разів з кожною стратегією\( k \in \{1, 2, 3, 4, 5\} \)
Ну, очевидно, ми не хочемо продовжувати робити це. Давайте подивимося, чи зможемо ми знайти загальний аналіз. З\(n\) кандидатами давайте\(X_n\) позначимо кількість (порядок прибуття) кращого кандидата, і нехай\(S_{n,k}\) позначимо подію успіху для стратегії\(k\) (вибираємо кращого кандидата).
\(X_n\)рівномірно розподіляється по\(\{1, 2, \ldots, n\}\).
Доказ
Це випливає, оскільки кандидати прибувають у випадковому порядку.
Далі ми обчислимо умовну ймовірність успіху, враховуючи порядок прибуття найкращого кандидата.
Для\( n \in \N_+ \) і\( k \in \{2, 3, \ldots, n\} \),\[ \P(S_{n,k} \mid X_n = j) = \begin{cases} 0, & j \in \{1, 2, \ldots, k-1\} \\ \frac{k-1}{j-1}, & j \in \{k, k + 1, \ldots, n\} \end{cases} \]
Доказ
Для першого випадку зверніть увагу, що якщо номер прибуття кращого кандидата є\(j \lt k\), то стратегія\(k\) неодмінно провалиться. Для других випадків зверніть увагу, що якщо порядок прибуття найкращого кандидата є\(j \ge k\), то стратегія\(k\) буде успішною, якщо і тільки в тому випадку, якщо один з перших\(k - 1\) кандидатів (тих, які автоматично відхиляються) буде кращим серед перших\(j - 1\)
Два випадки проілюстровані нижче. Велика точка вказує на найкращого кандидата. Червоні крапки вказують на кандидатів, які відхилені з-під контролю, а сині - кандидатів, які розглядаються.
Малюнок\(\PageIndex{1}\): Випадок, коли\( X_n = j \lt k \)
Малюнок\(\PageIndex{2}\): Випадок, коли\( X_n = j \ge k \)
Тепер ми можемо обчислити ймовірність успіху за допомогою стратегії\(k\).
Для\( n \in \N_+ \)\[ p_n(k) = \P(S_{n,k}) = \begin{cases} \frac{1}{n}, & k = 1 \\ \frac{k - 1}{n} \sum_{j=k}^n \frac{1}{j - 1}, & k \in \{2, 3, \ldots, n\} \end{cases} \]
Доказ
Коли\( k = 1 \) ми просто відбираємо першого кандидата. Цей кандидат буде найкращим з ймовірністю\( 1 / n \). Результат для\( k \in \{2, 3, \ldots, n\} \) випливає з попередніх двох результатів, обумовлюючи\(X_n\):\[ \P(S_{n,k}) = \sum_{j=1}^n \P(X_n = j) \P(S_{n,k} \mid X_n = j) = \sum_{j=k}^n \frac{1}{n} \frac{k - 1}{j - 1} \]
Значення функції\(p_n\) можуть бути обчислені вручну для малих\(n\) і за допомогою комп'ютерної алгебри системи для помірних\(n\). Графік роботи\(p_{100}\) наведено нижче. Зверніть увагу на увігнуту вниз форму графіка і оптимальне значення\(k\), яке виходить 38. Оптимальна ймовірність - близько 0,37104.
Оптимальна стратегія\(k \mapsto p_n(k)\),\(k_n\) яка максимізує\(k_n / n\), співвідношення і оптимальна\(p_n(k_n)\) ймовірність пошуку найкращого кандидата, як функції\(n \in \{3, 4, \dots, 20\}\) наведені в наступній таблиці:
| Кандидати\(n\) | Оптимальна стратегія\(k_n\) | Співвідношення\(k_n / n\) | Оптимальна ймовірність\(p_n(k_n)\) |
|---|---|---|---|
| \ (n\) ">3 | \ (k_n\) ">2 | \ (k_n/n\) ">0.6667 | \ (p_n (k_n)\) ">0,5000 |
| \ (n\) ">4 | \ (k_n\) ">2 | \ (k_n/n\) ">0,5000 | \ (p_n (k_n)\) ">0.4583 |
| \ (n\) ">5 | \ (k_n\) ">3 | \ (k_n/n\) ">0.6000 | \ (p_n (k_n)\) ">0.4333 |
| \ (n\) ">6 | \ (k_n\) ">3 | \ (k_n/n\) ">0,5000 | \ (p_n (k_n)\) ">0.4278 |
| \ (n\) ">7 | \ (k_n\) ">3 | \ (k_n/n\) ">0,4286 | \ (p_n (k_n)\) ">0.4143 |
| \ (n\) ">8 | \ (k_n\) ">4 | \ (k_n/n\) ">0,5000 | \ (p_n (к_n)\) ">0.4098 |
| \ (n\) ">9 | \ (k_n\) ">4 | \ (k_n/n\) ">0.4444 | \ (p_n (k_n)\) ">0.4060 |
| \ (n\) ">10 | \ (k_n\) ">4 | \ (k_n/n\) ">0.4000 | \ (p_n (k_n)\) ">0.3987 |
| \ (n\) ">11 | \ (k_n\) ">5 | \ (k_n/n\) ">0,4545 | \ (p_n (k_n)\) ">0.3984 |
| \ (n\) ">12 | \ (k_n\) ">5 | \ (k_n/n\) ">0,4167 | \ (p_n (k_n)\) ">0.3955 |
| \ (n\) ">13 | \ (k_n\) ">6 | \ (k_n/n\) ">0.4615 | \ (p_n (k_n)\) ">0.3923 |
| \ (n\) ">14 | \ (k_n\) ">6 | \ (k_n/n\) ">0,4286 | \ (p_n (k_n)\) ">0.3917 |
| \ (n\) ">15 | \ (k_n\) ">6 | \ (k_n/n\) ">0.4000 | \ (p_n (k_n)\) ">0.3894 |
| \ (n\) ">16 | \ (k_n\) ">7 | \ (k_n/n\) ">0,4375 | \ (p_n (k_n)\) ">0.3881 |
| \ (n\) ">17 | \ (k_n\) ">7 | \ (к_n/n\) ">0.4118 | \ (p_n (k_n)\) ">0.3873 |
| \ (n\) ">18 | \ (k_n\) ">7 | \ (k_n/n\) ">0.3889 | \ (p_n (k_n)\) ">0.3854 |
| \ (n\) ">19 | \ (k_n\) ">8 | \ (k_n/n\) ">0.4211 | \ (p_n (k_n)\) ">0.3850 |
| \ (n\) ">20 | \ (k_n\) ">8 | \ (k_n/n\) ">0.4000 | \ (p_n (k_n)\) ">0.3842 |
Мабуть, як і слід було очікувати, оптимальна стратегія\(k_n\) збільшується, а оптимальна ймовірність\(p_n(k_n)\) зменшується\(n \to \infty\). З іншого боку, це обнадійливо і трохи дивно, що оптимальна ймовірність, здається, не зменшується до 0. Мабуть, найменш зрозуміло, що відбувається з співвідношенням. Графічне відображення деякої інформації в таблиці може допомогти:
Малюнок\(\PageIndex{4}\): Оптимальна ймовірність\( p_n(k_n) \)
Малюнок\(\PageIndex{5}\): Оптимальне співвідношення\( k_n / n \)
Чи може бути так, що співвідношення\(k_n / n\) і ймовірність\(p_n(k_n)\) одночасно сходяться, і тим більше, сходяться до одного числа? Для початку спробуємо жорстко встановити деякі тенденції, що спостерігаються в таблиці.
Імовірність успіху\(p_n\) задовольняє\[ p_n(k - 1) \lt p_n(k) \text{ if and only if } \sum_{j=k}^n \frac{1}{j-1} \gt 1 \]
Звідси випливає\(n \in \N_+\), що для кожного функція\(p_n\) спочатку збільшується, а потім зменшується. Максимальне значення\(p_n\) відбувається при найбільшому\(k\) с\(\sum_{j=k}^n \frac{1}{j - 1} \gt 1\). Це оптимальна стратегія з\(n\) кандидатами, яку ми позначили\(k_n\).
У міру\(n\) збільшення\(k_n\) збільшується і оптимальна ймовірність\(p_n(k_n)\) знижується.
Асимптотичний аналіз
Нас, природно, цікавить асимптотична поведінка функції\(p_n\), і оптимальна стратегія як\(n \to \infty\). Ключем є\(p_n\) визнання суми Рімана для простого інтеграла. (Суми Рімана, звичайно, названі на честь Георга Рімана.)
Якщо\(k(n)\) залежить від\(n\) і\(k(n) / n \to x \in (0, 1)\) як\(n \to \infty\) тоді\(p_n[k(n)] \to -x \ln x\) як\(n \to \infty\).
Доказ
Спочатку зауважте, що\[ p_n(k) = \frac{k-1}{n} \sum_{j=k}^n \frac{1}{n} \frac{n}{j-1} \] Ми визнаємо суму вище як ліву суму Рімана для функції, що\(f(t) = \frac{1}{t}\) відповідає поділу інтервалу\(\left[\frac{k-1}{n}, 1\right]\) на\((n - k) + 1\) підінтервали довжини\(\frac{1}{n}\) кожен:\(\left(\frac{k-1}{n}, \frac{k}{n}, \ldots, \frac{n-1}{n}, 1\right)\). Звідси випливає, що\[ p_n[k(n)] \to x \int_x^1 \frac{1}{t} dt = -x \ln x \text{ as } n \to \infty\]
Оптимальна стратегія\(k \mapsto p_n(k)\),\(k_n\) яка максимізує\(k_n / n\), співвідношення і оптимальна\(p_n(k_n)\) ймовірність пошуку найкращого кандидата, як функції\(n \in \{10, 20, \dots, 100\}\) наведені в наступній таблиці:
| Кандидати\(n\) | Оптимальна стратегія\(k_n\) | Співвідношення\(k_n / n\) | Оптимальна ймовірність\(p_n(k_n)\) |
|---|---|---|---|
| \ (n\) ">10 | \ (k_n\) ">4 | \ (k_n/n\) ">0.4000 | \ (p_n (k_n)\) ">0.3987 |
| \ (n\) ">20 | \ (k_n\) ">8 | \ (k_n/n\) ">0.4000 | \ (p_n (k_n)\) ">0.3842 |
| \ (n\) ">30 | \ (k_n\) ">12 | \ (k_n/n\) ">0.4000 | \ (p_n (k_n)\) ">0.3786 |
| \ (n\) ">40 | \ (k_n\) ">16 | \ (k_n/n\) ">0.4000 | \ (p_n (k_n)\) ">0.3757 |
| \ (n\) ">50 | \ (k_n\) ">19 | \ (k_n/n\) ">0,3800 | \ (p_n (k_n)\) ">0.3743 |
| \ (n\) ">60 | \ (k_n\) ">23 | \ (k_n/n\) ">0.3833 | \ (p_n (k_n)\) ">0.3732 |
| \ (n\) ">70 | \ (k_n\) ">27 | \ (k_n/n\) ">0,3857 | \ (p_n (k_n)\) ">0.3724 |
| \ (n\) ">80 | \ (k_n\) ">30 | \ (k_n/n\) ">0,3750 | \ (p_n (k_n)\) ">0.3719 |
| \ (n\) ">90 | \ (k_n\) ">34 | \ (k_n/n\) ">0.3778 | \ (p_n (k_n)\) ">0.3714 |
| \ (n\) ">100 | \ (k_n\) ">38 | \ (k_n/n\) ">0,3800 | \ (p_n (k_n)\) ">0.3710 |
На графіку нижче показані істинні ймовірності\(p_n(k)\) та граничні значення\(-\frac{k}{n} \, \ln\left(\frac{k}{n}\right)\) як функція\(k\) з\(n = 100\).
Для оптимальної стратегії існує\(x_0 \in (0, 1)\) така\(k_n\), що\(k_n / n \to x_0\) як\(n \to \infty\). Таким чином,\(x_0 \in (0, 1)\) є гранична частка кандидатів, яких ми відхиляємо з рук. Більш того,\(x_0\) максимізує\(x \mapsto -x \ln x\) на\((0, 1)\).
Максимальне значення\(-x \ln x\) відбувається при\(x_0 = 1 / e\) і максимальне значення також\(1 / e\).
Доказ
Таким чином, магічне число\(1 / e \approx 0.3679\) зустрічається двічі в задачі. Для великих\(n\):
- Наша приблизна оптимальна стратегія - відхилити з рук перші 37% кандидатів, а потім вибрати першого кандидата (якщо вона з'явиться), який кращий за всіх попередніх кандидатів.
- Наша ймовірність знайти найкращого кандидата близько 0.37.
Стаття Хто вирішив проблему секретаря?
Том Фергюсон (1989) має цікаве історичне обговорення проблеми, включаючи припущення про те, що Йоганнес Кеплер, можливо, використовував оптимальну стратегію для вибору своєї другої дружини. У статті також розглянуто багато цікавих узагальнень проблеми. Інша версія проблеми секретаря, в якій кандидатам присвоюється бал\([0, 1]\), а не відносний ранг, обговорюється в розділі «Час зупинки» у розділі про Мартінгалес