Изменения
Нет описания правки
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание модуля координаты точки за $n$ шагов есть $O(\sqrt{n})$.
# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание максимума координаты точки за $n$ шагов есть $O(\sqrt{n})$.
# Предложите алгоритм решения задачи 41 48 для произвольных выигрышных строк Васи и Пети (работающий за полином от суммы длин этих строк).
# Петя и Вася играют в игру. Они бросают честную монету, и выписывают результаты бросков. У каждого из игроков есть критерий победы, выигрывает тот, чей критерий наступит раньше. Петя выигрывает в тот момент, когда результаты последних трех бросков равны 001. Какую строку длины 3 оптимально выбрать Васе, чтобы его вероятность выигрыша была максимальна?
# Предложите решение предыдущей задачи для произвольной выигрышной строки Пети (за полином от длины этой строки).
# Будем генерировать последовательность из 0 и 1 длины $n$ с помощью бросков честной монеты. Определите, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на 3.
# Будем генерировать последовательность из 0 и 1 длины $n$ с помощью бросков честной монеты. Предложите алгоритм определения, с какой вероятностью некоторый префикс этой последовательности представляет собой запись двоичного числа, которое делится на $p$ для заданного целого $p$.
# В Киндер-сюрпризах бывает $n$ различных игрушек. Вы покупаете по одному Киндер-сюрпризу со случайной игрушкой (может содержать игрушку, уже попадавшуюся ранее), пока не получите каждую из $n$ игрушек. Опишите процесс с помощью цепи Маркова. Посчитайте и оцените асимптотически матожидание количества купленных Киндер-сюрпризов.
# Посчитайте и оцените дисперсию для предыдущего задания.
