Изменения
Нет описания правки
# Докажите, что если у вас есть случайный источник с распределением вероятностей $p_1, \ldots, p_n$, где хотя бы две значения отличны от 0, то вы можете получить случайный источник с распределением вероятностей $q_1, \ldots, q_m$ для любых значений $q_i$.
# Пусть у вас есть случайный источник с распределением вероятностей $1/n, \ldots, 1/n$ и вы используете его, чтобы получить случайный источник с распределением вероятностей $1/m, ..., 1/m$, где $m > n$. Оцените число экспериментов, которые в среднем необходимы для соответствующей симуляции. Сделайте вывод с точки зрения теории информации.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке $p$ ($p$ - целое) и каждую секунду переходит равновероятно на 1 влево или вправо. Точка поглощается в точках 0 и $n$ ($n$ целое, больше $p$). Найдите вероятность поглощения в точке 0.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание максимума координаты точки за $n$ шагов есть $O(\sqrt{n})$.
# Дана марковская цепь с двумя состояниями и вероятностью перехода из 1 в 2 равной $a$, вероятностью перехода из 2 в 1 равной $b$. Найдите в явном виде $n$-ю степень матрицы переходов.
# Предложите решение задачи 41 для произвольных выигрышных строк Васи и Пети (за полином от суммы длин этих строк).
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних двух бросков равны 001. Какую строку длины 3 оптмально выбрать Васе, чтобы его вероятность выигрыша была максимальна?
# Предложите решение предыдущей задачи для произвольной выигрышной строки Пети (за полином от длины этой строки).
# Пусть последовательно генерируется последовательность из 0 и 1 длины $n$. Каждый элемент последовательности определяется с помощью броска честной монеты. Определите, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на 3.
# Пусть последовательно генерируется последовательность из 0 и 1 длины $n$. Каждый элемент последовательности определяется с помощью броска честной монеты. Предложите алгоритм определния, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на $p$ для заданного целого $p$.
</wikitex>
