Teoria informacji/TI Ćwiczenia 2

From Studia Informatyczne

Spis treści

Ć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

a) H(X)=\log 6 \approx 2,585
b) H(X)=\frac{2}{36} \log 36 + \frac{2}{18} \log 18 + \frac{2}{12}\log 12 + \frac{2}{9}\log 9 + \frac{10}{36}\log \frac{36}{5} + \frac{1}{6}\log 6 \approx 3,274
c) H(X)=\frac{1}{2} \log 2 + \frac{1}{4} \log 4 + \ldots = \sum_{i=1}^{\infty} i2^{-i} = \sum_{i=1}^{\infty} 2^{-i} + \sum_{i=2}^{\infty} 2^{-i} + \ldots = \sum_{i=0}^{\infty} 2^{-i} = 2


Ć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) Y = 2^X
b) Y = \sin X?

Rozwiązanie

a) 2^X jest funkcją różnowartościową, a więc każdej wartości X odpowiada dokładnie jedna wartość Y. Zatem H(Y)=H(X)
b) \sin X nie jest funkcją różnowartościową. W ogólności Y może przyjmować takie same wartości dla różnych X. H(Y)\le H(X)


Ćwiczenie 3 [Losowanie ze zwracaniem i bez]

Urna zawiera z zielonych kul, c czerwonych i n niebieskich. Które losowanie da wynik o większej entropii: losowanie k\ge 2 kul ze zwracaniem czy bez zwracania?

Rozwiązanie

Większą entropię ma losowanie kul ze zwracaniem. W tym przypadku kolory kolejnych kul są zdarzeniami niezależnymi. Losując bez zwracania zmniejszamy oczekiwaną entropię każdej kolejnej kuli.


Ćwiczenie 4 [Kombinacja entropii]

Załóżmy, że mamy dwa źródła X i Y o entropiach H(X) i H(Y), takie że zbiory ich symboli są rozłączne. Przeprowadzamy losowanie i z prawdopodobieństwem p podajemy symbol ze źródła X, a z prawdopodobieństwem 1-p ze źródła Y.

Jaka jest entropia wyniku takiej procedury?

Rozwiązanie

Rozpisujemy:

\aligned H & = - \sum_{s \in S} p(s) \cdot \log {p(s)} \\ & = - \sum_{s \in X} p \cdot p(s|X) \log (p \cdot p(s|X)) - \sum_{s \in Y} (1-p) \cdot p(s|Y) \log ((1-p) \cdot p(s|Y)) \\ & = - p \sum_{s \in X} p(s|X) (\log p + \log p(s|X)) - (1-p) \sum_{s \in Y} p(s|Y) (\log(1-p) + \log p(s|Y)) \\ & = -p \log p - (1-p) \log{(1-p)} + p H(X) +(1-p) H(Y)\\ & = H(p) + p H(X) + (1-p) H(Y) \endaligned

Zadania domowe

Zadanie 1 - Aksjomatyzacja entropii

Niech H będzie funkcją rzeczywistą określoną na rozkładach prawdopodobieństwa, spełniającą warunki:

(a) H(\langle p,1-p \rangle) jest ciągłą funkcją p

(b) H(\langle \frac{1}{mn}, \ldots, \frac{1}{mn} \rangle)= H(\langle \frac{1}{n}, \ldots, \frac{1}{n} \rangle) + H(\langle \frac{1}{m}, \ldots, \frac{1}{m} \rangle)


(c) \aligned H(\langle p_1, \ldots, p_m \rangle)& =H(\langle p_1 + \ldots + p_k, p_{k+1} + \ldots + p_m\rangle)\\ & + (p_1 + \ldots + p_k)H(\langle\frac{p_1}{\sum_{i=1}^k p_i}, \ldots, \frac{p_k}{\sum_{i=1}^k p_i}\rangle)\\ & + (p_{k+1} + \ldots + p_m)H(\langle\frac{p_{k+1}}{\sum_{i=k+1}^m p_i}, \ldots, \frac{p_m}{\sum_{i=k+1}^m p_i}\rangle) \endaligned

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

H(\langle p_1, \ldots, p_m \rangle)= - \sum_{i=1}^{m} p_i \log p_i


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

H_2(X)=-\log (\sum_{x \in X} P^2(x))

Definicja [Entropia minimum]

Entropia minimum mierzy prawdopodobieństwo odgadnięcia wartości zmiennej pochodzącej z danego rozkładu

H_{\infty}(X)=-\log \max_{x \in X} P(x)

Udowodnij następujące nierówności:

H(X)\ge H_2(X) \ge H_{\infty}(X) \ge \frac{H_2(X)}{2}


Zadanie 3 - Nieskończona entropia

W szczególnych przypadkach wartość entropii zmiennej losowej może być nieskończona. Niech P(X=n)= \frac{1}{c} \cdot \frac{1}{n \log^2 n} dla n = 2, 3, \ldots. c jest tu stałą normalizującą: c = \sum_{n=2}^{\infty} \frac{1}{n \log^2 n}. Pokaż, że c ma skończoną wartość (np. przez ograniczenie jej z góry przez całkę funkcji \frac{1}{x \log^2 x}), a więc definicja jest sensowna. Pokaż, że entropia tak zdefiniowanej zmiennej losowej jest nieskończona.