271
правка
Изменения
Нет описания правки
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Вася выигрывает, когда результаты последних трех бросков равны 010. С какой вероятностью Петя выиграет?
# Можно ли сделать игру в предыдущем задании честной (чтобы вероятности выигрышей оказались равны $1/2$), используя нечестную монету?
# Сколько байт в бите? Можно ли ответить на этот вопрос с точки зрения теории информации? Какое определение нужно дать для байта в этом случае?
# Найдите в интернете распределение букв в английском тексте. Найдите энтропию этого распределения. Сравните с энтропией в случае, когда все буквы равновероятны.
# Найдите в интернете распределение букв в русском тексте. Найдите энтропию этого распределения. Сравните с энтропией в случае, когда все буквы равновероятны.
# Посмотрите комикс: https://xkcd.com/936/ Рассмотрим следующий подход к генерации пароля: выбираются 4 случайных английских слова и записываются через пробел. Найдите энтропию такого пароля.
# На контрольной работе по дискретной математике будет 76 вариантов. Студент хочет передать номер своего варианта коллеге, используя двоичный код. Какое наименьшее число бит нужно передавать, чтобы коллега гарантированно смог узнать вариант студента?
# На контрольной работе по дискретной математике будет 76 вариантов. Четыре студента хотят передать номера своих вариантов одному коллеге, используя одно сообщение в двоичном коде. Какое наименьшее число бит нужно передавать, чтобы коллега гарантированно смог узнать варианты студентов?
# Я загадал число от 1 до 1000. Вы можете задавать вопросы, на которые я смогу отвечать только ""да"" или ""нет"". За какое наименьшее число вопросов гарантрованно можно узнать мое число?
# Я загадал число от 1 до 1000. Вы пишете несколько вопросов на карточках. Я их беру и на каждой из них отвечаю ""да"" или ""нет"". За какое наименьшее число вопросов гарантрованно можно узнать мое число?
# Докажите, что для монеты энтропия максимальна в случае честной монеты
# Докажите, что для $n$ исходов энтропия максимальна, если они все равновероятны
# Есть нечестная монета с неизвестной вероятностью $p \in (0, 1)$. Проэмулируйте с помощью этой нечестной монеты честную
# Найдите энтропию для геометрического распределения с $p = 1/2$ (счетное число исходов, $i$-й исход происходит с вероятностью $1/2^i$).
# Найдите энтропию для геометрического распределения с произвольным $p$ (счетное число исходов, $i$-й исход происходит с вероятностью $(1-p)p^{i-1}$).
# Пусть заданы полные системы событий $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)$?
# Симуляция дискретного распределения непрерывным. Рассмотрим источник, который возвращает равномерно распределенное вещественное число от 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)$.
