Задача о разборчивой невесте (занимательная статистика)

Задача о разборчивой невесте (проблема остановки выбора) — оптимизационная задача, впервые сформулированная Мартином Гарднером в 1960 году.

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

Задача может быть сформулирована следующим образом:

Невеста ищет себе жениха (существует единственное вакантное место).

Есть известное число претендентов — n.

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

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

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

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

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

Переспать для начала со всеми.

Размещено через приложение ЯПлакалъ

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

История
Задача о разборчивой невесте, по-видимому, была введена в 1949 году Мерриллом М. Фладом, который назвал её проблемой невесты в лекции, которую он прочитал в том же году. Он упоминал ее несколько раз в течение 1950-х годов, например, в выступлении на конференции в Purdue 9 мая 1958 года, и в конечном итоге она стала широко известна в народе, хотя в то время ничего не было опубликовано. В 1958 году он отправил письмо Леонарду Гиллману с копиями дюжине друзей, включая Сэмюэля Карлина и Дж. Роббинса, в котором изложил доказательство оптимальной стратегии с приложением Р. Палермо, который доказал, что среди всех стратегий доминирует стратегия "отклонить первое p безоговорочно, затем принять следующего кандидата, который лучше".

Первая публикация, очевидно, была сделана Мартином Гарднером в журнале Scientific American за февраль 1960 года. Он слышал об этом от Джона Х. Фокса-младшего и Л. Джеральда Марни, которые независимо друг от друга придумали аналогичную задачу в 1958 году; они назвали это «game of googol». Фокс и Марни не знали оптимального решения; Гарднер обратился за советом к Лео Мозеру, который (вместе с Дж. Р. Паундером) предоставил правильный анализ для публикации в журнале. Вскоре после этого несколько математиков написали Гарднеру об эквивалентной задаче, о которой они знали по слухам, и вероятном схождении всех задач к оригинальной работе Флада.

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

1/e-закон наилучшего выбора принадлежит Ф. Томасу Брюссу (1984).

Фергюсон (1989) имеет обширную библиографию и указывает, что подобная (но другая) проблема рассматривалась Артуром Кейли в 1875 году и даже Иоганном Кеплером задолго до этого.

ИИ решение не интересно. Лучше самим тут преддагать нормальные решения

Размещено через приложение ЯПлакалъ

Мужики уже все решили и обосновали - в среднем лучше чем 37 % невесте получить нереально. Либо кошки и старость.

Исследование рынка и лучший выбор за ограниченное время.

Можно в магазинах пользоваться :)

Нифига не понял. Это значит что 37ой человек из 100 будет лучший варик ?
А 2й из 5 ?
Может лучше огласить весь список ?

Размещено через приложение ЯПлакалъ

А не мало? Может пусть лучше будет Х?

Так тачки можно выбирать

Размещено через приложение ЯПлакалъ

Да, хуле решать-то!
Выбирать с условием самого богатого и самого старого одновременно!

Э-э-э, а как же любовь? Хотя о чём я...

Товарищи курсанты, в качестве примера возьмём N танков. Нет, N мало, лучше возьмём M танков!

Размещено через приложение ЯПлакалъ

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

Бля, может нужно за первого выходить, а не становиться nлядью

Размещено через приложение ЯПлакалъ

Пфф. Отсортировать массив претендентов по "лучшести" от лучшего к худшему и взять первого из списка даже не общаясь.
Ну а что, в задаче не сказано что их сортировать предварительно нельзя.

Товарищ! Я вас умоляю! Не надо о сложном! Вон на улице, поглядите, солнышко светит, льдинка плывёт, лягушка лягушку на льдинке е***т. Давайте о сиськах невесты этой лучше. Они большие были?

И потом оказаться никому не нужной.

Приблизительно так выглядит эта задача в фильме «Трасса 60».

Размещено через приложение ЯПлакалъ

Это решение работает когда вариантов больше 10 (а лучше более нескольких десятков). В противном случае высок шанс всё лучшее пропустить в начале, и задача не будет иметь решения.

Не могу себе представить, как вбить это всё в женскую голову...

Да, потом ещё анекдот про них придумали

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

1. Вы можете посетить магазин ТОЛЬКО ОДИН РАЗ.
2. В магазине 6 этажей, качество мужчин повышается с увеличением
порядкового номера этажа.
3. Вы можете выбрать любого мужчину на каком-либо этаже или подняться
на верхний этаж.
4. Не разрешается возвращаться на нижний этаж.
Одна женщина решила посетить этот самый "Магазин мужей", чтобы найти
себе спутника.
Прочитав у входа на первый этаж вывеску: "Мужчины, имеющие работу", -
она идет сразу на второй этаж.
Вывеска на втором этаже: "Мужчины, имеющие работу и любящие детей".
Женщина идет на третий.
Вывеска на третьем этаже: "Мужчины, имеющие работу, любящие детей и
необычайно красивые". "Ух ты! " - подумала женщина, но все же пошла на
четвертый этаж.
Вывеска на четвертом этаже: "Мужчины, имеющие работу, любящие детей,
ослепительной красоты и помогающие по дому".
- Невероятно! – воскликнула женщина. – Мне очень трудно устоять!
Но, произнеся это, все же поднимается на пятый этаж.
Вывеска на пятом этаже: "Мужчины, имеющие работу, любящие детей,
ослепительной красоты, помогающие по дому и очень романтичные".
Женщине очень захотелось остаться на этом этаже и выбрать себе пару, но
все же она, преодолев себя, пошла на последний этаж.
И на шестом этаже она читает вывеску вот такого содержания: "Вы на этом
этаже посетительница № 31 456 012, здесь нет мужчин, этот этаж
существует лишь для того, чтобы лишний раз доказать, что женщину
удовлетворить невозможно. Благодарим за посещение нашего магазина!"

Размещено через приложение ЯПлакалъ

Забеременеть от них и родить.

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

Сказано, что с каждым можно общаться только один раз.