Teoria informacji/TI Ćwiczenia 2
Ćwiczenia
Ćwiczenie 1 [Obliczanie entropii]
Oblicz entropię wyniku w następujących eksperymentach:
- a) Rzucamy jedną kostką sześcienną,
- b) Rzucamy dwiema kostkami sześciennymi i sumujemy liczbę oczek,
- c) Rzucamy symetryczną monetą do uzyskania pierwszego orła. Wynikiem jest liczba wykonanych rzutów.
Rozwiązanie
Ćwiczenie 2 [Entropia funkcji]
Niech X będzie zmienną losową przyjmującą skończoną liczbę wartości. Jaka będzie zależność między entropią X a entropią Y, jeśli:
- a)
- b) ?
Rozwiązanie
Ćwiczenie 3 [Losowanie ze zwracaniem i bez]
Rozwiązanie
Ćwiczenie 4 [Kombinacja entropii]
Załóżmy, że mamy dwa źródła
Jaka jest entropia wyniku takiej procedury? i o entropiach i , takie że zbiory ich symboli są rozłączne. Przeprowadzamy losowanie i z prawdopodobieństwem podajemy symbol ze źródła , a z prawdopodobieństwem ze źródła .Rozwiązanie
Zadania domowe
Zadanie 1 - Aksjomatyzacja entropii
Niech
będzie funkcją rzeczywistą określoną na rozkładach prawdopodobieństwa, spełniającą warunki:(a)
jest ciągłą funkcją p(b)
(c)
Udowodnij, że H jest miarą entropii Shannona. Innymi słowy, że z dokładnością do wyboru podstawy logarytmu, jedyną funkcją spełniającą podane warunki jest
Zadanie 2 - Inne miary entropii
W kryptografii używa się często innych miar entropii. Przykładami są:
Definicja [Entropia kolizji]
Entropia kolizji mierzy prawdopodobieństwo, że dwie zmienne z danego rozkładu będą sobie równe
Definicja [Entropia minimum]
Entropia minimum mierzy prawdopodobieństwo odgadnięcia wartości zmiennej pochodzącej z danego rozkładu
Udowodnij następujące nierówności:
Zadanie 3 - Nieskończona entropia
W szczególnych przypadkach wartość entropii zmiennej losowej może być nieskończona. Niech
dla . jest tu stałą normalizującą: . Pokaż, że ma skończoną wartość (np. przez ograniczenie jej z góry przez całkę funkcji ), a więc definicja jest sensowna. Pokaż, że entropia tak zdefiniowanej zmiennej losowej jest nieskończona.