Детская бродилка

[staric]

Принц Флоризель и Клетчатый играют на бриллиант "Око света" в детскую бродилку с 1 фишкой и 12-ю лунками по кругу. Ходы общей фишкой делаются по следующим правилам. Игроки по очереди бросают пару костей. Если на обеих выпадает по нечетному количеству очков ("нечет-нечет"), фишка передвигается по часовой стрелке на соседнюю лунку, если по четному ("чет-чет") - на следующую за соседней. Если на одной кости выпадает нечет, на другой - чет, игрок может выбирать между этой парой лунок. Тот, кто своим ходом попадает на лунку №12, забирает себе бриллиант.
Принц ходит первым с лунки №3. Какова вероятность его победы, если по условиям игры:
а) игрок, находящийся на лунке №11 после броска "чет-чет", проигрывает (перебор);
б) игра после броска продолжается (следующий игрок продолжает с лунки №1), пока кто-нибудь не не попадет на лунку №12.

[Dendr]

Мы же здесь полагаем, что
1) оптимальная стратегия есть,
2) оба игрока ее придерживаются,
3) оба осведомлены о п. 2?


Игрок бросает кости, и по результатам броска двигает фишку, с вероятностью $1/4$ на одну лунку, с $1/4$ - на две лунки вперед. А с вероятностью $1/2$ - выбирает лунку из этих двух. Оптимальная стратегия означает, что он выбирает так, чтобы его соперник, начинающий с новой лунки, имел более низкие шансы на победу, чем в альтернативном случае.

В случае (а) замечаем:
Если перед ходом игрока фишка находится в лунке 12, то он сразу проиграл, $p_{12}=0$
Если - в лунке 11, то он с вероятностью $1/4$ получает перебор, в противном случае либо автоматически попадает в целевую лунку, либо выбирает ее из двух (дилемма простая: перебор или победа, и решается очевидным образом). Таким образом, $p_{11}=3/4$.

Пусть фишка в лунке $k$. Тогда (повторюсь, на этот раз с числами) с вероятностью $1/4$ фишка немедленно попадет в клетку $k+1$, где вероятность его поражения равна $p_{k+1}$, с той же вероятностью в клетку $k+2$, вероятность поражения $p_{k+2}$. А в прочих случаях (вероятность $1/2$) он выбирает. Здесь вероятность поражения равна $\min(p_{k+1},p_{k+2})$.
Таким образом, рекуррентная формула для вероятности победы при начале в лунке $k$ выглядит так:

$$1-p_k=\frac{p_{k+1}+p_{k+2}}{4}+\frac{\min(p_{k+1},p_{k+2})}{2}=\frac{p_{k+1}+p_{k+2}}{2}-\frac{|p_{k+1}-p_{k+2}|}{4}$$

(если круг состоит не из 12, а из много большего количества лунок, то на достаточно большом расстоянии до финиша вероятности ожидаемо осциллируют около $0.5$)

Используя вычисленные ранее значения $p_{11,12}$, получим, что $p_3=\frac{114159}{262144}\approx43,55\%$.

В случае (б) есть небольшое изменение: при "проскоке" фишка оказывается в лунке 1, с которой начинает соперник, то есть вероятность победы - это вероятность поражения соперника, в итоге $p_{11}=3/4+(1-p_1)/4$. Но исходно $p_1$ нам неизвестна (хотя уже можно предполагать, что близка к $1/2$), и получается система из 11 уравнений с 11 неизвестными. Была бы она линейной, было бы здорово. Но модуль (или $\min$) портят всю малину. Здесь понадобится либо догадка о соотношении вероятностей для соседних лунок, по критерию "больше-меньше", либо итеративные вычисления $p_1$. Второе проще, если решать численно, и получается $p_3\approx41,66\%$.

[staric]

а) - все верно
б) по процентам близко, но попробуйте поискать "самосогласованное" решение; как и в а), его можно выразить в виде рациональной дроби.

[Dendr]

Бродилка-то совсем недетская выходит. Без большого количества муторных вычислений (в столбик или на компьютере) продвигается слабо.

Но если вводить обозначение $\delta_k=p_{k+1}-p_k$, то можно немного упростить выражения с модулями, получая:

$$\delta_{11}=-p_{11}<0, \delta_{10}=\frac{5p_{11}-4}{4}$$

$$\delta_k=\frac{(|\delta_{k+2}|-2\delta_{k+2})-(|\delta_{k+1}|+2\delta{k+1})}{4}$$

Тут без первой интуитивной догадки получается плохо, но по общим соображениям, мы можем предполагать, что на первой лунке, то есть, по меньшей мере, за 6 бросков кости до финиша, шансы победить и проиграть отличаются, во всяком случае, не в разы, так что наверняка $p_1<4/5$, тогда $p_{11}=1-p_1/4>4/5$, и $\delta_{10}>\frac{5}{4}\cdot\frac{4}{5}=0$.
Пользуясь этим, мы постепенно убираем скобки модуля, при этом знаки $\delta_k$ определяются уже однозначно (достаточно условия $0<p_{11}<1$), в результате получаем:
$\delta_9=\frac{12-3p_{11}}{16}>0$
...
$\delta_1=\frac{-5065p_{11}-13468}{1048576}<0$
Сложив полученные дроби, получим $\delta_{10}+...+\delta_1=p_{11}-p_1=5p_{11}-4$ - линейное уравнение, решение которого:

$$p_{11}=\frac{1215388}{1410551}$$

Из этого получаются уже явные значения всех "дельт", откуда легко узнать и все вероятности. В частности: $p_3=\frac{587644}{1410551}\approx41.66\%$ (то же, только приближенное, значение, было получено итерациями)

Под спойлером приведу тройки чисел и знак ($k: a_k, b_k, c_k (\pm)$) для остальных выражений вида $\delta_k=\frac{a_k+b_kp_{11}}{c_k}$

(Оффтоп)

8: -20, -11, 64 $(-)$
7: -28, 23, 256 $(-)$
6: 268, 109, 1024 $(+)$
5: -468, -603, 4096 $(-)$
4: -604, 167, 16384 $(-)$
3: 6220, 7069, 65536 $(+)$
2: -11412, -5065, 1048576 $(-)$

[staric]

Ну да, по большому счету, главное здесь - упростить вычисления + пара-тройка догадок, которые вы совершили. Наверное, мне, как автору, было попроще. Впрочем, вы и сами еще по а) заметили, что вероятности "гуляют" рядом с $ \frac {1} {2}$, поэтому естественным выглядит переход к работе с $a_n=p_n -\frac {1} {2}$. Я принял "зеркальную" нумерацию лунок (бриллиант в лунке 0, предыдущая лунка 1, начинаем с лунки 9). Тогда, если рассматривать последовательные тройки лунок, нетрудно видеть, что при $a_{3k+2}>a_{3k+1} $ имеем: $ \begin{pmatrix} a_{3k+1} \\a_{3k+2} \\ a_{3k+3} \end{pmatrix} = M \begin{pmatrix} a_{3k-2} \\ a_{3k-1} \\ a_{3k} \end{pmatrix}$, где $M=\begin{pmatrix} 0 & -\frac {1} {4} & -\frac {3} {4}\\ 0 & \frac {1} {16} & -\frac {9} {16}\\0 & \frac {11} {64} & \frac {45} {64}\\\end{pmatrix}$. И в варианте а) $ \begin{pmatrix} p_{7} \\p_{8} \\ p_{9} \end{pmatrix} = M^3 \begin{pmatrix} ... \\ \frac {1} {2} \\ -\frac {1} {2} \end{pmatrix}+ \begin{pmatrix} \frac {1} {2} \\ \frac {1} {2} \\ \frac {1} {2} \end{pmatrix}=\begin{pmatrix} \frac {9135} {16384} \\ \frac {38365} {65536} \\ \frac {114159} {262144} \end{pmatrix}$.
При $a_{3k+2}<a_{3k+1} $ имеем: $ \begin{pmatrix} a_{3k+1} \\a_{3k+2} \\ a_{3k+3} \end{pmatrix} = S \begin{pmatrix} a_{3k-2} \\ a_{3k-1} \\ a_{3k} \end{pmatrix}$, где $S=\begin{pmatrix} 0 & -\frac {1} {4} & -\frac {3} {4}\\ 0 & \frac {1} {16} & -\frac {9} {16}\\0 & \frac {1} {64} & \frac {39} {64}\\\end{pmatrix}$. И, как вы верно заметили, в варианте б) $ \begin{pmatrix} a_{10} \\a_{11} \\ a_{12} \end{pmatrix} = M^3 S \begin{pmatrix} ... \\ x \\ -\frac {1} {2} \end{pmatrix}=\begin{pmatrix} ... \\ \frac {452259} {8388608}-x\frac {37349} {4194304}\\... \end{pmatrix}$, откуда $x=\frac {150753} {2821102}$ и $ \begin{pmatrix} p_{7} \\p_{8} \\ p_{9} \end{pmatrix} = M^2 S \begin{pmatrix} ... \\ \frac {150753} {2821102} \\ -\frac {1} {2} \end{pmatrix}+ \begin{pmatrix} \frac {1} {2} \\ \frac {1} {2} \\ \frac {1} {2} \end{pmatrix}=\begin{pmatrix} \frac {813004} {1410551} \\ \frac {852616} {1410551} \\ \frac {587644} {1410551} \end{pmatrix}$.
Собственно, все операции с матрицами за меня делал силиконовый друг, жаль, ему не поручить печатать этот пост... Но мне казалось, что за пару дней расколоть задачку не выйдет. Респект.