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

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+\dots =\sum _{i=1}^{\mathrm{\infty }}i{2}^{-i}=\sum _{i=1}^{\mathrm{\infty }}{2}^{-i}+\sum _{i=2}^{\mathrm{\infty }}{2}^{-i}+\dots =\sum _{i=0}^{\mathrm{\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:

$\begin{array}{rl}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)+pH(X)+(1-p)H(Y)\\ & =H(p)+pH(X)+(1-p)H(Y)\end{array}$

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(⟨p,1-p⟩)$ jest ciągłą funkcją p

(b) $H(⟨\frac{1}{mn},\dots ,\frac{1}{mn}⟩)=H(⟨\frac{1}{n},\dots ,\frac{1}{n}⟩)+H(⟨\frac{1}{m},\dots ,\frac{1}{m}⟩)$

(c) $\begin{array}{rl}H(⟨p_1,\dots ,p_m⟩)& =H(⟨p_1+\dots +p_k,p_{k+1}+\dots +p_m⟩)\\ & +(p_1+\dots +p_k)H(⟨\frac{p_1}{\sum _{i=1}^k{p}_i},\dots ,\frac{p_k}{\sum _{i=1}^k{p}_i}⟩)\\ & +(p_{k+1}+\dots +p_m)H(⟨\frac{p_{k+1}}{\sum _{i=k+1}^m{p}_i},\dots ,\frac{p_m}{\sum _{i=k+1}^m{p}_i}⟩)\end{array}$

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(⟨p_1,\dots ,p_m⟩)=-\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_{\mathrm{\infty }}(X)=-\log \underset{x\in X}{\max }P(x)$

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

$H(X)\ge H_2(X)\ge H_{\mathrm{\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,\dots$. $c$ jest tu stałą normalizującą: $c=\sum _{n=2}^{\mathrm{\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.