Previous Entry Share Next Entry
Теория вероятности
traveller2
Мой друг ВД задал задачу по теории вероятности. Задача имеет совершенно научное решение.
Я его спрятал под катом, чтобы была возможность подумать (или заглянуть в учебники).

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

Предположим, ей ответили 100 кандидатов. С каждым из них она решила провести интервью, но есть одно непременное условие: в конце интервью она должна сказать 'да или нет'. Если нет, молодой человек выбывает из игры и исчезает навсегда. Обиженный, снова он к этой девушке не вернется. Если да, то дальнейшие интервью, естественно, прекращаются.

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





Теория вероятности дает следующий алгоритм. Девушке надо проинтервьюировать первых 100/е = 37 кандидатов (здесь е основание натуральных логарифмов, е = 2.71828...). Все плюсы и минусы каждого кандидата записать. Из этих первых 37 кандидатов выбрать самого лучшего. После этого продолжить интервью и остановиться на первом молодом человеке, который будет лучше выбранного из 37-мерки. Таков оптимальный алгоритм по науке.

  • 1
Да-да-да, любимая задача из книжки "50 вероятностых задач" Мостселлера(?) или что-то вроде этого. Прочитано в школе, а восхищение не прошло до сих пор. В жизни проблема в том, что неизвестна длина очереди.

Все верно. Кроме того, в жизни вам не скажут сразу 'да или нет'. Но задача клевая!

А если лучшего, чем тот из первых 37-ми не будет?

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

(Deleted comment)
Точно. Вы правы. В таких вопросах, конечно, решать надо сердцем. Да реально так и получается в жизни ... Кстати, я тоже из тех, кто обойдет стороной 50 чистых скамеек и сядет на 51-ую, только что покрашенную!

Лучший из 100 находится равновероятно под каждым номером -> вероятность того, что он -- среди первых 37, равна 37%. Это вы называете "маловероятно"?

Вы немного не поняли условие. Вероятность найти лучшего, при запрете на возвращение назад, таким образом как вы описываете, меньше 1/3, а составляет 1%. Поскольку вы не знаете, кто будем следующий, а назад вернуться не можете. Вероятность того, что лучший в контрольной группе действительно 37%, но вы его оттуда выудите с малой вероятностью.

Это - задача об оптимальной стратегии выбора при запрете на возвращение назад. Предположим для простоты, что все кандидаты можно разделить на три класса: хорошие, плохие и середнячки.
Опрос первой контрольной группы (37 человек, в предположении о случайности выборки и очередности интервью) позволит вам определить уровень кандидатов, т.е. какой кандидат может считаться хорошим в данном ансамбле, с вероятностью около 95%. Это будет вашей реперной точкой. Опять-таки, с вероятностью около 95%, в оставшейся группе 63х будет хотя бы один кандидат лучше 'реперного'.

Таким образом, вероятность прокола всего 10%.

Если для простоты предположить, что оценки кандидатов не дискретны (т.е. принадлежат непрерывному распределению), то среди 100 кандидатов есть ровно один "чемпион" с максимальным баллом. Далее при случайной выборке 37 кандидатов чемпион попадает в эту группу с вероятностью 37% и становится "реперным". Далее с вероятностью 100% в
"оставшейся группе 63х" все -- хуже чемпиона и не выбран никто. Т.о., имеется "прокол" с вероятностью 37%. Как вы получаете 10% -- остается загадкой, как и то, что именно вы называете проколом.

Вообще-то я потратил некоторое время на эту задачу, рассмотрев описанную вами стратегию для частного случая "канонических" оценок кандидатов, распределенных равномерно в интервале (0,1) (первообразная от функции распределения вероятности любых оценок -- очевидный пример канонической оценки).
Я вычислял мат. ожидание оценки выбранного кандидата (для определенности, если дело доходило до последнего кандидата, я выбирал его) в зависимости от размера "контрольной выборки", после чего находил точку максимума этой функции.
Если, как вы сказали, я "немного не понял условие", то процедура, описанная в предыдущем предложении, должна не совпадать с подразумеваемой вами?
Без каких-либо приближений получил ответ sqrt(N) - 1 вместо ожидаемого N / e, и ощущение, что ответ может зависеть от формы исходного распределения оценок. Возможно, я проврался. Для контроля разыскал в инете упомянутый azb1958'ом задачник Ф.Мостеллера, где ваша задача действительно имеется под номером 47, с приблизительным ответом N / e, и решением, которое, к сожалению, понять не смог.... Сплошные фрустрации. Единственный плюс -- djvu viewer, установленный ради задачника на комп.

Большое спасибо вам за усилия, которые вы вложили в эту задачу, и за ваши комментарии. Я сам помню о ней со студенческих времен и именно из этого задачника. Сейчас я ничего не могу добавить, к сожалению, но я обещаю на каникулах взглянуть в задачник; и тогда попробую вернуться к этому вопросу.... ☹

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

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

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

Да уж понятно, что на 99-ом шаге надо соглашаться ...

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

Есть функциональное уравнение
f(f(x)) = x*x -2.

Звездочка в правой части - умножение, т.е. стоит х в квадрате минус 2.
Требуется найти f(x).

Аналитического решения найти пока не могу. По ночам, вместо сна, пытаюсь проанализировать численно. Вроде решения есть, и не одно, а два или 4. Но надо еще подумать... Врезалось, как колючка!

Четыре, которые "вроде", -- ряды Тейлора около неподвижных точек -1 (два комплексных) и 2 (два действительных)?

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

Да, ряды Тэйлора на стационарных точках. Что еще не проверил, это сшиваются ли эти ряды (вручную вычислил по 5 членов ряда) с разложением решения по 1/х при больших х (точнее по определенным степеням 1/х; пока построил 3 члена, начиная с х в степени корень из 2). Кроме того, есть некоторые сомнения относительно пары комплексных решений. Просто не было времени подумать.
***
Задачу о выборе цитировал по памяти, и если слегка спутал, прошу прощения, чего уж тут возмущаться, память уже не та ... А задача о выборе кандидата на выборах, насколько я понимаю, научного решения не имеет.

Нашел одно аналитическов решение. Если интересно, ответ здесь: https://twiki.cern.ch/twiki/bin/view/Main/AVFedotovHowTo#functional_equations .

Очень интересно!!!!!!!!!!
Проверил численно, что вы нашли решение.
Не могли бы вы хотя бы намекнуть, как вы нашли это решение?
Кстати, с вашим решением f(x) в ряд Тейлора вблизи х=2
не разлагается, так? Из-за корневой сингулярности. Это как бы не соответствует моему ряду Тэйлора, который я нашел "руками". Или я что-то путаю? Загадка... Кстати, если хотите вы мне можете писать напрямую.

Я сделал это на Математике, и сейчас опять не очень уверен. Проверю еще.

А вы заметили, что я тоже проверял решение программно -- численно на фортране (ссылка "numerical tables")? Пока не проверил, не поверил...

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

На то, что корневая особенность против Тейлора, я обратил внимание. Хотел увидеть ее численным сканированием, но неожиданно увидел вполне линейную функцию. Либо недо-zoom-ил, либо, может быть, она, присутствуя как в z, так и 1/z, сокращается в их сумме.

..."Писать вам напрямую" -- куда?

задача о разборчивой невесте.
есть лекция гуссейн-заде для школьников на малом мехмате.
http://libgen.info/view.php?id=183236

задача о разборчивой невесте.
есть популярная лекция для школьников, прочитанная на малом мехмате гуссейн-заде.

на сайте мцмно есть файл с текстом.
пытался положить здесь линк, но мне сказали, что это спам.

Спасибо, сейчас попытаюсь разыскать.

Спасибо. Гуссейн-Заде нашел.

Да что Вы. не стоит благодарности

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

так оно и бывает, Света!... по крайнем мере, хотелось бы.

Света, я же написал, что это оптимальная стратегия поиска по *науке. В жизни, особенно когда он (она) ищет, с кем ее (жизнь) прожить, так не бывает. Выбирают не по науке, а сердцем, и очень часто выбор оказывается весьма далек от оптимума. Но люди есть люди. Это и делает жизнь в среднем прекрасной, но с флуктуациями ...

Какова же вероятность того, что следуюшие 63 окажутся поголовно женатыми?::))) кажется, была задачка из динамического программирования о том, что кажлая новая сккретарша лучше предыдущей?

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

Решение сердцем - это явно не для сайтов знакомств :)))

Разумеется. На таких сайтах *как правило* люди своеобразные. Но вы знаете, бывают счастливые исключения. Сам был свидетелем.

Я тоже. Два случая на тысячи - не очень оптимистичный прогноз!

Все почти правильно! При абсолютно случайной выборке, референтная группа "первых", из которых выбирается "эталон" (с которым потом надо сравнивать), содержит 100/е = 37 человек.
Любопытно, что получиться если вы прогоните вашу программу, заменив 20 на 37?..

как то слишком умно, ничего не понял))))
ЗЫ. спал сегодня 2 часа((
ЗЫ2. розовый карабин - это нечто))))

Так девочка же... Конечно, карабин должен быть розовым!

re: карабин должен быть...

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

Re: карабин должен быть...

Израильская армия самая крутая.

Ошибка в ответе.
Во первых, выборка может быть нерепрезентативных, если например первые 37 были самыми лучшими, а вот уже остальные уже хуже. Для этого делают смешивание, но никакх не первых
Также постановка задача не верная. Если она этим 37 отказала, то их она уже отнесла к классу НЕТ, чтобы обучить выбрать лучшего она должна иметь и тех кому сказала ДА, а по условии этого нельзя делать
Короче в такой задаче много но.
И почему именно делить на основание натуральных логарифмом?

Это правильное решение. Там в комментах по-моему были ссылки
на книжку, где оно подробно описано.

В жизни как-то как в анекдоте:

Открытие мужского публичного дома (в смысле, для женщин). Радостная толпа клиенток вваливается в заведение и читает таблички: "1 этаж", под ней "Короткие и тонкие". И всей толпой на лестницу. Поднимаются. На втором этаже таблички: "2 этаж", "Короткие и толстые". Всей толпой бегут выше. На следующем - "3 этаж", "Длинные и тонкие". Толпа клиенток, не останавливаясь, бежит еще выше. Там таблички "4 этаж", "Длинные и толстые". Клиентки бегут дальше и читают: "5 этаж", а ниже крупно-крупно: "Ну какого же вам еще %уя надо?!".

  • 1
?

Log in

No account? Create an account