- Задача о разорении игрока
-
Задача о разорении игрока — задача из области теории вероятностей. Подробно рассматривалась российским математиком А. Н. Ширяевым в монографии «Вероятность»[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.