(Python) Markov，Chebyshev，Chernoff上界函数

Question

在我的学习道路上，我被困在一项任务中。

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

公式

任务是分别为每个不等式编写三个函数。它们必须以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

我完全被困住了。我只是想不出如何把所有的数学都插入到函数中(或者如何在这里用算法思考)。如果有人能帮我，那会有很大帮助的！

附注：除math.exp之外，任务条件不允许所有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与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

这给了我们计算uper界所需的一切：

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

Chebyshev不等式界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