Задача о разорении игрока — задача из области теории вероятностей.
Формулировка За столом сидят два игрока. У первого в распоряжении находится рублей, у второго в распоряжении находится рублей. Перед ними на столе лежит асимметричная монета (вероятность, что выпадет аверс, может равняться любому числу от 0 до 1 включительно). Если на монете выпадает аверс, то рубль выигрывает первый игрок (второй игрок выплачивает первому 1 рубль), а если выпадает реверс, то первый игрок платит второму один рубль. Требуется найти вероятность того, что один из игроков проиграется в ноль за шагов, и вероятность проигрыша каждого азартного игрока. Также необходимо вычислить среднюю длину игры.
Данная ситуация может быть смоделирована подобным образом: имеется блуждающая частица и коридор . Рассматривается вероятность того, что частица выйдет из коридора за шагов (проскочит через верхнюю или нижнюю стенку).
Схема Бернулли Рассмотрим схему Бернулли с испытаниями.
Пусть — вероятностное пространство, где — элементарные исходы, — алгебра подмножеств вероятностного пространства, , где — количество выпавших в данной последовательность единиц.
В выражении выше число выпавших единиц можно найти так: .
Введём последовательность бернуллиевских случайных величин:
Подзадача о нормированности вероятности Доказать, что
Решение
Это справедливо в силу того, что
, поскольку по условию .
Подзадача о независимости случайных величин ξi Доказать, что и независимы.
Решение
Независимость случайных величин означает, что
покажем это:
Случайное блуждание Для схемы Бернулли договоримся о следующем смысле случайной величины ξ: означает, что второй игрок платит первому, а — первый игрок второму.
Введём новое обозначение:
, .
Число равно длительности игры, а последовательность можно рассматривать как траекторию случайного блуждания некоторой частицы, выходящей из нуля, при этом очевидно равенство , а само означает выигрыш первого игрока у второго (который может быть отрицательным).
Пусть , — два целых числа, , . Требуется найти, с какой вероятностью за шагов будет осуществлён выход частицы из коридора, ограниченного и .
Далее, пусть — целое число, . Пусть также для верно, что (что означает, что игроки начинали играть с ненулевым капиталом в распоряжении). Пусть . Условимся считать, что , если . Если частица так и не пересекла границы, то не определён.
Для каждого и момент называется моментом остановки, который является случайной величиной, определённой на пространстве элементарных событий . — это событие, состоящее в том, что случайное блуждание , начинающееся в точке , выйдет из интервала в момент . Введём новые обозначения: , для . Пусть , — вероятности выхода частицы за время из интервала соответственно в точках и .
Пусть ; очевидно, что (пока игра не началась, частица находится внутри интервала с вероятностью 1). Пусть теперь . Тогда по формуле полной вероятности
Подзадача о рекуррентности Доказать, что
(1) ,
(2) .
Доказательство.
(1) Докажем, что .
, где — множество траекторий вида , которые за время впервые выходят из интервала в точке (показано на рисунке). Если случайный вектор попадает в подходящую траекторию, то он попадает в множество . Представим множество как . Дизъюнктное объединение правомерно по причине того, что у любой частицы, проходящей по траектории, . — те траектории из , для которых . — те траектории из , для которых . Заметим, что каждая траектория из находится в однозначном соответствии с траекторией из . Взаимно-однозначное соответствие доказывается от противного. Предположим, что (неоднозначное соответствие); тогда данная траектория не сможет вывести частицу из коридора за шагов (а только лишь за из-за изначального отдаления от верхней стенки коридора). В обратную сторону соответствие является также однозначным из определения: . Из этого следует, что (так как суть независимые одинаково распределённые случайные величины).
Существует и другой способ доказательства:
.
Это справедливо потому, что вероятности независимы (это было доказано ранее).
(2) Аналогично докажем, что .
Каждая траектория из находится в однозначном соответствии с траекторией из . Отсюда
Вывод рекуррентного соотношения Из уравнения для следует, что для и верно:
, для .
Формула полной вероятности также даёт нам следующий результат: .
Также отметим, что , и поэтому для . Это утверждение верно, так как к любой траектории, выводящей частицу за меньшее количество шагов, можно прибавить в начало один шаг (), на котором частица может прийти в точку как из (для ), так и из ().
Нахождение вероятностей При достаточно больших вероятность близка к — решению уравнения при тех условиях, что (выход произошёл сразу же из точки — конец игры, выиграл первый игрок), (первый игрок никогда не выиграет, если выход произойдёт мгновенно в точке ). Эти условия следуют из того, что . Это также будет доказано в этом разделе.
Сначала получим решение уравнения . Пусть игра несправедливая (). В таком случае найдём корни уравнения, то есть . Одно частное решение видно сразу: . Другое решение найдём, воспользовавшись тем, что — функция. Целесообразно употребить выражение с отношением , учитывая, что : . Отсюда правомерно предположить, что . Добавление константы ничего не изменит благодаря тому, что .
Теперь рассмотрим общее решение: . Воспользуемся теми условиями, что и , и получим, что
Подзадача о единственности решения Докажем единственность решения данной задачи. Для этого покажем, что любое решение задачи с граничными условиями может быть представлено в виде .
Решение
Рассмотрим некоторое решение при условиях , . Тогда всегда можно подобрать такие константы и , что , . Тогда из уравнения поставленной задачи следует, что . Тогда в общем случае . Следовательно, решение является единственным. Точно такой же ход рассуждений может быть применён и к .
Предельная сходимость Рассмотрим вопрос о быстроте предельной сходимости и к и . Пусть блуждание начинается из начала координат (). Для простоты обозначим , , . Иными словами, — это единица минус сумма вероятностей выхода частицы из коридора — вероятность того, что она останется блуждать в коридоре: . представляет собой событие . Рассмотрим число , где , и цепочку случайных величин . Если обозначить совокупное богатство за , то тогда . Этому есть разумное объяснение: если частица выходит из нуля и не пересекает границ, то тогда совершенно определённо сумма штук меньше, чем совокупный запас.
Подзадача о независимости случайных величин ζi Докажем, что независимы и одинаково распределённые. Достаточно доказать, что они независимы, так как все они имеют биномиальное распределение.
Решение
Докажем, что .
Вернёмся к рассмотрению сходимости.
Из только что доказанного следует что .
Рассмотрим дисперсию: (что вполне правомерно, так как , а — модифицированная бернуллиевская случайная величина), поэтому для достаточно больших и верно: , где , так как если , то . Если или , то для довольно больших верно, что , поэтому неравенство верно . Из вышесказанного следует, что , где . Так как , то ; так как и , то ; при . Аналогичные оценки справедливы и для разностей и , так как можно свести эти разности к разностям и при , .
Вернёмся к рассмотрению . По аналогии с решением уравнения , можно сказать, что у уравнения при граничных условиях , существует единственное решение
Нетрудно заметить, что при любых . Если же игра является справедливой (вероятность выпадения аверса равна вероятности выпадения реверса), то решения будут выглядеть следующим образом: , .
Ответ о вероятности разорения Величины и можно назвать вероятностями разорения первого и второго игрока при начальных капиталах и при стремлении количества ходов к бесконечности и характеризации случайной величина как выигрыша первого игрока, а — проигрыша первого игрока. В дальнейшем будет показано, почему такую последовательность действительно можно построить.
Если , то интуитивный смысл функции — это вероятность того, что частица, вышедшая из положения , достигнет верхней стенки () ранее, чем нуля. Из формул видно, что .
Парадокс увеличения ставки при неблагоприятной игре Что необходимо сделать первому игроку, если игра неблагоприятна для него?
Его вероятность проигрыша задана формулой .
Теперь пусть первый игрок с капиталом примет решение удвоить ставку и играть на два рубля, то есть , . Тогда обозначим предельную вероятность разорения первого игрока так: .
Поэтому , так как умножается на дробь, которая больше единицы при .
Поэтому если вероятность выпадения столь желанного для первого игрока аверса меньше , то ему выгодно увеличить ставку в раз: это уменьшает вероятность его терминального разорения за счёт того, что вырастает вероятность выскочить из коридора в точке . Это решение кажется парадоксальным, так как складывается впечатление, что при неблагоприятной ситуации надо снизить ставку и уменьшить проигрыш, но в действительности при бесконечном числе игр и низкой ставке проигрывающий игрок в конечном счёте обязательно проиграется в ноль, а игрок с высокой ставкой обладает большими шансами выпадения количества аверсов, достаточного для завершения игры в точке .
Длительность случайного блуждания Рассмотрим среднюю длительность блуждания нашей частицы. Введём математическое ожидание момента, когда игра прекращается: для . Выведем рекуррентное соотношение для математического ожидания продолжительности игры:
Для и мы получили рекуррентное соотношение для функции : при .
Введём граничные условия: если игра начинается в точке или , то тогда она тут же и завершится — её длительность будет равна 0: .
Из рекуррентного соотношения и граничных условий можно один за другим вычислить . Так как , то существует предел , который удовлетворяет соотношению : при выполнении . Данные переходы аналогичны тем, что мы рассмотрели при переходе к в уравнении вероятности проигрыша. Для того чтобы решить данное уравнение, надо ввести ещё одно условие: матожидание количества ходов должно быть конечным, то есть , .
Решим данное уравнение. В уравнении вероятности проигрыша () уже были получены частные решения и . Здесь же появляется ещё один претендент на роль частного решения: , поэтому . С учётом граничного условия находим при помощи ранее полученных соотношений : . В случае идеальной монетки получаем следующее выражение: . Применение граничного условия даёт: . Из этого следует, что в случае равных стартовых капиталов . Например, если у каждого игрока есть по 5 рублей, а ставка — 1 рубль, то в среднем разоряться игроки будут через 25 ходов.
При рассмотрении вышеуказанных формул подразумевалась конечностью математического ожидания числа ходов: . Теперь будет предложено доказательство этого факта.
Задача о конечности ожидаемого числа ходов Доказать, что .
Решение
Достаточно доказать это для случая (так как ранее было уже продемонстрировано, что случаи могут быть сведены к вариацией и ) и , а затем рассмотреть случай .
Итак, рассмотрим последовательность и введём случайную величину , где — момент остановки.
Пусть . Интерпретация такова: — это значение случайного блуждания в момент . Если , то ; если , то . Вспомним, что , и докажем, что , .
Для доказательства первого равенства напишем: . Совершенно очевидно, что , так как , при . Осталось доказать, что .
Для справедливо, что . Последнее событие может быть представлено в виде , где — некоторое подмножество множества . Это множество определяется только при . Для больших значения не влияют на . Множество вида также может быть представлено в виде . Благодаря независимости (доказано в подзадаче 2) вытекает, что случайные величины и независимы. Отсюда в силу того, что первый множитель нулевой.
Установлено, что для идеальной монетки , .
В случае же имеют место соотношения (поскольку ) и , поскольку . Теперь покажем, что .