Markow-Ungleichung

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten auf deiner Diskussionsseite.

In der Wahrscheinlichkeitstheorie gibt die Markow-Ungleichung (nach Andrei Andrejewitsch Markow) eine obere Schranke für die Wahrscheinlichkeit an, dass eine nicht-negative Funktion einer Zufallsvariable größer oder gleich einer positiven Konstante ist.

Die Markow-Ungleichung (wie ähnliche Ungleichungen) vergleicht Wahrscheinlichkeit und Erwartungswert und gibt eine in aller Regel schwache, aber nützliche Grenze für die Verteilungsfunktion einer Zufallsvariable an.

Inhaltsverzeichnis

1 Satz
- 1.1 Beweis
- 1.2 Alternativer Beweis
2 Varianten
3 Beispiele
4 Quellen

[Bearbeiten] Satz

Sei $X$ eine Zufallsvariable und $a$ eine positive, reellwertige Konstante. Sei ferner $h:\mathbb{R} \rightarrow [0,\infty)$ eine positive, reellwertige Funktion. Die allgemeine Markow-Ungleichung besagt dann:

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

[Bearbeiten] Beweis

Sei $Ω$ der zu Grunde liegende diskrete Wahrscheinlichkeitsraum. Dann gilt nach der Definition des Erwartungswertes:

$\textrm{E}\left[h(X)\right] = \sum_{\omega \in \Omega} \omega \cdot \Pr[h(X) = \omega] \geq \sum_{\omega \in \Omega,\atop \omega \geq a} \omega \cdot \Pr[h(X) = \omega]$

$\geq \sum_{\omega \in \Omega,\atop \omega \geq a} a \cdot \Pr[h(X) = \omega] = a \cdot \sum_{\omega \in \Omega,\atop \omega \geq a} Pr[h(X) = \omega] \geq a \cdot \Pr[h(X) \geq a],$

wobei die letzte Abschätzung auf Grund der ersten Bonferroni-Ungleichung gilt. Nach Division durch $a$ folgt die Behauptung. ^[1]

[Bearbeiten] Alternativer Beweis

Sei $A = \left\{x: h(x) \geq a \right\}$ und bezeichne $I A (x)$ die charakteristische Funktion der Menge $A$ . Dann gilt:

$a \cdot I_A(x) \leq h(x).$

Der Satz folgt, wenn man auf beiden Seiten den Erwartungswert nimmt und

$\textrm{E}\left[I_A(X)\right] = \Pr\left[h(X) \geq a\right]$

berücksichtigt.

[Bearbeiten] Varianten

Setzt man $h (x) = | x |$ , so erhält man den bekannten Spezialfall der Markow-Ungleichung

$\Pr\left[|X| \geq a\right] \leq \frac{\textrm{E}\left[|X|\right]}{a}.$

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:

$\Pr\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 - 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 $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$ :

$\Pr\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]

[Bearbeiten] 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:

$\Pr \left[ X \geq 4 \right] \leq \frac{\textrm{E}\left[X\right]}{4} = \frac{3{,}5}{4} = \frac{7}{8}$ .

[Bearbeiten] Quellen

↑ Ulrich Krengel, Einführung in die Wahrscheinlichkeitstheorie und Statistik, 7. Auflage, Vieweg Verlag, 2003. ISBN 3-528-67259-5
↑ Piotr Indyk, Sublinear Time Algorithms for Metric Space Problems, Proceedings of the 31st Symposium on Theory of Computing (STOC'99), 428--434, 1999.

Von „http://de.wikipedia.org../../../m/a/r/Markow-Ungleichung_3a52.html“

Kategorien: Stochastik | Statistik | Ungleichung

Markow-Ungleichung

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Satz

[Bearbeiten] Beweis

[Bearbeiten] Alternativer Beweis

[Bearbeiten] Varianten

[Bearbeiten] Beispiele

[Bearbeiten] Quellen

Views

Navigation

Mitmachen

Suche

Andere Sprachen