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

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) ${\begin{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 )\end{aligned}}$

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)\geq H_{2}(X)\geq H_{\infty }(X)\geq {\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.