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

Question

我在学习道路上遇到了一项任务。

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

Formulas

任务是分别为每个不等式写三个函数。他们必须将 n , p and c 作为输入，return 由上述马尔可夫、切比雪夫和切尔诺夫不等式给出的 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。任务条件不允许所有库，除了 math.exp

Answer 1

好的，让我们看看给出的内容：

输入值和派生值：

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

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

你被要求实现 Markov(n,p,c)，这将 return 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) Markov, Chebyshev, Chernoff upper bound functions