Как я могу эффективно вычислить биномиальную кумулятивную функцию распределения?
По моему опыту, иногда простое решение к , называют изображения согласно первичному ключу . Таким образом, легко найти изображение, которое принадлежит конкретной записи, и наоборот. Но в то же время Вы не храните ничто об изображении в базе данных.
6 ответов
Точное биномиальное распределение
def factorial(n):
if n < 2: return 1
return reduce(lambda x, y: x*y, xrange(2, int(n)+1))
def prob(s, p, n):
x = 1.0 - p
a = n - s
b = s + 1
c = a + b - 1
prob = 0.0
for j in xrange(a, c + 1):
prob += factorial(c) / (factorial(j)*factorial(c-j)) \
* x**j * (1 - x)**(c-j)
return prob
>>> prob(20, 0.3, 100)
0.016462853241869437
>>> 1-prob(40-1, 0.3, 100)
0.020988576003924564
Нормальная оценка, подходит для больших n
import math
def erf(z):
t = 1.0 / (1.0 + 0.5 * abs(z))
# use Horner's method
ans = 1 - t * math.exp( -z*z - 1.26551223 +
t * ( 1.00002368 +
t * ( 0.37409196 +
t * ( 0.09678418 +
t * (-0.18628806 +
t * ( 0.27886807 +
t * (-1.13520398 +
t * ( 1.48851587 +
t * (-0.82215223 +
t * ( 0.17087277))))))))))
if z >= 0.0:
return ans
else:
return -ans
def normal_estimate(s, p, n):
u = n * p
o = (u * (1-p)) ** 0.5
return 0.5 * (1 + erf((s-u)/(o*2**0.5)))
>>> normal_estimate(20, 0.3, 100)
0.014548164531920815
>>> 1-normal_estimate(40-1, 0.3, 100)
0.024767304545069813
Оценка Пуассона: подходит для больших n и малых p
import math
def poisson(s,p,n):
L = n*p
sum = 0
for i in xrange(0, s+1):
sum += L**i/factorial(i)
return sum*math.e**(-L)
>>> poisson(20, 0.3, 100)
0.013411150012837811
>>> 1-poisson(40-1, 0.3, 100)
0.046253037645840323
Я думаю, вы хотите оценить неполную бета-функцию .
В «Числовых рецептах на языке C», глава 6, есть хорошая реализация с использованием представления непрерывной дроби: «Специальные функции».
Из части вашего вопроса «получить не менее S голов» вам нужна кумулятивная функция биномиального распределения. См. http://en.wikipedia.org/wiki/Binomial_distribution , где описано уравнение, которое описывается в терминах «регуляризованной неполной бета-функции» (как уже было сказано). Если вы просто хотите вычислить ответ без необходимости самостоятельно реализовывать все решение, Научная библиотека GNU предоставляет функции: gsl_cdf_binomial_P и gsl_cdf_binomial_Q.
В области кривых Безье , используемых в автоматизированном проектировании, существует эффективный и, что более важно, численный стабильный алгоритм. Он называется алгоритмом де Кастельжау , который используется для оценки многочленов Бернштейна , используемых для определения кривых Безье.
Я считаю, что мне разрешена только одна ссылка на ответ, поэтому начните с Википедия - Полиномы Бернштейна
Обратите внимание на очень тесную взаимосвязь между биномиальным распределением и полиномами Бернштейна. Затем перейдите по ссылке на алгоритм де Кастельжау.
Допустим, я знаю, что вероятность выпадения орла с конкретной монетой равна P. Какова вероятность того, что я брошу монету T раз и получить не менее S головок?
- Установить n = T
- Установить beta [i] = 0 для i = 0, ... S - 1
- Установить beta [i] = 1 для i = S, ... T
- Установить t = p
- Оценить B (t) с использованием де Кастельжау
или не более S головок?
- Установить n = T
- Установить beta [i] = 1 для i = 0,. .. S
- Установить beta [i] = 0 для i = S + 1, ... T
- Установить t = p
- Оценить B (t) с помощью de Casteljau
Открытый исходный код, вероятно, существует уже. NURBS Curves (Неоднородные рациональные кривые B-сплайна) являются обобщением кривых Безье и широко используются в САПР. Попробуйте openNurbs (лицензия очень либеральная) или, в случае неудачи, Open CASCADE (несколько менее либеральная и непрозрачная лицензия). Оба инструментария написаны на C ++, однако существуют привязки IIRC, .NET.
The DCDFLIB Project has C# functions (wrappers around C code) to evaluate many CDF functions, including the binomial distribution. You can find the original C and FORTRAN code here. This code is well tested and accurate.
If you want to write your own code to avoid being dependent on an external library, you could use the normal approximation to the binomial mentioned in other answers. Here are some notes on how good the approximation is under various circumstances. If you go that route and need code to compute the normal CDF, here's Python code for doing that. It's only about a dozen lines of code and could easily be ported to any other language. But if you want high accuracy and efficient code, you're better off using third party code like DCDFLIB. Several man-years went into producing that library.