python - (Python)Markov，Chebyshev，Chernoff上限函数

我的学习道路上只有一项任务。

对于均值μ= np且方差σ**2=np(1−p)的二项式分布X〜Bp，n，我们希望将概率P(X≥c⋅μ) for c≥1上限。
引入了三个界限：

Formulas

任务是为每个不等式分别编写三个函数。他们必须将n , p and c作为输入，并返回上述马尔可夫，切比雪夫和切尔诺夫不等式给出的P(X≥c⋅np)上限作为输出。

还有一个IO的示例：

码：

print Markov(100.,0.2,1.5)

print Chebyshev(100.,0.2,1.5)

print Chernoff(100.,0.2,1.5)

Output

0.6666666666666666

0.16

0.1353352832366127

我完全被困住了。我只是想不通如何将所有数学运算插入函数中（或在此处如何算法思考）。如果有人可以帮助我，那将是极大的帮助！

ps。任务条件不允许所有库，只有math.exp除外

最佳答案

好的，让我们看看给出了什么：

输入和派生值：


n = 100
p = 0.2
c = 1.5
m = n*p = 100 * 0.2 = 20
s2 = n*p*(1-p) = 16
s = sqrt(s2) = sqrt(16) = 4


您具有形式为P(X>=a*m)的多个不等式，并且需要为术语P(X>=c*m)提供界限，因此您需要考虑在所有情况下a与c的关系。

马尔可夫不等式：P(X>=a*m) <= 1/a

系统要求您实现Markov(n,p,c)，该方法将返回P(X>=c*m)的上限。自从

  P(X>=a*m)
= P(X>=c*m)

很明显a == c，您得到1/a = 1/c。好吧，那只是

def Markov(n, p, c):
  return 1.0/c

>>> Markov(100,0.2,1.5)
0.6666666666666666

那很容易，不是吗？

Chernoff不等式指出P(X>=(1+d)*m) <= exp(-d**2/(2+d)*m)

首先，让我们验证一下

  P(X>=(1+d)*m)
= P(X>=c    *m)

然后

1+d = c
  d = c-1

这为我们提供了计算上限所需的一切：

def Chernoff(n, p, c):
  d = c-1
  m = n*p
  return math.exp(-d**2/(2+d)*m)

>>> Chernoff(100,0.2,1.5)
0.1353352832366127

切比雪夫不等式边界P(X>=m+k*s)由1/k**2

再说一次，如果

  P(X>=c*m)
= P(X>=m+k*s)

然后

c*m     = m+k*s
m*(c-1) = k*s
k       = m*(c-1)/s

然后直接实施

def Chebyshev(n, p, c):
  m = n*p
  s = math.sqrt(n*p*(1-p))
  k = m*(c-1)/s
  return 1/k**2

>>> Chebyshev(100,0.2,1.5)
0.16

关于python - (Python)Markov，Chebyshev，Chernoff上限函数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47953098/