Zad. 1. Dwa dyskretne źródła wiadomości opisane są rozkładami prawdopodobieństwa podanymi w
tabelce. Obliczyć ilość informacji zawartej w każdej z wiadomości oraz dywergencję Kullbacka-Leiblera
D
KL
(P
X
, P
V
).
x
i
a
b
c
P
X
(x
i
)
1/4
1/2
1/4
x
i
a
b
c
P
V
(x
i
)
1/3
1/3
1/3
Rozwiązanie 1:
Ilość informacji zawartą w wiadomości x
i
wyznaczamy wg wzoru:
I(X = x
i
) = − log
2
(P (X = x
i
)) = − ln P (X = x
i
)/ ln 2
W naszym przypadku otrzymujemy
x
i
a
b
c
I(X = x
i
)
2 [bit]
1 [bit]
2 [bit]
x
i
a
b
c
I(V = x
i
)
1.58 [bit]
1.58 [bit]
1.58 [bit]
Z kolei dywergencja Kulbacka-Leiblera zdefiniowana jest wzorem
D
KL
(P
X
, P
V
) =
X
∀i
P (X = x
i
)· log
2
P (X = x
i
)
P (V = x
i
)
=
X
∀i
P (X = x
i
)· {log
2
P (X = x
i
) − log
2
P (V = x
i
)}
=
X
∀i
P (X = x
i
)·(I(V = x
i
) − I(X = x
i
))
W naszym przypadku :
D
KL
(P
X
, P
V
) ≈
1
4
(1.58 − 2) +
1
2
(1.58 − 1) +
1
4
(1.58 − 2) ≈ 0.08
Zauważmy, że zgodnie z właściwościami dywergencji Kulbacka-Leiblera wynik jest 0.
Rozwiązanie 2:
Ilość informacji zawartą w wiadomości x
i
wyznaczamy jak w pierwszym rozwiązaniu. Z
kolei dywergencję Kulbacka-Leiblera można obliczyć inaczej, korzystając z faktu, że rozkład
prawdopodobieństw opisujący źródło V jest rozkładem równomiernym. W takim przypadku
można skorzystać ze wzoru, który był wyprowadzony na ćwiczeniach.
D
KL
(P
X
, P
V
) = H
MAX
− H(X)
gdzie entropia maksymalna dla źródła X równa entropii źródła V ,
H
MAX
= log
2
M = log
2
3 ≈ 1.58 [bit]
a entropia źródła X
H(X) =
3
X
i=1
P (X = x
i
)I(X = x
i
) = 2·
1
4
·2 [bit] +
1
2
·1 [bit] = 1.5 [bit]
Stąd
D
KL
(P
X
, P
V
) ≈ 1.58 − 1.5 = 0.08
Zad. 2. Stacjonarne źródło nadające wiadomości a, b i c z jednakowym
prawdopodobieństwem jest opisane grafem przedstawiony obok. Obliczyć
entropię graniczną na symbol tego źródła przy założeniu, że wszystkie przejścia
przedstawione na grafie są jednakowo prawdopodobne.
Rozwiązanie:
Źródło jest stacjonarne i nadaje trzy różne wiadomości z jednakowym prawdopodobieństwem
stąd
P (X
k
= a) = P (X
k
= b) = P (X
k
= c) = 1/3
Na podstawie grafu możemy dodatkowo określić prawdopodobieństwa przejść, ze stanu
nadawania jednego symbolu (np. „a”) do stanu nadawania innego symbolu (np. „b”) .
Wiadomo, że wszystkie te przejścia cechuje takie samo prawdopodobieństwo p. Ponadto
można zauważyć, że źródło nigdy nie pozostaje w tym samym stanie. Zauważmy też, że
prawdopodobieństwo tego, że k + 1 symbol przyjmie określoną postać zależy od tego jaką
postać przyjął poprzedni symbol ale nie zależy od wcześniejszych symboli. Rozpatrywane
źródło można zatem opisać za pomocą łańcucha Markowa pierwszego rzędu z następującymi
prawdopodobieństwami warunkowymi:
P (X
k+1
= a|X
k
= a) = 0,
P (X
k+1
= a|X
k
= b) = p,
P (X
k+1
= a|X
k
= c) = p
P (X
k+1
= b|X
k
= a) = p,
P (X
k+1
= b|X
k
= b) = 0,
P (X
k+1
= b|X
k
= c) = p
P (X
k+1
= c|X
k
= a) = p,
P (X
k+1
= c|X
k
= b) = p,
P (X
k+1
= c|X
k
= c) = 0
Wartość parametru p można określić z warunku normalizacyjnego, z którego wynika, że
3
X
j=1
P (X = x
j
|X = x
i
) = 2p = 1
Skąd mamy p=0.5.
W przypadku stacjonarnego źródła dającego się opisać łańcuchem Markowa pierwszego rzędu
entropia graniczna na symbol H
∞
jest równa średniej entropii warunkowej bieżącego symbolu X
2
pod warunkiem, że znany jest symbol poprzedni X
1
.
H
∞
(X) = H(X
2
|X
1
) =
X
∀i
P (X
1
= x
i
)·H(X
2
|X
1
= x
i
)
gdzie entropia warunkowa symbolu X
2
pod warunkiem, że poprzedni symbol X
1
przyjął postać x
i
jest wyrażona wzorem:
H(X
2
|X
1
= x
i
) = −
X
∀j
P (X
2
= x
j
|X
1
= x
i
) log
2
(P (X
2
= x
j
|X
1
= x
i
))
W naszym przypadku:
H(X
2
|X
1
= a) =
−P (X
2
= a|X
1
= a) log
2
(P (X
2
= a|X
1
= a)) +
−P (X
2
= b|X
1
= a) log
2
(P (X
2
= b|X
1
= a)) +
−P (X
2
= c|X
1
= a) log
2
(P (X
2
= c|X
1
= a))
=
0· log
2
0 − 0.5· log
2
(0.5) − 0.5· log
2
(0.5) = 1 [bit]
podobnie
H(X
2
|X
1
= b) = 1 [bit]
oraz
H(X
2
|X
1
= c) = 1 [bit]
stąd średnia entropia warunkowa
H(X
2
|X
1
)
=
P (X
1
= a)H(X
2
|X
1
= a) + P (X
1
= b)H(X
2
|X
1
= b) + P (X
1
= c)H(X
2
|X
1
= c)
=
3·
1
3
·1 = 1 [bit]
Czyli graniczna entropia na symbol rozpatrywanego źródła H
∞
(X) = 1 [bit].