Простенькая задачка по теорверу

natunchik

http://projecteuler.net/index.php?section=problems&id=21...
A 30х30 grid of squares contains 900 fleas, initially one flea per square.
When a bell is rung, each flea jumps to an adjacent square at random (usually 4 possibilities, except for fleas on the edge of the grid or at the corners).
What is the expected number of unoccupied squares after 50 rings of the bell? Give your answer rounded to six decimal places.

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

FieryRush

Есть мнение, это потому, что произведение вероятностей сильно меньше заявленной точности. Ну т.е. если вероятность того, что клетка пуста меньше 1/1000000, то p1*p2 уже меньше 1/1000000000000, что уже позволяет забыть о всех членах матожидания, кроме p1+...+pN. (900*899/2 * 1/10000000000 < 1/1000000). Но даже если p1*p2 велико, то можно добавить все попарные вероятности, произведение трех будет уже точно пренебрежимо малым.

demiurg

Я задачу не решал, а отвечал на вопрос "почему".
Среднее суммы равно сумме средних, даже если величин целых n, и все они распределены по-разному. А вероятность клетке быть пустой — это среднее число пустых клеток на доске из одной клетки.

luherstag

 А как в этом рассуждении используется тот факт, что блох столько же, сколько клеток?

demiurg

Написал же, что я задачу я не решал. Для ответа на вопрос блохи вообще не важны.

natunchik

я специально проверял для четырёх клеток, равенство точное.
: правильно ли я понял, что ты предлагаешь рассмотреть матожидание пустоты первой клетки (но на полной доске, видимо, потому что если клетка всего одна, то пустой она не бывает никогда второй, третьей и просуммировать? Но ведь рассматриваемые тобой случайные величины (пустота/непустота и-той клетки) не независимы! Мне совершенно не кажется очевидным, что матожидание суммы равно сумме матожиданий в случае коррелирующих величин.

a101

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

MammonoK

я так и не понял - этому проекту euler нужны аналитические решения? т.е., грубо говоря роль компьютера здесь отводится только для подсчета вероятностей для каждой клетки? можно ведь запустить ее n-ое количество раз, и посмотреть какое распределение получится. :) хотя тут одной минуты маловато будет, конечно.

a101

Если говорить о задаче, я бы решал так. 
Если есть распределение между клетками, где сейчас может быть одна блоха (фиксированная) с какими-то вероятностями, то распределение после колокольчика - это просто ее распределние умножить на какую-то матрицу переходов (она 900 на 900 и легко считается). Дальше не важно сколько было переходов, 50 или 500 - мы эту матрицу довольно легко может возвести в нужную степень (2 логарифма от степени операций * 900^3). Сразу после этого мы имеем распределение по клеткам для каждой блохи, откуда получением вероятностью для каждой клетки, что блох там нет.
Думаю в минуту на С++ влезает вообще без проблем. Да и потери точности только при операциях с double, там еще большой запас по знакам будет.

Vadim46

ему вообще решения не нужны, только ответы.
можно например в уме решать :)
Оставить комментарий
Имя или ник:
Комментарий: