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