（Python）Markov，Chebyshev，Chernoff上界函数

Question

在我的学习道路上，我只能做一件事。在

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

Formulas

任务是分别为每个不等式编写三个函数。它们必须以n , p and c为输入，并返回由上述Markov、Chebyshev和Chernoff不等式给出的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

我完全卡住了。我就是不知道如何把所有的数学都插入函数中（或者在这里如何进行算法思考）。如果有人能帮我，那将是很大的帮助！在

任务条件不允许p.s.和所有LIB，除非数学实验在

Answer 1

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

输入值和派生值：

• 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与{}之间的关系。在

马尔可夫不等式

要求您实现Markov(n,p,c)，它将返回P(X>=c*m)的上限。从开始

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

很明显，a == c，你得到{}。嗯，那只是

^{pr2}$

那很简单，不是吗？在

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

首先，让我们验证一下

^{3}$

那么

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>=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