Задача о разорении с ограничением числа партий

Привет, продолжаем изучать орлянку — игру, в которой сосредоточена вся вероятностная премудрость. В прошлый раз мы разобрали задачи о вероятности выиграть и о среднем числе партий до окончания игры: когда кто-то из игроков разорится. Это число оказалось неожиданно велико: результат перемножения числа ставок у каждого. То есть, если у меня 2 ставки, а у вас 50, до среднее число игр равно ста, хотя большинство существенно короче. Причем если играть (лучше на симуляторе) и считать среднее, то оно отнюдь не обязательно подтвердит теоретический результат. На рисунке более или менее подтверждает, потому что числа маленькие.

Десять тысяч партий в орлянку, 1 ставка против 20 ставок. Для каждой партии показано число ходов до разорения одного из игроков. Теоретическое среднее число ходов равно 20. Оценка равна 19. Львиная доля, конечно, в районе 1, но некоторые партии подзатянулись, да

А давайте теперь ограничим число партий! Игра считается оконченной, если один их игроков разорился или если они сыграли предписанное число М партий. Изначально у одного a ставок, у второго b, а a+b=N.

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

Теперь уже мы не можем говорить, что после одной партии задача остается такой же с новым параметром числа ставок на руках. Партия имеет номер, и это важно. Если играется партия номер M, то она всяко последняя.

Обозначим через J(n,i) среднее число партий до конца игры, при условии что у игрока n ставок на руках и играется партия номер m. Тогда уравнение будет такое:

J(n,m-1) = 1 + 0.5J(n-1,m) + 0.5J(n+1,m)

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

J(0,m) = J(N,m)=0, J(n,M)=0.

Здесь N — суммарный капитал игроков. Первая пара условий означает, что игра кончается на разорении одного из игроков, а третье условие прекращает игру по лимиту партий.

Этому разностному уравнению и двум граничным условиям удовлетворяет решение для задачи без лимита ходов: j(n,m)=j(n)=(N-n)n, не зависящее от m. Сделаем замену J(n,m) = j(n) + I(n,m):

2I(n,m-1) = I(n-1,m) + I(n+1,m)

При этом граничные условия не меняются, а третье, конечное условие переходит в I(n,M)=-n(N-n). Конечное условие пока будем игнорировать, а уравнение вместе с граничными условиями образует линейную систему. Правда, теперь ее размерность слишком высока (N-1), чтобы собрать все решения из нескольких немногочисленных. Придется придумать другой способ.

Попробуем искать решения в виде произведения двух величин:

I(n,m) = X(n)Y(m).

Подстановка в систему дает

Левая часть не зависит от n, а правая от m, поэтому обе они не зависят ни от той, ни от другой переменной:

Это дает нам раздельные уравнения (системы) для Y(m) и X(n), но с неизвестным параметром ω.

Система уравнений

X(n-1) + X(n+1) = 2ωX(n),

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

X(n)=λⁿ

приводит к

Сделаем замену ω=cosθ (ограничившись |ω|<1) и получим

Это дает нам решения, удовлетворяющие системе (но не граничным условиям).

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

Чтобы выполнялось и второе граничное условие, необходимо sin(θN)=0, откуда

θ = πk/N, k=1,2, ..., N-1.

Итак, у нас есть набор из N-1 решения X(n)=sin(πkn/N) при разных k от 1 до N-1, которые являются собственными векторами преобразования

(X(n-1) + X(n+1)) / 2,

а собственными числами выступают ω=cos(πk/N).

Теперь найдем Y(m) из уравнения

Y(m-1} = ωY(m) = cos(πk/N)Y(m).

Это несложно, так как это просто геометрическая прогрессия:

Y(m)=Y₀cos⁻ᵐπk/N.

Можно даже выбрать константу Y₀=1, потому что нас устраивают любые решения, лишь бы их было достаточно много, не сводящихся друг к другу.

Окончательно мы имеем

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

I(n,M) = -n(N-n).

Это дает систему линейных уравнений для коэффициентов C.

Некоторая сложность связана с тем, что матрица системы может быть с проблемами. В частности (но не только), если N четно: посмотрите на столбец с номером N/2.

Эту проблему в данном случае можно обойти. То есть "система не решается" — это не тупик, а развилка.

Рассмотрим матрицу A с элементами A(n,k)=sin(πkn/N) и диагональную матрицу B, на диагонали которой стоят cos(πk/N). Матрица нашей системы — это AB⁻ᴹ.

Вспомним, что у нас j(n)=n(N-n); тогда система имеет вид AB⁻ᴹC = -j, здесь C — вектор неизвестных. Полагая матрицы невырожденными, домножим на BᴹA⁻¹: C=-BᴹA⁻¹j.

Теперь заметим, что I(n,m)=AB⁻ᵐC. Поэтому

I(n,m) = -AB⁻ᵐBᴹA⁻¹j = -ABᴹ⁻ᵐA⁻¹j.

Заметим, что в этой формуле степень матрицы В неотрицательна.

Запишем J(n,m) = j(n) + I(n,m) и подставим полученное:

J(n,m) = (E - ABᴹ⁻ᵐA⁻¹) j(n).

Здесь E — единичная матрица. При больших M матрица Bᴹ⁻ᵐ стремится к нулевой (ведь ее элементы по модулю меньше 1), так что решение стремится к решению j(n) без ограничения на число ходов, что и естественно.

Как пользоваться формулой на практике?

1. Запишем ее в виде J(n,m) = b - ABᴹ⁻ᵐz, z = A⁻¹j.
2. Решаем систему Az=j, определяя z.
3. Записываем диагональную матрицу Bᴹ⁻ᵐ, располагая на диагонали величины cosᴹ⁻ᵐ(πk/N);
4. умножаем эту матрицу на z — по существу, умножаем элементы z на соответствующие элементы диагонали построенной матрицы.
5. Умножаем матрицу A на полученный вектор.
6. И, наконец, вычитаем результат (а это не что иное, как снижение среднего числа партий из-за ограничения числа партий) из j.

Например, при N=1000, n=1 (когда у одного игрока изначально одна ставка, а у другого 999), среднее число партий до разорения равно 999, однако при ограничении числа партий M=100 получаем J(n,0)=15. С ростом n величина быстро растет, приближаясь к 100 уже при n≈ 50.

Численный пример. Суммарный капитал равен 50. По оси х - начальный капитал одного из игроков. Линии описывают среднее число ходов до конца игры: либо разорения одного из игроков, либо до достижения лимита числа хоов: 25, 30 и 50. Видно, как сильно ограничивает лимит число ходов при маленьком начальном капитале.

Давайте разберем простой пример, когда у игроков три монеты на двоих (N=3) и ограничение числа ходов M какое-то задано. Запишем матрицу A(n,k)=sin(πkn/N):

sin(π/3) sin(2π/3)
sin(2π/3) sin(4π/3)

Или

sin(π/3) sin(π/3)
sin(π/3) -sin(π/3)

Вектор j=n(N-n) есть (2,2), так как N=3, а n=1 или 2. Система уравнений с такой матрицей и такой правой частью сводится к

z1 + z2 = 4/√3,
z1 - z2 = 4/√3.

Эта система легко решается, давая вектор z=(4/√3, 0).

На диагонали матрицы Bᴹ⁻ᵐ стоят числа cosᴹ⁻ᵐ(πk/N) при k=1 и 2, то есть (±½)ᴹ, если нас интересует начало игры (m=0).

Вектор Bᴹz равен (2²⁻ᴹ/√3, 0).

Умножение матрицы А на этот вектор — это первый столбец матрицы, умноженный на первую компоненту вектора. Первый столбец имеет вид (√3/2, √3/2), так что корень сократится и получится (2¹⁻ᴹ, 2¹⁻ᴹ).

Это мы получили сокращение среднего числа партий из-за ограничения числа партий числом М. Среднее же число партий описывается вектором (2, 2) — либо у одного две ставки, а у другого одна, либо наоборот. В итоге среднее число игр в данном примере равно 2(1-2⁻ᴹ).

Если М=0 (играть вообще запрещено), то и будет нуль. Если М=1, то "куда ни шло — один ход!", то и будет один ход. Вот если М=2, то в среднем будет полтора хода. Ну, правильно: либо игрок с одной ставкой проиграет на первом ходу, либо выиграет и на втором ходу игра так и так кончится. Либо один, либо два хода с равными шансами.

Вот такая любопытная задачка, коллеги.