Теория вероятности
Mar. 1st, 2012 06:21 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
traveller2Мой друг ВД задал задачу по теории вероятности. Задача имеет совершенно научное решение.
Я его спрятал под катом, чтобы была возможность подумать (или заглянуть в учебники).
Предположим, молодая женщина ищет в интернете молодого человека. Она сформулировала критерии отбора. Скажем, молодой человек должен быть:
- молодым
- красивым
- умным
- богатым
- здоровым
- сексуальным
- веселым
- добрым
- играть на гитаре
- отличать Монтеня от Монтана
- уметь готовить
- мыть посуду
- не изменять.
Предположим, ей ответили 100 кандидатов. С каждым из них она решила провести интервью, но есть одно непременное условие: в конце интервью она должна сказать 'да или нет'. Если нет, молодой человек выбывает из игры и исчезает навсегда. Обиженный, снова он к этой девушке не вернется. Если да, то дальнейшие интервью, естественно, прекращаются.
Какова оптимальная (с точки зрение теории вероятности) стратегия? Вот пятнадцатый вроде ничего, а вдруг следующий будет еще лучше, и будешь потом сожалеть всю оставшуюся жизнь...
Теория вероятности дает следующий алгоритм. Девушке надо проинтервьюировать первых 100/е = 37 кандидатов (здесь е основание натуральных логарифмов, е = 2.71828...). Все плюсы и минусы каждого кандидата записать. Из этих первых 37 кандидатов выбрать самого лучшего. После этого продолжить интервью и остановиться на первом молодом человеке, который будет лучше выбранного из 37-мерки. Таков оптимальный алгоритм по науке.
Я его спрятал под катом, чтобы была возможность подумать (или заглянуть в учебники).
Предположим, молодая женщина ищет в интернете молодого человека. Она сформулировала критерии отбора. Скажем, молодой человек должен быть:
- молодым
- красивым
- умным
- богатым
- здоровым
- сексуальным
- веселым
- добрым
- играть на гитаре
- отличать Монтеня от Монтана
- уметь готовить
- мыть посуду
- не изменять.
Предположим, ей ответили 100 кандидатов. С каждым из них она решила провести интервью, но есть одно непременное условие: в конце интервью она должна сказать 'да или нет'. Если нет, молодой человек выбывает из игры и исчезает навсегда. Обиженный, снова он к этой девушке не вернется. Если да, то дальнейшие интервью, естественно, прекращаются.
Какова оптимальная (с точки зрение теории вероятности) стратегия? Вот пятнадцатый вроде ничего, а вдруг следующий будет еще лучше, и будешь потом сожалеть всю оставшуюся жизнь...
Теория вероятности дает следующий алгоритм. Девушке надо проинтервьюировать первых 100/е = 37 кандидатов (здесь е основание натуральных логарифмов, е = 2.71828...). Все плюсы и минусы каждого кандидата записать. Из этих первых 37 кандидатов выбрать самого лучшего. После этого продолжить интервью и остановиться на первом молодом человеке, который будет лучше выбранного из 37-мерки. Таков оптимальный алгоритм по науке.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2012-03-02 01:41 am (UTC)no subject
Date: 2012-03-02 03:12 pm (UTC)no subject
Date: 2012-03-02 01:44 am (UTC)no subject
Date: 2012-03-02 03:15 pm (UTC)no subject
Date: 2012-03-02 10:50 pm (UTC)no subject
Date: 2012-03-03 06:47 am (UTC)no subject
Date: 2012-03-03 11:52 pm (UTC)Это - задача об оптимальной стратегии выбора при запрете на возвращение назад. Предположим для простоты, что все кандидаты можно разделить на три класса: хорошие, плохие и середнячки.
Опрос первой контрольной группы (37 человек, в предположении о случайности выборки и очередности интервью) позволит вам определить уровень кандидатов, т.е. какой кандидат может считаться хорошим в данном ансамбле, с вероятностью около 95%. Это будет вашей реперной точкой. Опять-таки, с вероятностью около 95%, в оставшейся группе 63х будет хотя бы один кандидат лучше 'реперного'.
Таким образом, вероятность прокола всего 10%.
no subject
Date: 2012-03-04 07:39 am (UTC)"оставшейся группе 63х" все -- хуже чемпиона и не выбран никто. Т.о., имеется "прокол" с вероятностью 37%. Как вы получаете 10% -- остается загадкой, как и то, что именно вы называете проколом.
Вообще-то я потратил некоторое время на эту задачу, рассмотрев описанную вами стратегию для частного случая "канонических" оценок кандидатов, распределенных равномерно в интервале (0,1) (первообразная от функции распределения вероятности любых оценок -- очевидный пример канонической оценки).
Я вычислял мат. ожидание оценки выбранного кандидата (для определенности, если дело доходило до последнего кандидата, я выбирал его) в зависимости от размера "контрольной выборки", после чего находил точку максимума этой функции.
Если, как вы сказали, я "немного не понял условие", то процедура, описанная в предыдущем предложении, должна не совпадать с подразумеваемой вами?
Без каких-либо приближений получил ответ sqrt(N) - 1 вместо ожидаемого N / e, и ощущение, что ответ может зависеть от формы исходного распределения оценок. Возможно, я проврался. Для контроля разыскал в инете упомянутый azb1958'ом задачник Ф.Мостеллера, где ваша задача действительно имеется под номером 47, с приблизительным ответом N / e, и решением, которое, к сожалению, понять не смог.... Сплошные фрустрации. Единственный плюс -- djvu viewer, установленный ради задачника на комп.
no subject
Date: 2012-03-04 08:49 pm (UTC)no subject
Date: 2012-03-05 04:38 am (UTC)В этом смысле изначально задача сформулирована не полно поскольку не задана функция выгоды девушки, то есть чего она хочет от жизни: обязательно лучшего, в среднем хорошего, обязательно не худшего итд. В зависимости от этого оптимальные стратегии будут разными.
В частности в случае мат ожидания стратегия будет сильно зависеть от шага. Например на 99м шаге надо соглашаться если кандидат лучше среднего из просмотренных ранее.
no subject
Date: 2012-03-05 05:25 pm (UTC)no subject
Date: 2012-03-05 05:32 pm (UTC)Есть функциональное уравнение
f(f(x)) = x*x -2.
Звездочка в правой части - умножение, т.е. стоит х в квадрате минус 2.
Требуется найти f(x).
Аналитического решения найти пока не могу. По ночам, вместо сна, пытаюсь проанализировать численно. Вроде решения есть, и не одно, а два или 4. Но надо еще подумать... Врезалось, как колючка!
no subject
Date: 2012-03-06 12:52 am (UTC)По поводу кандидатов из предыдущей задачи. Вчера, не сумев правильно выбрать кандидата на выборах, я в конце концов опять открыл Мостеллера и, к своему возмущению, на этот раз обнаружил, что задачу вы подменили, а ответ оставили. Сейчас увидел, что это уже подмечено уважаемым Анонимом.
no subject
Date: 2012-03-06 08:55 pm (UTC)***
Задачу о выборе цитировал по памяти, и если слегка спутал, прошу прощения, чего уж тут возмущаться, память уже не та ... А задача о выборе кандидата на выборах, насколько я понимаю, научного решения не имеет.
no subject
Date: 2012-03-09 12:51 am (UTC)no subject
Date: 2012-03-09 10:50 pm (UTC)Проверил численно, что вы нашли решение.
Не могли бы вы хотя бы намекнуть, как вы нашли это решение?
Кстати, с вашим решением f(x) в ряд Тейлора вблизи х=2
не разлагается, так? Из-за корневой сингулярности. Это как бы не соответствует моему ряду Тэйлора, который я нашел "руками". Или я что-то путаю? Загадка... Кстати, если хотите вы мне можете писать напрямую.
no subject
Date: 2012-03-09 11:00 pm (UTC)no subject
Date: 2012-03-10 10:40 am (UTC)К ответу я прилинковал отдельную страницу с "выводом", который, по сути, явлется цепочкой угадываний.
На то, что корневая особенность против Тейлора, я обратил внимание. Хотел увидеть ее численным сканированием, но неожиданно увидел вполне линейную функцию. Либо недо-zoom-ил, либо, может быть, она, присутствуя как в z, так и 1/z, сокращается в их сумме.
..."Писать вам напрямую" -- куда?
no subject
Date: 2012-05-29 10:29 pm (UTC)есть лекция гуссейн-заде для школьников на малом мехмате.
http://libgen.info/view.php?id=183236
no subject
Date: 2012-05-29 10:31 pm (UTC)есть популярная лекция для школьников, прочитанная на малом мехмате гуссейн-заде.
на сайте мцмно есть файл с текстом.
пытался положить здесь линк, но мне сказали, что это спам.
no subject
Date: 2012-05-30 08:06 pm (UTC)no subject
Date: 2012-05-30 08:33 pm (UTC)no subject
Date: 2012-05-30 09:05 pm (UTC)no subject
Date: 2012-03-02 04:33 am (UTC)вообще я за исключения из правиллл)) - вот бы первый кто ошибся дверью - на самом деле- попал в самоеяблочко).
no subject
Date: 2012-03-02 04:54 am (UTC)no subject
Date: 2012-03-02 03:18 pm (UTC)no subject
Date: 2012-03-02 06:21 am (UTC)no subject
Date: 2012-03-02 03:21 pm (UTC)no subject
Date: 2012-03-04 07:09 am (UTC)no subject
Date: 2012-03-04 08:46 pm (UTC)no subject
Date: 2012-03-04 08:48 pm (UTC)no subject
Date: 2012-03-02 07:42 am (UTC)no subject
Date: 2012-03-02 03:24 pm (UTC)Любопытно, что получиться если вы прогоните вашу программу, заменив 20 на 37?..
no subject
Date: 2012-03-02 06:19 pm (UTC)no subject
Date: 2012-03-02 09:14 am (UTC)ЗЫ. спал сегодня 2 часа((
ЗЫ2. розовый карабин - это нечто))))
no subject
Date: 2012-03-02 03:25 pm (UTC)re: карабин должен быть...
Date: 2012-05-27 08:39 pm (UTC)Re: карабин должен быть...
Date: 2012-05-27 08:47 pm (UTC)no subject
Date: 2015-01-28 07:07 am (UTC)Во первых, выборка может быть нерепрезентативных, если например первые 37 были самыми лучшими, а вот уже остальные уже хуже. Для этого делают смешивание, но никакх не первых
Также постановка задача не верная. Если она этим 37 отказала, то их она уже отнесла к классу НЕТ, чтобы обучить выбрать лучшего она должна иметь и тех кому сказала ДА, а по условии этого нельзя делать
Короче в такой задаче много но.
И почему именно делить на основание натуральных логарифмом?
no subject
Date: 2015-01-28 08:47 pm (UTC)на книжку, где оно подробно описано.
no subject
Date: 2015-02-06 03:33 am (UTC)no subject
Date: 2015-01-30 09:30 am (UTC)Открытие мужского публичного дома (в смысле, для женщин). Радостная толпа клиенток вваливается в заведение и читает таблички: "1 этаж", под ней "Короткие и тонкие". И всей толпой на лестницу. Поднимаются. На втором этаже таблички: "2 этаж", "Короткие и толстые". Всей толпой бегут выше. На следующем - "3 этаж", "Длинные и тонкие". Толпа клиенток, не останавливаясь, бежит еще выше. Там таблички "4 этаж", "Длинные и толстые". Клиентки бегут дальше и читают: "5 этаж", а ниже крупно-крупно: "Ну какого же вам еще %уя надо?!".