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\ge 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(⟨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) Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \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{align} }

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.