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