(Python) 马尔科夫、切比雪夫、切尔诺夫上界函数

Question

在我的学习路径上，我被一项任务困住了。

对于二项式分布 X?Bp,n，均值为 ?=np 且方差为 ?**2=np(1?p)，我们希望为概率设置上限 P(X?c??) for c?1。引入了三个边界：

公式

任务是分别为每个不等式编写三个函数。它们必须 将上述马尔可夫、切比雪夫和切尔诺夫不等式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

我完全被困住了。我只是不知道如何将所有这些数学插入到函数中（或者如何在这里进行算法思考）。如果有人可以帮助我，那将是非常有帮助的！

除 math.exp 外，任务条件不允许使用 ps 和所有库

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

那很容易，不是吗？

切尔诺夫不等式表明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