Diskussion:Chernoff-Ungleichung

Bei den Beispielen ist wohl was schiefgegangen. Die Wahrscheinlichkeit beim zehnmaligen Münzwurf für mehr als fünfmal Zahl kann nicht größer als 0,5 werden... --213.54.216.54 11:45, 18. Sep 2005 (CEST)

Stimmt, aber die Chernoff-Ungleichung ist nur eine (oft recht schlechte) Schranke, sie macht keine Aussage über Gleichheit. --Rubik-wuerfel 22:55, 30. Okt. 2008 (CET)

andere Schreibweise?

ich habe die chernoff ungleichung in folgender form gesehen: $\operatorname {E} (e^{sX}>=\alpha )<=\psi _{X}(s)/\alpha$

ist das äquivalent zu der im artikel? kann da leider nicht wirklich einen zusammenhang sehen. (psi ist die momentenerzeugende funktion) --Manfreeed 20:43, 9. Nov 2005 (CET)

summe bernoulliverteilter zufallsvariable

nennt man gewoehnlich auch binomialverteilte zufallsvariable... (nicht signierter Beitrag von 85.180.146.74 (Diskussion | Beiträge) 13:45, 19. Sep. 2009 (CEST))

Aber nur, falls diese bernoulliverteilten Zufallsvariablen alle dieselbe Erfolgswahrscheinlichkeit haben. Es gibt auch Formen der Ungleichung, die nur ein wenig allgemeiner sind und es zulassen, dass sich die Wahrscheinlichkeiten unterscheiden. --Iksbat (Diskussion) 21:29, 1. Nov. 2017 (CET)

Ist das überhaupt die Chernoff Schranke?

Mir kommt das suspekt vor. Ich habe die Ungleichung (für Binomialverteilungen) in anderer Form kennengelernt, nämlich in der, wie sie sich auch in der englischen Variante findet:

$\Pr[X\geq (1+\delta )np]\leq {\frac {e^{\delta np}}{(1+\delta )^{(1+\delta )np}}}=\left[{\frac {e^{\delta }}{(1+\delta )^{1+\delta }}}\right]^{np}$

Für p := 0.001 bekomme ich mit dieser Variante eine deutlich schärfere Schranke als mit der aus dem deutschen Artikel. --Iksbat (Diskussion) 21:29, 1. Nov. 2017 (CET)

Der Artikel ist im Vergleich zur englischen Variante leider sehr unvollständig. Der deutsche Artikel betrachtet zur Zeit nur die simplen Chernoff-Ungleichung und nur für Binomialverteilungen. Die simplen Schranken aus der deutschen Wikipedia findest du übrigens auch im englischen Artikel en:Chernoff_bound#Multiplicative form (relative error).

Richtig sind sowohl die Schranken im Artikel als auch deine Schranke. Beide werden in der Literatur als Chernoff bounds bezeichnet -- Wdvorak (Diskussion) 16:20, 1. Nov. 2017 (CET)

Interessant. Man müsste aber doch zumindest anmerken, dass der deutsche Artikel stark unvollständig ist und überarbeitet werden sollte, um zu verhindern, dass sich Leute an dieser einen Gleichung festbeißen, obwohl es eine unter dem gleichen Namen geläufige, schärfere gibt. --Iksbat (Diskussion) 21:29, 1. Nov. 2017 (CET)

Du hast natürlich Recht. Ich habe mal eine Überabeiten-Baustein im Artikel gesetzt. Vielleicht findet sich ja jemand um das einzuarbeiten -- Wdvorak (Diskussion) 17:25, 2. Nov. 2017 (CET)

Ich würde das dann irgendwann dieses Jahr mal machen, orientiert an http://www14.in.tum.de/lehre/2014SS/dwt/2014-dwt.pdf Satz 64 66 und daraus folgend Korollar 68. Letzteres würde insbesondere die bis her erwähnten Schranken als Folgerung der Chernoff-Ungleichung subsumieren --Iksbat (Diskussion) 23:36, 3. Nov. 2017 (CET)

Das ist dann natürlich immer noch auf Sequenzen von unabhängigen, bernoulliverteilten Zufallsvariablen beschränkt - mit dem Rest kenne ich mich leider nicht aus --Iksbat (Diskussion) 23:40, 3. Nov. 2017 (CET)

Ich habe mich auch gefragt, welche anderen Fälle außer die im Baustein erwähnten "Bernoulli-Experimente mit identischem Parameter" gemeint sein könnten. Das Einzige was mir einfiel war die Hoeffding-Ungleichung (die bereits einen eigenen Artikel hat) oder noch allgemeiner die Ungleichung von Azuma-Hoeffding. Beides würde ich aber nicht als Variante der Chernoff-Ungleichung sehen. @Wdvorak: Welche hattest du genau im Sinn? @Iksbat: Toll, dass sich bereits ein Autor für die nötigen Veränderungen gefunden hat. Viel Erfolg! Liebe Grüße -- 2A02:8109:9400:474:A58C:583C:8826:4DFE 10:45, 24. Nov. 2017 (CET)

mein "Problem" ist der "identische Parameter": im Artikel haben alle Bernoulli-Experimente die gleiche Wahrscheinlichkeit und das Ganze ist damit auf Binomialverteilungen beschränkt. Ich kenne Chernoff Ungleichungen hauptsächlich aus der Analyse von (randomisierten) Algorithmen, die Varianten die dort verwendet werden betrachten Sequenzen von unabhängigen, bernoulliverteilten Zufallsvariablen (die aber verschieden Verteilungen folgen). Ich hatte also sowas wie hier im Sinne en:Chernoff_bound#Multiplicative form (relative error)). Im englischen Artikel gibt es dann auch noch die "generic bound", die ist mir aber sonst noch nicht untergekommen lg -- Wdvorak (Diskussion) 15:46, 24. Nov. 2017 (CET)

@Iksbat: wäre super wenn du das einbaust. Ich denke die Schranken aus dem Skriptum würden den Artikel schon deutlich aufwerten. lg -- Wdvorak (Diskussion) 15:46, 24. Nov. 2017 (CET)