Задача о разборчивой невесте:

Десять женихов сватаются к принцессе. Она знакомится с ними по одному, и ей сразу нужно решить — выйти замуж или прогнать жениха навсегда. Если принцесса не выберет лучшего, то с горя уйдёт в монастырь

Как принцессе действовать, если она знает только число женихов?

Эта статья написана по мотивам лекции, которая я недавно прочел на Летней Школе. Слайды можно найти в моём телеграм канале Кроссворд Тьюринга Подписывайтесь!) 

От игр к терверу

Задачу о невесте удобно переформулировать как игру между Аней и Борисом

Задача о карточках: В начале игры Аня выписывает на 10 карточках по числу. Они могут быть любыми, но не должны повторяться. Аня тасует карточки и вскрывает их по одной. Цель Бориса — остановить игру на наибольшем из чисел. Он знает только, что карточек десять

Гарантировать Борису победу невозможно. Если известно, как он будет играть, Аня всегда может разложить карточки так, чтобы он проиграл. Поэтому мы ищем стратегию, которая приводит к победе чаще других — то есть выигрывает при наибольшем числе возможных раздач

Например, можно выбрать первую карточку — или последнюю, или случайную. Вероятность успеха у таких стратегий всего 10%. Но есть стратегия, которая приводит к победе с вероятностью больше 1/3 — независимо от числа карточек. Это знаменитое правило :

Правилопропустить примерно карточек и взять первое число, которое больше всех предыдущих

Эта стратегия оптимальна (для достаточно большого количества карточек) — ее вероятность успеха больше, чем у любой другой. То, что она работает для любого количества женихов — красивый пример предельный теоремы в теории вероятностей

Число 37% возникает не случайно: это 1/e. Мы докажем это правило и заодно поймем, что такое число e на самом деле

Зачем это нужно?

Во многих жизненных ситуациях приходится делать выбор, не зная всех вариантов:

• предложить или принять оффер;

• найти самую дешёвую заправку (интересный ресторан, обменник с лучшим курсом) на вашем маршруте;

• снять подходящую квартиру, пока её не перехватили;

• или даже — выбрать партнёра

Задачу о разборчивой принцессе популяризовал Мартин Гарднер

Одно из первых решений принадлежит совесткому математику Евгению Дынкину, но говорят что еще Кеплер использовал правило 37% для того, чтобы выбрать вторую жену

Обобщение задачи — тема докторской диссертации Бориса Березовского

Чтобы применить задачу к таким ситуациям, нужно чуть-чуть обобщить нашу игру. Например:

• можно рассматривать любое фиксированное число карточек — хоть тысячу;

• можно предположить, что у каждой карточки есть срок годности, когда к ней ещё можно вернуться;

• или считать, что число карточек неизвестно, но игра идёт фиксированное время, и известно распределение карточек по времени.

Все эти обобщения можно получить тем же путем, который мы сегодня пройдем. Пусть стратегии уже не будут такими наглядными, как правило , — но их можно вывести, и они остаются оптимальными

В финале статьи вас ждет пример такого вопроса, над которым можно подумать самостоятельно

Новый взгляд на классику

Возможно, вы уже слышали о правиле . О нем часто рассказывают, но мне хочется не просто дать готовый алгоритм, а показать, откуда он берётся и почему оптимален

Часто алгоритмы — это эвристики, и доказательств оптимальности либо нет, либо они слишком сложны. Повезло, что в задаче о невесте это не так! Мы вместе поймём, какими свойствами должен обладать оптимальный алгоритм, и сами изобретём правило — шаг за шагом

Такой путь подробно изложен в брошюре «Разборчивая невеста» Сабира Меджидовича Гусейна-Заде. Но пройти его не так просто: формулировки тонкие, шаги технические, и понятно пересказать всё это в короткой статье почти невозможно

Пару недель назад я узнал про Теорему о Шансах, которая охватывает гораздо более широкий класс игр — и доказывается гораздо проще! Она опубликована в 2000 году, но на русском языке о ней вообще ничего не написано

Вот почему мне захотелось рассказать эту историю. Обобщение оказывается не только мощнее, но и понятнее. На самом деле, в математике такое часто случается, но редко получается продемонстрировать это на относительно элементарном сюжете

В этой статье мы разберём Теорему о Шансах и выведем из неё правило . Подробнее об устройстве теоремы и её роли — в следующем разделе

Для начала я хочу рассказать общий план, следуя которому мы прийдем к правилу . Вместо того чтобы разбирать задачу о невесте, мы рассмотрим более общие игры. Чтобы придумать это обобщение, понадобится понятие лидеров раздачи

Лидеры раздачи

Аня выкладывает перед Борисом десять карточек с числами. Например, таких:

Борис должен остановиться на карточке с самым большим числом. Делать это на — бессмысленно: уже были числа больше него, так что оно точно нам не подходит

Назовем лидерами раздачи карточки с числами, большими всех предыдущих

В этом примере лидеры

Первая карточка — всегда лидер. Лидеров обычно несколько (в среднем около трех)

Простое, но важное замечание: Борису нужно найти последнего лидера — это и есть карточка с самым большим числом

Задача о лампочках

Задача о невесте оказывается частным случаем другой, более общей игры

Задача о лампочках: Лампочка вспыхивает раз — красным или зелёным.
Цель Бориса — остановиться на последнем зелёном сигнале. Ему известны вероятности зелёного и красного сигнала. Они могут зависеть от номера вспышки

Удивительно, но найти оптимальную стратегию в этой, очень абстрактной ситуации — проще, чем в задаче о невесте. Теорема о Шансах — именно об этом

Чтобы было легче следить за рассуждениями, будем держать в голове конкретный пример

Угадай последнюю шестерку: Аня бросает кубик раз и по одному называет Борису результаты. Цель Бориса — остановить Аню на последней шестёрке

Это частный случай задачи о лампочках: она загорается зелёным на шестёрке, красным — на остальных числах. Тут вероятности не зависят от номера хода. Все наши рассуждения будут относиться к общей задаче, но на примере с кубиком легче понять, что происходит

Момент остановки

Будем говорить, что  — оптимальный момент остановки, если лучшая стратегия это

: Борис пропускает ходы вне зависимости от сигналов, а когда остается t ходов до конца говорит «стоп» на первом зеленом сигнале

Упражнение: в игре «угадай вторую шестёрку» нет такого момента!

Теорема о Шансах — о том, что оптимальный момент остановки всегда существует в задаче о лампочках, и о том, как его найти

Сегодня мы:

• докажем, что в задаче о лампочках существует оптимальный момент остановки

• найдём формулу, по которой его можно вычислить (это и есть Теорема о Шансах)

• применим её к задаче о невесте — и увидим, откуда берётся правило

Определение оптимального момента остановки выглядит странно. Почему вообще нужно искать такие стратегии? В следующем разделе мы придем к этому понятию постепенно

Мы начинаем анализировать задачу о лампочках с нуля. Пока у нас нет ни формул, ни списка стратегий — мы ничего не знаем про то, как именно должен действовать Борис

Но мы точно знаем, что какая-то оптимальная стратегия существует. Сейчас мы ее проанализируем и увидим, что у неё есть момент остановки

Пусть Борис действует оптимально. Как он принимает решение после зеленой вспышки? Предположим, что осталось ходов до конца игры. Рассмотрим две вероятности:

• : за оставшиеся ходов зеленых вспышек больше не будет

• : Борис выиграет, если продолжит игру и будет действовать оптимально

Тогда, если — выгоднее сказать «стоп», если — продолжать игру

Решение Бориса зависит только от того, какой сейчас по счёту ход, а не от того, что происходило раньше. Это логично — прошлое не влияет на последний зеленый сигнал

Оптимальная стратегия устроена просто: у Бориса есть список номеров, и если лампочка моргнула зеленым на одном из них — он останавливается, а в остальных случаях — продолжает игру. Сейчас мы поймем, как этот список может выглядеть

Как меняются Sₙ  и Cₙ ?

убывает: чем больше времени — тем меньше шанс, что все сигналы будут красными
не убывает: больше времени — больше доступных стратегий, выше шанс выиграть

Получается, чем меньше ходов осталось Борису, тем больше оснований остановить игру

Формальное объяснение

Пусть — вероятность зелёного сигнала, — красного. Вероятность может быть любой — и даже зависеть от номера вспышки

Все сигналов будут красными с вероятностью

Вероятность, что Борис выиграет за ход, действуя оптимально, это:

• если первый сигнал зелёный — наибольшее из чисел и

• если первый сигнал красный — число

Итого:

Значит, убывает, а не убывает

Посмотрим на графики и

Можно найти точку , до которой , а в точке  и после наоборот — (если всегда, положим )

Мы убедимся, что – момент остановки

Что делать Борису?

Пусть до конца игры осталось ходов и Борису надо решить, как играть

• если , то — пропускаем ход независимо от сигнала

• как только , то — говорим «стоп» на первом зеленом сигнале

Значит, — оптимальный момент остановки игры. Пока мы не знаем, чему равно , но знаем, что самая лучшая стратегия есть среди списка

Мы свели бесконечное множество возможных стратегий к десяти кандидатам
Осталось понять, какая из них даёт наибольшую вероятность выигрыша

Упражнение: Найдите оптимальную стратегию в игре «угадай последнюю шестерку». Для этого посчитайте вероятности победы каждой из стратегий (математически или смоделировав их на компьютере) и сравните их

Есть формула, которая точно указывает оптимальный момент остановки в задаче о лампочках — это и есть содержание Теоремы о шансах. К ней мы и перейдём

Наша цель — найти лучшую стратегию среди . Напомним, что устроена так — Борис пропускает ходы, а когда остается берёт первую зелёный сигнал. Её вероятность победы обозначим за

Сначала разберём случай с постоянными вероятностями — там всё совсем просто. Потом перейдём к общему случаю: формулы станут чуть длиннее, но логика не изменится.

Разминка

Для начала мы найдем момент остановки в задаче о лампочках в предположении, что вероятности зеленого и красного сигнала и не зависят от номера хода

Стратегия приводит к победе в двух случаях:

• единственный зеленый сигнал первый — с вероятностью

• сигнал красный, но в итоге Борис победил — с вероятностью

Итого . Сравнивая с , получаем:

Если Борис использует , он побеждает, когда из последних сигналов зеленый ровно один. Таких ситуаций , вероятность каждой . Значит, вероятность победы равна . Подставим эту формулу и получим критерий:

В игре «угадай последнюю шестерку» такие вероятности:

, ,

Значит растут до , а потом убывают. Соответственно, оптимальный момент остановки

Это рассуждение работает для любого количества сигналов — а не только для

Главная теорема

Пусть теперь вероятности зависят от номера хода: на -м ходу с конца вероятность зелёного сигнала равна , красного — . Обозначим — шансы на зелёный сигнал. Если проделать все тоже самое, получится критерий

Если вероятности не зависят от , то , и этот критерий дает

Доказательство критерия

Обозначим . Стратегия приводит к победе, если среди последних вспышек ровно одна зелёная. Вероятность этого:

Точно также, как в разминке, получаем неравенство:

Подставляя выражение для , получаем:

Упражнение: Сколько оптимальных стратегий может быть в задаче о лампочках?

Будем складывать шансы по порядку: . Пусть — первый момент, когда эта сумма превысит 1 (если она всегда, положим ). Тогда

Теорема о Шансах (Bruss, 2000) Стратегия оптимальна, а вероятность ее победы равна

Осталось применить Теорему о Шансах к задаче о разборчивой невесте

В задаче о невесте зелёная лампочка загорается тогда, когда текущая карточка — лидер раздачи, то есть число на ней больше всех предыдущих

Рассмотрим ход , считая с конца. Его номер с начала . Вероятность того, что именно здесь окажется наибольшее число среди первых карточек, равна:

Таким образом, шансы равны

Складываем шансы с конца, пока сумма не превысит . Это происходит на шаге

Значит, оптимальный момент остановки равен , оптимальная стратегия — пропустить карточки и взять первого лидера. Вероятность успеха примерно

Теперь перейдём к общему случаю, где карточек может быть сколько угодно. Нам нужно научиться приближённо считать сумму шансов. Тут нам поможет геометрический взгляд

Сумма шансов и площадь

Чтобы посчитать сумму шансов, посмотрим на неё как на сумму площадей прямоугольников

Рассмотрим прямоугольники с шириной , высотой и площадью

Получается, сумма шансов примерно равна площади под гиперболой от до

Аналогично, любая сумма вида приближённо равна площади под гиперболой от до

Теперь на сцену выходит число . По определению, это такое число, что площадь под гиперболой от до равна . Значит,

Правило

Пусть женихов не , а, скажем,

Мы ищем , для которого Это происходит, когда

Число , так что . Значит, оптимальная стратегия:

Пропустить ≈ 370 женихов и выбрать первого, кто лучше всех предыдущих

Вероятность победы

Этот результат справедлив для любого (достаточно большого) числа женихов — это и есть правило 37 %. Получается, и алгоритм и ответ не зависят от числа женихов

Ура! Мы прошли весь путь и переоткрыли правило Мы поняли, что в задаче о невесте обязательно существует оптимальный момент остановки. Научились его находить с помощью Теоремы о Шансах. А заодно — поговорили о площади под гиперболой и числе 

Спасибо, что дошли до конца! Я надеюсь, этот путь оказался увлекательным) Подписывайтесь на мой тг-канал Кроссворд Тьюринга, оставляйте комментарии и делитесь статьей. Это мотивирует писать новые тексты — и очень радует

Материалы и ссылки

Кроме слайдов моей лекции, могу посоветовать следующие источники

• «Теорема шансов и разборчивая невеста», Кириченко В. А. YouTube

• «Разборчивая невеста», Гусейн‑Заде С. М. (МЦНМО, 2003)

• «Sum the Odds to One and Stop», Bruss F. T. (Ann. Probab. 2000)

• «Логарифм и экспонента», Шень А.Х. (МЦНМО, 2013)

P.S. Задача

Борис ищет квартиру в новом городе. Он договорился о 12 показах: 3 в понедельник, 2 во вторник, 3 в среду, 1 в четверг и 3 в пятницу

Каждый вечер он решает: выбрать одну из просмотренных сегодня квартир или отказаться — тогда он больше к ним вернуться не сможет. Борис хочет снять лучшую из 12 квартир

Придумайте оптимальный алгоритм и найдите его вероятность победы