Markov-Ungleichung

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 X:\Omega \rightarrow \mathbb{R} eine reele Zufallsvariable und a eine positive, reellwertige Konstante und ferner h:\mathbb{R} \rightarrow [0,\infty[ 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

Sei IA(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

  • 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}.
  • 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) = 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 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.[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:


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

Einzelnachweise

  1. 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.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Andrey Markov — Andrei A. Markow als Dreißigjähriger Andrei A. Markow Andrei Andrejewitsch Markow (russisch Андрей Андреевич Марков, wiss. Translite …   Deutsch Wikipedia

  • Probabilistischer Algorithmus — Ein randomisierter Algorithmus (auch stochastischer oder probabilistischer Algorithmus) verwendet im Gegensatz zu einem deterministischen Algorithmus Zufallsbits um seinen Ablauf zu steuern. Es wird nicht verlangt, dass ein randomisierter… …   Deutsch Wikipedia

  • Stochastischer Algorithmus — Ein randomisierter Algorithmus (auch stochastischer oder probabilistischer Algorithmus) verwendet im Gegensatz zu einem deterministischen Algorithmus Zufallsbits um seinen Ablauf zu steuern. Es wird nicht verlangt, dass ein randomisierter… …   Deutsch Wikipedia

  • Markoff — Markow bezeichnet: Markow (Ivenack), Ortsteil der Gemeinde Ivenack im Landkreis Demmin in Mecklenburg Vorpommern Markow ist ein russischer Familienname. Bekannte Namensträger sind: Alexei Markow (* 1979), russischer Radsportler Andrei… …   Deutsch Wikipedia

  • Andrej Andrejewitsch Markow — Andrei A. Markow als Dreißigjähriger Andrei A. Markow Andrei Andrejewitsch Markow (russisch Андрей Андреевич Марков, wiss. Translite …   Deutsch Wikipedia

  • Andrei Andrejewitsch Markow — Andrei A. Markow als Dreißigjähriger Andrei A. Markow Andrei Andrejewitsch …   Deutsch Wikipedia

  • Markow — ist der Familienname folgender Personen: Alexei Michailowitsch Markow (* 1979), russischer Radsportler Andrei Andrejewitsch Markow (1856–1922), russischer Mathematiker Andrei Sergejewitsch Markow (* 1980), russischer Bogenbiathlet Andrei… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”