Как эффективно моделировать сумму случайных величин Бернулли?

Question

Я использую Perl для моделирования случайной величины (Y), которая является суммой приблизительно ~ 15-40k независимых случайных величин Бернулли (X_i), каждая с различной вероятностью успеха (p_i).Формально Y=Sum{X_i}, где Pr(X_i=1)=p_i и Pr(X_i=0)=1-p_i.

. Меня интересуют быстро отвечающие запросы, такие как Pr(Y<=k) (где указано k).

В настоящее время яиспользовать случайные симуляции для ответа на такие запросы.Я случайным образом рисую каждый X_i в соответствии с p_i, затем суммирую все X_i значения, чтобы получить Y'.Я повторяю этот процесс несколько тысяч раз и возвращаю долю раз Pr(Y'<=k).

Очевидно, что это не совсем точно, хотя точность значительно увеличивается с увеличением количества использованных имитаций.

Можете ли вы придумать разумный способ получить точную вероятность?

Answer 1

Во-первых, я бы не использовал для этой цели встроенный rand, который слишком надежен для реализации базовой библиотеки C (см., Например, мой пост в блоге , указывающий, чтодиапазон rand в Windows имеет мощность 32 768).

Чтобы использовать подход Монте-Карло, я бы начал с известного хорошего генератора случайных чисел, такого как Rand :: MersenneTwister или просто использовал один из Random.org услуги и предварительное вычисление CDF для Y при условии, что Y довольно стабильно.Если каждый Y используется только один раз, предварительное вычисление CDF явно бессмысленно.

Цитируя Wikipedia :

В теории вероятностей и статистике, Пуассоновское биномиальное распределение - это дискретное распределение вероятностей суммы независимых испытаний Бернулли.

Другими словами, это распределение вероятностей числа успехов впоследовательность n независимых да / нет экспериментов с вероятностями успеха p1,…, pn .(выделение мое)

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

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

Answer 2

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

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

Answer 3

Насколько я помню, не должно ли это закончиться асимптотически как нормальное распределение?Смотрите также эту ветку новостной группы: http://newsgroups.derkeiler.com/Archive/Sci/sci.stat.consult/2008-05/msg00146.html

Если это так, вы можете использовать Статистика :: Распределение :: Нормальная .