S sei eine abzahlbare Menge (ein “Alphabet”).
Die Elemente von S nennen wir Buchstaben.
X sei eine S-wertieg Zufallsvariable
(ein “zufalliger Buchstabe”).
S sei eine abzahlbare Menge (ein “Alphabet”).
Die Elemente von S nennen wir Buchstaben.
X sei eine S-wertieg Zufallsvariable
(ein “zufalliger Buchstabe”).
H2[X] := −∑
a∈Sν(a) log2 ν(a)
S sei eine abzahlbare Menge (ein “Alphabet”).
Die Elemente von S nennen wir Buchstaben.
X sei eine S-wertieg Zufallsvariable
(ein “zufalliger Buchstabe”).
H2[X] := −∑
a∈Sν(a) log2 ν(a)
heißt die Entropie von X (zur Basis 2).
Es ist sinnvoll, auch andere Basen zu erlauben.
Wir schreiben
H[X] := −∑
a∈Sν(a) log ν(a),
wobei log zu einer beliebigen, festen Basis genommen wird:
Es ist sinnvoll, auch andere Basen zu erlauben.
Wir schreiben
H[X] := −∑
a∈Sν(a) log ν(a),
wobei log zu einer beliebigen, festen Basis genommen wird:
Hb[X] := −∑
a∈Sν(a) logb ν(a).
Die Entropie ist der fundamentale Begriff
der Informationstheorie.
Nach dem Quellenkodierungssatz gibt die Entropie
fast genau die mittlere Anzahl von Ja-Nein Fragen an,
Die Entropie ist der fundamentale Begriff
der Informationstheorie.
Nach dem Quellenkodierungssatz gibt die Entropie
fast genau die mittlere Anzahl von Ja-Nein Fragen an,
die notwendig und
- bei guter Wahl des Codes - auch hinreichend ist,
um den unbekannten Wert von X von jemandem zu erfragen,
der X beobachten kann.
Die Entropie ist der fundamentale Begriff
der Informationstheorie.
Nach dem Quellenkodierungssatz gibt die Entropie
fast genau die mittlere Anzahl von Ja-Nein Fragen an,
die notwendig und
- bei guter Wahl des Codes - auch hinreichend ist,
um den unbekannten Wert von X von jemandem zu erfragen,
der X beobachten kann.
Dies ist gemeint, wenn man die Entropie beschreibt als den
Grad von Unbestimmtheit oder Ungewissheit
uber den Wert, den X annimmt.
Die relative Entropie
Definition: Seien ν und ρ Wahrscheinlichkeitsverteilungen
mit Gewichten ν(a) und ρ(a), a ∈ S. Dann ist die relative
Entropie von ν bzgl. ρ definiert als
Die relative Entropie
Definition: Seien ν und ρ Wahrscheinlichkeitsverteilungen
mit Gewichten ν(a) und ρ(a), a ∈ S. Dann ist die relative
Entropie von ν bzgl. ρ definiert als
D(ν‖ρ) :=∑
a∈Sν(a) log
ν(a)
ρ(a),
Die relative Entropie
Definition: Seien ν und ρ Wahrscheinlichkeitsverteilungen
mit Gewichten ν(a) und ρ(a), a ∈ S. Dann ist die relative
Entropie von ν bzgl. ρ definiert als
D(ν‖ρ) :=∑
a∈Sν(a) log
ν(a)
ρ(a),
wobei die Summanden mit ν(a) = 0
gleich 0 gesetzt werden.
Interpretation der relativen Entropie:
Man denke sich einen zufalligen Buchstaben mit Verteilung ν
mit einem Shannon-Code codiert, der nicht der Verteilung ν,
sondern der Verteilung ρ angepasst ist,
Interpretation der relativen Entropie:
Man denke sich einen zufalligen Buchstaben mit Verteilung ν
mit einem Shannon-Code codiert, der nicht der Verteilung ν,
sondern der Verteilung ρ angepasst ist,
also mit Codewortlangen
− log ρ(a) ≤ ℓ(a) < − log ρ(a) + 1.
Interpretation der relativen Entropie:
Man denke sich einen zufalligen Buchstaben mit Verteilung ν
mit einem Shannon-Code codiert, der nicht der Verteilung ν,
sondern der Verteilung ρ angepasst ist,
also mit Codewortlangen
− log ρ(a) ≤ ℓ(a) < − log ρ(a) + 1.
Dann ist die Zunahme der erwarteten Codelange
bis auf ein Bit gleich
−∑
aν(a) log ρ(a) −
(
−∑
aν(a) log ν(a)
)
= D(ν‖ρ).
In der Tat gilt ja fur die Lange ℓρ des
an ρ angepassten Shannon-Codes:
−∑
a ν(a) log ρ(a) ≤ E[ℓρ(X)] < −∑
a ν(a) log ρ(a) + 1.
Und fur fur die Lange ℓρ des
an ν angepassten Shannon-Codes gilt:
In der Tat gilt ja fur die Lange ℓρ des
an ρ angepassten Shannon-Codes:
−∑
a ν(a) log ρ(a) ≤ E[ℓρ(X)] < −∑
a ν(a) log ρ(a) + 1.
Und fur fur die Lange ℓρ des
an ν angepassten Shannon-Codes gilt:
−∑
a ν(a) log ν(a) ≤ E[kν(X)] < −∑
a ν(a) log ν(a) + 1.
In der Tat gilt ja fur die Lange ℓρ des
an ρ angepassten Shannon-Codes:
−∑
a ν(a) log ρ(a) ≤ E[ℓρ(X)] < −∑
a ν(a) log ρ(a) + 1.
Und fur fur die Lange ℓρ des
an ν angepassten Shannon-Codes gilt:
−∑
a ν(a) log ν(a) ≤ E[kν(X)] < −∑
a ν(a) log ν(a) + 1.
Daraus folgt fur die Differenz:
In der Tat gilt ja fur die Lange ℓρ des
an ρ angepassten Shannon-Codes:
−∑
a ν(a) log ρ(a) ≤ E[ℓρ(X)] < −∑
a ν(a) log ρ(a) + 1.
Und fur fur die Lange ℓρ des
an ν angepassten Shannon-Codes gilt:
−∑
a ν(a) log ν(a) ≤ E[kν(X)] < −∑
a ν(a) log ν(a) + 1.
Daraus folgt fur die Differenz:
E[ℓρ(X)] − E[ℓν(X)] ∈ [D(ν‖ρ) − 1, D(ν‖ρ) + 1). 2
Satz: (“Informationsungleichung”) D(ν‖ρ) ≥ 0.
Beweis: Wieder verwenden wir die Abschatzung
logx ≤ c · (x − 1) mit passendem c > 0:
8
Satz: (“Informationsungleichung”) D(ν‖ρ) ≥ 0.
Beweis: Wieder verwenden wir die Abschatzung
logx ≤ c · (x − 1) mit passendem c > 0:
D(ν‖ρ) = −∑
a:ν(a)>0
ν(a) logρ(a)
ν(a)
Satz: (“Informationsungleichung”) D(ν‖ρ) ≥ 0.
Beweis: Wieder verwenden wir die Abschatzung
logx ≤ c · (x − 1) mit passendem c > 0:
D(ν‖ρ) = −∑
a:ν(a)>0
ν(a) logρ(a)
ν(a)
≥ −∑
a:ν(a)>0
ν(a) c ·(ρ(a)
ν(a)− 1
)
Satz: (“Informationsungleichung”) D(ν‖ρ) ≥ 0.
Beweis: Wieder verwenden wir die Abschatzung
logx ≤ c · (x − 1) mit passendem c > 0:
D(ν‖ρ) = −∑
a:ν(a)>0
ν(a) logρ(a)
ν(a)
≥ −∑
a:ν(a)>0
ν(a) c ·(ρ(a)
ν(a)− 1
)
= −c(
∑
a:ν(a)>0
ρ(a) −∑
aν(a)
)
≥ 0. 2
Bemerkung: Aus D(ν‖ρ) = 0 folgt ν = ρ.
In der Tat: In logx ≤ c(x − 1)
besteht abgesehen fur x = 1 strikte Ungleichung.
Bemerkung: Aus D(ν‖ρ) = 0 folgt ν = ρ.
In der Tat: In logx ≤ c(x − 1)
besteht abgesehen fur x = 1 strikte Ungleichung.
Also folgt aus
−∑
a:ν(a)>0
ν(a) logρ(a)
ν(a)= −c
∑
a:ν(a)>0
ν(a)(ρ(a)
ν(a)− 1
)
,
Bemerkung: Aus D(ν‖ρ) = 0 folgt ν = ρ.
In der Tat: In logx ≤ c(x − 1)
besteht abgesehen fur x = 1 strikte Ungleichung.
Also folgt aus
−∑
a:ν(a)>0
ν(a) logρ(a)
ν(a)= −c
∑
a:ν(a)>0
ν(a)(ρ(a)
ν(a)− 1
)
,
dass ρ(a) = ν(a) fur alle a mit ν(a) > 0.
Bemerkung: Aus D(ν‖ρ) = 0 folgt ν = ρ.
In der Tat: In logx ≤ c(x − 1)
besteht abgesehen fur x = 1 strikte Ungleichung.
Also folgt aus
−∑
a:ν(a)>0
ν(a) logρ(a)
ν(a)= −c
∑
a:ν(a)>0
ν(a)(ρ(a)
ν(a)− 1
)
,
dass ρ(a) = ν(a) fur alle a mit ν(a) > 0.
Und aus∑
a:ν(a)>0
ρ(a) −∑
aν(a) = 0
Bemerkung: Aus D(ν‖ρ) = 0 folgt ν = ρ.
In der Tat: In logx ≤ c(x − 1)
besteht abgesehen fur x = 1 strikte Ungleichung.
Also folgt aus
−∑
a:ν(a)>0
ν(a) logρ(a)
ν(a)= −c
∑
a:ν(a)>0
ν(a)(ρ(a)
ν(a)− 1
)
,
dass ρ(a) = ν(a) fur alle a mit ν(a) > 0.
Und aus∑
a:ν(a)>0
ρ(a) −∑
aν(a) = 0
folgt ρ(a) = ν(a) fur alle a mit ν(a) = 0. 2
Zusammenfassend ergibt sich der
Satz (von der relativen Entropie):
Die relative Entropie D(ν‖ρ) ist nichtnegativ,
Zusammenfassend ergibt sich der
Satz (von der relativen Entropie):
Die relative Entropie D(ν‖ρ) ist nichtnegativ,
und verschwindet genau fur ν = ρ.
In den folgenden Beispielen
benutzen wir den Satz in der Gestalt
(∗) −∑
aν(a) log ν(a) ≤ −
∑
aν(a) log ρ(a)
11
In den folgenden Beispielen
benutzen wir den Satz in der Gestalt
(∗) −∑
aν(a) log ν(a) ≤ −
∑
aν(a) log ρ(a)
mit Gleichheit genau fur ν = ρ.
In den folgenden Beispielen
benutzen wir den Satz in der Gestalt
(∗) −∑
aν(a) log ν(a) ≤ −
∑
aν(a) log ρ(a)
mit Gleichheit genau fur ν = ρ.
Wir sehen:
Hat X die Verteilung ν,
so liefert jede Wahl von ρ eine Schranke fur H[X],
mit Gleichheit genau fur ν = ρ.
Beispiel: Vegleich mit der uniformen Verteilung:
Sei S endlich mit n Elementen
und sei ρ(a) = 1/n fur alle a ∈ S.
Dann folgt aus (∗):
H[X] ≤ −∑
aν(a) log(
1
n) = logn .
Beispiel: Vegleich mit der uniformen Verteilung:
Sei S endlich mit n Elementen
und sei ρ(a) = 1/n fur alle a ∈ S.
Dann folgt aus (∗):
H[X] ≤ −∑
aν(a) log(
1
n) = logn .
H[X] ≤ logn.
Beispiel: Vegleich mit der uniformen Verteilung:
Sei S endlich mit n Elementen
und sei ρ(a) = 1/n fur alle a ∈ S.
Dann folgt aus (∗):
H[X] ≤ −∑
aν(a) log(
1
n) = logn .
H[X] ≤ logn.
Gleichheit gilt genau im Fall der uniformen Verteilung,
sie maximiert auf S die Entropie. 2
Beispiel: Vergleich mit (verschobener) geom. Verteilung:
Sei nun S = {0,1,2, . . .}, und ρ(k) := 2−k−1
Dann folgt aus (∗):
H2[X] ≤∑
aν(a) log2(−2−k−1)
=∞∑
k=0
(k + 1)ν(k) = (E[X] + 1) .
Beispiel: Vergleich mit (verschobener) geom. Verteilung:
Sei nun S = {0,1,2, . . .}, und ρ(k) := 2−k−1
Dann folgt aus (∗):
H2[X] ≤∑
aν(a) log2(−2−k−1)
=∞∑
k=0
(k + 1)ν(k) = (E[X] + 1) .
Gleichheit gilt fur ν(k) = 2−k−1, dann ist H2[X] = 2. Also:
Beispiel: Vergleich mit (verschobener) geom. Verteilung:
Sei nun S = {0,1,2, . . .}, und ρ(k) := 2−k−1
Dann folgt aus (∗):
H2[X] ≤∑
aν(a) log2(−2−k−1)
=∞∑
k=0
(k + 1)ν(k) = (E[X] + 1) .
Gleichheit gilt fur ν(k) = 2−k−1, dann ist H2[X] = 2. Also:
Unter allen N0-wertigen ZV’en mit EW ≤ 1
hat das X mit Gewichten 2−k−1 die großte Entropie,
namlich H2[X] = 2. 2
Beispiel: Vergleich mit einer “Gibbsverteilung”:
Gegeben sei u : S → R, β ≥ 0.
Wir definieren die Gewichte ρ(a) := e−βu(a)/z mit
z :=∑
a∈Se−βu(a) ( Annahme: z < ∞.)
14
Beispiel: Vergleich mit einer “Gibbsverteilung”:
Gegeben sei u : S → R, β ≥ 0.
Wir definieren die Gewichte ρ(a) := e−βu(a)/z mit
z :=∑
a∈Se−βu(a) ( Annahme: z < ∞.)
Die Abschatzung (∗) ergibt
He[X] ≤ β E[u(X)] + ln z .
Ist E[u(X)] ≤∑
au(a)ρ(a), so folgt
He[X] ≤ β∑
au(a)ρ(a) + ln z = −
∑
aρ(a) ln ρ(a),
mit Gleichheit genau dann, wenn X die Verteilung ρ hat.
Zusammengefasst:
Unter allen Zufallsvariablen mit
Erwartungswert ≤∑
au(a)e−βu(a)/z
hat diejenige die großte Entropie,
die die Verteilungsgewichte e−βu(a)/z hat.
Zusammengefasst:
Unter allen Zufallsvariablen mit
Erwartungswert ≤∑
au(a)e−βu(a)/z
hat diejenige die großte Entropie,
die die Verteilungsgewichte e−βu(a)/z hat.
Die Verteilung mit diesen Gewichten heißt Gibbsverteilung
zum Potenzial u mit Parameter β. 2
Beispiel:
ν und ρ binomialverteilt zu den Parametern (n, α) bzw. (n, p)
D(ν‖ρ) =?
logν(k)
ρ(k)= log
αk(1 − α)n−k
pk(1 − p)n−k= k log
α
p+(n−k) log
1 − α
1 − p
Beispiel:
ν und ρ binomialverteilt zu den Parametern (n, α) bzw. (n, p)
D(ν‖ρ) =?
logν(k)
ρ(k)= log
αk(1 − α)n−k
pk(1 − p)n−k= k log
α
p+(n−k) log
1 − α
1 − p
Wegen∑
k ν(k) = nα ist somit
Beispiel:
ν und ρ binomialverteilt zu den Parametern (n, α) bzw. (n, p)
D(ν‖ρ) =?
logν(k)
ρ(k)= log
αk(1 − α)n−k
pk(1 − p)n−k= k log
α
p+(n−k) log
1 − α
1 − p
Wegen∑
k ν(k) = nα ist somit
D(ν‖ρ) =∑
ν(k) logν(k)
ρ(k)
= n
α logα
p+ (1 − α) log
1 − α
1 − p
=: n h(α, p). 2
Beispiel: Fur p ∈ (0,1) sei Y1, Y2, . . . ein p-Munzwurf.
Kn := Y1 + . . . + Yn sei die “Anzahl der Erfolge” bis n.
Sei [c, d] ein Intervall rechts von p (mit p < c < d).
Beispiel: Fur p ∈ (0,1) sei Y1, Y2, . . . ein p-Munzwurf.
Kn := Y1 + . . . + Yn sei die “Anzahl der Erfolge” bis n.
Sei [c, d] ein Intervall rechts von p (mit p < c < d).
Satz (Boltzmann)
Beispiel: Fur p ∈ (0,1) sei Y1, Y2, . . . ein p-Munzwurf.
Kn := Y1 + . . . + Yn sei die “Anzahl der Erfolge” bis n.
Sei [c, d] ein Intervall rechts von p (mit p < c < d).
Satz (Boltzmann)
lnP
{
Kn
n∈ [c, d]
}
∼ −n h(c, p) fur n → ∞,
Beispiel: Fur p ∈ (0,1) sei Y1, Y2, . . . ein p-Munzwurf.
Kn := Y1 + . . . + Yn sei die “Anzahl der Erfolge” bis n.
Sei [c, d] ein Intervall rechts von p (mit p < c < d).
Satz (Boltzmann)
lnP
{
Kn
n∈ [c, d]
}
∼ −n h(c, p) fur n → ∞,
mit h wie im vorigen Beispiel.
Beispiel: Fur p ∈ (0,1) sei Y1, Y2, . . . ein p-Munzwurf.
Kn := Y1 + . . . + Yn sei die “Anzahl der Erfolge” bis n.
Sei [c, d] ein Intervall rechts von p (mit p < c < d).
Satz (Boltzmann)
lnP
{
Kn
n∈ [c, d]
}
∼ −n h(c, p) fur n → ∞,
mit h wie im vorigen Beispiel.
Beweis: siehe Skript Wakolbinger, Seite 96-98.
S = k logW
Entropie =k malLogarithmus derWahrscheinlichkeit
Ludwig Boltzmann1844-1906
Grabmal amWienerZentralfriedhof 18
Zur Erinnerung:
Aufgabe 51: n Daten werden erst per “Wurfeln” mit den
Gewichten p1, . . . , pr in r Listen einsortiert. Dann wird aus
diesen n Daten rein zufallig ein Paar ausgewahlt.
Berechenen Sie Wahrscheinlichkeit, dass diese beiden Daten
in derselben Liste sind.
19
Losung:
Es seiein J1 und J2 die Listenkennzahlen
der beiden ausgewahlten Daten.
Zerlegung nach den Ausgangen von K ergibt:
Losung:
Es seiein J1 und J2 die Listenkennzahlen
der beiden ausgewahlten Daten.
Zerlegung nach den Ausgangen von K ergibt:
P{J1 = J2} =∑
k P{K = k}Pk{J1 = J2}=
∑
k P{K = k}∑rj=1
kj(kj−1)
n(n−1)
Losung:
Es seiein J1 und J2 die Listenkennzahlen
der beiden ausgewahlten Daten.
Zerlegung nach den Ausgangen von K ergibt:
P{J1 = J2} =∑
k P{K = k}Pk{J1 = J2}=
∑
k P{K = k}∑rj=1
kj(kj−1)
n(n−1)
= 1n(n−1)
∑rj=1 E[Kj(Kj − 1)].
In VL 10a haben wir ausgerechnet:
Losung:
Es seiein J1 und J2 die Listenkennzahlen
der beiden ausgewahlten Daten.
Zerlegung nach den Ausgangen von K ergibt:
P{J1 = J2} =∑
k P{K = k}Pk{J1 = J2}=
∑
k P{K = k}∑rj=1
kj(kj−1)
n(n−1)
= 1n(n−1)
∑rj=1 E[Kj(Kj − 1)].
In VL 10a haben wir ausgerechnet:
E[K2j ] = p2
j n(n − 1) + npj.
Losung:
Es seiein J1 und J2 die Listenkennzahlen
der beiden ausgewahlten Daten.
Zerlegung nach den Ausgangen von K ergibt:
P{J1 = J2} =∑
k P{K = k}Pk{J1 = J2}=
∑
k P{K = k}∑rj=1
kj(kj−1)
n(n−1)
= 1n(n−1)
∑rj=1 E[Kj(Kj − 1)].
In VL 10a haben wir ausgerechnet:
E[K2j ] = p2
j n(n − 1) + npj.
Somit ist E[Kj(Kj − 1)] = p2j n(n − 1),
Losung:
Es seiein J1 und J2 die Listenkennzahlen
der beiden ausgewahlten Daten.
Zerlegung nach den Ausgangen von K ergibt:
P{J1 = J2} =∑
k P{K = k}Pk{J1 = J2}=
∑
k P{K = k}∑rj=1
kj(kj−1)
n(n−1)
= 1n(n−1)
∑rj=1 E[Kj(Kj − 1)].
In VL 10a haben wir ausgerechnet:
E[K2j ] = p2
j n(n − 1) + npj.
Somit ist E[Kj(Kj − 1)] = p2j n(n − 1),
und die gesuchte Wahrscheinlichkeit ist∑
j p2j . 2
Abwandlung einer Quizaufgabe:
Sei K = (K1, . . . , K6) multinomialverteilt zu den
Parametern 10 und (p1, . . . , p6) = (1/6, . . . ,1/6).
21
Abwandlung einer Quizaufgabe:
Sei K = (K1, . . . , K6) multinomialverteilt zu den
Parametern 10 und (p1, . . . , p6) = (1/6, . . . ,1/6).
Fur i = 1, . . . ,6 sei Zi := I{Ki=0}.
Es sei Y := #{i : Ki = 0}.
Abwandlung einer Quizaufgabe:
Sei K = (K1, . . . , K6) multinomialverteilt zu den
Parametern 10 und (p1, . . . , p6) = (1/6, . . . ,1/6).
Fur i = 1, . . . ,6 sei Zi := I{Ki=0}.
Es sei Y := #{i : Ki = 0}.
Berechnen Sie den Erwartungswert von Y .
Abwandlung einer Quizaufgabe:
Sei K = (K1, . . . , K6) multinomialverteilt zu den
Parametern 10 und (p1, . . . , p6) = (1/6, . . . ,1/6).
Fur i = 1, . . . ,6 sei Zi := I{Ki=0}.
Es sei Y := #{i : Ki = 0}.
Berechnen Sie den Erwartungswert von Y .
Losung: E[Zi] = P{Ki = 0} = (5/6)10,
denn Ki ist binomial (10,1/6)- verteilt.
Abwandlung einer Quizaufgabe:
Sei K = (K1, . . . , K6) multinomialverteilt zu den
Parametern 10 und (p1, . . . , p6) = (1/6, . . . ,1/6).
Fur i = 1, . . . ,6 sei Zi := I{Ki=0}.
Es sei Y := #{i : Ki = 0}.
Berechnen Sie den Erwartungswert von Y .
Losung: E[Zi] = P{Ki = 0} = (5/6)10,
denn Ki ist binomial (10,1/6)- verteilt.
E[Y ] =6
∑
i=1E[Zi] = 6 · (5/6)10. 2
Abwandlung von Aufgabe 41:
X1, . . . , Xn seien unabhangig und N(µ, σ2) verteilt,
Xn := 1n(X1 + · · · + Xn)
Abwandlung von Aufgabe 41:
X1, . . . , Xn seien unabhangig und N(µ, σ2) verteilt,
Xn := 1n(X1 + · · · + Xn)
Warum uberdeckt das zufallige Intervall
[Xn − 2σ/√
n, Xn + 2σ/√
n[
den Parameter µ mit W’keit 0.95 ?
Sind X1, . . . , , Xn unabhangig und N(µ, σ2)-verteilt,
dann ist Xn := 1n(X1 + · · · + Xn)
N(µ, σ2/n)-verteilt
23
Sind X1, . . . , , Xn unabhangig und N(µ, σ2)-verteilt,
dann ist Xn := 1n(X1 + · · · + Xn)
N(µ, σ2/n)-verteilt
Xn fallt also mit Wahrscheinlichkeit 0.95 zwischen die
Grenzen µ − 2σ√n
und µ +2σ√
n.