(Python) Markov, Chebyshev, Chernoff 상한 함수

Question

내 학습 경로에 하나의 작업이 있습니다.

평균 μ = np이고 분산이 σ**2=np(1−p) 인 이항 분포 X ~ Bp에 대해 우리는 확률을 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. 주어진 무슨 모든 libs와는 math.exp 제외하고는 작업 조건에 의해 허용되지 않습니다

Answer 1

좋아, 이제 살펴 보자 :

입력 및 파생 값 :

• n = 100
• p = 0.2
• c = 1.5
• m = n*p = 100 * 0.2 = 20
• 01

2,354,512,146,821,128,367,413,210

s = sqrt(s2) = sqrt(16) = 4 당신은 형태 P(X>=a*m)의 여러 불평등이 있고 a이 모든 경우에 c 관련이 있는지 생각해야합니다, 그래서 당신은 용어 P(X>=c*m)에 대한 경계를 제공해야합니다.

마르코프 불평등는 : P(X>=a*m) <= 1/a

당신은 P(X>=c*m)에 대한 상한을 반환합니다 Markov(n,p,c)을 구현하도록 요청하고 있습니다.

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 바운드 계산해야하는지 확인 할 수 있음을 주장한다 :

똑바로 앞으로 구현하는 것 다음

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

그런

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

경우

체비 쇼프 불평등 경계 P(X>=m+k*s), 그래서 다시

1/k**2에 의해

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