Teoria informacji/TI Ćwiczenia 2

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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

Urna zawiera zielonych kul, czerwonych i niebieskich. Które losowanie da wynik o większej entropii: losowanie kul ze zwracaniem czy bez zwracania?

Rozwiązanie


Ćwiczenie 4 [Kombinacja entropii]

Załóżmy, że mamy dwa źródła 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 .

Jaka jest entropia wyniku takiej procedury?

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.