Вычисление вероятности суммы распределений

[LTU]

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

Имеется любое дискретное распределение. Например $P(X=0) = 0.4, P(X=1) = 0.4, P(X=2) = 0.2$. Требуется программным образом вычислять вероятность суммы $t$ данных случайных величин (независимы, одинаково распределены). То есть $p^*(n,t) = P(X_1 + X_2 + ... + X_t = n)$. $S(2) = X_1 + X_2$. Например $p^*(4,2) = P(S(2) = 4) = P(X_1 = 2, X_2 = 2) = 0.2 * 0.2$. Разумеется, это очень простой случай, но принцип такой. У меня получилось реализовать это с помощью рекурсии, но проблема в том, что при t > 10 получается огромное число рекурсивных вызовов функций, около $n^t$, что делает невозможным расчет для $t > 10$ и $n > 10$. Может стоит апроксимировать нормальным распределением?

[Alexey1]

В принципе да, можно использовать Центральную Предельную Теорему.

[LTU]

То есть быстрых алгоритмов, которые были бы реализованы без использования апроксимаций, не существует?

[Gortaur]

Что у Вас фиксировано? Число значений случайно величины (только 3) или оно тоже может изменяться? Если они распределены так, как Вы говорите, то можно попробовать использовать что-нибудь вроде биноминального распределения.

[--mS--]

Gortaur в сообщении #316906 писал(а):

Если они распределены так, как Вы говорите, то можно попробовать использовать что-нибудь вроде биноминального распределения.

Приведенное распределение не является биномИАльным.

[PAV]

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

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

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

А далее делаем так. Сначала считаем распределение сумм, в которых счисло слагаемых есть степень двойки. То есть сначала сумму двух исходных распределений, затем - четырех (разумеется, складывая уже найденные 2+2), затем 8 как 4+4. Если, например, надо в итоге найти сумму 10 слагаемых, то теперь остается только сложить уже найденные 8+2. Итого всего 4 вызова данной функции (из которых три складывают одинаковые распределения) и никаких рекурсий.

Вычисляться должно влет.

[Евгений Машеров]

Вам нужно быстро считать свёртку. Фурье от свёртки равно произведению Фурье от свёртываемых. А так как n одинаковых - то Фурье просто возводится в степень.