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

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

Формулировка

Жила была принцесса, которая ни за кого не хотела замуж, даже видеться не хотела ни с одним мужчиной. Возраст у неё был уже вполне себе. Терпение у её отца-короля кончилось, и он поставил условие: завтра к принцессе из множества других королевств приедут 100 принцев, они будут заходить к невесте по одному, знакомиться, предлагая свою руку и сердце. Принцесса может либо принять предложение - тогда остальные принцы разъезжаются, либо отказать - тогда этот принц сразу же уезжает и заходит следующий. По условию принцесса не может отказать всем: если заходит последний 100-й, то она обязана принять его предложение независимо от того, какой он. Порядок, в котором заходят принцы, никак не связан с их личностными качествами. Вопрос состоит в том, какой стратегии должна придерживаться принцесса, чтобы выбрать себе лучшего принца.

Думаю, не нужно объяснять, почему эта задача настолько популярная. Подобная проблема выбора встречается во многих сферах жизни, будь то выбор супруга или сотрудника на вакансию. И каждый из нас решает её так, как считает нужным.

Теперь поговорим о деталях. Разумеется, интересно обощить задачу для произвольного числа принцев. А также я умышленно размыто сформулировал критерий выбора "выбрать лучшего принца". Дело в том, что строгий формальный критерий может быть разным. В классической формулировке он выглядит как наибольная вероятность того, что выбранный принц является лучшим среди всех приехавших.

1) максимизировать вероятность выбора лучшего принца

Также мне кажется интересным (и даже интереснее) критерий, в котором мы ищем не обязательно самого лучшего принца, а стараемся выбрать одного из лучших. Предположим, что принцы могут быть отсортированы, образовав рейтинг: самый лучший на первом месте (имеет цифру 1), следующий по лучшести на втором (имеет цифру 2) и т.д. В этой формулировке мы стараемся сделать как можно выше место в рейтинге, которое займёт выбранный принц.

2) минимизировать математическое ожидание места в рейтинге у выбранного принца

Из здравого смысла очевидно, что первый критерий не даст очень большую вероятность даже в случае оптимальной стратерии. Действительно, выбрав какого-то принца, придётся проигнорировать всех последующих, среди которых очень вероятно может оказаться принц лучше. Кроме того, на первых порах есть большой шанс пропустить и не выбрать лучшего, решив перебирать последующих. Из-за пропуска лучшего и надежды встретить ещё лучше придётся согласиться на последнего. Таким образом достаётся либо лучший, либо какой-то случайный, например, 54-й. В реальной же жизни если пропущен лучший, то может устроить и второй, и третий, но не 54-й. Поэтому вторая формулировка кажется более реалистичной. Ниже я предлагаю рассмотреть решения для обеих.

Критерий первый: максимизировать вероятность лучшего принца

Очевидно, что принцессе не имеет смысла выбирать принца, который хуже хотя ты одного из уже просмотренных, так как это заведомо проигрышно. Следовательно, ей необходимо остановить свой выбор только на том, кто лучше всех предыдущих. Но также к моменту выбора она уже должна просмотреть достаточно много вариантов. Действительно, если она смотрит второго, он лучше первого (лучше всех предыдущих), то не следует его выбирать, ведь из следующих 98-ми очень вероятно найдётся хоть кто-то лучше этих двух. А вот если она смотрит 99-го, он лучше всех остальных, то выбор разумнее всё-таки сделать, так как невелики шансы, что последний оставшийся будет лучше этого 99-го.

Из вышесказанного следует, что есть какое-то разделяющее число, начиная с которого нужно принимать предложение принца, если он лучше всех просмотренных, а до этого числа все принцы должны быть отвергнуты. Это разделяющее число можно найти из соображений максимизации вероятности выбрать по-настоящему лучшего принца (лучшего из всех ста приехавших).

Пусть p - число принцев, которым должен быть дан отказ в любом случае (то самое разделяющее число). И пусть мы сейчас рассматриваем k-го принца. Вероятность того, что k-й принц лучше всех предыдущих:

$$ \frac{1}{k} $$

А вероятность того, что все предыдущие принцы, начиная с (p+1)-го, которые потенциально могли быть выбранными, никогда не оказывались лучше всех предыдущих для них:

$$ \left(1 - \frac{1}{p+1}\right) \left(1 - \frac{1}{p+2}\right) ... \left(1 - \frac{1}{k-1}\right) $$

Таким образом получаем, что вероятность выбрать k-го принца равна:

$$ P_{1}(k) = \left(1 - \frac{1}{p+1}\right) \left(1 - \frac{1}{p+2}\right) ... \left(1 - \frac{1}{k-1}\right) \frac{1}{k} = \frac{p}{p+1} \frac{p+1}{p+2} ... \frac{k-2}{k-1} \frac{1}{k} = \frac{p}{k(k-1)} $$

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

$$ P_{2}(k) = \left(1 - \frac{1}{k+1}\right) \left(1 - \frac{1}{k+2}\right) ... \left(1 - \frac{1}{n}\right) = \frac{k}{k+1} \frac{k+1}{k+2} ... \frac{n-1}{n} = \frac{k}{n} $$

Следовательно, вероятность того, что лучший принц выберется на k-м кандидате равна:

$$ P(k) = P_{1}(k) P_{2}(k) = \frac{p}{n(k-1)} $$

Вероятность того, что вообще выберется лучший принц есть сумма вероятностей для всех возможных k от (p+1) до n:

$$ P_{best} = \sum_{k=p+1}^{n} P(k) = \frac{p}{n} \left(\frac{1}{p} + \frac{1}{p+1} + ... + \frac{1}{n-1}\right) $$

Максимизируя эту вероятность по p, можно найти искомое p, для которого данная стратегия оптимальна. Условие оптимальности выглядит следующим образом:

$$ \begin{cases} P_{best}(p) \ge P_{best}(p + 1) \ P_{best}(p) > P_{best}(p - 1) \end{cases} $$

Для первого:

$$ P_{best}(p) \ge P_{best}(p + 1) $$ $$ \frac{p}{n} \left(\frac{1}{p} + \frac{1}{p+1} + ... + \frac{1}{n-1}\right) \ge \frac{p + 1}{n} \left(\frac{1}{p+1} + ... + \frac{1}{n-1}\right) $$ $$ \frac{1}{n} + \frac{p}{n} \left(\frac{1}{p+1} + ... + \frac{1}{n-1}\right) \ge \frac{p}{n} \left(\frac{1}{p+1} + ... + \frac{1}{n-1}\right) + \frac{1}{n} \left(\frac{1}{p+1} + ... + \frac{1}{n-1}\right) $$ $$ 1 \ge \frac{1}{p+1} + ... + \frac{1}{n-1} $$

Аналогично для второго можно получить:

$$ 1 < \frac{1}{p} + \frac{1}{p+1} + ... + \frac{1}{n-1} $$

Переписываем в следующем виде:

$$ \begin{cases} \frac{1}{n-1} + \frac{1}{n-2} + ... + \frac{1}{p+1} \le 1 \ \frac{1}{n-1} + \frac{1}{n-2} + ... + \frac{1}{p+1} + \frac{1}{p} > 1 \end{cases} $$

Другими словами, чтобы найти оптимальное p, нужно накапливать сумму $ \frac{1}{n-1} + \frac{1}{n-2} + ... $ до тех пор, пока она не первысит 1. То значение знаменателя, на котором происходит это превышение, и есть искомое p.

Интересно рассмотреть случай очень больших значений n (как в нашей исходной формулировке n=100). Уместно будет вспомнить следующее приближение:

$$ 1 + \frac{1}{2} + \frac{1}{3} + ... + \frac{1}{m} \approx ln(m) $$, при m >> 1

Тогда:

$$ \frac{1}{n-1} + \frac{1}{n-2} + ... + \frac{1}{p+1} \approx ln(n) - ln(p) = ln\left(\frac{n}{p}\right) $$, при n >> 1, p >> 1

Следовательно, наши неравенства эквивалентны равенству:

$$ ln\left(\frac{n}{p}\right) = 1 $$ $$ p = \frac{n}{e} $$

А значение для вероятности найти лучшего:

$$ P_{best}(p) = \frac{p}{n} \left(\frac{1}{p} + \frac{1}{p+1} + ... + \frac{1}{n-1}\right) \approx \frac{1}{e} $$

То есть при больших n необходимо отказать доле $ \frac{1}{e} $ всех принцев, а, рассматривая остальных, согласиться на того, кто оказался лучше всех предыдущих. Для n = 100 доля $ \frac{1}{e} $ поставляет 37 принцев, предложения которых должны быть отклонены. И такая стратегия гарантирует успех (выбор по-настоящему лучше принца) с вероятностью $ \frac{1}{e} $.

Критерий второй: минимизировать математическое ожидание места в рейтинге у выбранного принца

Мат. часть

Теперь рассмотрим критерий, стратегия к которому стремится выбрать одного из лучших. Принцы могут быть проранжированы в порядке от 1 до n. По итогам выбора принцессе достаётся принц с каким-то местом r в этом рейтинге. Чем ниже значение r, тем лучше. Ниже мы будем рассматривать стратегию, которая, очевидно, будет давать в результате разные значения r при разном порядке принцев. Следовательно, имеет смысл говорить о математическом ожидании (среднем значении) итогового r, которое и разумно минимизировать.

Попробуем теперь лучше формализировать нашу задачу. Допустим, у нас всего n принцев, мы сейчас смотрим k-го, которого мы соотнесли с местом r в рейтинге (пока что среди k просмотренных принцев). И нам необходимо решить, стоит ли останавливать на нём выбор или нет. Если мы останавлиемся, то реальное место в рейтинге у этого прица будет r или больше, так как среди ещё не просмотренных могут найтись лучше. Следующие могут как бы "вытеснить" выбранного с места r на какое-то другое. Иначе говоря, в случае выбора у нас есть какое-то финальное математическое ожидание выбранного принца. Обозначим его:

$$ r_{chosen} $$

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

$$ r_{non-chosen} $$

Так как мы минимизируем место в рейтинге в нашей стратегии, то условие остановки должно выглядеть так:

$$ r_{chosen} \le r_{non-chosen} $$

Основная идея изложена, но важны детали и конкретные формулы, которые позволили бы нам посчитать оба мат. ожидания, чтобы делать правильный выбор на каждом шаге. Предлагаю рассмотреть задачу "с конца". Допустим, мы вообще никого не выбрали и сейчас смотрим последниего n-го принца. Тогда мат. ожидание его места в рейтинге равно:

$$ r_{last} = \frac{1+2+...+n}{n} = \frac{n+1}{2} $$

Теперь предположим, что мы смотрим предпоследнего ((n-1)-го), который оказался на месте r. Последний принц может потенциально оказаться хуже этого - тогда место остаётся r-м, или лучше - тогда текущий принц будет сдвинут на место (r+1). Вероятность первого равна $ \frac{n-r}{n} $, а вероятность второго равна $ \frac{r}{n} $. Поэтому мат. ожидание в случае выбора равно:

$$ r_{chosen} = r \frac{n-r}{n} + (r+1) \frac{r}{n} = r \frac{n+1}{n} $$

Если мы не выберем предпоследнего принца, то придётся согласиться на последнего:

$$ r_{non-chosen} = r_{last} = \frac{n+1}{2} $$

Собственно, мы получаем условие выбора:

$$ r_{chosen} \le r_{non-chosen} $$ $$ r \frac{n+1}{n} \le \frac{n+1}{2} $$ $$ r \le \frac{n}{2} $$

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

Теперь перейдём от частного случая к общему. Допустим, мы рассматриваем k-го принца, который оказался на r-м месте в рейтинге. У нас впереди ещё (n-k) принцев, чтобы рассмотреть. Тогда вероятность $ r_{chosen} $ является функцией:

$$ r_{chosen} = r_{chosen}(k, r) $$

Очевидно, что:

$$ r_{chosen}(n, r) = r $$

Ведь если нам досталось r-е место в самом конце, то оно таким и останется, потому что нет впереди принцев, которые могут сместить последнего.

Я долго думал о том, как написать аналитическое вычисление функции $ r_{chosen}(k, r) $. Было много разных мыслей, но в итоге я решил остановиться на методе математеческой индукции. Я не очень люблю этот метод для объяснения сути, но конкретно здесь он позволяет объяснить проще всего, как мне кажется. Если у вас есть более красивые идеи на этот счёт, то я был бы рад их выслушать.

По предположению мат. индукции:

$$ r_{chosen}(k, r) = r \frac{n+1}{k+1} $$

Шаг 1. Проверяем базу:

$$ r_{chosen}(n, r) = r \frac{n+1}{n+1} = r $$

Это соответствует действительности. Доказано.

Шаг 2. Переход. Нужно доказать:

$$ r_{chosen}(k, r) = r \frac{n+1}{k+1} => r_{chosen}(k-1, r) = r \frac{n+1}{k} $$

Когда у нас впереди (n-k+1) принц, то мы можем свести задачу к (n-k) принцам. Ведь следующий либо оставит рассматриваемого принца на r-м месте с вероятностью $ \frac{k-r}{k} $, либо сместит его на (r+1)-е с вероятностью $ \frac{r}{k} $. Поэтому:

$$ r_{chosen}(k-1, r) = \frac{k-r}{k} r_{chosen}(k, r) + \frac{r}{k} r_{chosen}(k, r+1) = \frac{k-r}{k} r \frac{n+1}{k+1} + \frac{r}{k} (r+1) \frac{n+1}{k+1} = r \frac{n+1}{k} $$

Доказано. Теперь мы знаем $ r_{chosen} $ в любой ситуации.

Теперь давайте рассматривать $ r_{non-chosen} $. Здесь ситуация несколько сложнее, поскольку после не-выбора, можно сделать выбор на любом одном из следующих. Для предпоследнего мы уже посчитали:

$$ r_{non-chosen}(n-1) = r_{last} = \frac{n+1}{2} $$

Для простоты давайте рассмотрим пред-пред-последний случай. Если мы не выбираем, то на пред-последнем случае может равновероятно выпасть любое место принца с местами r от 1 до (n-1). В зависимости от $ r_{chosen}(n-1, r) $ мы либо остановим наш выбор, либо согласимся на последнего. Поэтому:

$$ r_{non-chosen}(n-2) = \frac{1}{n-1} \sum_{r=1}^{n-1} min(r_{chosen}(n-1, r), r_{non-chosen}(n-1)) $$

Аналогично получаем для любого k:

$$ r_{non-chosen}(k) = \frac{1}{k+1} \sum_{r=1}^{k+1} min(r_{chosen}(k+1, r), r_{non-chosen}(k+1)) = \frac{1}{k+1} \sum_{r=1}^{k+1} min(r \frac{n+1}{k+2}, r_{non-chosen}(k+1)) $$

Таким образом у нас теперь есть мат. ожидания $ r_{chosen}(k, r) $ и $ r_{non-chosen}(k) $, на любом этапе выбора. Этого достаточно, чтобы стратегию можно было продуктивно использовать.

Интересным выглядит значение $ r_{non-chosen}(0) $. Оно показывает мат. ожидание выбранного принца ещё до того, как мы начали их смотреть. Это то место в рейтинге, на которое мы можем расчитывать, пользуясь данной стратегией.

На формулах всё выглядит страшно и непрактично. Поэтому давайте немного конкретных чисел.

Числовые оценки

Рассмотрим самый простой нетривиальный случай. Он достаточно интересен для демонстрации. Допустим, у нас не сто, а 3 принца. Очевидно, что на первого соглашаться не стоит, так как слишком мало информации. Соглашаясь на него, мы получаем в среднем итоговое 2-е место. Второго просто пропустить, невзирая ни на что, нельзя тоже, потому что это автоматически означает согласие на 3-го, который тоже, очевидно, даст нам итоговое 2-е место. Когда мы смотрим второго принца, он может быть либо лучше, либо хуже первого. Если мы соглашамеся, когда он лучше первого (с вероятностью 50%), то итоговое место у нас будет 1-е с вероятностью 2/3 или 2-е с вероятностью 1/3. Если же второй оказывается хуже (с вероятностью 50%), то мы смотрим и берём третьего, что даёт нам в среднем 2-е место. В итоге такая стратегия даёт нам:

$$ \frac{1}{2} (\frac{2}{3} 1 + \frac{1}{3} 2) + \frac{1}{2} 2 = \frac{5}{3} $$

Это лучше, чем итоговое 2-е.

На уровне наших формул это выглядело бы вот как:

1) Считаем $ r_{non-chosen} $:

$$ r_{non-chosen}(n-1) = r_{non-chosen}(2) = \frac{n+1}{2} = \frac{3+1}{2} = 2 $$ $$ r_{non-chosen}(1) = \frac{1}{k+1} \sum_{r=1}^{k+1} min(r \frac{n+1}{k+2}, r, n-k-1), r_{non-chosen}(k+1)) = \frac{1}{2} \sum_{r=1}^{2} min(r \frac{4}{3}, 2) = \frac{1}{2} (min(\frac{4}{3}, 2) + min(\frac{8}{3}, 2)) = \frac{1}{2} (\frac{4}{3} + 2) = \frac{5}{3} $$

2) Смотрим на 1-го принца. Разумеется, он занимает у нас 1-е место. Вычисляем $ r_{chosen} $:

$$ r_{chosen}(k=1, r=1) = r \frac{n+1}{k+1} = 2 $$

Так как $ \frac{5}{3} < 2 $, то мы не выбираем первого, а идём ко второму.

3) Аналогично смотрим на 2-го и понимаем, что если у него место в рейтинге 1 - то его следует выбрать, а если 2 - то не следует.

Интересно рассмотреть несколько частных случаев. Для разных n. Я специально подготовил таблицы, чтобы самому в них заглядывать по мере необходимости.

n = 5, r = 2.05

1       nobody
2 - 3   1
4       1 - 2
5       1 - 5
n = 10, r = 2.558

1 - 3   nobody
4 - 5   1
6 - 7   1 - 2
8       1 - 3
9       1 - 5
10      1 - 10
n = 20, r = 3.002

1 - 5   nobody
6 - 10  1
11 - 13 1 - 2
14 - 15 1 - 3
16      1 - 4
17      1 - 5
18      1 - 7
19      1 - 10
20      1 - 20
n = 30, r = 3.204

1 - 8   nobody
9 - 15  1
16 - 19 1 - 2
20 - 21 1 - 3
22 - 23 1 - 4
24      1 - 5
25      1 - 6
26      1 - 7
27      1 - 8
28      1 - 11
29      1 - 15
30      1 - 30
n = 40, r = 3.328

1 - 11  nobody
12 - 19 1
20 - 25 1 - 2
26 - 28 1 - 3
29 - 30 1 - 4
31 - 32 1 - 5
33      1 - 6
34      1 - 7
35      1 - 8
36      1 - 9
37      1 - 11
38      1 - 14
39      1 - 20
40      1 - 40
n = 50, r = 3.412

1 - 13  nobody
14 - 24 1
25 - 30 1 - 2
31 - 34 1 - 3
35 - 37 1 - 4
38 - 39 1 - 5
40 - 41 1 - 6
42      1 - 7
43      1 - 8
44      1 - 9
45      1 - 10
46      1 - 12
47      1 - 14
48      1 - 18
49      1 - 25
50      1 - 50
n = 100, r = 3.603

1 - 27  nobody
28 - 47 1
48 - 59 1 - 2
60 - 67 1 - 3
68 - 73 1 - 4
74 - 77 1 - 5
78 - 80 1 - 6
81 - 82 1 - 7
83 - 84 1 - 8
85 - 86 1 - 9
87      1 - 10
88 - 89 1 - 11
90      1 - 12
91      1 - 14
92      1 - 15
93      1 - 17
94      1 - 19
95      1 - 21
96      1 - 25
97      1 - 30
98      1 - 37
99      1 - 50
100     1 - 100

Давайте рассмотрим таблицу для n = 100. Именно этот случай выпал принцессе. Выходит, что она должна отказывать первым 27-ми в любом случае, потом до 47-го соглашаться только на лучшего из всех предыдущих, потом до 59-го на 1-го или 2-го по рейтингу среди просмотренных, и т.д. Такая стратагия в среднем гарантирует место в рейтинге 3.603. Согласитесь, весьма неплохо получить 3-го или 4-го мужчину в рейтинге из ста кандидатов при таких жёстких условиях со стороны короля.