Изменения
Нет описания правки
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Вася выигрывает, когда результаты последних трех бросков равны 010. С какой вероятностью Петя выиграет?
# Можно ли сделать игру в предыдущем задании честной (чтобы вероятности выигрышей оказались равны $1/2$), используя нечестную монету?
# Сколько байт в бите? Можно ли ответить на этот вопрос с точки зрения теории информации? Какое определение нужно дать для байта в этом случае?
# Сравните количество информации в одном броске честной монеты и одном броске честной игральной кости.
# Докажите, что для монеты энтропия максимальна в случае честной монеты
# Докажите, что для $n$ исходов энтропия максимальна если они все равновероятны
# Найдите энтропию для геометрического распределения с $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$ называется величина $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)$.
