Изменения
Нет описания правки
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Вася выигрывает, когда результаты последних трех бросков равны 010. С какой вероятностью Петя выиграет?
# Можно ли сделать игру в предыдущем задании честной (чтобы вероятности выигрышей оказались равны $1/2$), используя нечестную монету?
# Сколько байт в бите? Можно ли ответить на этот вопрос с точки зрения теории информации? Какое определение нужно дать для байта в этом случае?
# Найдите в интернете распределение букв в английском тексте. Найдите энтропию этого распределения. Сравните с энтропией в случае, когда все буквы равновероятны.
# Найдите в интернете распределение букв в русском тексте. Найдите энтропию этого распределения. Сравните с энтропией в случае, когда все буквы равновероятны.
# Посмотрите комикс: https://xkcd.com/936/ Рассмотрим следующий подход к генерации пароля: выбираются 4 случайных английских слова и записываются через пробел. Найдите энтропию такого пароля.
# Докажите, что для монеты энтропия максимальна в случае честной монеты
# Докажите, что для $n$ исходов энтропия максимальна, если они все равновероятны
# Есть нечестная монета с неизвестной вероятностью $p \in (0, 1)$. Проэмулируйте с помощью этой нечестной монеты честную
# Найдите энтропию для геометрического распределения с $p = 1/2$ (счетное число исходов, $i$-й исход происходит с вероятностью $1/2^i$).
# Найдите энтропию для геометрического распределения с произвольным $p$ (счетное число исходов, $i$-й исход происходит с вероятностью $(1-p)p^i$).
# Пусть заданы полные системы событий $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)$
# Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$?
# Что можно сказать про $H(A | A)$?
# Энтропия кода Хемминга. Рассмотрим четырехбитный код Хемминга. По четырем информационным битам $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)$?
# Продолжение предыдущей задачи. Отправленное сообщение либо доставляется корректно, либо в нем изменяется ровно один бит. Пусть все восемь перечисленных вариантов равновероятны. Доставляется сообщение $Z$. Чему равна энтропия $H(Z | Y)$?
# Продолжение предыдущей задачи. Чему равна энтропия $H(Z)$?
# Зафиксируем любой язык программирования. Колмогоровской сложностью слова $x$ называется величина $K(x)$ - минимальная длина программы на зафиксированном языке программирования, которая на пустом входе выводит $x$. Обозначим длину слова $x$ как $|x|$. Докажите, что $K(x) \le |x| + c$ для некоторой константы $c$.
# Предложите семейство слов $x_1, x_2, \ldots, x_n, \ldots$, где $|x_i|$ строго возрастает и выполнено $K(x_i) = o(|x_i|)$.
# Предложите семейство слов $x_1, x_2, \ldots, x_n, \ldots$, где $|x_i|$ строго возрастает и выполнено $K(x_i) = o(\log_2 |x_i|)$.
# Колмогоровская сложность и энтропия Шеннона. Для слова $x$, в котором $i$-й символ алфавита встречается $f_i$ раз обозначим как $H(x)$ величину, равную энтропии случайного источника с распределением $p_i = f_i/|x|$. Докажите, что $K(x) \le nH(x) + O(\log n)$.
# Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c n H(x)$
# Симуляция дискретного распределения непрерывным. Рассмотрим источник, который возвращает равномерно распределенное вещественное число от 0 до 1 (для решения этой задачи достаточно формального определения, что для любого отрезка вероятность попадания значения в этот отрезок пропорциональна его длине). Мы хотим просимулировать дискретное равновероятное распределение с $n$ исходами. Как это сделать за $O(1)$? Будем считать, что тип данных double имеет достаточно точности и что операции со значениями типа double выполняются за $O(1)$.
# Пусть теперь мы хотим просимулировать с помощью непрерывного равномерного распределения дискретное распределение с распределением вероятностей $[p_1, \ldots, p_n]$. Как это сделать за $O(\log n)$? Разрешается провести предподготовку за $O(n)$.
# Схема Уолкера. Требуется просимулировать с помощью непрерывного равномерного распределения дискретное распределение с распределением вероятностей $[p_1, \ldots, p_n]$. Как это сделать за $O(1)$? Разрешается провести предподготовку за $O(n)$.
