Решение. Задача Пенни (#150)
Ответ: слово «ОРР» выигрывает с вероятностью 7/8, «РРР» – 1/8; средняя продолжительность игры – 7 бросков
Будем обозначать pₐ вероятность того, что первой в игре появится слово a.
Заметим, что «РРР» появляется всегда позже «ОРР» за исключением ситуации, когда «РРР» выбросили первыми тремя бросками. Таким образом, pₚₚₚ = 1/8. Хочется сразу сказать, что pₒₚₚ = 1 - pₚₚₚ = 7/8. Однако для строгости сначала покажем, что вероятность ничьи (или бесконечной игры) равна нулю.
Действительно, рассмотрим упрощение данной игры. Фиксируем слово a длины три.
- Делаем 3 броска монетки (серию)
- Смотрим, появилось ли a в серии
- Если появилось, то игра останавливается. Если нет, то продолжаем с шага 1, причём смотрим на совпадения только в данной серии бросков, предыдущие серии мы забываем.
Очевидно, что вероятность p появления слова a в отдельно взятой серии равна 1/8. Обозначим X случайную величину равную продолжительности (в сериях) этой упрощённой игры. Например, X = 1 с вероятностью p = 1/8 (если в первой же серии выбросили a), X = n с вероятностью p(1 - p)ⁿ⁻¹. Говорят, что X имеет геометрическое распределение с параметром p. Рассмотрим
Таким образом, множество всех конечных значений X имеет вероятность 1, поэтому вероятность того, что игра идёт бесконечно долго, равна нулю.
Заметим, что для любого слова a и для любой реализации бросков монетки упрощённая игра продолжается не менее исходной игры, так как при упрощении мы убрали связь с предыдущими бросками. С учётом этого, тем более, исходная игра будет конечной с вероятностью 1. Раз так, то вероятность ничьи равна нулю.
Ответ: последовательность «ОРР» выигрывает с вероятностью 7/8, «РРР» – 1/8
Средняя продолжительность игры
Рассмотрим случайную величину Y, которая принимает следующие 6 значений:
- S – стартовое состояние (до первого броска монетки)
- F – финальное состояние (после появления «ОРР» или «РРР»)
- ОО, ОР, РО, РР – по последним двум буквам в последовательности исходов
Нетрудно проверить, что Y – цепь Маркова, то есть вероятность перехода из состояние i в состояние j не зависит от всей предыдущей истории до попадания в i. Для наглядности изобразим множество состояний и матрицу перехода Y в виде графа.
Пусть mⱼ – среднее время попадания из состояния j в финальное состояние F, pᵢⱼ – вероятность перехода из i в j (за один шаг-бросок). Время мы исчисляем количеством бросков монетки. Для цепей Маркова верны следующие равенства для любого состояния j
Интуитивно их можно истолковать следующим образом. Среднее время перехода из i в некоторое фиксированное состояние F равно сумме средних времён перехода из следующих состояний j в F, взвешенных по вероятностям перехода из i в j, плюс 1 за переход из i в j. За строгим доказательством отсылаю к моей настольной книге по теории вероятности Ширяев «Вероятность – 1», §12, пункт 5.
По условию задачи нам нужно найти mₛ. Составим систему уравнений применительно к цепи Маркова Y
Отметим, что в первом уравнении системы мы использовали инкремент 2, так как переход из S в любое другое состояние осуществляется за 2 броска.
Заключительный комментарий: данный метод с использованием системы уравнений на основе графа переходов подходит также и для отыскания вероятностей выигрыша. Попробуйте составить систему и получить тот же ответ.
Ответ: средняя продолжительность игры – 7 бросков