Изменения
Нет описания правки
# Пусть теперь мы хотим просимулировать с помощью непрерывного равномерного распределения дискретное распределение с распределением вероятностей $[p_1, \ldots, p_n]$. Как это сделать за $O(\log n)$? Разрешается провести предподготовку за $O(n)$.
# Схема Уолкера. Требуется просимулировать с помощью непрерывного равномерного распределения дискретное распределение с распределением вероятностей $[p_1, \ldots, p_n]$. Как это сделать за $O(1)$? Разрешается провести предподготовку за $O(n)$.
# Будем генерировать бесконечную последовательность из 0 и 1 с помощью бросков честной монеты. Найдите матожидание числа бросков до выпадения трех нулей подряд. Проверьте свой результат численным моделированием.
# Будем генерировать бесконечную последовательность из 0 и 1 с помощью бросков честной монеты. Найдите матожидание числа бросков до первого вхождения 011. Проверьте свой результат численным моделированием.
# Будем генерировать бесконечную последовательность из 0 и 1 с помощью бросков честной монеты. Найдите матожидание числа бросков до первого вхождения 010. Проверьте свой результат численным моделированием.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке $p$ ($p$ - целое) и каждую секунду переходит равновероятно на 1 влево или вправо. Точка поглощается в точках 0 и $n$ ($n$ целое, больше $p$). Найдите вероятность поглощения в точке 0. Проверьте свой результат численным моделированием.
# Дана марковская цепь с двумя состояниями и вероятностью перехода из 1 в 2 равной $a$, вероятностью перехода из 2 в 1 равной $b$. Найдите в явном виде $n$-ю степень матрицы переходов.
# Для заданной рациональной дроби $p/q$ постройте марковскую цепь, все переходы которой имеют вероятность $1/2$ или $1$, которая имеет поглощающее состояние с вероятностью поглощения $p/q$.
# Для заданной рациональной дроби $p/q$ постройте марковскую цепь, все переходы которой имеют вероятность $1/3$ или $1$, которая имеет поглощающее состояние с вероятностью поглощения $p/q$.
# Для заданной рациональной дроби $p/q$ и целого $n$ постройте марковскую цепь, все переходы которой имеют вероятность $1/n$ или $1$, которая имеет поглощающее состояние с вероятностью поглощения $p/q$.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Чему равно математическое ожидание координаты точки после $n$ шагов? Проверьте свой результат численным моделированием.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Чему равно математическое ожидание квадрата координаты точки после $n$ шагов? Проверьте свой результат численным моделированием.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание модуля координаты точки за $n$ шагов есть $O(\sqrt{n})$.
# У Марии есть три зонта, некоторые хранятся дома, некоторые на работе. Если она идет из дома на работу (или наоборот), и видит, что идет дождь, она берет с собой зонт, если он есть в том месте, где она находится. Если зонта на месте нет, она не берет зонт и промокает под дождем. Считаем, что дождь во время каждого перемещения Марии идет с вероятностью 0.2. Постройте марковскую цепь, описывающую этот процесс. Найдите, к чему стремится отношение перемещений, когда Мария промокнет под дождем.
# Будем генерировать последовательность из 0 и 1 длины $n$ с помощью бросков честной монеты. Определите, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на 3. Проверьте свой результат численным моделированием.
# Будем генерировать последовательность из 0 и 1 длины $n$ с помощью бросков честной монеты. Предложите алгоритм определения, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на $p$ для заданного целого $p$. Проверьте свой результат численным моделированием.
# В Киндер-сюрпризах бывает $n$ различных игрушек. Вы покупаете по одному Киндер-сюрпризу со случайной игрушкой (может содержать игрушку, уже попадавшуюся ранее), пока не получите каждую из $n$ игрушек. Опишите процесс с помощью цепи Маркова. Посчитайте и оцените асимптотически матожидание количества купленных Киндер-сюрпризов. Проверьте свой результат численным моделированием.
# Посчитайте и оцените асимптотически дисперсию для предыдущего задания.
# Блуждания по булевому кубу. Дана строка из $n$ нулей. За один шаг выбирается равномерно случайное число $i$ от $1$ до $n$ и $i$-й элемент строки заменяется на противоположный (0 на 1, а 1 на 0). Требуется найти математическое ожидание числа шагов до первого момента, когда строка будет полностью состоять из единиц. Разработайте алгоритм, который находит искомое матожидание. Примените свой алгоритм, чтобы найти значения матожидания для $n$ от 1 до 20.
# Предложите алгоритм решения задач 55-56 для произвольных выигрышных строк Васи и Пети (работающий за полином от суммы длин этих строк).
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Какую строку длины 3 оптимально выбрать Васе, чтобы его вероятность выигрыша была максимальна?
# Предложите решение предыдущей задачи для произвольной выигрышной строки Пети (за полином от длины этой строки).
