![](https://habrastorage.org/webt/ep/b1/eh/epb1eh9aechq_ujbzpudaqvl7as.jpeg)
Настало время занимательных задач. Представьте, что вы снимаете квартиру в огромном городе. Как свести к минимуму риски при столь значимом выборе, когда вы ничего не знаете о вариантах заранее? На этот вопрос отвечает теория вероятности и задача о проблеме секретаря. Графики, рассуждения, немного кода на Julia — все подробности под катом.
Как теория вероятностей отвечает на вопрос «согласиться или отказать»?
Проблема секретаря или задача о разборчивой невесте в русскоязычной литературе — это известная загадка на тему принятия решений. Речь идет о том, чтобы найти наилучшую стратегию выбора из последовательности, когда вы не знаете, какой вариант лучше. Формулировка задачи звучит так:
Вы менеджер по персоналу и должны нанять лучшего секретаря изкандидатов. Вы можете собеседовать их одного за другим в случайном порядке. Однако решение о назначении или отказе в назначении на должность должно приниматься сразу после собеседования. Если никто не был принят, выбирается последний кандидат. Какую стратегию вы выберете, чтобы максимально увеличить шансы нанять лучшего кандидата?
На первый взгляд, эта задача кажется неразрешимой или даже кажется обманом. На самом деле у нее есть элегантное математическое решение. Вытекающая из задачи практическая мудрость обычно теряется на страницах книг по теории вероятностей. Я думаю, что это очень печально, потому что есть много ситуаций, в которых знание оптимальной стратегии выбора среди неизвестных альтернатив может пригодиться. Например:
- Решение снять квартиру в переполненном городе.
- Быстрый поиск старшей карты при перетасовывании колоды.
- Поиск магазина с невысокими ценами без проходов туда и обратно.
- Обязательства перед долгосрочным партнером.
Во всех этих случаях вы не знаете, какие варианты будут следующими. Тем не менее, вы, возможно, захотите принять решение быстро, но также и правильно. Цель этого поста — раскрыть решение проблемы секретаря понятными словами и при необходимости проиллюстрировать решение.
Прежде чем приступать к делу, нужно принять важное решение. Решите для себя, хотите ли вы снова прочитать загадку и подумать о решении самостоятельно. Я настоятельно рекомендую это сделать, потому что это упражнение для ума. Независимо от того, осознаете вы лучшую стратегию или нет. Если вы нетерпеливы, просто прочитайте вывод.
Случайность? Спасибо, не надо
Проблема секретаря сложна. Невозможно прямо в момент собеседования понять, собеседуете ли вы лучшего кандидата. Вы можете только сравнивать с теми кандидатами, которых уже опросили. Но даже если нынешний кандидат оказался блестящим, самый лучший всегда может прийти сразу после него.
Перед лицом этой полной неопределенности заманчиво довериться удаче. Можно принять произвольное решение: «как бы то ни было, я выбираю первый вариант». Неудивительно, что эта случайная стратегия работает плохо. У вас есть только вероятность
Случайная стратегия становится все менее пригодной по мере увеличения числа претендентов. Если бы у вас было всего
Подождать. Подобрать критерии. Опять подождать
В этот момент вы, возможно, поняли, что единственная контролируемая вами переменная — это число людей, которым вы отказали.
Ваша стратегия может состоять только в том, чтобы решить, скольким людям вы хотите отказать, прежде чем начать решать по-настоящему. Сущность подхода — вы хотите подождать достаточно долго, чтобы получить хорошую точку отсчета, а затем выбрать следующего кандидата, подходящего лучше людей, которых вы собеседовали. В количественном выражении эта стратегия формулируется так:
- Собеседуем R людей и отказываемся нанимать их. Запоминаем лучшего кандидата. Назовем его
.
- Продолжаем опрашивать следующих кандидатов, пока не найдется первый с оценкой выше
. То есть,
. Выбираем этого кандидата.
Эта стратегия звучит многообещающе, но нужно уточнить деталь: установить, какому количеству людей вы должны отказать.
Когда число
Однако прежде чем заняться математикой, всегда разумно перепроверить, имеет ли смысл общая идея. Рассмотренную стратегию удобно тестировать в случае
На приведенном ниже рисунке показаны все 6 возможных комбинаций прибытия трех кандидатов вместе с соответствующими результатами стратегии «вызвать первого кандидата, а затем выбрать следующего лучшего (в противном случае последнего)».
![](https://habrastorage.org/webt/ta/wo/8k/tawo8kamikluearg67myiidqxie.png)
Тестирование оптимальной стратегии остановки с тремя кандидатами.
Стратегия способна выявить лучшего в трех сценариях из шести. То есть мы имеем вероятность успеха
Оптимизация стратегии
Во-первых, нам нужно вычислить вероятность успеха
![](https://habrastorage.org/webt/66/ho/-h/66ho-hl9n25x3kuxop-vvtcuq74.png)
Рассуждение 1: раскладываем вероятность успеха на взаимоисключающие события, где выбирается кандидат n, который также является лучшим.
Напомним, что принятый кандидат — это первый кандидат, набравший наибольшее количество баллов из
Первый способ: рассуждение о втором лучшем кандидате
Выбранный кандидат
![](https://habrastorage.org/webt/az/bu/hb/azbuhb-yfgxdemgmuzwujtrnlvg.png)
Визуализация рассуждений о позиции второго по значимости кандидата.
На язык математики это переводится так:
![](https://habrastorage.org/webt/y9/c4/cg/y9c4cgy5g6tj7fcbmk-b9njqj7e.png)
Рассуждение 2(а): вычисляем вероятность успеха, установив, что второй лучший кандидат был отброшен среди первых
Последнее рассуждение просто выводит из суммы независимые от
Второй способ: рассуждение о количестве зарегистрированных записей
Альтернативный способ потребовать, чтобы был выбран кандидат
Монета решит, будет ли этот кандидат регистрировать запись о новом рекордном балле. Из-за случайного упорядочения запись происходит с вероятностью
![](https://habrastorage.org/webt/nk/wy/fh/nkwyfhtn9mc_7sal8eqduhis6is.png)
Визуализация рассуждений о наивысших баллах. Математический эквивалент этой идеи:
![](https://habrastorage.org/webt/3l/r8/bj/3lr8bj6wwcxyjqtfpkeodzeemzo.png)
Рассуждение 2(b): вычисляем вероятность успеха, установив, что новый высший балл будет иметь место только один раз до последнего кандидата.
Последняя строка — это просто некоторая алгебраическая манипуляция. Мы проверили, что формула такая же, как и полученная предыдущим способом. В математике это прекрасный момент, когда два разных подхода приводят к одному и тому же результату: часто это весомый признак того, что вы не ошибаетесь.
Оптимальное количество отказов
Теперь, когда у нас есть пуленепробиваемая формула для
Ns = collect(1:50) # number of candidates
P(R,N) = R/N*sum([1/(n-1) for n=R+1:N]) # define function P(R)
Ropt = zeros(Int64,length(Ns)) # define vector for R*
Popt = zeros(length(Ns)) # define vector for P(R*)
for N in Ns # optimization loop
Popt[N], Ropt[N] = findmax([P(R,N) for R=1:N])
end
Ниже вы можете увидеть график оптимального
![](https://habrastorage.org/webt/uv/0l/rn/uv0lrnozpyedtxtvxw-undrnfrc.png)
Вверху оптимальное значение отказов, как функция от общего числа кандидатов. Зеленым обозначена вероятность успеха выбора лучшего кандидата, следуя оптимальной стратегии отказов. Красным цветом обозначена низкая вероятность успеха при принятии решения с помощью случайности.
Можно отметить две интересные тенденции. Во-первых, вероятность успеха при оптимальной стратегии не стремится к нулю при больших
Во-вторых, оптимальное значение
Да, это закон
.
Закон
Точно так же мы наблюдаем, что оптимальное число отказов
Кажущееся магическим значение
Заключение
Итак, вы хотите выбрать лучший из нескольких вариантов по принципу «бери или уходи», но ничего не знаете о вариантах? Тогда:
- Отклоните первые приблизительно
вариантов.
- Выберите вариант лучше тех, что вы увидели.
Получить востребованную профессию с нуля или Level Up по навыкам и зарплате, можно пройдя онлайн-курсы SkillFactory:
- Обучение профессии Data Science с нуля
- Онлайн-буткемп по Data Science
- Профессия аналитика с любым стартовым уровнем
- Онлайн-буткемп по Data Analytics
- Курс по аналитике данных
- Курс «Python для веб-разработки»
Eще курсы
- Профессия C++ разработчик
- Профессия Java-разработчик с нуля
- Курс по JavaScript
- Профессия Веб-разработчик
- Курс по Machine Learning
- Курс «Математика и Machine Learning для Data Science»
- Продвинутый курс «Machine Learning Pro + Deep Learning»
- Курс по DevOps
- Профессия iOS-разработчик с нуля
- Профессия Android-разработчик с нуля
- Профессия UX-дизайнер с нуля
- Профессия Web-дизайнер