Teoria informacji
i kodowanie

Ćwiczenia I

4. marca 2011 r.

Informacja, niepewność, entropia

Zadanie 1

Która z poniższych sekwencji niesie większą informację:

1. 10 liter alfabetu łacińskiego (zakładamy, że wystąpienie każdej z 32 liter jest równie praw-

dopodobne, nie interesuje nas rozróżnienie między wielkimi a małymi literami),

2. 32 cyfry (zakładamy, że wystąpienie każdej z dziesięciu cyfr jest równoprawdopodobne)?

Zadanie 2

Jaką maksymalną nieokreśloność może zawierać fotografia 6 × 9 cm

2

, jeśli rozmiar ziarna jest

równy 0, 01 × 0, 01 cm

2

, a każde ziarno może mieć trzy odcienie: biały, czarny i szary?

Zadanie 3

Źródło generuje wiadomości według następującego schematu:

1. losowane są 0 oraz 1 (odpowiednio z prawdopodobieństwem p

0

= p, p

1

= 1 − p);

2. losowanie kończy się w chwili wylosowania pierwszej jedynki;

3. źródło wysyła informację, za którym razem to nastąpiło.

Znajdź entropię takiego źródła.

Zadanie 4

(kolokwium z lat poprzednich)

Źródło Z jest zdefiniowane w sposób następujący:

1. mamy dwa źródła X i Y o entropiach odpowiednio H(X) i H(Y );

2. wiadomości generowane przez te źródła nie pokrywają się (np. jedno generuje litery, a

drugie — cyfry);

3. ze źródła Z wysyłamy informację na tej zasadzie, że z prawdopodobieństwem p podajemy

na jego wyjście wiadomość ze źródła X, a z prawdopodobieństwem (1 − p) — wiadomość
ze źródła Y .

Jaka jest entropia Z?

Zadanie 5

Pokaż, że dla niezależnych zmiennych losowych X, Y entropia łączna wynosi:

H(X, Y ) = H(X) + H(Y ).

Zadanie 6

Dla połączonych doświadczeń X i Y entropia warunkowa H(Y |X) jest definiowana jako wartość
średnia entropii Y pod warunkiem znanej realizacji zmiennej X. Wyprowadź wzór na entropię
warunkową oraz udowodnij następującą właściwość (reguła łańcuchowa):

H(X, Y ) = H(X) + H(Y |X).

Zadanie 7

Udowodnij że dla informacji wzajemnej (transinformacji ) zachodzą poniższe tożsamości:

I(X; Y ) = I(Y ; X)

= H(X) − H(X|Y )

= H(Y ) − H(Y |X)

= H(X) + H(Y ) − H(X, Y )

Strona 1 z 3

Teoria informacji
i kodowanie

Ćwiczenia I

4. marca 2011 r.

Zadanie 8

Zmienna losowa X przebiega z takim samym prawdopodobieństwem wartości całkowitoliczbowe
1, 2, . . . , 2N . Zmienna losowa Y jest zdefiniowana jako równa 0, gdy wartość X jest parzysta,
natomiast Y = 1, gdy wartość X jest nieparzysta. Udowodnij, że w takim przypadku zachodzi
następująca zależność dla entropii warunkowej :

H(X|Y ) = H(X) − 1.

Następnie pokaż, że zachodzi również:

H(Y |X) = 0.

Zadanie 9

(kolokwium z lat poprzednich)

Nasz kolega wykonuje w ukryciu trzy rzuty niesfałszowaną monetą, po czym mówi nam, ile w
sumie wypadło orłów. Jak wiele informacji na temat wyniku pierwszego rzutu dostarcza nam
w ten sposób?

Zadanie 10

(kolokwium z lat poprzednich)

Dana jest dyskretna zmienna losowa X. Inna zmienna losowa zdefiniowana jest przez funkcję:

Y = g(X),

gdzie g(·) jest dowolną funkcją. Jaka zależność ogólna zachodzi między H(Y ) i H(X):

H(Y ) ¬ H(X),

H(Y ) ­ H(X)?

Przy jakich warunkach nałożonych na funkcję g(·) zachodzi równość?

Zadanie 11

(*)

Używając właściwości logarytmu naturalnego:

ln x =

x − 1,

gdy x = 1

y < x − 1,

gdy x 6= 1

udowodnij następujące twierdzenie: Jeśli źródło generuje N ­ 1 wiadomości (1, . . . , N ), każdą z
prawdopodobieństwem odpowiednio p

i

, to entropia tego źródła charakteryzuje się następującą

właściwością:

H(X) = H (p

1

, p

2

, . . . , p

N

) ¬ lg N,

przy czym równość zachodzi wtedy i tylko wtedy gdy ∀

i

p

i

=

1

N

.

Zadanie 12

(**)

Pokaż, że źródło informacji X generujące wiadomości x

0

, x

2

, . . . , x

N

zgodnie z rozkładem dwu-

mianowym (rozkładem Bernoulliego), tj. dla 0 ¬ k ¬ N , 0 < p < 1 oraz q = 1 − p:

Pr{X = x

i

} =

N

i

!

p

i

q

N −i

,

charakteryzuje się entropią:

H(X) ¬ −N (p log

2

p + q log

2

q).

Strona 2 z 3

Teoria informacji
i kodowanie

Ćwiczenia I

4. marca 2011 r.

Informacja dodatkowa:
Na kartkach z zadaniami do kolejnych kolokwiów znajdą Państwo następujące dane:

„Legalna ściąga”:

H(X, Y ) = H(X) + H(Y |X) (reguła łańcuchowa)

I(X; Y ) = H(X) − H(X|Y ) = H(Y ) − H(Y |X) = H(X) + H(Y ) − H(X, Y )

X, Y — niezależne: H(X, Y ) = H(X) + H(Y )

Strona 3 z 3