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}}}

Zadania do rozwiązania

Zadanie 1

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) \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(⟨p_1,\dots ,p_m⟩)=-\sum _{i=1}^m{p}_i\log p_i$

Zadanie 2

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

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.