反复横跳游戏
甲、乙两人玩一个反复横跳游戏。首先决定先手、后手，以及固定值 \(a, b, S_1\)。随后的每一轮，第 \(i\) 轮依次进行如下操作：
- 获取 \(X_i \sim U(0, 1)\)，计算 \(S_{2i} = S_{2i-1} + X_i\)。若 \(S_{2i} \geq a\)，则先手获胜，游戏结束。
- 获取 \(Y_i \sim U(0,1)\)，计算 \(S_{2i + 1} = S_{2i} - Y_i\)。若 \(S_{2i+1} \leq b\)，则后手获胜，游戏结束。
所有的 \(X_i, Y_i\) 都是独立同分布的。
- 若 \(S_1 = 0, a = 1/2, b = -1/2\)，求先手获胜的概率。
- 若 \(a = 1/2, b = -1/2\)，求 \(S_1\) 的值，使得先手和后手获胜的概率一致。
- （很困难）试着继续推广结论至更一般的 \(a, b, S_1\)。
解答
记第 \(i\) 轮结束时，状态为 \(S_{2i}\)，先手获胜的概率为 \(p(S_{2i})\)。
设游戏从 \(S = x, x \in (b,a)\) 开始。若先手第一步没有获胜，记此时 \(S = y\)，那么后手变成先手，且后手此时的获胜概率为
\[ (a-x) \frac{\int_x^a p(-b-a-y) \, \mathrm dy}{a-x} = 1 - p(x) \]
其中 \(a-x\) 是先手第一步没有获胜的概率，\(\frac{\int_x^a p(-b-a-y)}{a-x}\) 是条件概率，其意义是先手第一步结束后位于 \(y\) 处，其中 \(y\) 服从 \((x, a)\) 上的均匀分布，且此时后手若想获胜，需要移动的相对 \(a\) 的距离是 \((|b|-a) - y\)。上式仅在 \(b < 0 < a\) 且 \(|a-b| \leq 1\) 时成立。上述积分方程可化简为
\[ F(-(x+a+b)) - F(-(2a+b)) = 1 - F'(x) \]
其中 \(F'(x) = p(x)\)。
我们分析一下这个函数方程和微分方程的混合等式。首先两边求导，得到
\[ -F'(-(x+a+b)) = -F''(x) \]
即
\[ p(-(x+a+b)) = p'(x). \]
继续两边求导，得到
\[ p'(-(x+a+b)) = -p''(x) \]
另一方面，做变量替换 \(y = -(x+a+b)\)，得到
\[ p(y) = p'(-(y+a+b)) \]
比较上下两式得
\[ p(x) = -p''(x). \]
这是一个简谐运动微分方程，其通解为
\[ p(x) = A \cos x + B \sin x, \]
其中 \(A, B\) 为待定系数。
于是
\[ p'(x) = B \cos x - A \sin x \]
代入 \(p(-(x+a+b)) = p'(x)\) 得到
\[ A \cos (x + a + b) - B \sin(x + a + b) = -A \sin x + B \cos x \]
用和角公式展开左边并比较系数，得到
\[ \frac{B}{A} = \frac{\cos(a + b)}{1 + \sin(a + b)} = \frac{1 - \sin(a + b)}{\cos (a + b)} \]
于是
\[ p(x) = A \left(\cos x + \frac{1 - \sin(a + b)}{\cos (a + b)} \sin x \right). \]
于是
\[ F(x) = A \left(\sin x - \frac{1 - \sin(a + b)}{\cos (a + b)} \cos x \right) + D \]
代入原式 \(F(-(x+a+b)) - F(-(2a+b)) = 1 - F'(x)\)，令 \(x=0\)，解得
\[ A = \frac{1}{\sin (2a+b) + \frac{1 - \sin(a + b)}{\cos (a + b)} \cos (2a+b)}. \]
于是，\(p(x)\) 的表达式为
\[ p(x) = \frac{\cos x + \frac{1 - \sin(a + b)}{\cos (a + b)} \sin x }{\sin (2a+b) + \frac{1 - \sin(a + b)}{\cos (a + b)} \cos (2a+b)}. \]
当 \(a+b=0\) 时，该公式退化到仅求解特殊情况时的情形
\[ p(x) = \frac{\cos x + \sin x}{\cos a + \sin a}. \]
于是，1.，2. 的答案为：
先手获胜的概率为
\[ p(0) = \frac{1}{\cos \frac{1}{2} + \sin \frac{1}{2}} \approx 0.737. \]
令 \(p(x_0) = 1/2\)，得 \(x_0 \approx -0.285\)。于是，当 \(S_1 = x_0\) 时，先手和后手的胜率一致。
注意到 \(p(a)=1\) 恒成立。为了避免出现 \(p(x) \notin [0,1]\) 的情况，需要确定该公式的适用范围为
- \(b < 0 < a\) 且 \(|a-b| \leq 1\) 且 \(p(b) \geq 0\) 且 \(\forall x \in [b, a], p'(x) \geq 0\)。
可以推出不等式后，画一个图看看这个范围。
然后，对于更一般的 \(a, b\)，没有什么好的思路，做蒙特卡洛模拟吧。