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

{{{3}}}

Ć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

{{{3}}}

Ć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

{{{3}}}

Ć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

{{{3}}}

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.