i kodowanie
Ćwiczenia
20. lutego 2008 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 prawdopodobne, 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 cm2, jeśli rozmiar ziarna jest równy 0 , 01 × 0 , 01 cm2, 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 2
i kodowanie
Ćwiczenia
20. lutego 2008 r.
Zadanie 8
Zmienna losowa X przebiega z takim samym prawdopodobieństwem wartości całkowitoliczbowe 1 , 2 , . . . , 2 N . 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)
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 10
(*)
Używając właściwości logarytmu naturalnego:
x − 1 ,
gdy x = 1
ln x =
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 pi, to entropia tego źródła charakteryzuje się następującą właściwością:
H( X) = H( p 1 , p 2 , . . . , pN ) ¬ lg N, przy czym równość zachodzi wtedy i tylko wtedy gdy ∀ipi = 1 .
N
Zadanie 11
(**)
Pokaż, że źródło informacji X generujące wiadomości x 0 , x 2 , . . . , xN zgodnie z rozkładem dwu-mianowym (rozkładem Bernoulliego), tj. dla 0 ¬ k ¬ N , 0 < p < 1 oraz q = 1 − p:
!
N
Pr {X = xi} =
piqN−i,
i
charakteryzuje się entropią:
H( X) ¬ −N ( p log2 p + q log2 q) .
Informacja dodatkowa:
Na kartkach z zadaniami do kolejnych kolokwiów znajdą Państwo następujące dane: 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 2 z 2