Zzz

1. Сколько байт в бите? Можно ли ответить на этот вопрос с точки зрения теории информации? Какое определение нужно дать для байта в этом случае?
2. Докажите, что для монеты энтропия максимальна в случае честной монеты
3. Докажите, что для $n$ исходов энтропия максимальна, если они все равновероятны
4. Есть нечестная монета с неизвестной вероятностью $p \in (0, 1)$. Проэмулируйте с помощью этой нечестной монеты честную
5. Найдите энтропию для геометрического распределения с $p = 1/2$ (счетное число исходов, $i$-й исход происходит с вероятностью $1/2^i$).
6. Найдите энтропию для геометрического распределения с произвольным $p$ (счетное число исходов, $i$-й исход происходит с вероятностью $(1-p)p^i$).
7. Пусть заданы полные системы событий $A = \{a_1, ..., a_n\}$ и $B = \{b_1, ..., b_m\}$. Определим условную энтропию $H(A | B)$ как $-\sum\limits_{i = 1}^m P(b_i) \sum\limits_{j = 1}^n P(a_j | b_i) \log P(a_j | b_i))$. Докажите, что $H(A | B) + H(B) = H(B | A) + H(A)$
8. Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$?
9. Что можно сказать про $H(A | A)$?
10. Энтропия кода Хемминга. Рассмотрим четырехбитный код Хемминга. По четырем информационным битам $X = (x_3, x_5, x_6, x_7)$ формируется три контрольных бита $y_1, y_2$ и $y_4$. Рассмотрим семерку битов $Y = (y_1, y_2, x_3, y_4, x_5, x_6, x_7)$. Пусть информационные биты выбираются случайно равновероятно. Чему равна энтропия $H(Y)$?
11. Продолжение предыдущей задачи. Отправленное сообщение либо доставляется корректно, либо в нем изменяется ровно один бит. Пусть все восемь перечисленных вариантов равновероятны. Доставляется сообщение $Z$. Чему равна энтропия $H(Z | Y)$?
12. Продолжение предыдущей задачи. Чему равна энтропия $H(Z)$?
13. Зафиксируем любой язык программирования. Колмогоровской сложностью слова $x$ называется величина $K(x)$ - минимальная длина программы на зафиксированном языке программирования, которая на пустом входе выводит $x$. Обозначим длину слова $x$ как $|x|$. Докажите, что $K(x) \le |x| + c$ для некоторой константы $c$.
14. Предложите семейство слов $x_1, x_2, \ldots, x_n, \ldots$, где $|x_i|$ строго возрастает и выполнено $K(x_i) = o(|x_i|)$.
15. Предложите семейство слов $x_1, x_2, \ldots, x_n, \ldots$, где $|x_i|$ строго возрастает и выполнено $K(x_i) = o(\log_2 |x_i|)$.
16. Колмогоровская сложность и энтропия Шеннона. Для слова $x$, в котором $i$-й символ алфавита встречается $f_i$ раз обозначим как $H(x)$ величину, равную энтропии случайного источника с распределением $p_i = f_i/|x|$. Докажите, что $K(x) \le nH(x) + O(\log n)$.
17. Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c n H(x)$
18. Симуляция дискретного распределения непрерывным. Рассмотрим источник, который возвращает равномерно распределенное вещественное число от 0 до 1 (для решения этой задачи достаточно формального определения, что для любого отрезка вероятность попадания значения в этот отрезок пропорциональна его длине). Мы хотим просимулировать дискретное равновероятное распределение с $n$ исходами. Как это сделать за $O(1)$? Будем считать, что тип данных double имеет достаточно точности и что операции со значениями типа double выполняются за $O(1)$.
19. Пусть теперь мы хотим просимулировать с помощью непрерывного равномерного распределения дискретное распределение с распределением вероятностей $[p_1, \ldots, p_n]$. Как это сделать за $O(\log n)$? Разрешается провести предподготовку за $O(n)$.
20. Схема Уолкера. Требуется просимулировать с помощью непрерывного равномерного распределения дискретное распределение с распределением вероятностей $[p_1, \ldots, p_n]$. Как это сделать за $O(1)$? Разрешается провести предподготовку за $O(n)$.