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