Возвращаемся к теме разностных уравнений и случайных блужданий. Почти всю теорию вероятностей можно изложить на примере орлянки: игры, один из вариантов которой выглядит так. У одного игрока А ставок, у другого В ставок; они подбрасывают монетку или ещё как-то генерируют случайную величину и с равными вероятностями ставка переходит от одного к другому. Игра идет до разорения одного из игроков.
Мы уже анализировали эту игру и выяснили, что вероятность окончания игры за конечное число ходов равна единице: хотя вариант "гонять одну ставку из рук в руки до бесконечности" есть, но все такие варианты имеют совместно нулевую вероятность. Выяснили и вероятность выиграть данному игроку (с капиталом А): она равна А/(А+В). Вычислили и среднее число партий до конца игры: оно равно АВ, и это довольно удивительно.
В пределе, когда капитал противника В стремится к бесконечности, вероятность выиграть у него стремится к нулю (что понятно), а вот средняя длина игры стремится к бесконечности (что странно).
В этой заметке мы освежим в памяти технику получения этих результатов и вычислим ещё одну величину: средний капитал на руках у игрока за всю игру. Под средним капиталом будем понимать среднее из всех значений, которые имел игрок ПОСЛЕ хода при всевозможных сериях. Сам начальный капитал тоже учтем под конец.
Давайте начнем с простого. У каждого игрока по одной ставке: тогда с вероятностью ½ наш игрок проиграет и у него 0, и с той же вероятностью он победит и у него 2. В среднем у него 1. Поскольку у него и изначально была одна ставка, то среднее и с учетом начального капитала тоже 1.
Пусть у каждого по две ставки. Среднее обозначим Е(2) и у нас есть такие варианты:
две победы подряд: 3,4; два поражения: 1,0; победа, поражение, всё сначала: 3,2,Е(2); наоборот: 1,2,Е(2).
Всего 10 вариантов, и их сумма, деленная на 10, должна быть равна Е(2):
3+4+1+0+3+2+1+2+2Е(2)=10Е(2),
то есть 8Е(2)=16, Е(2)=2.
Начальный капитал тоже равен 2, то есть на среднее его учет не повлияет.
Теперь обозначим средний капитал при старте с n ставок через Е(n), и запишем уравнение
E(n) = ½E(n-1) + ½E(n+1).
То есть, средний капитал равен (начальный мы пока не учитываем) среднему между средним после проигрыша ставки и после выигрыша ставки.
Такое уравнение мы уже умеем решать. Давайте вспомним, как.
Это уравнение для бесконечных последовательностей E(n). Не всякая ему удовлетворяет, но если данная последовательность удовлетворяет, то можно ее умножить на любое число и это тоже решение. Более того, если две последовательности удовлетворяют уравнению, то их сумма также решение. То есть решения образуют линейное пространство.
Более того, пространство двумерно, так как, комбинируя два решения, можно задать какие угодно первые два члена последовательности — а остальные получатся из уравнения сами собой.
То есть если мы найдем две последовательности, удовлетворяющие уравнению, то мы найдем все, комбинируя эти две.
Две мы найдем легко: это E₁(n)=1 и E₂(n)=n. То есть, все решения имеют вид C₁+C₂n. Можно было начать с 1+n и 1-n, тоже вариант.
Теперь посмотрим на граничные условия. Средний капитал на руках игрока, если у него ничего нет, равен нулю. Отсюда сразу C₁=0.
Если же игрок уже выиграл, средний капитал у него на руках равен А+В. Отсюда C₂=1.
В итоге E(n)=n, a E(A)=A.
Получается странная вещь: в среднем капитал в ходе игры не меняется. В том смысле, что может стать и много, и мало, но в среднем все равно столько, сколько было изначально. И независимо от капитала противника, то есть даже при бесконечном капитале противника игрок в среднем при своих. Вероятность проиграть единица, средняя длина игры бесконечна, а средний капитал равен исходному.
Всё дело в длинных сериях, которые очень маловероятны, но вносят большой вклад в среднее. Мы это тоже обсуждали.
Давайте кратенько посмотрим, как решаются две другие задачи. Вероятность выиграть подчинена тому же уравнению, так как вероятность P(n) выиграть с капиталом n получается по формуле полной вероятности для случаев "выиграл ставку" и "проиграл ставку" выраженной через вероятности P(n-1) и P(n+1). Решением будет C₁+C₂n.
Только граничные условия другие: P(0)=0, P(A+B)=1. Первое означает, что проигравший не имеет шансов выиграть, и второе — что выигравший точно выиграл. Это и дает искомую формулу.
Среднее число ходов N(n) подчинено чуть другому уравнению:
N(n)=½N(n-1)+½N(n+1)+1.
Оно не линейно, но разность двух его решений удовлетворяет линейному уравнению, все решения которого мы уже знаем: это C₁+C₂n. Поэтому достаточно найти одно решение, чтобы получить из него все.
Одно решение подбирается: это -n². Тогда все вообще улавливает формула
-n²+C₁+C₂n.
Граничные условия N(0)=0, N(A+B)=0: оконченная игра далее не продолжается. Это приводит к C₁=0, C₂=A+B, и к N(n)=n(A+B-n).
Отсюда получаем N(A)=AB.
Любопытно здесь то, что сразу решить задачу для бесконечного капитала — не получится.
В следующий раз рассмотрим нечестную орлянку: с несимметричной монетой.