Изменения
Нет описания правки
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 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)$.
# Будем генерировать бесконечную последовательность из 0 и 1 с помощью бросков честной монеты. Найдите матожидание числа бросков до выпадения трех нулей подряд.
# Будем генерировать бесконечную последовательность из 0 и 1 с помощью бросков честной монеты. Найдите матожидание числа бросков до первого вхождения 011.
# Будем генерировать бесконечную последовательность из 0 и 1 с помощью бросков честной монеты. Найдите матожидание числа бросков до первого вхождения 010.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке $p$ ($p$ - целое) и каждую секунду переходит равновероятно на 1 влево или вправо. Точка поглощается в точках 0 и $n$ ($n$ целое, больше $p$). Найдите вероятность поглощения в точке 0.
# Дана марковская цепь с двумя состояниями и вероятностью перехода из 1 в 2 равной $a$, вероятностью перехода из 2 в 1 равной $b$. Найдите в явном виде $n$-ю степень матрицы переходов.
# Для заданной рациональной дроби $p/q$ постройте марковскую цепь, все переходы которой имеют вероятность $1/2$, которая имеет поглощающее состояние с вероятностью поглощения $p/q$.
# Для заданной рациональной дроби $p/q$ постройте марковскую цепь, все переходы которой имеют вероятность $1/3$, которая имеет поглощающее состояние с вероятностью поглощения $p/q$.
# Для заданной рациональной дроби $p/q$ и целого $n$ постройте марковскую цепь, все переходы которой имеют вероятность $1/n$, которая имеет поглощающее состояние с вероятностью поглощения $p/q$.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Чему равно математическое ожидание координаты точки после $n$ шагов?
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание модуля координаты точки за $n$ шагов есть $O(\sqrt{n})$.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание максимума координаты точки за $n$ шагов есть $O(\sqrt{n})$.
# Предложите алгоритм решения задачи 48 для произвольных выигрышных строк Васи и Пети (работающий за полином от суммы длин этих строк).
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Какую строку длины 3 оптимально выбрать Васе, чтобы его вероятность выигрыша была максимальна?
# Предложите решение предыдущей задачи для произвольной выигрышной строки Пети (за полином от длины этой строки).
# Будем генерировать последовательность из 0 и 1 длины $n$ с помощью бросков честной монеты. Определите, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на 3.
# Будем генерировать последовательность из 0 и 1 длины $n$ с помощью бросков честной монеты. Предложите алгоритм определения, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на $p$ для заданного целого $p$.
# В Киндер-сюрпризах бывает $n$ различных игрушек. Вы покупаете по одному Киндер-сюрпризу со случайной игрушкой (может содержать игрушку, уже попадавшуюся ранее), пока не получите каждую из $n$ игрушек. Опишите процесс с помощью цепи Маркова. Посчитайте и оцените асимптотически матожидание количества купленных Киндер-сюрпризов.
# Посчитайте и оцените дисперсию для предыдущего задания.
