Список заданий по ДМ-сем2

<wikitex>

Дискретная математика, алгоритмы и структуры данных, 2 семестр

1. Докажите, что для монеты энтропия максимальна в случае честной монеты
2. Докажите, что для n исходов энтропия максимальна если они все равновероятны
3. Зафиксируйте ваш любимый язык программирования. Колмогоровской сложностью $K(x)$ для слова $x$ называется длина минимальной программы, которая выводит слово $x$. Докажите, что колмогоровская сложность не превышает $n H(x) + O(\log n)$, где $n$ - длина строки $x$, $H(x)$ - энтропия случайного источника с распределением соответствующим частотам встречания символов в $x$, константа в $O$, не зависит от слова $x$ (но может зависеть от выбранного языка программирования)
4. Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c H(x)$
5. Пусть заданы полные системы событий $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)$
6. Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$?
7. Что можно сказать про $H(A | A)$?
8. Постройте схему получения вероятности 1/3 с помощью честной монеты, имеющую минимальное математическое ожидание числа бросков. Докажите оптимальность вашей схемы.
9. Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке $p$ ($p$ - целое) и каждую секунду переходит равновероятно на 1 влево или вправо. Точка поглощается в точках 0 и $n$ ($n$ целое, больше $p$). Найдите вероятность поглощения в точке 0.
10. Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание максимума координаты точки за $n$ шагов есть $O(\sqrt{n})$.
11. Докажите, что математическое ожидание числа экспериментов при симуляции одного распределения другим асимптотически равно отношению энтропий распределений (считайте, что энтропия симулируемого распределения больше).
12. Пусть $f$ и $g$ - непрерывные возрастающие функции, причем $\lim\limits_{x\to-\infty}f(x)=0$, $\lim\limits_{x\to-\infty}g(x)=0$, $\lim\limits_{x\to+\infty}f(x)=1$, $\lim\limits_{x\to+\infty}g(x)=1$, кроме того считайте, что вы можете вычислять $f(x)$, $g(x)$, $f^{-1}(x)$ и $g^{-1}(x)$. У вас есть случайная величина с функцией распределения $f(x)$. Как вам получить случайную величину с функцией распределения $g(x)$?

</wikitex>