Меня очень радует, когда в обычных вроде как задачах воплощаются придуманные "монстры" высокой теории. Об одной такой жемчужине я расскажу сегодня.
Итак, вернемся к игре вроде орлянки, в которой игрок делает ставку и выигрывает с вероятностью p. Игра идет до тех пор, пока игрок не разорится, либо не достигнет заданной суммы В. Начинает он с некоторой суммы А.
Если он ставит по одной монете, то вероятность выигрыша и среднее число партий получается довольно просто с применением разностных уравнений. Я об этом писал в одной из своих ранних заметок.
Если р=0.5, то вероятность выиграть равна A/(A+B), среднее число партий равно АВ, где А и В выражены в ставках. Заметьте, что АВ может быть удивительно велико, хотя большинство игр намного короче. Например, при А=1 и В=1000 половина игр кончается на первом ходу, но АВ=1000. Реальное среднее намного меньше, так как надо отсечь очень длинные маловероятные игры, которые "никогда" не случаются, но свой вклад вносят.
Если вероятность выиграть партию не равна 0.5, то формулы немного усложняются.
Такая тактика — ставить минимум — хороша, если p>0.5, то есть игра в пользу игрока. Более того, если разрешается ставить сколь угодно мало, то вероятность выигрыша может быть равна единице.
А вот если p<0.5, то есть игра не в пользу игрока, то оптимальна другая тактика. Надо ставить всё, что есть, либо ровно столько, сколько нужно для победы. Скажем, если цель сто монет и у вас на руках 20, то ставьте все 20. А если на руках 70, то ставьте 30.
Удобно считать капиталы дробными, цель равной 1, и работать на отрезке [0, 1].
Любопытно, что из этой оптимальной тактики можно получить другие оптимальные тактики! Причем простым масштабированием. Имея меньше 0.5, ставим целью 0.5; а имея больше, убираем 0.5 в карман, играя остальным и ставя целью 0.5. Эта тактика тоже оптимальна, но дает больше партий в среднем.
Поначалу кажется, что такая тактика означает одну партию, в которой либо победа, либо поражение — но нет. Так только в случае А=0.5. Во всех остальных можно выиграть за один ход (если А>0.5) или проиграть за один ход; а если игра не закончилась одним ходом, то будет новая игра. Например, если А=0.2 и игрок выиграл, то у него 0.4. Если опять повезло, то 0.8. Теперь он поставит 0.2 и может позволить себе проиграть. У него окажется 0.6 и можно играть дальше.
Давайте последим за числом партий. Если A=0.5, то игра в любом случае закончится за один ход: либо повезло и достиг 1, либо не повезло и разорился. Если А=0.25, то можно проиграть на первом ходу, но если выиграл, то получил 0.5 и следующий ход так и так последний. Аналогично в случае А=0.75.
Удивительным образом, все зависит от двоичного разложения числа А. Если оно записано конечной двоичной дробью, то игра кончится за конечное число ходов. Например, пусть А=0.625, в двоичном коде 0.101. Считаем исход игры таким, чтобы можно было сыграть еще. Так, в первой партии игрок ставит 0.375 и проигрывает, сократив капитал до 0.25. Ставит всё и выигрывает, получив 0.5. Ставит всё, и теперь уж игра точно кончится, как уж повезет.
То есть, если за данный ход игра не кончилась, то новое А получается из предыдущего сдвигом на один двоичный разряд. Если А имеет вид 0.0ххх, то ставится все, и при победе А умножается на 2, что и есть сдвиг запятой. Если же А=0.1ххх, то ставится 1-А, и при проигрыше у игрока станет 2А-1, что означает сдвиг запятой и удаление целой части. То есть тоже сдвиг на один разряд.
Если разложение бесконечное, то игра может идти сколь угодно долго, хотя, конечно, вероятность длинной игры маленькая. Какая же?
Доказано, что игрок выигрывает, если выполнено неравенство W<A, где W — это случайная величина, составленная по следующему правилу: это двоичное разложение числа из [0,1], каждый бит определяется как дополнение результата соответствующей партии. Если в первой партии победа, то бит берем 0, если во второй поражение, то 1.
Так, если в первой партии поражение, то игрок проигрывает на первом ходу, если у него меньше 0.5. Правильно: у него A=0.0???, а W=0.1???>A.
Функция распределения F(x), то есть вероятность, что W<x, она же вероятность победы при данном капитале A=x, записывается так:
Здесь x с индексом — биты разложения числа х.
Опечатки нет: последние символы именно "p умножить на х с индексом n".
Что такое первое слагаемое, при n=1? Это и есть pxn. Если оно не нуль, то первый бит (xn) равен 1, то есть капитал 0.5 или больше. Если повезло (вероятность р), то всё, игра кончилась.
Второе слагаемое, при n=2. Если оно не нуль, то игра должна пережить первую партию (игрок выиграл, если у него меньше 0.5 или проиграл, если больше) и кончиться на второй.
Всё это довольно понятно, если вдуматься, но может быть я переведу оригинальную статью потом, попозже.
Эта функция монотонно возрастает, а значит, нет интервалов ненулевой длины, но с нулевой вероятностью.
В частности, если обозначить вероятность проигрыша в партии через q=1-p, то:
F(1/8)=p³, F(2/8)=p², p(3/8)=p²+p²q, F(4/8)=p,
F(5/8)=p+p²q, F(6/8)=p+pq, p(7/8)=p+pq+pq².
В случае p=q=0.5, всё довольно банально, F(x)=x. Однако при других значениях вероятности распределение сингулярно. Функция F(x) непрерывна, но имеет почти всюду производную, равную нулю.
Доказательство не очень сложно, но выходит за рамки заметки. В другой раз.
Но вообще, такие функции, мягко говоря, нетипичны. Потому и радостно, когда они возникают в таких бытовых обстоятельствах.
Вторая величина, которая нас интересует, это G(x): среднее число игр до разорения или достижения цели, то есть до конца игры. Здесь x — опять начальный капитал игрока. Формула такая:
Здесь использовано соглашение, что если слагаемое пустое, то это 1. Таково первое, при n=0. Число r(x) есть ранг: длина двоичной дроби. Если дробь бесконечна, то и сумма тоже.
Первое слагаемое описывает первый ход. Если r=1 (то есть x=0.5), то он единственный. Если битов два, то слагаемых тоже два. Первое уловит первый ход, второе — второй. До него должно дойти дело, то есть первой партией дело не кончилось. Если битов два, то и ходов не более двух, так что сумма на этом кончается.
В самом деле, два бита — это либо 0.01, либо 0.11 в двоичном коде, или 0.25 или 0.75 в десятичном. Можно проиграть/выиграть первую партию — тогда все кончится на первом ходе. А можно сыграть первый ход, придя к 0.5 в обоих случаях, и вторым ходом всё решится.
Функция, при p≠0.5, непрерывна на бесконечных двоичных дробях и разрывна на конечных. Некоторые ее значения:
G(1/8)=1+p+p², G(2/8)=1+p, G(3/8)=1+p+pq, G(4/8)=1,
G(5/8)=1+q+pq, G(6/8)=1+q, G(7/8)=1+q+q².
А при x=0.1010101... в двоичном коде, или 2/3 в десятичном, получим
Вот так вот. Функция, разрывная на всюду плотном множестве точек... Другая, непрерывная, но не абсолютно...И это в самой обычной задачке про орлянку с кривой монетой!
А вы изволите толковать про пятое измерение.
Заметка основана на статье Siegrist K. "How to gamble if you must", которая легко находится в Сети. Планирую осветить ее подробнее.
Оглавление рубрики "Вероятность..."
