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