- Markow-Ungleichung
-
In der Wahrscheinlichkeitstheorie gibt die Markow-Ungleichung (nach Andrei Andrejewitsch Markow) eine obere Schranke für die Wahrscheinlichkeit an, dass eine Zufallsvariable eine positive Konstante überschreitet.
Inhaltsverzeichnis
Satz
Sei (Ω,Σ,P) ein Wahrscheinlichkeitsraum und eine reelle 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. Man kann zeigen, dass diese Abschätzung unter gewissen Voraussetzungen sogar optimal ist.
Einzelnachweise
- ↑ Piotr Indyk, Sublinear Time Algorithms for Metric Space Problems, Proceedings of the 31st Symposium on Theory of Computing (STOC'99), 428--434, 1999.
Siehe auch
Wikimedia Foundation.