我如何可以有效计算二项的累计分配的功能?
-
11-09-2019 - |
题
让我们说,我知道的概率"成功"是P.我运行测试N次,我看见S成功。测试是类似的折腾的一个不均加权硬币(或许是头一个成功,尾巴是一个失败)。
我想要知道近似的概率,看到无论是S成功,或一些成果不太可能比S成功。
因此,举例来说,如果P0.3,N为100,并且我得到20个成功的,我正在寻找的概率越来越20 或者更少 成功。
如果没有,P0.3,N为100,并且我得到40取得的成功,我正在寻找的概率越来越40我们更多的成功。
我知道,这个问题涉及寻找该地区的下一二项式的曲线,但是:
- 我的数学-fu是没有达到任务的翻译这一知识纳入有效的代码
- 虽然我理解二项曲线将给出一个确切结果,我得到的印象是,这将是固有的效率低下。一个快速方法计算出一个大致结果就足够了。
我应该强调,这种计算已经够快速,并最好应确定与标准64或128位浮点运算。
我在寻找一个函数,P、S、N和返回的概率。因为我更熟悉代比数学符号,我比较喜欢的是任何答案采用伪码或代码。
解决方案
确切二项分布
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
其他提示
我是在一个项目,我们需要能够计算出的二项综合发展框架的环境中,没有一个因子或伽马功能定义。我花了几周,但最后我来了与下列算法计算的民防部队正(即没有近似需要)。蟒蛇的基本上是好的伪,对吗?
import numpy as np
def binomial_cdf(x,n,p):
cdf = 0
b = 0
for k in range(x+1):
if k > 0:
b += + np.log(n-k+1) - np.log(k)
log_pmf_k = b + k * np.log(p) + (n-k) * np.log(1-p)
cdf += np.exp(log_pmf_k)
return cdf
业绩的尺度与x。对于小价值x,这种解决方案是有关一个数量级的速度比 scipy.stats.binom.cdf
, 类似的性能在周围的x=10 000人。
我不会走进一个充分的推导这种算法,因为计算器不支持MathJax,但主旨,它是第一个确定的以下等值:
- 对于所有的k>0,
sp.misc.comb(n,k) == np.prod([(n-k+1)/k for k in range(1,k+1)])
我们可以改写为:
sp.misc.comb(n,k) == sp.misc.comb(n,k-1) * (n-k+1)/k
或日志的空间:
np.log( sp.misc.comb(n,k) ) == np.log(sp.misc.comb(n,k-1)) + np.log(n-k+1) - np.log(k)
因为民防部队是一个总结PMFs,我们可以使用这种制剂二项计算系数(log是 b
在功能上文)PMF_{x=i}从我们计算系数为PMF_{x=i-1}.这意味着我们可以做的一切内部的一个单一的循环利用蓄电池,我们不需要计算的任何阶乘!
其原因大部分的计算都是在日志的空间,是提高数值的稳定的多项条款,即 p^x
和 (1-p)^(1-x)
有可能是非常大或者非常小,这可能会导致计算错误。
编辑:这是一种新颖的算法?我一直闲逛和关闭,因为在我之前发布此,我越来越想知道,如果我应该写更多的正式和提交给杂志。
我觉得你想要的评估 不完全的功能测试.
那里有一个很好的执行使用一个继续分数表示在"数值的食谱在C",第6章:'特殊功能的'.
我不能完全保证的效率,但这有一个 模块这个
from scipy.stats.distributions import binom
binom.cdf(successes, attempts, chance_of_success_per_attempt)
一个高效率的,更重要的是,数值的稳定算法域中存在的 贝塞尔的曲线 使用计算机辅助设计。它被称为 de可的算法 用于评估 伯恩斯坦多项式 用来定义贝塞尔的曲线。
我相信,我是只允许一个链接每答案,所以开始 维基百科-伯恩斯坦多项式
注意到非常密切的关系之间的二项分布和伯恩斯坦多项式。然后通过点击的链接de可的算法。
可以说我知道的概率投掷的头一个特别的硬币是P.什么样的的概率是我扔的 硬币T次和获得至少 S头?
- 设置n=T
- Beta组[i]=0用于我=0,...S-1
- Beta组[i]=1i=S...T
- 设置t=p
- 评估B(t)使用可de
或者在大多数S头?
- 设置n=T
- Beta组[i]=1i=0,...S
- Beta组[i]=0用于我=S+1,...T
- 设置t=p
- 评估B(t)使用可de
开放源代码可能存在了。 创建曲线 (非统一合理的B样的曲线)是一个概括的贝塞尔的曲线和广泛应用于加元。尝试openNurbs(许可证,是非常自由)或者失败,开级(一个有些不自由和不透明的许可证).这两个工具包是用C++,虽然,请参考,.净绑定的存在。
如果您使用的是蟒蛇,没有必要编写它自己。这有你的包括:
from scipy.stats import binom
# probability that you get 20 or less successes out of 100, when p=0.3
binom.cdf(20, 100, 0.3)
>>> 0.016462853241869434
# probability that you get exactly 20 successes out of 100, when p=0.3
binom.pmf(20, 100, 0.3)
>>> 0.0075756449257260777
从部分的你的问题"至少获得S头"你想要的累计二项分配的功能。看看 http://en.wikipedia.org/wiki/Binomial_distribution 为方程式,它描述为在"正规化不完整的测试功能"(如已经回答).如果你只是想要计算答案没有实现整个自己的解决方案,GNU科学图书馆提供的功能:gsl_cdf_binomial_P和gsl_cdf_binomial_Q.
import numpy as np
np.random.seed(1)
x=np.random.binomial(20,0.6,10000) #20 flips of coin,probability of
heads percentage and 10000 times
done.
sum(x>12)/len(x)
The output is 41% of times we got 12 heads.