Изменения
Нет описания правки
# Используйте метод границы Чернова, чтобы следующее. Пусть нечестную монету с вероятностью выпадения 1 равной p бросили $n$ раз. Обозначим случайную величину "число выпавших единиц" как $\xi$. Тогда $P(\xi \le n/2) \le exp(-\frac{1}{2p}n\left(p-\frac{1}{2}\right)^2)$.
# Как использовать результат из предыдущего задания для проверки, в какую сторону "перекошена" нечестная монета?
# Сколько байт в бите?
# Докажите, что для монеты энтропия максимальна в случае честной монеты
# Докажите, что для n исходов энтропия максимальна если они все равновероятны
# Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c n H(x)$
# Пусть заданы полные системы событий $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)$?
# Петя хочет пойти в кино с вероятностью ровно 1/3, а у него есть только честная монета. Может ли он осуществить свой замысел?
# Петя хочет пойти в кино с вероятностью ровно 1/13, а у него есть только честная монета. Может ли он осуществить свой замысел?
# Решите предудыщее задание для любой дроби $0 \le p/q \le 1$.
# Постройте схему получения вероятности 1/3 с помощью честной монеты, имеющую минимальное математическое ожидание числа бросков. Докажите оптимальность вашей схемы.
# Докажите, что если у вас есть честная монета, то вы можете получить случайный источник с распределением вероятностей $q_1, \ldots, q_m$ для любых значений $q_i$.
# Докажите, что если у вас есть случайный источник с распределением вероятностей $p_1, \ldots, p_n$, где хотя бы две значения отличны от 0, то вы можете получить случайный источник с распределением вероятностей $q_1, \ldots, q_m$ для любых значений $q_i$.
# Пусть у вас есть случайный источник с распределением вероятностей $1/n, \ldots, 1/n$ и вы используете его, чтобы получить случайный источник с распределением вероятностей $1/m, ..., 1/m$, где $m > n$. Оцените число экспериментов, которые в среднем необходимы для соответствующей симуляции. Сделайте вывод с точки зрения теории информации.
</wikitex>
