Изменения
Нет описания правки
# Пусть последовательно генерируется последовательность из 0 и 1 длины $n$. Каждый элемент последовательности определяется с помощью броска честной монеты. Определите, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на 3.
# Пусть последовательно генерируется последовательность из 0 и 1 длины $n$. Каждый элемент последовательности определяется с помощью броска честной монеты. Предложите алгоритм определния, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на $p$ для заданного целого $p$.
# Для симуляции распределения двумя исходами с вероятностями $p/q$ и $1-p/q$, где $p$ и $q$ целые, с помощью честной монеты можно использовать метод с делением отрезка [0-1], изложенный на лекции, а можно использовать поглощающую марковскую цепь "пьяницы на прямой" с $q+1$ вершиной. Проведите сравнительный анализ этих двух методов.
# Докажите, что математическое ожидание числа экспериментов при симуляции одного распределения другим асимптотически пропорционально отношению энтропий распределений (считайте, что энтропия симулируемого распределения больше).
# Постройте регулярную Марковскую цепь с двумя состояниями и эргодическим распределением $[a, 1-a]$ для заданного $a$.
# Постройте регулярную Марковскую цепь с $n$ состояниями и заданным распределением $[a, 1-a]$.
# В случае, если НОД длин циклов единственного эргодического класса не равен 1, соотвтствующая Марковская цепь будет периодической и эргодического распреления не будет. Тем не менее, что можно сказать про распределения в моменты с заданным остатком по модулю НОД длин циклов?
# Завершите доказательство леммы из эргодической теоремы для регулярных цепей. Доказите, что если $P$ - матрица переходов, не содержащая нулей, то для любого вектора $u$ с максимальным элементом $M$ и минимальным элементом $m$ максимальный и минимальный элементы $Pu$ $M'$ и $m'$, соответственно, удовлетворяют условиям $m \le m'$, $M \ge M'$, $M'-m' \le (M - m)(1 - 2\varepsilon)$, где $\varepsilon$ - минимальный элемент $P$.
</wikitex>
