За столом сидят два игрока. У первого в распоряжении находится рублей, у второго в распоряжении находится рублей. Перед ними на столе лежит асимметричная монета (вероятность, что выпадет аверс, может равняться любому числу от 0 до 1 включительно). Если на монете выпадает аверс, то рубль выигрывает первый игрок (второй игрок выплачивает первому 1 рубль), а если выпадает реверс, то первый игрок платит второму один рубль. Требуется найти вероятность того, что один из игроков проиграется в ноль за шагов, и вероятность проигрыша каждого азартного игрока. Также необходимо вычислить среднюю длину игры.
Данная ситуация может быть смоделирована подобным образом: имеется блуждающая частица и коридор . Рассматривается вероятность того, что частица выйдет из коридора за шагов (проскочит через верхнюю или нижнюю стенку).
Для схемы Бернулли договоримся о следующем смысле случайной величины ξ: означает, что второй игрок платит первому, а – первый игрок второму.
Введём новое обозначение:
, .
Число равно длительности игры, а последовательность можно рассматривать как траекторию случайного блуждания некоторой частицы, выходящей из нуля, при этом очевидно равенство , а само означает выигрыш первого игрока у второго (который может быть отрицательным).
Пусть , — два целых числа, , . Требуется найти, с какой вероятностью за шагов будет осуществлён выход частицы из коридора, ограниченного и .
Далее, пусть — целое число, . Пусть также для верно, что (что означает, что игроки начинали играть с ненулевым капиталом в распоряжении). Пусть . Условимся считать, что , если . Если частица так и не пересекла границы, то не определён.
Для каждого и момент называется моментом остановки, который является случайной величиной, определённой на пространстве элементарных событий . — это событие, состоящее в том, что случайное блуждание, начинающееся в точке , выйдет из интервала в момент . Введём новые обозначения: , для . Пусть , — вероятности выхода частицы за время из интервала соответственно в точках и .
Пусть ; очевидно, что (пока игра не началась, частица находится внутри интервала с вероятностью 1). Пусть теперь . Тогда по формуле полной вероятности
, где — множество траекторий вида , которые за время впервые выходят из интервала в точке (показано на рисунке). Если случайный вектор попадает в подходящую траекторию, то он попадает в множество . Представим множество как . Дизъюнктное объединение правомерно по причине того, что у любой частицы, проходящей по траектории, . — те траектории из , для которых . — те траектории из , для которых . Заметим, что каждая траектория из находится в однозначном соответствии с траекторией из . Взаимно-однозначное соответствиедоказывается от противного. Предположим, что (неоднозначное соответствие); тогда данная траектория не сможет вывести частицу из коридора за шагов (а только лишь за из-за изначального отдаления от верхней стенки коридора). В обратную сторону соответствие является также однозначным из определения: . Из этого следует, что (так как суть независимые одинаково распределённые случайные величины).
Существует и другой способ доказательства:
.
Это справедливо потому, что вероятности независимы (это было доказано ранее).
(2) Аналогично докажем, что .
Каждая траектория из находится в однозначном соответствии с траекторией из . Отсюда
Также отметим, что , и поэтому для . Это утверждение верно, так как к любой траектории, выводящей частицу за меньшее количество шагов, можно прибавить в начало один шаг (), на котором частица может прийти в точку как из (для ), так и из ().
При достаточно больших вероятность близка к — решению уравнения при тех условиях, что (выход произошёл сразу же из точки — конец игры, выиграл первый игрок), (первый игрок никогда не выиграет, если выход произойдёт мгновенно в точке ). Эти условия следуют из того, что . Это также будет доказано в этом разделе.
Сначала получим решение уравнения . Пусть игра несправедливая (). В таком случае найдём корни уравнения, то есть . Одно частное решение видно сразу: . Другое решение найдём, воспользовавшись тем, что — функция. Целесообразно употребить выражение с отношением , учитывая, что : . Отсюда правомерно предположить, что . Добавление константы ничего не изменит благодаря тому, что .
Теперь рассмотрим общее решение: . Воспользуемся теми условиями, что и , и получим, что
Докажем единственность решения данной задачи. Для этого покажем, что любое решение задачи с граничными условиями может быть представлено в виде .
Решение
Рассмотрим некоторое решение при условиях , . Тогда всегда можно подобрать такие константы и , что , . Тогда из уравнения поставленной задачи следует, что . Тогда в общем случае . Следовательно, решение является единственным. Точно такой же ход рассуждений может быть применён и к .
Рассмотрим вопрос о быстроте предельной сходимости и к и . Пусть блуждание начинается из начала координат (). Для простоты обозначим , , . Иными словами, — это единица минус сумма вероятностей выхода частицы из коридора — вероятность того, что она останется блуждать в коридоре: . представляет собой событие . Рассмотрим число , где , и цепочку случайных величин . Если обозначить совокупное богатство за , то тогда . Этому есть разумное объяснение: если частица выходит из нуля и не пересекает границ, то тогда совершенно определённо сумма штук меньше, чем совокупный запас.
Рассмотрим дисперсию: (что вполне правомерно, так как , а — модифицированная бернуллиевская случайная величина), поэтому для достаточно больших и верно: , где , так как если , то . Если или , то для довольно больших верно, что , поэтому неравенство верно . Из вышесказанного следует, что , где . Так как , то ; так как и , то ; при . Аналогичные оценки справедливы и для разностей и , так как можно свести эти разности к разностям и при , .
Вернёмся к рассмотрению . По аналогии с решением уравнения , можно сказать, что у уравнения при граничных условиях , существует единственное решение
Нетрудно заметить, что при любых . Если же игра является справедливой (вероятность выпадения аверса равна вероятности выпадения реверса), то решения будут выглядеть следующим образом: , .
Величины и можно назвать вероятностями разорения первого и второго игрока при начальных капиталах и при стремлении количества ходов к бесконечности и характеризации случайной величина как выигрыша первого игрока, а — проигрыша первого игрока. В дальнейшем будет показано, почему такую последовательность действительно можно построить.
Если , то интуитивный смысл функции — это вероятность того, что частица, вышедшая из положения , достигнет верхней стенки () ранее, чем нуля. Из формул видно, что
.
Парадокс увеличения ставки при неблагоприятной игре
Что необходимо сделать первому игроку, если игра неблагоприятна для него?
Его вероятность проигрыша задана формулой .
Теперь пусть первый игрок с капиталом примет решение удвоить ставку и играть на два рубля, то есть , . Тогда обозначим предельную вероятность разорения первого игрока так: .
Поэтому , так как умножается на дробь, которая больше единицы при .
Поэтому если вероятность выпадения столь желанного для первого игрока аверса меньше , то ему выгодно увеличить ставку в раз: это уменьшает вероятность его терминального разорения за счёт того, что вырастает вероятность выскочить из коридора в точке . Это решение кажется парадоксальным, так как складывается впечатление, что при неблагоприятной ситуации надо снизить ставку и уменьшить проигрыш, но в действительности при бесконечном числе игр и низкой ставке проигрывающий игрок в конечном счёте обязательно проиграется в ноль, а игрок с высокой ставкой обладает большими шансами выпадения количества аверсов, достаточного для завершения игры в точке .
Рассмотрим среднюю длительность блуждания нашей частицы. Введём математическое ожидание момента, когда игра прекращается: для . Выведем рекуррентное соотношение для математического ожидания продолжительности игры:
Для и мы получили рекуррентное соотношение для функции : при .
Введём граничные условия: если игра начинается в точке или , то тогда она тут же и завершится — её длительность будет равна 0: .
Из рекуррентного соотношения и граничных условий можно один за другим вычислить . Так как , то существует предел , который удовлетворяет соотношению : при выполнении . Данные переходы аналогичны тем, что мы рассмотрели при переходе к в уравнении вероятности проигрыша. Для того чтобы решить данное уравнение, надо ввести ещё одно условие: матожидание количества ходов должно быть конечным, то есть , .
Решим данное уравнение. В уравнении вероятности проигрыша () уже были получены частные решения и . Здесь же появляется ещё один претендент на роль частного решения: , поэтому . С учётом граничного условия находим при помощи ранее полученных соотношений : . В случае идеальной монетки получаем следующее выражение: . Применение граничного условия даёт: . Из этого следует, что в случае равных стартовых капиталов . Например, если у каждого игрока есть по 5 рублей, а ставка — 1 рубль, то в среднем разоряться игроки будут через 25 ходов.
При рассмотрении вышеуказанных формул подразумевалась конечностью математического ожидания числа ходов: . Теперь будет предложено доказательство этого факта.
Достаточно доказать это для случая (так как ранее было уже продемонстрировано, что случаи могут быть сведены к вариацией и ) и , а затем рассмотреть случай .
Итак, рассмотрим последовательность и введём случайную величину , где — момент остановки.
Пусть . Интерпретация такова: — это значение случайного блуждания в момент . Если , то ; если , то . Вспомним, что , и докажем, что , .
Для доказательства первого равенства напишем: . Совершенно очевидно, что , так как , при . Осталось доказать, что .
Для справедливо, что . Последнее событие может быть представлено в виде , где — некоторое подмножество множества . Это множество определяется только при . Для больших значения не влияют на . Множество вида также может быть представлено в виде . Благодаря независимости (доказано в подзадаче 2) вытекает, что случайные величины и независимы. Отсюда в силу того, что первый множитель нулевой.
Установлено, что для идеальной монетки , .
В случае же имеют место соотношения (поскольку ) и , поскольку . Теперь покажем, что .
В случае справедливой игры в силу соотношения верно, что . Тогда же , поэтому . Из неравенства следует, что математическое ожидание сходится при к предельному значению . В случае несправедливой игры . Так как за обозначался момент первого вылета частицы за пределы коридора, то математическое ожидание его меньше определённых чисел, следовательно, меньше бесконечности. При таком условии .
n=100;% The length of \xi_i seriesU=rand(n,1);% Generate 100 random uniform [0;1] valuesXI=zeros(n,1);% Reserve memory for 100 modified Bernoulliq=0.55;% Reverse probabilityp=1-q;% Averse probability% The following cycle creates a Bernoulli distribution based on uniform [0;1]fori=1:n% This cycle divides the [0;1] array into 2 parts: lengths q and p, q+p=1if(U(i,1)<q)XI(i,1)=-1;% If a uniform random value falls into q then \xi=-1elseXI(i,1)=1;% If a uniform random value falls into p then \xi=+1endendx=10;% Initial 1st player's budget offsetS=zeros(n,1);% Reserve memory for 100 S_1...S_100fori=1:n% Make S_k series according to rule S_{k+1} = S_k + \xi_{k+1}S(i,1)=x+sum(XI(1:i,1));% considering the initial welfare offset xend
Затем введём функцию getS(n, q, x), которая бы не просто, как листинг выше, генерировала ряд сразу и мгновенно, а позволяла бы обобщённо на основе введённых значений , и построить ряд, не усложняя вычислений. Это бы упростило рабочую область.
function[S]=getS(n, q, x)% This function depends on n, q and x --- 3 variablesU=rand(n,1);XI=zeros(n,1);fori=2:n% Uniform->Bernoulli distribution transformationif(U(i,1)<q)XI(i,1)=-1;elseXI(i,1)=1;endendS=zeros(n,1);% Reserve memory for n S_1...S_nfori=2:n% Calculate the S_1...S_n seriesS(i,1)=sum(XI(1:i,1));% Sums the \xi'sendS=x+S;% Adds initial welfare to each S_k of the whole matrix
Возникает разумный вопрос: зачем считать , начиная только со второй величины (for i = 2:n)? Дело в том, что это делается исключительно в целях наглядной визуализации. При построении графика в следующем коде будут строиться траектории , и если бы было написано for i = 1:n, то тогда уже с самого первого значения некоторые траектории бы выходили из , некоторые — из . Так как в данной программе из соображений оптимальности лучше не задействовать нулевое значение (из него частица выходит, но не рисуется, так как прибавление происходит сразу), то просто-напросто сдвинем нумерацию на оси абсцисс на единицу вправо. Теперь проведём серию тестов и наглядно рассмотрим возможные траектории при некоторых вероятностях, длинах игры и количестве игр.
Три игры в 10 шагов при .Пять игр в 100 шагов при . Видно, что частицу «тянет вниз» к точке .Сто справедливых игр в 10000 шагов.
N=3;% Number of games playedn=10;% Number of tossesq=0.45;% Chance 1st player loses 1 roublex=0;% Initial welfare offsetmatrS=zeros(N,n);% Reserve memory for N rows n cols matrixfori=1:N% This loop fills the S matrix with S_k, yielding N trajectoriesmatrS(i,:)=getS(n,q,x)';plot(matrS(i,:));% Gives an imageholdon;% Holds the axes for next trajectory overlayendholdoff;% Clears axes for a new plot
Теперь подойдём к самой главной составляющей программной части — алгоритму, который позволил бы вычислять среднюю длину игры при заданных параметрах . Если теория верна, то нижеследующий эксперимент её лишь подтвердит. Также допишем в программу строчку, которая будет вычислять вероятность разорения первого игрока () при заданных начальных капиталах и сопоставлять её с теоретической.
N=3000;% Number of games playedn=3000;% Number of tossesq=0.5;% Chance 1st player loses 1 roublep=1-q;% Chance 1st player wins 1 roubleA=-10;% 1st player budgetB=10;% 2nd player budgetx=0;% Budget offset towards 1st playerBs=0;% amount of cases particle hits B (it will change soon)As=0;% amount of cases particle hits A (it will change soon)matrS=zeros(N,n);% Reserve memory for N rows n cols matrixTAU1=n*ones(N,n);% Fill another N rows n cols matrix with n'sfori=1:N% This loop makes up N trajectories of S_k relying on input q, x, nmatrS(i,:)=getS(n,q,x)';forj=1:nif(matrS(i,j)==A)||(matrS(i,j)==B)% If a particle exceeds A or B, thenTAU1(i,j)=j;% put the number of step into the tableendendplot(matrS(i,:));% Displays a figuregridon;holdon;% Simultaneous plots within same axesendholdoff;% Clears axes for a new plotTAU=(min(TAU1'))';% TAU = earliest step of [A;B] corridor overrun% As [min] affects columns and gives row then we transpose TAU1,% minimize it by rows and make it a column againfori=1:N% Our S_n series are ready; they nest in matrSforj=1:TAU(i)% Scan only till we encounter the escape step!if(matrS(i,j)==A);% If a particle escaped through A (1st player busted)As=As+1;% then add +1 to 1st player's failureselseif(matrS(i,j)==B)% Otherwise if its first threshold was BBs=Bs+1;% then add +1 to 1st player's winsend% If n is not large enough, thenend% As + Bs may not make up NendALPHA=As/(As+Bs)% Match alphas with their theoretical valuesif(q==p)THEORALPHA=(B-x)/(B-A)elseTHEORALPHA=((q/p)^B-(q/p)^x)/((q/p)^B-(q/p)^A)endBETA=1-ALPHA% Same for betasif(q==p)THEORBETA=(x-A)/(B-A)elseTHEORBETA=1-THEORALPHAendmeanTAU=mean(TAU)% Law of large numbers for great N'sif(q==p)THEORTAU=(B-x)*(x-A)elseTHEORTAU=1/(p-q)*(B*THEORBETA+A*THEORALPHA-x)end
Отметим, что при небольших не все частицы вылетают из коридора, поэтому здесь надо подчеркнуть, что теория говорит: «при достаточно больших вероятность близка к ».
В экспериментах 2 и 3 продемонстрировано свойство: если игра проигрышная для первого игрока, то увеличение ставки в модели эквивалентно сокращению , и в одно и то же число раз относительно нуля. Ставка увеличилась втрое — вероятность выскочить из коридора со значением выросла в 11 раз!