Изменения
Нет описания правки
# Пусть теперь мы хотим просимулировать с помощью непрерывного равномерного распределения дискретное распределение с распределением вероятностей [p1,…,pn]. Как это сделать за O(logn)? Разрешается провести предподготовку за O(n).
# Схема Уолкера. Требуется просимулировать с помощью непрерывного равномерного распределения дискретное распределение с распределением вероятностей [p1,…,pn]. Как это сделать за 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, которая имеет поглощающее состояние с вероятностью поглощения p/q.
# Для заданной рациональной дроби p/q постройте марковскую цепь, все переходы которой имеют вероятность 1/3, которая имеет поглощающее состояние с вероятностью поглощения p/q.
# Для заданной рациональной дроби p/q и целого n постройте марковскую цепь, все переходы которой имеют вероятность 1/n, которая имеет поглощающее состояние с вероятностью поглощения p/q.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Чему равно математическое ожидание координаты точки после n шагов? Проверьте свой результат численым численным моделированием.# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Чему равно математическое ожидание квадрата координаты точки после n шагов? Проверьте свой результат численым численным моделированием.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание модуля координаты точки за n шагов есть O(√n).
# Будем генерировать последовательность из 0 и 1 длины n с помощью бросков честной монеты. Определите, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на 3. Проверьте свой результат численым численным моделированием.# Будем генерировать последовательность из 0 и 1 длины n с помощью бросков честной монеты. Предложите алгоритм определения, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на p для заданного целого p. Проверьте свой результат численым численным моделированием.# В Киндер-сюрпризах бывает n различных игрушек. Вы покупаете по одному Киндер-сюрпризу со случайной игрушкой (может содержать игрушку, уже попадавшуюся ранее), пока не получите каждую из n игрушек. Опишите процесс с помощью цепи Маркова. Посчитайте и оцените асимптотически матожидание количества купленных Киндер-сюрпризов. Проверьте свой результат численым численным моделированием.
# Посчитайте и оцените дисперсию для предыдущего задания.
# Блуждания по булевому кубу. Дана строка из n нулей. За один шаг выбирается равномерно случайное число i от 1 до n и i-й элемент строки заменяется на противоположный (0 на 1, а 1 на 0). Требуется найти математическое ожидание числа шагов до первого момента, когда строка будет полностью состоять из единиц. Разработайте алгоритм, который находит искомое матожидание. Примените свой алгоритм, чтобы найти значения матожидания для n от 1 до 20.
