Dieser Artikel oder Abschnitt bedarf einer grundsatzlichen Uberarbeitung Der Artikel betrachtet zur Zeit nur zwei der zahlreich existierenden Chernoff Ungleichungen insbesondere nur fur Bernoulli Experimente mit identischem Parameter im allgemeinen ist dies jedoch keine Voraussetzung fur Chernoff Schranken wobei auch fur in diesem Falle scharfere Chernoff Schranken existieren Bitte hilf mit ihn zu verbessern und entferne anschliessend diese Markierung In der Wahrscheinlichkeitstheorie beschreibt der Begriff Chernoff Ungleichung eine obere Schranke fur die Wahrscheinlichkeit dass eine Sequenz unabhangiger Zufallsvariablen von ihrer erwarteten Anzahl an Erfolgen abweicht Die Ungleichung wurde nach Herman Chernoff benannt geht jedoch auf Herman Rubin zuruck 1 2 Die Chernoff Ungleichung ist ein vielseitiges und vielfach verwendetes Hilfsmittel bei der Analyse von randomisierten Algorithmen in der Informatik Inhaltsverzeichnis 1 Allgemeine Formulierung 2 Chernoff Ungleichung fur Binomialverteilungen 2 1 Beweis 2 1 1 Erste Chernoff Schranke 2 1 2 Zweite Chernoff Schranke 3 Chernoff Ungleichung mithilfe der Standardabweichung 4 Beispiele 5 Literatur 6 EinzelnachweiseAllgemeine Formulierung BearbeitenDie allgemeinste Form der Chernoff Ungleichung fur eine Zufallsvariable X displaystyle X nbsp erhalt man durch Anwenden der Markov Ungleichung auf e t X displaystyle e tX nbsp Fur alle t gt 0 displaystyle t gt 0 nbsp gilt Pr X a Pr e t X e t a E e t X e t a displaystyle Pr X geq a Pr e t cdot X geq e t cdot a leq frac operatorname E left e t cdot X right e t cdot a nbsp und somit auch Pr X a inf t gt 0 E e t X e t a displaystyle Pr X geq a leq inf t gt 0 frac operatorname E left e t cdot X right e t cdot a nbsp Diese Form der Chernoff Ungleichung verwendet die momenterzeugende Funktion von X displaystyle X nbsp Fur eine gegebene Verteilung von X displaystyle X nbsp kann durch Ausrechnen dieser Funktion eine spezifische Chernoff Ungleichung errechnet werden Chernoff Ungleichung fur Binomialverteilungen BearbeitenSei X 1 X 2 X n displaystyle X 1 X 2 ldots X n nbsp eine Sequenz von n displaystyle n nbsp unabhangigen Bernoulli Experimenten mit P X i 1 p displaystyle P X i 1 p nbsp und P X i 0 1 p displaystyle P X i 0 1 p nbsp Demnach beschreibt p n displaystyle pn nbsp die erwartete Anzahl an Erfolgen X i 1 displaystyle X i 1 nbsp des Experiments 1 Dann gilt fur jedes d gt 0 displaystyle delta gt 0 nbsp P X i 1 d p n exp min d d 2 3 p n displaystyle P left sum X i geq 1 delta cdot pn right leq exp left frac min delta delta 2 3 pn right nbsp dd 2 Fur jedes d 0 1 displaystyle delta in 0 1 nbsp gilt P X i 1 d p n exp d 2 2 p n displaystyle P left sum X i leq 1 delta cdot pn right leq exp left frac delta 2 2 pn right nbsp dd Beweis Bearbeiten Erste Chernoff Schranke Bearbeiten Sei t gt 0 displaystyle t gt 0 nbsp eine zunachst beliebige Konstante Bezeichne Y displaystyle Y nbsp im Folgenden zur Vereinfachung der Schreibweise eine neue Zufallsvariable vermoge Y exp t X i displaystyle textstyle Y exp left t sum X i right nbsp Auf Grund der Monotonie der Abbildung x exp t x displaystyle x mapsto exp tx nbsp folgt dann P X i 1 d p n P Y exp t 1 d p n P Y k E Y 1 k displaystyle P left sum X i geq 1 delta cdot pn right P left Y geq exp left t 1 delta cdot pn right right P left Y geq k textrm E left Y right right leq frac 1 k nbsp wobei k displaystyle k nbsp als k exp t 1 d p n E Y displaystyle k tfrac exp t 1 delta pn textrm E Y nbsp definiert ist und die letzte Abschatzung mittels Markow Ungleichung folgt Nun gilt E exp t X i 1 p e 0 p e t 1 e t 1 p displaystyle textrm E left exp tX i right 1 p e 0 pe t 1 e t 1 p nbsp und somit E Y E exp t X i E exp t X i E exp t X i 1 e t 1 p n displaystyle textrm E left Y right textrm E left exp t sum X i right textrm E left prod exp tX i right prod textrm E left exp tX i right left 1 e t 1 p right n nbsp Damit folgt 1 k e t 1 d p n 1 e t 1 p n e t 1 d p n e e t 1 p n e t 1 d p n e t 1 p n displaystyle frac 1 k e t 1 delta pn left 1 e t 1 p right n leq e t 1 delta pn cdot e e t 1 pn e t 1 delta pn e t 1 pn nbsp Betrachte nun t log 1 d displaystyle t log 1 delta nbsp Dann gilt 1 k e log 1 d 1 d p n d p n e d 1 d log 1 d p n displaystyle frac 1 k leq e log 1 delta 1 delta pn delta pn e delta 1 delta log 1 delta pn nbsp Fur einen Teil des Exponenten des rechten Terms L d 1 d log 1 d displaystyle L delta 1 delta log 1 delta nbsp kann man mittels Kurvendiskussion und Taylor Reihenentwicklung zeigen dass stets L d d 1 3 min d d 2 displaystyle L delta geq delta tfrac 1 3 min delta delta 2 nbsp gilt Auf Grund der Monotonie der Exponentialfunktion gilt 1 k e d d 1 3 min d d 2 p n exp min d d 2 3 p n displaystyle frac 1 k leq e delta delta frac 1 3 min delta delta 2 pn exp left frac min delta delta 2 3 pn right nbsp Zusammen mit der ersten Abschatzung folgt die Behauptung Zweite Chernoff Schranke Bearbeiten Der Beweis der zweiten Schranke folgt technisch analog zur ersten Schranke Chernoff Ungleichung mithilfe der Standardabweichung BearbeitenEine allgemeine Variante der Chernoff Ungleichung lasst sich mittels der Standardabweichung formulieren Seien X 1 X 2 X n displaystyle X 1 X 2 ldots X n nbsp diskrete unabhangige Zufallsvariablen mit E X i 0 displaystyle textrm E X i 0 nbsp und X i 1 displaystyle X i leq 1 nbsp Bezeichne s 2 displaystyle sigma 2 nbsp die Varianz von X X i displaystyle textstyle X sum X i nbsp Dann gilt fur jedes 0 lt l 2 s displaystyle 0 lt lambda leq 2 sigma nbsp P X i l s 2 exp l 2 4 displaystyle P left left sum X i right geq lambda sigma right leq 2 exp left frac lambda 2 4 right nbsp Der Beweis ist technisch analog zu dem oben gezeigten Beweis Beispiele BearbeitenBetrachte die folgende Frage Wie wahrscheinlich ist es beim zehnmaligen Wurf einer fairen Munze wenigstens siebenmal das Ergebnis Zahl zu erhalten Die Munzwurfe stellen Bernoulli Experimente X 1 X 2 X 10 displaystyle X 1 X 2 ldots X 10 nbsp mit p n 1 2 10 5 displaystyle pn tfrac 1 2 cdot 10 5 nbsp dar Somit folgt nach der ersten Chernoff Ungleichung P X i 7 P X i 1 4 10 5 displaystyle P left sum X i geq 7 right P left sum X i geq left 1 frac 4 10 right cdot 5 right nbsp exp min 4 10 16 100 3 5 exp 4 15 0 766 displaystyle leq exp left frac min frac 4 10 frac 16 100 3 cdot 5 right exp left frac 4 15 right approx 0 766 ldots nbsp Man formuliere das obige Beispiel nur leicht um und frage stattdessen Wie wahrscheinlich ist es bei hundertmaligem fairen Munzwurf wenigstens siebzigmal das Ergebnis Zahl zu erhalten Sofort erweist sich die erste Chernoff Schranke als deutlich starker P X i 70 P X i 1 4 10 50 displaystyle P left sum X i geq 70 right P left sum X i geq left 1 frac 4 10 right cdot 50 right nbsp exp min 4 10 16 100 3 50 exp 8 3 0 069 displaystyle leq exp left frac min frac 4 10 frac 16 100 3 cdot 50 right exp left frac 8 3 right approx 0 069 ldots nbsp Literatur BearbeitenChristian Schindelhauer Algorithmen fur Peer to Peer Netzwerke Vorlesungsmaterialien http wwwcs upb de cs ag madh WWW Teaching 2004SS AlgoP2P skript html Universitat Paderborn 2004 Kirill Levchenko Notizen http www cs ucsd edu klevchen techniques chernoff pdfEinzelnachweise Bearbeiten John Bather A Conversation with Herman Chernoff In Statistical Science 11 Jahrgang Nr 4 November 1996 S 335 350 doi 10 1214 ss 1032280306 Herman Chernoff A career in statistics In Xihong Lin Christian Genest David L Banks Geert Molenberghs David W Scott Jane Ling Wang Hrsg Past Present and Future of Statistics CRC Press 2014 ISBN 978 1 4822 0496 4 S 35 crcpress com Abgerufen von https de wikipedia org w index php title Chernoff Ungleichung amp oldid 237794966
