Markow-Ungleichung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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.

Satz[Bearbeiten]

Sei (\Omega,\Sigma,P) ein Wahrscheinlichkeitsraum und X:\Omega \rightarrow \mathbb{R} eine reellwertige Zufallsvariable und a eine positive, reelle Konstante und ferner h:\mathbb{R} \rightarrow [0,\infty[ eine monoton wachsende Funktion. Die allgemeine Markow-Ungleichung besagt dann:

P \left[ X \geq a \right] \leq \frac{\textrm{E}\left[h(X)\right]}{h(a)}.

Beweis[Bearbeiten]

Sei I_A(x) die charakteristische Funktion der Menge A. Dann gilt:

P \left[ X \geq a \right] = \int I_{\{X \geq a\}} \ dP \leq \int I_{\{X \geq a\}} \frac{h(X)}{h(a)} \ dP  \leq \frac{\textrm{E}\left[h(X)\right]}{h(a)}

Varianten[Bearbeiten]

  • Setzt man h(x) = x und betrachtet die reelle Zufallsvariable |X|, so erhält man den bekannten Spezialfall der Markow-Ungleichung
P\left[|X| \geq a\right] \leq \frac{\textrm{E}\left[|X|\right]}{a}.
Wie man diese Ungleichung mit schulgemäßen Mitteln aus einem unmittelbar einsichtigen Flächenvergleich folgern und dann daraus eine Version der Ungleichung von Tschebyschew herleiten kann, findet man in [1]
  • Betrachtet man a = c \cdot \textrm{E}[|X|] 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:
P\left[|X| \geq c \cdot \textrm{E}[|X|] \right] 
\leq \frac{\textrm{E}\left[|X|\right]}{c \cdot \textrm{E}\left[|X|\right]} = \frac{1}{c}.
  • Ist h(x) = x^2 und wendet man die Markow-Ungleichung auf eine Zufallsvariable Y = |X - \textrm{E}[X]| an, so erhält man eine Version der Tschebyscheff-Ungleichung:
P\left[|X - \textrm{E}[X]| \geq a\right] \leq \frac{\textrm{E}[(X-\textrm{E}[X])^2]}{a^2} = \frac{\operatorname{Var}[X]}{a^2}.
  • 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 a,b \geq 0 und sei X eine Zufallsvariable mit |X| \leq a und \textrm{E}\left[|X|\right] \geq \frac{a}{b}. Dann gilt für alle c>0:
P\left[ |X| \leq (1-c)\textrm{E}\left[|X|\right] \right] \leq 1-\frac{c}{b}.
Der Beweis dieser Aussage ist ähnlich dem Beweis der Markow-Ungleichung.[2]
  • Wählt man h(x) = e^{tx}, 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[Bearbeiten]

  1. H.Wirths : Der Erwartungswert - Skizzen zur Begriffsentwickung von Klasse 8 bis 13. In : Mathematik in der Schule 1995/Heft6, S. 330 - 343.
  2. 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[Bearbeiten]