- Задача о разорении игрока
-
Задача о разорении игрока — задача из области теории вероятностей. Подробно рассматривалась российским математиком А. Н. Ширяевым в монографии «Вероятность»[1].
Содержание
Формулировка
За столом сидят два игрока. У первого в распоряжении находится рублей, у второго в распоряжении находится рублей. Перед ними на столе лежит асимметричная монета (вероятность, что выпадет аверс, может равняться любому числу от 0 до 1 включительно). Если на монете выпадает аверс, то рубль выигрывает первый игрок (второй игрок выплачивает первому 1 рубль), а если выпадает реверс, то первый игрок платит второму один рубль. Требуется найти вероятность того, что один из игроков проиграется в ноль за шагов, и вероятность проигрыша каждого азартного игрока. Также необходимо вычислить среднюю длину игры.
Данная ситуация может быть смоделирована подобным образом: имеется блуждающая частица и коридор . Рассматривается вероятность того, что частица выйдет из коридора за шагов (проскочит через верхнюю или нижнюю стенку).
Схема Бернулли
Рассмотрим схему Бернулли с испытаниями. Пусть — вероятностное пространство, где . — алгебра подмножеств вероятностного пространства. Вероятность задана следующим образом: , где — количество выпавших в данной последовательность единиц: . Данная формула позволяет считать количество единиц: превращает соответственно полученные значения в и затем уже считает полученные единицы. Введём последовательность бернуллиевских случайных величин
Подзадача о нормированности вероятности
Доказать, что
Решение. Это справедливо в силу того, что , поскольку по условию .
Подзадача о независимости случайных величин
Доказать, что и независимы.
Решение. Достаточно доказать, что
Случайное блуждание
Введём новое обозначение: , . — длина игры, а последовательность можно рассматривать как траекторию случайного блуждания некоторой частицы, выходящей из нуля. При этом . Пусть , — два целых числа, , . Требуется найти, с какой вероятностью за шагов будет осуществлён выход частицы из коридора, ограниченного и . Если , то второй игрок платит первому. Если , то первый игрок платит второму. Поэтому может рассматриваться в качестве выигрыша первого игрока у второго (который, естественно, может быть отрицательным). Далее, пусть — целое число, . Пусть также для верно, что (что означает, что игроки начинали играть с ненулевым капиталом в распоряжении). Пусть . Условимся считать, что , если . Если частица так и не пересекла границы, то не определён.
Для каждого и момент называется моментом остановки, который является случайной величиной, определённой на пространстве элементарных событий . — это событие, состоящее в том, что случайное блуждание , начинающееся в точке , выйдет из интервала в момент . Введём новые обозначения: , для . Пусть , — вероятности выхода частицы за время из интервала соответственно в точках и .
Пусть ; очевидно, что (пока игра не началась, частица находится внутри интервала с вероятностью 1). Пусть теперь . Тогда по формуле полной вероятности
Подзадача о рекуррентности
Доказать, что (1) и (2) .
Доказательство.
(1) Докажем, что . , где — множество траекторий вида , которые за время впервые выходят из интервала в точке (показано на рисунке). Если случайный вектор попадает в подходящую траекторию, то он попадает в множество . Представим множество как . Дизъюнктное объединение правомерно по причине того, что у любой частицы, проходящей по траектории, . — те траектории из , для которых . — те траектории из , для которых . Заметим, что каждая траектория из находится в однозначном соответствии с траекторией из . Взаимно-однозначное соответствие доказывается от противного. Предположим, что (неоднозначное соответствие); тогда данная траектория не сможет вывести частицу из коридора за шагов (а только лишь за из-за изначального отдаления от верхней стенки коридора). В обратную сторону соответствие является также однозначным из определения: . Из этого следует, что (так как суть независимые одинаково распределённые случайные величины).
Существует и другой способ доказательства:
. Это справедливо потому, что вероятности независимы (это было доказано ранее).
(2) Аналогично докажем, что . Каждая траектория из находится в однозначном соответствии с траекторией из . Отсюда
Вывод рекуррентного соотношения
Из уравнения для следует, что для и верно:
, для . Формула полной вероятности также даёт нам следующий результат: . Также отметим, что , и поэтому для . Это утверждение верно, так как к любой траектории, выводящей частицу за меньшее количество шагов, можно прибавить в начало один шаг (), на котором частица может прийти в точку как из (для ), так и из ().
Нахождение вероятностей
При достаточно больших вероятность близка к — решению уравнения при тех условиях, что (выход произошёл сразу же из точки — конец игры, выиграл первый игрок), (первый игрок никогда не выиграет, если выход произойдёт мгновенно в точке ). Эти условия следуют из того, что . Это также будет доказано в этом разделе.
Сначала получим решение уравнения . Пусть игра несправедливая (). В таком случае найдём корни уравнения, то есть . Одно частное решение видно сразу: . Другое решение найдём, воспользовавшись тем, что — функция. Целесообразно употребить выражение с отношением , учитывая, что : . Отсюда правомерно предположить, что . Добавление константы ничего не изменит благодаря тому, что .
Теперь рассмотрим общее решение: . Воспользуемся теми условиями, что и , и получим, что
Подзадача о единственности решения
Докажем единственность решения данной задачи. Для этого покажем, что любое решение задачи с граничными условиями может быть представлено в виде .
Решение. Рассмотрим некоторое решение при условиях , . Тогда всегда можно подобрать такие константы и , что , . Тогда из уравнения поставленной задачи следует, что . Тогда в общем случае . Следовательно, решение является единственным. Точно такой же ход рассуждений может быть применён и к .
Предельная сходимость
Рассмотрим вопрос о быстроте предельной сходимости и к и . Пусть блуждание начинается из начала координат (). Для простоты обозначим , , . Иными словами, — это единица минус сумма вероятностей выхода частицы из коридора — вероятность того, что она останется блуждать в коридоре: . представляет собой событие . Рассмотрим число , где , и цепочку случайных величин . Если обозначить совокупное богатство за , то тогда . Этому есть разумное объяснение: если частица выходит из нуля и не пересекает границ, то тогда совершенно определённо сумма штук меньше, чем совокупный запас.
Подзадача о независимости случайных величин
Докажем, что независимы и одинаково распределённые. Достаточно доказать, что они независимы, так как все они имеют биномиальное распределение.
Решение. Докажем, что
. Вернёмся к рассмотрению сходимости. , что следует из только что доказанного. Рассмотрим дисперсию: (что вполне правомерно, так как , а — модифицированная бернуллиевская случайная величина), поэтому для достаточно больших и верно: , где , так как если , то . Если или , то для довольно больших верно, что , поэтому неравенство верно . Из вышесказанного следует, что , где . Так как , то ; так как и , то ; при . Аналогичные оценки справедливы и для разностей и , так как можно свести эти разности к разностям и при , .
Вернёмся к рассмотрению . По аналогии с решением уравнения , можно сказать, что у уравнения при граничных условиях , существует единственное решение
Нетрудно заметить, что при любых . Если же игра является справедливой (вероятность выпадения аверса равна вероятности выпадения реверса), то решения будут выглядеть следующим образом: , .
Ответ о вероятности разорения
Величины и было бы можно назвать вероятностями разорения первого и второго игрока при начальных капиталах и при стремлении количества ходов к бесконечности и характеризации случайной величина как выигрыша первого игрока, а — проигрыша первого игрока. В дальнейшем будет показано, почему такую последовательность действительно можно построить.
Если , то интуитивный смысл функции — это вероятность того, что частица, вышедшая из положения , достигнет верхней стенки () ранее, чем нуля. Из формул видно, что .
Парадокс увеличения ставки при неблагоприятной игре
Что необходимо сделать первому игроку, если игра неблагоприятна для него?
Его вероятность проигрыша задана формулой . Теперь пусть первый игрок с капиталом примет решение удвоить ставку и играть на два рубля. Теперь , . Тогда обозначим предельную вероятность разорения первого игрока так: . Тогда . Поэтому , так как уможается на дробь, которая больше единицы при .
Поэтому если вероятность выпадения столь желанного для первого игрока аверса меньше , то ему выгодно увеличить ставку в раз: это уменьшает вероятность его терминального разорения за счёт того, что вырастает вероятность выскочить из коридора в точке . Это решение кажется парадоксальным, так как складывается впечатление, что при неблагоприятной ситуации надо снизить ставку и уменьшить проигрыш, но в действительности при бесконечном числе игр и низкой ставке проигрывающий игрок в конечном счёте обязательно проиграется в ноль, а игрок с высокой ставкой обладает большими шансами выпадения количества аверсов, достаточного для завершения игры в точке .
Длительность случайного блуждания
Рассмотрим среднюю длительность блуждания нашей частицы. Введём математическое ожидание момента, когда игра прекращается: для . Выведем рекуррентное соотношение для математического ожидания продолжительности игры:
Для и мы получили рекуррентное соотношение для функции : при . Введём граничные условия: если игра начинается в точке или , то тогда она тут же и завершится — её длительность будет равна 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)
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 раз!
См. также
- Случайное блуждание
- Случайный процесс
- Формула полной вероятности
- Распределение Бернулли
- Метод Монте-Карло
Примечания
- ↑ Ширяев А. Н. Вероятность—1, Вероятность—2 // Москва, МЦНМО. — 2007.
Категории:- Теория вероятностей
- Теория вероятностей и математическая статистика
Wikimedia Foundation. 2010.