Tschebyscheffsche Ungleichung

Kernaussage und Definition

Die tschebyscheffsche Ungleichung ist ein grundlegender Satz der Stochastik. Sie schätzt die Wahrscheinlichkeit dafür ab, dass eine reelle Zufallsvariable X stärker als ein vorgegebener Schwellenwert von ihrem Erwartungswert abweicht. Dazu benötigt man keine bestimmte Verteilungsannahme; endliche Varianz genügt. Deshalb ist die Ungleichung auch für Verteilungen anwendbar, die sich deutlich von der Normalverteilung unterscheiden.

Sei μ := E(X) der Erwartungswert und σ² := Var(X) die endliche Varianz von X. Für jede reelle Zahl k > 0 gilt:

P(|X − μ| ≥ k) ≤ σ²/k².

Die Wahrscheinlichkeit einer Abweichung von mindestens k ist also höchstens die Varianz geteilt durch k². Für das komplementäre Ereignis folgt:

P(|X − μ| < k) ≥ 1 − σ²/k².

Mit dieser zweiten Form kann man eine Mindestwahrscheinlichkeit dafür angeben, dass X im Intervall (μ − k, μ + k) liegt. Die Ungleichung wird auch Tschebyscheff-Ungleichung oder Bienaymé-Tschebyscheff-Ungleichung genannt.

Güte der Abschätzung

Die Schranke ist scharf: Es gibt Zufallsvariablen, bei denen Gleichheit erreicht wird. Ein Beispiel ist eine diskrete Zufallsvariable mit

P(X = 0) = 1 − p, P(X = −a) = P(X = a) = p/2,

wobei a eine echt positive reelle Zahl und p ∈ (0, 1) ist. Für diese Zufallsvariable gilt μ = E(X) = 0 und σ² = Var(X) = a²p. Daher lautet die Ungleichung

P(|X| ≥ k) ≤ a²p/k².

Für k = a gilt auf beiden Seiten p, denn P(|X| ≥ a) = p.

Im Allgemeinen sind die Abschätzungen jedoch eher grob. Für k ≤ σ sind sie sogar trivial, weil der rechte Ausdruck σ²/k² dann mindestens 1 ist und Wahrscheinlichkeiten stets höchstens 1 betragen. Die Tschebyscheffsche Ungleichung bleibt trotzdem nützlich, weil sie einfach zu berechnen ist und ohne Kenntnisse über die konkrete Verteilung von X auskommt.

Varianten und Verallgemeinerungen

Ist σ von Null verschieden und λ > 0, setzt man k = λσ. Dadurch erhält man die häufig verwendete Form

P(|X − μ| ≥ λσ) ≤ 1/λ².

Eine sinnvolle, nichttriviale Abschätzung liefert diese Form nur für λ > 1. Für 0 < λ ≤ 1 ist sie trivial. Falls σ > 0, gelten für positive reelle k beziehungsweise λ außerdem die strikteren Ungleichungen

P(|X − μ| > k) < σ²/k²

beziehungsweise

P(|X − μ| > λσ) < 1/λ².

Die Ungleichung lässt sich auf höhere Momente verallgemeinern. Für einen Maßraum (Ω, Σ, ν), eine messbare Funktion f: Ω → R₀⁺ sowie ε, p ∈ R⁺ gilt

ν({x | f(x) ≥ ε}) ≤ (1/εᵖ) ∫Ω fᵖ dν.

Dies folgt daraus, dass das Integral von fᵖ über ganz Ω mindestens so groß ist wie das Integral über die Menge, auf der f ≥ ε gilt. Auf dieser Menge ist fᵖ mindestens εᵖ. Die ursprüngliche Tschebyscheffsche Ungleichung erhält man mit ν = P, f = |X − μ| und p = 2.

Es gibt außerdem eine mehrdimensionale Erweiterung. Ist X = (x¹, ..., xⁿ) eine n-dimensionale Zufallsvariable, die auf den Mittelpunkt (μ(x¹) / ... / μ(xⁿ)) zentriert wurde, gilt in der angegebenen Notation

1 − P((x¹, ... , xⁿ)C⁻¹(x¹, ... , xⁿ)ᵀ ≤ k²) ≤ n/k².

Eine weitere Anwendung der Verallgemeinerung führt zur exponentiellen Tschebyscheff-Ungleichung. Für X ∼ P und a ∈ R gilt

P(X ≥ a) ≤ infₚ∈R⁺ E(eᵖX)/eᵖᵃ.

Dabei ist M_X(p) = E(eᵖX) die momenterzeugende Funktion von X. Auf Summen unabhängiger und identisch verteilter Zufallsvariablen angewandt, ist diese Ungleichung ein entscheidender Schritt im Beweis der Chernoff-Ungleichung.

Beispiele und Anwendungen

Hat die Länge von Wikipedia-Artikeln den Erwartungswert 1000 Zeichen und die Standardabweichung 200 Zeichen, wählt man k = 400. Dann gilt

P(|X − 1000| < 400) ≥ 1 − 200²/400² = 0,75 = 75 %.

Mit mindestens 75 % Wahrscheinlichkeit liegt die Länge somit zwischen 600 und 1400 Zeichen.

Eine weitere direkte Folgerung lautet: Für jede reelle Zufallsvariable mit Mittelwert μ und endlicher Standardabweichung σ liegt X mit Wahrscheinlichkeit mindestens 1/2 im Intervall

(μ − √2σ, μ + √2σ),

denn man setzt k² = 2σ².

Für Anwendungen auf relative Häufigkeiten sei ein Ereignis bei einem einzelnen Versuch mit Wahrscheinlichkeit p gegeben und werde n-mal wiederholt. Tritt es k-mal ein, ist k binomialverteilt mit Erwartungswert np und Varianz np(1 − p). Die relative Häufigkeit k/n hat daher den Erwartungswert p und die Varianz p(1 − p)/n. Für ε > 0 folgt

P(|k/n − p| ≥ ε) ≤ p(1 − p)/(ε²n) ≤ 1/(4ε²n).

Für die zweite Abschätzung wird √(p(1 − p)) ≤ 1/2 verwendet. Diese Formel ist ein Spezialfall des Schwachen Gesetzes der großen Zahlen: Die relativen Häufigkeiten konvergieren stochastisch gegen den Erwartungswert. Die Tschebyscheffsche Ungleichung liefert hier nur eine grobe Schranke; die Chernoff-Ungleichung verbessert sie quantitativ.

Weitere Anwendungen sind der Beweis des Schwachen Gesetzes der großen Zahlen, der Schluss von der Lᵖ-Konvergenz einer Funktionenfolge auf Konvergenz im Maß sowie die Aussage, dass für einen Median m stets |μ − m| ≤ σ gilt.

Beweisidee und Einordnung

Für einen direkten Beweis betrachtet man das Ereignis A_k = {ω ∈ Ω | |X − μ| ≥ k} und die Indikatorfunktion 1_Ak. Für jedes ω gilt

|X(ω) − μ|² ≥ k²1_Ak(ω).

Liegt ω nicht in A_k, ist die rechte Seite 0. Liegt ω in A_k, ist die linke Seite nach Definition mindestens k². Mit der Monotonie des Erwartungswertes folgt daher

σ² = Var(X) = E(|X − μ|²) ≥ E(k²1_Ak) = k²P(A_k) = k²P(|X − μ| ≥ k).

Durch Teilen durch k² erhält man die Tschebyscheffsche Ungleichung. Häufig wird sie auch als Spezialfall der Markow-Ungleichung eingeführt, indem man Y = |X − μ| und h(x) = x² setzt.

Die Ungleichung wurde 1867 von Pafnuti Lwowitsch Tschebyschow für diskrete Zufallsvariablen bewiesen. Ein allgemeinerer Beweis war bereits 1853 von Irénée-Jules Bienaymé veröffentlicht worden; deshalb werden beide Namen verwendet. Verwandte Resultate sind unter anderem die Markow-, Cantelli-, Chernoff-, Hoeffding-, Jensen-, Kolmogorow-, Burkholder- und Doob-Ungleichung sowie die Ungleichungen von Ljapunow, Hájek und Rényi und Ottaviani-Skorokhod.