задачка (математическое)
Dec. 2nd, 2011 09:37 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaЗабавная задачка из теории вероятностей, с весьма анти-интуитивным условием.
Алиса и Боб - идеальные математики. Алиса показывает Бобу набор из m конвертов, в каждом из которых либо лежит долларовая монета, либо не лежит ничего. Алиса объясняет, что она выбрала количество конвертов, в которых лежит монета, случайным образом (необязательно равномерно случайным).
Алиса: "Если ты выберешь конверт наугад, каково матожидание суммы, которую ты получишь?"
Боб: "Это зависит от того, какую функцую ты использовала для выбора числа конвертов."
Алиса говорит Бобу, какую функцию она использовала на самом деле, и он вычисляет матожидание. После этого он вытягивает конверт наугад, и обнаруживает в нем доллар. Алиса отдает этот доллар Бобу, и перемешивает пустой конверт с оставшимися. "Теперь, когда денег на доллар меньше, а конвертов столько же, каково матожидание суммы, что ты получишь, если опять вытащишь конверт наугад?"
"То же, что и раньше" - отвечает Боб.
1. Предположим, Алиса выбрала кол-во конвертов с монетами путем равномерного выбора числа от 0 до m включительно. Чему равно m?
2. Можете ли вы придумать другую функцию выбора для Алисы, которая работает для какого-то m?
[внимание, в комментариях уже есть правильные ответы, так что не заглядывайте, если хотите самостоятельно решить]
Алиса и Боб - идеальные математики. Алиса показывает Бобу набор из m конвертов, в каждом из которых либо лежит долларовая монета, либо не лежит ничего. Алиса объясняет, что она выбрала количество конвертов, в которых лежит монета, случайным образом (необязательно равномерно случайным).
Алиса: "Если ты выберешь конверт наугад, каково матожидание суммы, которую ты получишь?"
Боб: "Это зависит от того, какую функцую ты использовала для выбора числа конвертов."
Алиса говорит Бобу, какую функцию она использовала на самом деле, и он вычисляет матожидание. После этого он вытягивает конверт наугад, и обнаруживает в нем доллар. Алиса отдает этот доллар Бобу, и перемешивает пустой конверт с оставшимися. "Теперь, когда денег на доллар меньше, а конвертов столько же, каково матожидание суммы, что ты получишь, если опять вытащишь конверт наугад?"
"То же, что и раньше" - отвечает Боб.
1. Предположим, Алиса выбрала кол-во конвертов с монетами путем равномерного выбора числа от 0 до m включительно. Чему равно m?
2. Можете ли вы придумать другую функцию выбора для Алисы, которая работает для какого-то m?
[внимание, в комментариях уже есть правильные ответы, так что не заглядывайте, если хотите самостоятельно решить]
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2011-12-03 09:58 am (UTC)Все суммы тут от 0 до m, Σkf(k) = Σk=0,1,..,mf(k)
Пусть вероятности гипотез H0, H1, ... , Hm что там 0,1,..m монеток равны p0, p1, ..., pm. Их сообщает Алиса Бобу.
Мат-ожидание E1 количества монеток равно Σi pi*i
Посчитаем вероятности гипотез после того как Боб увидел монетку (событие M), т.е. P(Hk | нашёл монетку в случайном конверте) = P(Hk | M ).
По теореме Байеса:
P(Hk | M ) = P(Hk) * P(M|Hk) / P(M) = pk * (k/m) / (Σi pi * i/m) =pk * k / (Σi pi * i) = pk * k / E1
Матожидание E2 количества монеток после события М:
E2 = Σk P(Hk | M )*(k-1) = Σk (pk * k / E1) * (k-1) = (Σk pk * k * (k-1)) / E1
Имеем уравнение E1 = E2
(Σk pk * k * (k-1)) / E1 = E1
(Σk pk * k * (k-1)) = E12 (I)
Для двух конвертов с распределением монеток p0, p1, p2 это (I) превращается в уравнение
p2 * 2*(2-1) = (p1*1 + p2 *2)2
Так же ограничение на то, что p0 + p1 + p2 = 1
Решением для двух конвертов является например p0 = 1/2, p1 = 0, p2 = 1/2 плюс ещё бесконечно много решений ( два уравнения, три неизвестных ).
Решать в общем случае это квадратное уравнение для любого m не хочется :] Там два уравнения и (m+1) неизвестных, выбор богатый.
Пример выбора функции для любого m (пункт 2) - это взять случай с двумя конвертами и распространить его на все остальные.
p0 = 1/2, p1 = 0, p2 = 1/2, p3 = p4 = ... pm = 0.
Для случая равномерного выбора кол-ва монеток (пункт 1) нужно проверить для каких m выбор pk=1/m подходит в уравнение.
Уравнение (I) превращается в
Σkk(k-1)/m = 1/m2(Σkk)2
или
m*Σkk(k-1) = (Σkk)^2
При m=7 видим справа и слева 784 784
Единственность можно доказать, исходя из того что предел на бесконечности равен 3/4
no subject
Date: 2011-12-03 10:08 am (UTC)Алиса с вероятностями 1/2 кладёт монетки или в 0 конвертов, или в 2 конверта.
Мат-ожидание монеток в первом случае 0*1/2 + 2*1/2 = 1
После того как Боб увидел одну монетку, это гарантировано означает что их было две, и осталась ровно одна (матожидание равно 1).
no subject
Date: 2011-12-03 10:45 am (UTC)Тут мелкий промах: на самом деле p_k = 1/(m+1). Это приводит к правильному ответу (m=4, а не m=7). Остальное все безупречно :)
no subject
Date: 2011-12-03 02:48 pm (UTC)Обидная ошибка :)
к формулировке условия
Date: 2011-12-03 03:01 pm (UTC)Прежде всего, что означает фраза Алисы:
> "Если ты выберешь конверт наугад, каково матожидание суммы, которую ты получишь?"
Я понимаю это дело так: можно либо говорить о матожидании суммы денег в конвертах, и тогда она никак не зависит от того, что мы берём конверт. Можно говорить о матожидании содержимого случайно взятого конверта, но в этом случае непонятна роль слова "сумма".
Ясно, что вероятность обнаружить доллар в случайно взятом конверте равна 1/2 из соображений симметрии: случай k=0 "симметричен" случаю k=m, и так далее. (Можно считать, что в конвертах без долларов лежат "антидоллары", и тогда полная симметрия бросается в глаза.)
Исходя из аддитивности матожидания, ясно, что оно равно m/2, если говорить о сумме всех конвертов. Но это просто матожидание суммы, и выбор конверта здесь никак не участвует вообще.
Вторую величину, которую надо будет далее сравнить с m/2, довольно трудно описать совсем коротко и "занимательно". Фактически, речь идёт о тех ситуациях, в которых случайно выбранный конверт оказался с долларом, и далее подсчёт "среднего" (после опустошения конверта) идёт только в пределах подмножества всего множества элементарных событий. Ведь конверт мог быть пустым, и такие случаи не учитывает новая статистика. Если бы она их учитывала, то, конечно, матожидание уменьшилось бы на 1/2 по сравнению с тем, что было.
В такой постановке, как у Вас написано, то есть
> "Теперь, когда денег на доллар меньше, а конвертов столько же, каково матожидание суммы, что ты получишь, если опять вытащишь конверт наугад?"
вопрос выглядит как минимум двусмысленно. Потому что при одной из интерпретаций совершенно ясно, что матожидание уменьшится. И здесь, мне кажется, необходимо в какой-то форме чётко указать на то, что это "условное" матожидание, и что относится оно только к ситуациям "успеха" (конверта с долларом при случайном выборе), а не ко всем ситуациям вообще.
Кстати, ещё одно "мелкое" замечание: фраза, что Алиса отдаёт доллар Бобу (а не откладывает его в сторону), способна немного сбить с толку. Потому что возникает предположение о том, что это доллар "гарантированно" мог войти в "сумму", которая "причитается" Бобу.
no subject
Date: 2011-12-05 02:32 pm (UTC):) Должен признаться, что у меня осознать смысл условия заняло примерно столько же времени, сколько потом решить задачу, и всё из-за этого слова "сумма". В этой фразе оно употреблено не в математическом, а в житейском смысле: некоторое количество денег (Вы, может быть, думаете, что сумма незначительная? Тургенев -- пример из Ушакова).
гвоздь программы
Date: 2011-12-05 04:36 pm (UTC)Я сейчас вспомнил очень смешной случай из школьного учебника. Там рассказывалось о большой "рачительности" товарища Калинина, "всесоюзного старосты". Он посетил какую-то стройку, подобрал там гвоздь. Спрашивает: "куда положить?" Рабочие смутилсь: "да куда угодно, Михаил Иванович!" А тот им с улыбкой: "куда угодно нельзя -- пропасть может!" :)
Я бы объявил нечто вроде "конкурса" на лучшую редакцию условия задачи (теперь уже всем понятной).