Vorlesung 13b Relative Entropie - math.uni-frankfurt.deismi/wakolbinger/teaching/Elesto07/... · S sei eine abzahlbare Menge (ein “Alphabet”).¨ Die Elemente von S nennen wir

Vorlesung 13b

Relative Entropie

1

S sei eine abzahlbare Menge (ein “Alphabet”).

2


Die Elemente von S nennen wir Buchstaben.



X sei eine S-wertieg Zufallsvariable

(ein “zufalliger Buchstabe”).





H2[X] := −∑

a∈Sν(a) log2 ν(a)





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

3


Wir schreiben

H[X] := −∑

a∈Sν(a) log ν(a),

wobei log zu einer beliebigen, festen Basis genommen wird:


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.

4



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

5



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),





D(ν‖ρ) :=∑

a∈Sν(a) log

ν(a)

ρ(a),

wobei die Summanden mit ν(a) = 0

gleich 0 gesetzt werden.

Interpretation der relativen Entropie:

6


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.





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:

7



−∑

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[ℓρ(X)] < −∑




−∑

a ν(a) log ν(a) ≤ E[kν(X)] < −∑

a ν(a) log ν(a) + 1.



−∑

a ν(a) log ρ(a) ≤ E[ℓρ(X)] < −∑




−∑

a ν(a) log ν(a) ≤ E[kν(X)] < −∑


Daraus folgt fur die Differenz:



−∑

a ν(a) log ρ(a) ≤ E[ℓρ(X)] < −∑




−∑

a ν(a) log ν(a) ≤ E[kν(X)] < −∑


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




D(ν‖ρ) = −∑

a:ν(a)>0

ν(a) logρ(a)

ν(a)




D(ν‖ρ) = −∑

a:ν(a)>0

ν(a) logρ(a)

ν(a)

≥ −∑

a:ν(a)>0

ν(a) c ·(ρ(a)

ν(a)− 1

)




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 ν = ρ.

9


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

)

,




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.




Also folgt aus

−∑

a:ν(a)>0

ν(a) logρ(a)

ν(a)= −c

∑

a:ν(a)>0

ν(a)(ρ(a)

ν(a)− 1

)

,


Und aus∑

a:ν(a)>0

ρ(a) −∑

aν(a) = 0




Also folgt aus

−∑

a:ν(a)>0

ν(a) logρ(a)

ν(a)= −c

∑

a:ν(a)>0

ν(a)(ρ(a)

ν(a)− 1

)

,


Und aus∑

a:ν(a)>0

ρ(a) −∑

aν(a) = 0

folgt ρ(a) = ν(a) fur alle a mit ν(a) = 0. 2

Zusammenfassend ergibt sich der

10


Satz (von der relativen Entropie):



Die relative Entropie D(ν‖ρ) ist nichtnegativ,



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



(∗) −∑


∑

aν(a) log ρ(a)

mit Gleichheit genau fur ν = ρ.



(∗) −∑


∑

aν(a) log ρ(a)


Wir sehen:

Hat X die Verteilung ν,

so liefert jede Wahl von ρ eine Schranke fur H[X],


Beispiel: Vegleich mit der uniformen Verteilung:

12


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] ≤ −∑

aν(a) log(

1

n) = logn .

H[X] ≤ logn.





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:

13


Sei nun S = {0,1,2, . . .}, und ρ(k) := 2−k−1


H2[X] ≤∑

aν(a) log2(−2−k−1)

=∞∑

k=0

(k + 1)ν(k) = (E[X] + 1) .


Sei nun S = {0,1,2, . . .}, und ρ(k) := 2−k−1


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:


Sei nun S = {0,1,2, . . .}, und ρ(k) := 2−k−1


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:

15

Zusammengefasst:

Unter allen Zufallsvariablen mit

Erwartungswert ≤∑

au(a)e−βu(a)/z

Zusammengefasst:



au(a)e−βu(a)/z

hat diejenige die großte Entropie,

die die Verteilungsgewichte e−βu(a)/z hat.

Zusammengefasst:



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)

16

Beispiel:


D(ν‖ρ) =?

Beispiel:


D(ν‖ρ) =?

logν(k)

ρ(k)= log

αk(1 − α)n−k

pk(1 − p)n−k= k log

α

p+(n−k) log

1 − α

1 − p

Beispiel:


D(ν‖ρ) =?

logν(k)

ρ(k)= log

αk(1 − α)n−k


α

p+(n−k) log

1 − α

1 − p

Wegen∑

k ν(k) = nα ist somit

Beispiel:


D(ν‖ρ) =?

logν(k)

ρ(k)= log

αk(1 − α)n−k


α

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.

17


Kn := Y1 + . . . + Yn sei die “Anzahl der Erfolge” bis n.

Sei [c, d] ein Intervall rechts von p (mit p < c < d).




Satz (Boltzmann)




Satz (Boltzmann)

lnP

{

Kn

n∈ [c, d]

}

∼ −n h(c, p) fur n → ∞,




Satz (Boltzmann)

lnP

{

Kn

n∈ [c, d]

}

∼ −n h(c, p) fur n → ∞,

mit h wie im vorigen Beispiel.




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.

20

Losung:



Zerlegung nach den Ausgangen von K ergibt:

Losung:




P{J1 = J2} =∑

k P{K = k}Pk{J1 = J2}=

∑

k P{K = k}∑rj=1

kj(kj−1)

n(n−1)

Losung:




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:




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)].


E[K2j ] = p2

j n(n − 1) + npj.

Losung:




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)].


E[K2j ] = p2

j n(n − 1) + npj.

Somit ist E[Kj(Kj − 1)] = p2j n(n − 1),

Losung:




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)].


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




Fur i = 1, . . . ,6 sei Zi := I{Ki=0}.

Es sei Y := #{i : Ki = 0}.




Fur i = 1, . . . ,6 sei Zi := I{Ki=0}.

Es sei Y := #{i : Ki = 0}.

Berechnen Sie den Erwartungswert von Y .




Fur i = 1, . . . ,6 sei Zi := I{Ki=0}.

Es sei Y := #{i : Ki = 0}.


Losung: E[Zi] = P{Ki = 0} = (5/6)10,

denn Ki ist binomial (10,1/6)- verteilt.




Fur i = 1, . . . ,6 sei Zi := I{Ki=0}.

Es sei Y := #{i : Ki = 0}.


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:

22


X1, . . . , Xn seien unabhangig und N(µ, σ2) verteilt,

Xn := 1n(X1 + · · · + Xn)


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


dann ist Xn := 1n(X1 + · · · + Xn)


Xn fallt also mit Wahrscheinlichkeit 0.95 zwischen die

Grenzen µ − 2σ√n

und µ +2σ√

n.


dann ist Xn := 1n(X1 + · · · + Xn)


Xn fallt also mit Wahrscheinlichkeit 0.95 zwischen die

Grenzen µ − 2σ√n

und µ +2σ√

n.

Damit gleichbedeutend: Das zufallige Intervall

Xn − 2σ√n

, Xn +2σ√

n

uberdeckt µ mit W’keit 0.95. 2

Documents

Vorlesung 13b Relative Entropie - math.uni-frankfurt.deismi/wakolbinger/teaching/Elesto07/... · S sei eine abzahlbare Menge (ein “Alphabet”).¨ Die Elemente von S nennen wir