- Markov-Ungleichung
-
In der Wahrscheinlichkeitstheorie gibt die Markow-Ungleichung (nach Andrei Andrejewitsch Markow) eine obere Schranke für die Wahrscheinlichkeit an, dass eine Zufallsvariable größer einer positiven Konstante ist.
Inhaltsverzeichnis
Satz
Sei (Ω,σ(Ω),P) ein Wahrscheinlichkeitsraum und eine reele Zufallsvariable und a eine positive, reellwertige Konstante und ferner monoton wachsende Funktion. Die allgemeine Markow-Ungleichung besagt dann:
Beweis
Sei IA(x) die charakteristische Funktion der Menge A. Dann gilt:
Varianten
- Setzt man h(x) = x und betrachtet die reelle Zufallsvariable | X | , so erhält man den bekannten Spezialfall der Markow-Ungleichung
- Betrachtet man für ein c > 0, so folgt der bekannte Spezialfall der Markow-Ungleichung, welcher die Wahrscheinlichkeit für das c-fache Übertreffen des Erwartungswertes begrenzt:
- Ist h(x) = x2 und wendet man die Markow-Ungleichung auf eine Zufallsvariable Y = X − E[X] an, so erhält man eine Version der Tschebyschow-Ungleichung.
- Für beschränkte Zufallsvariablen existiert die folgende Markow-artige Schranke für die Wahrscheinlichkeit, dass eine Zufallsvariable ihren Erwartungswert um den Faktor (1 − c) unterbietet. D.h., seien und sei X eine Zufallsvariable mit und . Dann gilt für alle c > 0:
- Der Beweis dieser Aussage ist ähnlich dem Beweis der Markow-Ungleichung.[1]
- Wählt man h(x) = etx, erhält man für geeignetes t eine sehr gute Abschätzung. Mann kann zeigen, dass diese Abschätzung unter gewissen Voraussetzungen sogar optimal ist.
Beispiele
Betrachte die folgende Frage: Wie wahrscheinlich ist es, bei einem Würfelwurf wenigstens eine 4 zu würfeln? Es sei X das Ergebnis des Würfelwurfes mit E[X] = 3,5. Dann folgt mit h(x) = x als identische Abbildung und mit a = 4 durch die Markow-Ungleichung:
- .
Einzelnachweise
- ↑ Piotr Indyk, Sublinear Time Algorithms for Metric Space Problems, Proceedings of the 31st Symposium on Theory of Computing (STOC'99), 428--434, 1999.
Wikimedia Foundation.