(Python) Markov, Chebyshev, Chernoff obere Grenze Funktionen

Question

Ich bin mit einer Aufgabe auf meinem Lernweg stecken.

Für die Binomialverteilung X~Bp, n mit Mittelwert μ = np und Varianz σ**2=np(1−p) möchten wir die Wahrscheinlichkeit P(X≥c⋅μ) for c≥1 nach oben begrenzen. Drei Grenzen eingeführt:

Formulas

Die Aufgabe drei Funktionen jeweils für jede der Ungleichheiten zu schreiben ist. Sie müssen n , p and c als Eingaben nehmen und die oberen Grenzen für P(X≥c⋅np), die durch die obigen Markov-, Chebyshev- und Chernoff-Ungleichungen gegeben sind, als Ausgaben zurückgeben.

Und es ist ein Beispiel für IO:

Code:

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 

Ich bin ganz fest. Ich kann einfach nicht herausfinden, wie man all diese Mathematik in Funktionen einfügt (oder wie man hier algorithmisch denkt). Wenn mir jemand helfen könnte, wäre das eine große Hilfe!

p.s. und alle Libs sind nicht durch Aufgabe Bedingungen außer math.exp erlaubt

Answer 1

Ok, schauen wir uns an, was gegeben ist:

Eingang und abgeleitete Werte:

• 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

Sie haben mehrere Ungleichheiten der Form P(X>=a*m) und Sie müssen Grenzen für den Begriff P(X>=c*m), zur Verfügung zu stellen, so dass Sie denken müssen, wie a-c in allen Fällen bezieht.

Markov Ungleichung: P(X>=a*m) <= 1/a

Sie werden gefragt, Markov(n,p,c) zu implementieren, die die Obergrenze für P(X>=c*m) zurückkehren wird. Da von

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

es klar, dass a == c, erhalten Sie 1/a = 1/c. Nun, das ist nur

def Markov(n, p, c): 
    return 1.0/c 

>>> Markov(100,0.2,1.5) 
0.6666666666666666 

Das war einfach, nicht wahr?

Chernoff Ungleichheit besagt, dass P(X>=(1+d)*m) <= exp(-d**2/(2+d)*m)

Lassen Sie uns zuerst überprüfen, ob, wenn

P(X>=(1+d)*m) 
= P(X>=c *m) 

dann

1+d = c 
    d = c-1 

Das uns alles gibt uns die uper gebunden berechnen müssen:

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 Ungleichheit Grenzen P(X>=m+k*s) von 1/k**2

Also noch einmal, wenn

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

dann

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

Dann ist es gerade nach vorne

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 

zu implementieren