Interested Article - Задача о разорении игрока

Задача о разорении игрока — задача из области теории вероятностей .

Траектории справедливой игры длиною 1000 шагов; коридор блуждания частицы обозначен горизонтальными линиями

Формулировка

За столом сидят два игрока . У первого в распоряжении находится рублей, у второго в распоряжении находится рублей. Перед ними на столе лежит асимметричная монета ( вероятность , что выпадет аверс , может равняться любому числу от 0 до 1 включительно). Если на монете выпадает аверс, то рубль выигрывает первый игрок (второй игрок выплачивает первому 1 рубль), а если выпадает реверс, то первый игрок платит второму один рубль. Требуется найти вероятность того, что один из игроков проиграется в ноль за шагов, и вероятность проигрыша каждого азартного игрока. Также необходимо вычислить среднюю длину игры.

Данная ситуация может быть смоделирована подобным образом: имеется блуждающая частица и коридор . Рассматривается вероятность того, что частица выйдет из коридора за шагов (проскочит через верхнюю или нижнюю стенку).

Схема Бернулли

Рассмотрим схему Бернулли с испытаниями.

Пусть — вероятностное пространство, где

  • – элементарные исходы,
  • алгебра подмножеств вероятностного пространства ,
  • , где — количество выпавших в данной последовательность единиц.

В выражении выше число выпавших единиц можно найти так: .

Введём последовательность бернуллиевских случайных величин:

Подзадача о нормированности вероятности

Доказать, что


Решение

Это справедливо в силу того, что

, поскольку по условию .

Подзадача о независимости случайных величин ξ i

Доказать, что и независимы.


Решение

Независимость случайных величин означает, что

покажем это:

Случайное блуждание

Для схемы Бернулли договоримся о следующем смысле случайной величины ξ: означает, что второй игрок платит первому, а – первый игрок второму.

Введём новое обозначение:

, .

Число равно длительности игры, а последовательность можно рассматривать как траекторию случайного блуждания некоторой частицы, выходящей из нуля, при этом очевидно равенство , а само означает выигрыш первого игрока у второго (который может быть отрицательным).


Пусть , — два целых числа, , . Требуется найти, с какой вероятностью за шагов будет осуществлён выход частицы из коридора, ограниченного и .

Далее, пусть — целое число, . Пусть также для верно, что (что означает, что игроки начинали играть с ненулевым капиталом в распоряжении). Пусть . Условимся считать, что , если . Если частица так и не пересекла границы, то не определён.

Для каждого и момент называется моментом остановки , который является случайной величиной , определённой на пространстве элементарных событий . — это событие, состоящее в том, что случайное блуждание , начинающееся в точке , выйдет из интервала в момент . Введём новые обозначения: , для . Пусть , — вероятности выхода частицы за время из интервала соответственно в точках и .

Пусть ; очевидно, что (пока игра не началась, частица находится внутри интервала с вероятностью 1). Пусть теперь . Тогда по формуле полной вероятности

Подзадача о рекуррентности

Доказать, что

(1) ,

(2) .

Доказательство.

(1) Докажем, что .

, где — множество траекторий вида , которые за время впервые выходят из интервала в точке (показано на рисунке). Если случайный вектор попадает в подходящую траекторию, то он попадает в множество . Представим множество как . Дизъюнктное объединение правомерно по причине того, что у любой частицы, проходящей по траектории, . — те траектории из , для которых . — те траектории из , для которых . Заметим, что каждая траектория из находится в однозначном соответствии с траекторией из . Взаимно-однозначное соответствие доказывается от противного . Предположим, что (неоднозначное соответствие); тогда данная траектория не сможет вывести частицу из коридора за шагов (а только лишь за из-за изначального отдаления от верхней стенки коридора). В обратную сторону соответствие является также однозначным из определения: . Из этого следует, что (так как суть независимые одинаково распределённые случайные величины ).

Существует и другой способ доказательства:

.

Это справедливо потому, что вероятности независимы (это было доказано ранее).


(2) Аналогично докажем, что .

Каждая траектория из находится в однозначном соответствии с траекторией из . Отсюда

Вывод рекуррентного соотношения

Из уравнения для следует, что для и верно:

, для .


Формула полной вероятности также даёт нам следующий результат: .


Также отметим, что , и поэтому для . Это утверждение верно, так как к любой траектории, выводящей частицу за меньшее количество шагов, можно прибавить в начало один шаг ( ), на котором частица может прийти в точку как из (для ), так и из ( ).

Нахождение вероятностей

При достаточно больших вероятность близка к — решению уравнения при тех условиях, что (выход произошёл сразу же из точки — конец игры, выиграл первый игрок), (первый игрок никогда не выиграет, если выход произойдёт мгновенно в точке ). Эти условия следуют из того, что . Это также будет доказано в этом разделе.

Сначала получим решение уравнения . Пусть игра несправедливая ( ). В таком случае найдём корни уравнения, то есть . Одно частное решение видно сразу: . Другое решение найдём, воспользовавшись тем, что — функция. Целесообразно употребить выражение с отношением , учитывая, что : . Отсюда правомерно предположить, что . Добавление константы ничего не изменит благодаря тому, что .

Теперь рассмотрим общее решение: . Воспользуемся теми условиями, что и , и получим, что

Подзадача о единственности решения

Докажем единственность решения данной задачи. Для этого покажем, что любое решение задачи с граничными условиями может быть представлено в виде .


Решение

Рассмотрим некоторое решение при условиях , . Тогда всегда можно подобрать такие константы и , что , . Тогда из уравнения поставленной задачи следует, что . Тогда в общем случае . Следовательно, решение является единственным. Точно такой же ход рассуждений может быть применён и к .

Предельная сходимость

Рассмотрим вопрос о быстроте предельной сходимости и к и . Пусть блуждание начинается из начала координат ( ). Для простоты обозначим , , . Иными словами, — это единица минус сумма вероятностей выхода частицы из коридора — вероятность того, что она останется блуждать в коридоре: . представляет собой событие . Рассмотрим число , где , и цепочку случайных величин . Если обозначить совокупное богатство за , то тогда . Этому есть разумное объяснение: если частица выходит из нуля и не пересекает границ, то тогда совершенно определённо сумма штук меньше, чем совокупный запас.

Подзадача о независимости случайных величин ζ i

Докажем, что независимы и одинаково распределённые . Достаточно доказать, что они независимы, так как все они имеют биномиальное распределение .


Решение

Докажем, что

.


Вернёмся к рассмотрению сходимости.

Из только что доказанного следует что .

Рассмотрим дисперсию : (что вполне правомерно, так как , а — модифицированная бернуллиевская случайная величина ), поэтому для достаточно больших и верно: , где , так как если , то . Если или , то для довольно больших верно, что , поэтому неравенство верно . Из вышесказанного следует, что , где . Так как , то ; так как и , то ; при . Аналогичные оценки справедливы и для разностей и , так как можно свести эти разности к разностям и при , .

Вернёмся к рассмотрению . По аналогии с решением уравнения , можно сказать, что у уравнения при граничных условиях , существует единственное решение

Нетрудно заметить, что при любых . Если же игра является справедливой (вероятность выпадения аверса равна вероятности выпадения реверса), то решения будут выглядеть следующим образом: , .

Ответ о вероятности разорения

Величины и можно назвать вероятностями разорения первого и второго игрока при начальных капиталах и при стремлении количества ходов к бесконечности и характеризации случайной величина как выигрыша первого игрока, а — проигрыша первого игрока. В дальнейшем будет показано, почему такую последовательность действительно можно построить.

Если , то интуитивный смысл функции — это вероятность того, что частица, вышедшая из положения , достигнет верхней стенки ( ) ранее, чем нуля. Из формул видно, что

.

Парадокс увеличения ставки при неблагоприятной игре

Что необходимо сделать первому игроку, если игра неблагоприятна для него?

Его вероятность проигрыша задана формулой .


Теперь пусть первый игрок с капиталом примет решение удвоить ставку и играть на два рубля, то есть , . Тогда обозначим предельную вероятность разорения первого игрока так: .

Поэтому , так как умножается на дробь, которая больше единицы при .


Поэтому если вероятность выпадения столь желанного для первого игрока аверса меньше , то ему выгодно увеличить ставку в раз: это уменьшает вероятность его терминального разорения за счёт того, что вырастает вероятность выскочить из коридора в точке . Это решение кажется парадоксальным, так как складывается впечатление, что при неблагоприятной ситуации надо снизить ставку и уменьшить проигрыш, но в действительности при бесконечном числе игр и низкой ставке проигрывающий игрок в конечном счёте обязательно проиграется в ноль, а игрок с высокой ставкой обладает большими шансами выпадения количества аверсов, достаточного для завершения игры в точке .

Длительность случайного блуждания

Рассмотрим среднюю длительность блуждания нашей частицы. Введём математическое ожидание момента, когда игра прекращается: для . Выведем рекуррентное соотношение для математического ожидания продолжительности игры:

Для и мы получили рекуррентное соотношение для функции : при .


Введём граничные условия: если игра начинается в точке или , то тогда она тут же и завершится — её длительность будет равна 0: .


Из рекуррентного соотношения и граничных условий можно один за другим вычислить . Так как , то существует предел , который удовлетворяет соотношению : при выполнении . Данные переходы аналогичны тем, что мы рассмотрели при переходе к в уравнении вероятности проигрыша. Для того чтобы решить данное уравнение, надо ввести ещё одно условие: матожидание количества ходов должно быть конечным, то есть , .


Решим данное уравнение. В уравнении вероятности проигрыша ( ) уже были получены частные решения и . Здесь же появляется ещё один претендент на роль частного решения: , поэтому . С учётом граничного условия находим при помощи ранее полученных соотношений : . В случае идеальной монетки получаем следующее выражение: . Применение граничного условия даёт: . Из этого следует, что в случае равных стартовых капиталов . Например, если у каждого игрока есть по 5 рублей, а ставка — 1 рубль, то в среднем разоряться игроки будут через 25 ходов.

При рассмотрении вышеуказанных формул подразумевалась конечностью математического ожидания числа ходов: . Теперь будет предложено доказательство этого факта.

Задача о конечности ожидаемого числа ходов

Доказать, что .


Решение

Достаточно доказать это для случая (так как ранее было уже продемонстрировано, что случаи могут быть сведены к вариацией и ) и , а затем рассмотреть случай .

Итак, рассмотрим последовательность и введём случайную величину , где — момент остановки.

Пусть . Интерпретация такова: — это значение случайного блуждания в момент . Если , то ; если , то . Вспомним, что , и докажем, что , .


Для доказательства первого равенства напишем: . Совершенно очевидно, что , так как , при . Осталось доказать, что .

Для справедливо, что . Последнее событие может быть представлено в виде , где — некоторое подмножество множества . Это множество определяется только при . Для больших значения не влияют на . Множество вида также может быть представлено в виде . Благодаря независимости (доказано в подзадаче 2 ) вытекает, что случайные величины и независимы. Отсюда в силу того, что первый множитель нулевой.

Установлено, что для идеальной монетки , .

В случае же имеют место соотношения (поскольку ) и , поскольку . Теперь покажем, что .

В случае справедливой игры в силу соотношения верно, что . Тогда же , поэтому . Из неравенства следует, что математическое ожидание сходится при к предельному значению . В случае несправедливой игры . Так как за обозначался момент первого вылета частицы за пределы коридора, то математическое ожидание его меньше определённых чисел, следовательно, меньше бесконечности. При таком условии .

Компьютерное моделирование (метод Монте-Карло)

Для моделирования игры воспользуемся программой MATLAB .

Для начала сгенерируем последовательность , а затем при некотором первоначальном богатстве создадим цепочку :

Последовательность ξ (getXI)

n = 100;                             % The length of \xi_i series
U = rand(n,1);                       % Generate 100 random uniform [0;1] values
XI = zeros(n,1);                     % Reserve memory for 100 modified Bernoulli
q = 0.55;                            % Reverse probability
p = 1 - q;                           % Averse probability

                                     % The following cycle creates a Bernoulli distribution based on uniform [0;1]
for i = 1:n                          % This cycle divides the [0;1] array into 2 parts: lengths q and p, q+p=1
   if (U(i,1) < q)                        
       XI(i,1) = -1;                 % If a uniform random value falls into q then \xi=-1
   else XI(i,1) = 1;                 % If a uniform random value falls into p then \xi=+1
   end
end

x = 10;                              % Initial 1st player's budget offset

S = zeros(n,1);                      % Reserve memory for 100 S_1...S_100

for i = 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 x
end

Затем введём функцию getS(n, q, x) , которая бы не просто, как листинг выше, генерировала ряд сразу и мгновенно, а позволяла бы обобщённо на основе введённых значений , и построить ряд, не усложняя вычислений. Это бы упростило рабочую область.

Генерация ряда (getS function)

function [S] = getS(n, q, x)         % This function depends on n, q and x --- 3 variables
U = rand(n,1);
XI = zeros(n,1);

for i = 2:n                          % Uniform->Bernoulli distribution transformation
   if (U(i,1) < q)
       XI(i,1) = -1; 
   else XI(i,1) = 1;
   end
end

S = zeros(n,1);                      % Reserve memory for n S_1...S_n

for i = 2:n                          % Calculate the S_1...S_n series
    S(i,1) = sum(XI(1:i, 1));        % Sums the \xi's
end
S = x + S;                           % Adds initial welfare to each S_k of the whole matrix

Возникает разумный вопрос: зачем считать , начиная только со второй величины ( for i = 2:n )? Дело в том, что это делается исключительно в целях наглядной визуализации. При построении графика в следующем коде будут строиться траектории , и если бы было написано for i = 1:n , то тогда уже с самого первого значения некоторые траектории бы выходили из , некоторые — из . Так как в данной программе из соображений оптимальности лучше не задействовать нулевое значение (из него частица выходит, но не рисуется, так как прибавление происходит сразу), то просто-напросто сдвинем нумерацию на оси абсцисс на единицу вправо. Теперь проведём серию тестов и наглядно рассмотрим возможные траектории при некоторых вероятностях, длинах игры и количестве игр.

Визуализация (graphS)

Три игры в 10 шагов при .
Пять игр в 100 шагов при . Видно, что частицу «тянет вниз» к точке .
Сто справедливых игр в 10000 шагов.
N = 3;                               % Number of games played
n = 10;                              % Number of tosses
q = 0.45;                            % Chance 1st player loses 1 rouble
x = 0;                               % Initial welfare offset

matrS = zeros(N, n);                 % Reserve memory for N rows n cols matrix
for i = 1:N                          % This loop fills the S matrix with S_k, yielding N trajectories
    matrS(i,:) = getS(n, q, x)';
    plot(matrS(i,:));                % Gives an image
    hold on;                         % Holds the axes for next trajectory overlay
end
hold off;                            % Clears axes for a new plot

Теперь подойдём к самой главной составляющей программной части — алгоритму, который позволил бы вычислять среднюю длину игры при заданных параметрах . Если теория верна, то нижеследующий эксперимент её лишь подтвердит. Также допишем в программу строчку, которая будет вычислять вероятность разорения первого игрока ( ) при заданных начальных капиталах и сопоставлять её с теоретической.

Полная модель игры (Monte_Carlo)

N = 3000;                                 % Number of games played
n = 3000;                                 % Number of tosses
q = 0.5;                                  % Chance 1st player loses 1 rouble
p = 1-q;                                  % Chance 1st player wins 1 rouble
A = -10;                                  % 1st player budget
B = 10;                                   % 2nd player budget
x = 0;                                    % Budget offset towards 1st player
Bs = 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 matrix
TAU1 = n * ones(N, n);                    % Fill another N rows n cols matrix with n's
for i = 1:N                               % This loop makes up N trajectories of S_k relying on input q, x, n
  matrS(i,:) = getS(n, q, x)';
  for j = 1:n
      if (matrS(i,j) == A)||(matrS(i,j) == B) % If a particle exceeds A or B, then
      TAU1(i,j) = j;                          % put the number of step into the table
      end
  end
  plot(matrS(i,:));                       % Displays a figure
  grid on;
  hold on;                                % Simultaneous plots within same axes
end
hold off;                                 % Clears axes for a new plot

TAU = (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 again
for i = 1:N                               % Our S_n series are ready; they nest in matrS
    for j=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 failures
        elseif (matrS(i,j) == B)          % Otherwise if its first threshold was B
        Bs = Bs+1;                        % then add +1 to 1st player's wins
        end                               % If n is not large enough, then
    end                                   % As + Bs may not make up N
end
ALPHA = As/(As+Bs)                        % Match alphas with their theoretical values
if (q == p)
   THEORALPHA = (B-x)/(B-A)
else THEORALPHA = ((q/p)^B - (q/p)^x)/((q/p)^B - (q/p)^A)
end
BETA = 1-ALPHA                            % Same for betas
if (q == p)
   THEORBETA = (x-A)/(B-A)
else THEORBETA = 1-THEORALPHA
end
meanTAU = mean(TAU)                       % Law of large numbers for great N's
if (q == p)
   THEORTAU = (B-x)*(x-A)
else THEORTAU = 1/(p-q)*(B*THEORBETA+A*THEORALPHA-x)
end

Отметим, что при небольших не все частицы вылетают из коридора, поэтому здесь надо подчеркнуть, что теория говорит: «при достаточно больших вероятность близка к ».

Тестирование

Нижеследующие данные рассчитаны для , .

№ теста ALPHA BETA meanTAU
1
2
3
4
5
6

В экспериментах 2 и 3 продемонстрировано свойство: если игра проигрышная для первого игрока, то увеличение ставки в модели эквивалентно сокращению , и в одно и то же число раз относительно нуля. Ставка увеличилась втрое — вероятность выскочить из коридора со значением выросла в 11 раз!

См. также

Примечания

Источник —

Same as Задача о разорении игрока