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

[Alise]

Помогите понять условие этой задачи. Я вот никак не могу, мне кажется, есть противоречие. Итак, она должна отбросить первые 37% женихов, а потом выбрать первого такого, который будет лучше любого из предыдущих.
Но!
Вдруг среди тех 37% уже был самый лучший жених? Ведь они выбираются случайным образом? И тогда, получается, она просто не найдет среди оставшихся такого, который был бы лучше!

В чем я не права?

Задача
Невеста ищет себе жениха (существует единственное вакантное место).
Есть известное число претендентов — n.
Невеста общается с претендентами в случайном порядке, с каждым не более одного раза.
О каждом текущем претенденте известно, лучше он или хуже любого из предыдущих.
В результате общения с текущим претендентом невеста должна либо ему отказать, либо принять его предложение. Если предложение принято, процесс останавливается, если невеста отказывает жениху, то вернуться к нему позже она не сможет.
Цель — выбрать лучшего претендента.

В 1963 году академик РАН Евгений Дынкин предложил решение этой задачи для частного случая. Общее решение было найдено Сабиром Гусейн-Заде в 1966 году.

Этой задаче было уделено много внимания во многом потому, что оптимальная стратегия имеет интересную особенность: если число кандидатов достаточно велико (порядка сотни), оптимальная стратегия будет заключаться в том, чтобы отклонить всех первых n/e} n/e (где e=2,718.. — основание натурального логарифма) претендентов и затем выбрать первого, кто будет лучше всех предыдущих. При увеличении n вероятность выбора наилучшего претендента стремится к 1/e, то есть примерно к 37 %.

[kotenok gav]

Alise в сообщении #1362117 писал(а):

В чем я не права?

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

[grizzly]

Alise в сообщении #1362117 писал(а):

Помогите понять условие этой задачи.

Да, Вы не поняли условие. Цель невесты в этой задаче только одна -- выбрать самого лучшего жениха. По описанной стратегии ей это удастся с ~37% вероятностью. В остальных случаях она либо останется старой девой (если лучший был среди первых перебранных), либо выйдет таки за кого-то и будет всю жизнь жалеть, если потом узнает, что он не был лучшим.

[Pphantom]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- для лучшего понимания стоило бы привести условие задачи.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[wrest]

Да, интересная задачка.

Горизонтальная ось -- сколько процентов женихов пропустит (откажет, но запомнит рейтинг лучшего из них).
Вертикальная ось -- вероятность.
Красный -- останется без жениха.
Желтый -- выйдет замуж, но не за лучшего.
Зеленый - выберет лучшего.

Моделировалось на 100 женихах в наборе, 100 000 случайных наборов по каждому проценту первоначального отсева (т.е. всего 10 млн. наборов). Рейтинги в наборе от 1 до 100 (т.е. без повторов).

[Legioner93]

Хм. А если максимизировать не вероятность выбрать самого лучшего, а матожидание рейтинга выбранного жениха? Стратегия измениться или нет?

То есть я хочу, чтобы за миллион попыток выбора из ста женихов средний рейтинг женихов был максимальный. При этом не против, что Ален Делон будет попадаться реже, чем в 37% случаях.

А ещё можно попытаться минимизировать вероятность выбора жениха не из, скажем, топ-10.

[wrest]

Legioner93 в сообщении #1362341 писал(а):

Хм. А если максимизировать не вероятность выбрать самого лучшего, а матожидание рейтинга выбранного жениха? Стратегия измениться или нет?

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

[Legioner93]

Цитата:

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

Никакого распределения рейтингов нет. Сами рейтинги присутствуют в условии задачи.

Alise в сообщении #1362117 писал(а):

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

То есть женихи вполне упорядочены, вот он и рейтинг.

[wrest]

Legioner93 в сообщении #1362385 писал(а):

Никакого распределения рейтингов нет. Сами рейтинги присутствуют в условии задачи.

Тогда не получится ничего сделать с матожиданием.

Legioner93 в сообщении #1362385 писал(а):

То есть женихи вполне упорядочены, вот он и рейтинг.

Например, рейтинги у группы женихов идут от 1 до 99, а лучшего жениха рейтинг 1 000 000.
Или наоборот, рейтинги идут от 999 901 до 1 000 000.
Будут, очевидно, разные стратегии по максимизации матожидания рейтинга, не так ли? Хотя всё и упорядочено.

[grizzly]

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

[wrest]

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

[grizzly]

wrest в сообщении #1362403 писал(а):

Например нулевой.

Да, такой выбор выглядит логично.

wrest в сообщении #1362403 писал(а):

если рейтинг невыхода замуж намного меньше рейтинга самого плохого жениха то очевидным выглядит стратегия выйти за первого встречного...

Вы имели в виду "за последнего встречного"? Или я не понял. То есть, даже в этом случае можно рисковать до самого последнего и следить за мат.ожиданием для выбранной стратегии.

-- 19.12.2018, 12:47 --

wrest в сообщении #1362403 писал(а):

но центр отрезка в произвольном месте.

И здесь не совсем понял. Есть 100 женихов. Их порядок в равномерном рейтинге известен всем, кроме невесты.

[wrest]

В общем, если случай невыбора жениха считаем случаем выбора жениха с рейтингом ноль, выбираем из 100 женихов с рейтингами от 1 до 100, то матожидание максимально если пропустить 6 или 7 женихов, а потом выйти за лучшего из предыдущих. Тогда средний рейтинг будет около 87,7

Если считать только случаи когда жених найден и пропускать когда не найден, то надо пропустить 99 и выйти за последнего (если он окажется лучшим чем все предыдущие, конечно) ну это очевидный случай, так мы гарантируем выход за лучшего.

Теперь допустим что рейтинг невыхода замуж отрицательный и мы это учитываем. Тогда, по мере увеличения "штрафа" надо продвигаться к началу очереди. При штрафе в 50 (рейтинг невыхода замуж равен -50) надо пропустить уже не 6 или 7, а 5. При штрафе в 100, пропустить надо 4. При штрафе 1000, пропустить надо одного. Начиная где-то с 2500, пропускать не надо, выходить надо за первого (тогда средний рейтинг будет 50 с чем-то).

Предположим что рейтинг невыхода замуж положительный. При премии в 25, пропускать надо 7 или 8. При премии 75, пропускать надо 12. При премии 100, пропускать надо 99, а при премии 101 и больше -- ясное дело, пропускать надо всех, замуж не выходить и получить 101 или больше.

-- 19.12.2018, 13:34 --

grizzly в сообщении #1362406 писал(а):

Вы имели в виду "за последнего встречного"? Или я не понял.

Ну я проверяю только стратегии "пропустить $n$, затем выйти за лучшего из предыдущих"

-- 19.12.2018, 13:41 --

grizzly в сообщении #1362406 писал(а):

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

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

[worm2]

wrest в сообщении #1362423 писал(а):

Теперь допустим что рейтинг невыхода замуж отрицательный и мы это учитываем.

Невеста легко избавится от сколь угодно большого штрафа, просто выйдя за последнего :)
Это я к тому, что различных стратегий вообще-то великое множество, они не сводятся к "Пропустить N и выйти за следующего, чей рейтинг больше".