扔骰子永远追不上的概率

lsr314

假设甲乙两个人轮流扔骰子，甲先扔，扔到几就走几步，直到一个人追到另一个人为止（即两人总点数一样），求：
（1）甲被乙追上的概率P1；（2）乙被甲追上的概率P2；（3）两人永远都不相遇的概率P0。

由于甲先扔，应该有P1>P2，程序模拟的结果，P2在0.3到0.4之间。好奇P0是否等于0？。

mathe

假设轮到扔骰子的玩家这时数字和对手差值为n时追上对手概率为a(n),在|n|>6时，分析两轮投掷情况后，就可以得到一个11阶线性递推式。由此我们可以得到一个有两个有11个参数的递推式。
然后在特别计算|n|比较小的情况的关系，再利用a(n)+a(-n)=1,就应该可以解出所有系数

mathe

两人对局，我们假设现在轮到扔骰子的人累积点数比对手少n时，最终他追上的概率为W(n),双方经过无限次都无法相互追上的概率为E(n), 最终对手追上的概率为L(n). 类似，如果他累积的点数比对手多n时，我们用-n表示这个差值，也就是他追上的概率为W(-n)等等。
于是显然对于\(n\ge 7\)或\(n\le -1\)时，都有\(E(n)=\frac{\sum_{h=1}^6 E(h-n)}6\)
对于其中每个E(h-n)再迭代使用这个公式，我们可以得出在\(n\ge7\)或\(n\le -6\)时，有
\(36E(n)=E(n-5)+2E(n-4)+3E(n-3)+4E(n-2)+5E(n-1)+6E(n)+5E(n+1)+4E(n+2)+3E(n+3)+2E(n+4)+E(n+5)\)
即
\(E(n-5)+2E(n-4)+3E(n-3)+4E(n-2)+5E(n-1)-30E(n)+5E(n+1)+4E(n+2)+3E(n+3)+2E(n+4)+E(n+5)=0\)
这是一个10阶线性递推数列。
对应特征多项式为\((x-1)^2(x^8 + 4x^7 + 10x^6 + 20x^5 + 35x^4 + 20x^3 + 10x^2 + 4x + 1)\)
这个方程除了二重根1以外，还有4个复数根绝对值小于1/2，4个复数根绝对值大于2, 而且它们两两互为倒数.
我们记4个绝对值小于1的复数根为\(r_1,r_2,r_3,r_4\), 由于数列E(n)有界，根据链接, 我们可以设\(n\ge 2\)时\(E(n)=c_0+c_1r_1^n+c_2r_2^n+c_3r_3^n+c_4r_4^n\)；
同样我们可以设\(n\le -1\)时，\(E(n)=d_0+d_1r_1^{-n}+d_2r_2^{-n}+d_3r_3^{-n}+d_4r_4^{-n}\)。
然后我们再次根据公式\(E(n)=\frac{\sum_{h=1}^6 E(h-n)}6\)，取任意\(n\ge 7\)，将两个通项公式代入，得到

\(6(c_0+c_1r_1^n+c_2r_2^n+c_3r_3^n+c_4r_4^n)=\sum_{h=1}^6 (d_0+d_1r_1^{n-h}+d_2r_2^{n-h}+d_3r_3^{n-h}+d_4r_4^{n-h})\)
两边比较可以得到
\(c_0=d_0, 6c_1=d_1(r_1^{-1}+r_1^{-2}+r_1^{-3}+r_1^{-4}+r_1^{-5}+r_1^{-6}),...\)
同理，对于充分小的负数n,我们类似代入递推式，得到
\(d_0=c_0, 6d_1=c_1(r_1^1+r_1^2+r_1^3+r_1^4+r_1^5+r_1^6),...\)
经计算得知，两者其实是等价的。也就是我们实际上只有5个可选参数\(c_0,c_1,c_2,c_3,c_4\),所有的对应的d参数已经被c参数唯一确定。

然后我们还可以使用递推关系
\(\begin{cases}6E(6)=E(-5)+E(-4)+E(-3)+E(-2)+E(-1)\\
6E(5)=E(-4)+E(-3)+E(-2)+E(-1)+E(1)\\
6E(4)=E(-3)+E(-2)+E(-1)+E(1)+E(2)\\
6E(3)=E(-2)+E(-1)+E(1)+E(2)+E(3)\\
6E(2)=E(-1)+E(1)+E(2)+E(3)+E(4)\\
6E(1)=E(1)+E(2)+E(3)+E(4)+E(5)\end{cases}\)
这六个方程式关于变量\(c_0,c_1,c_2,c_3,c_4,E(1)\)的齐次方程，其对应系数矩阵行列式数值计算结果为1.30215...不是0，所以得到只有零解，
所以我们得到双方经过无限轮还无法相互追上的概率为0。

pizza49

mathe 发表于 2025-11-2 21:30
假设轮到扔骰子的玩家这时数字和对手差值为n时追上对手概率为a(n),在|n|>6时，分析两轮投掷情况后，就可以 ...

可以详细写一下递推关系吗？

mathe

在已经得出E(n)=0以后，我们可以得到对于\(n\ge 7\)或\(n\le -1\)时，都有\(W(n)=1-\frac{\sum_{h=1}^6 W(h-n)}6\).
同样，我们对每个W(h-n)再次迭代使用这个公式，得到在\(n\ge7\)或\(n\le -6\)时，有
\(36W(n)=W(n-5)+2W(n-4)+3W(n-3)+4W(n-2)+5W(n-1)+6W(n)+5W(n+1)+4W(n+2)+3W(n+3)+2W(n+4)+W(n+5)\)
即
\(W(n-5)+2W(n-4)+3W(n-3)+4W(n-2)+5W(n-1)-30W(n)+5W(n+1)+4W(n+2)+3W(n+3)+2W(n+4)+W(n+5)=0\)。
类似前面的流程， 我们可以设\(n\ge 2\)时\(W(n)=c_0+c_1r_1^n+c_2r_2^n+c_3r_3^n+c_4r_4^n\)；
同样我们可以设\(n\le -1\)时，\(W(n)=d_0+d_1r_1^{-n}+d_2r_2^{-n}+d_3r_3^{-n}+d_4r_4^{-n}\)。
然后我们再次根据公式\(W(n)=1-\frac{\sum_{h=1}^6 W(h-n)}6\),得到在\(n\ge 7\)时，有
\(6(c_0+c_1r_1^n+c_2r_2^n+c_3r_3^n+c_4r_4^n)=6-\sum_{h=1}^6(d_0+d_1r_1^{n-h}+d_2r_2^{n-h}+d_3r_3^{n-h}+d_4r_4^{n-h})\)
由此我们得到
\(c_0+d_0=1\)
而且
\(6c_1=-d_1(r_1^{-1}+r_1^{-2}+r_1^{-3}+r_1^{-4}+r_1^{-5}+r_1^{-6}),...\)
然后我们同样还可以使用递推式
\(\begin{cases}6-6W(6)=W(-5)+W(-4)+W(-3)+W(-2)+W(-1)\\
6-6W(5)=W(-4)+W(-3)+W(-2)+W(-1)+W(1)\\
6-6W(4)=W(-3)+W(-2)+W(-1)+W(1)+W(2)\\
6-6W(3)=W(-2)+W(-1)+W(1)+W(2)+W(3)\\
6-6W(2)=W(-1)+W(1)+W(2)+W(3)+W(4)\\
6-6W(1)=W(1)+W(2)+W(3)+W(4)+W(5)\end{cases}\)
这个关于六个变量的数值计算结果W(1)=0.49059481704690211391583944815240877925
\(c_0=0.71885522847792362796896851339640098693\)
\(c_1=-1.2172146502750563413147127227965991873 + 0.54120494249845070237417831344645497817*I\)
\(c_2=-1.2172146502750563413147127227965991873 - 0.54120494249845070237417831344645497814*I\)
\(c_3= -0.23648910635352361251461410088360624079 + 0.89857829922008009018418069799931657003*I\)
\(c_4=-0.23648910635352361251461410088360624079 - 0.89857829922008009018418069799931657003*I\)
其中4个根
r1=-0.36381019364557737845173569693150849646 - 0.22924870795789949980001605750194933912*I
r2=-0.36381019364557737845173569693150849646 + 0.22924870795789949980001605750194933912*I
r3=0.062087113729964518847213789650984951176 - 0.47622253025094262857882693522779027194*I
r4=0.062087113729964518847213789650984951176 + 0.47622253025094262857882693522779027194*I

然后使用公式\(n\ge 2\)时\(W(n)=c_0+c_1r_1^n+c_2r_2^n+c_3r_3^n+c_4r_4^n\)数值计算得W(2)=0.55574480974371952727776759115873671128, W(3)=0.61759875412518015401778152835348161193,W(4)=0.67303383900190347780765563310364913545,W(5)=0.71945887780088204348591911031727108658， W(6)=0.75501661750217640380535155495044280626
由此可以得到后手先达到的概率为\(\frac{W(1)+W(2)+W(3)+W(4)+W(5)+W(6)}6=0.63524128587012728671838581100599835512\)

mathe

关于这个问题，我们可以进行推广，
i）换成一个n面均匀骰子，数字从1到n (n>1)，那么是不是双方永远无法追上的概率都是0？
ii) 换成n面非均匀骰子，数字从1到n,那么是不是双方永远无法追上的概率都是0？
iii)换成n面非均匀骰子，上面数字是任意的n个不同正整数,那么是不是双方永远无法追上的概率都是0？

mathe

假设骰子有k个面，数值是整数\(f_1,f_2,\cdots,f_k\),概率为\(p_1,p_2,\cdots,p_k\)，\(\sum_{h=1}^k p_h=1\)。
不妨假设\(gcd(f_1,f_2,\cdots,f_k)=1\) 而且\(0\lt f_1\le f_2\le\cdots\le f_k\)。
于是类似前面的定义，我们可以有\(E(n)=\sum_{h=1}^k p_h E(f_h - n), n \neq 0 , n\neq f_h\).
如果我们补充定义E(0)=0, 那么对于任意\(n\neq 0\)都有\(E(n)=\sum_{h=1}^k p_h E(f_h - n)\).
同样对于绝对值充分大的n，我们可以通过两轮迭代，得到
\(E(n)=\sum_{s=1}^k\sum_{t=1}^k p_s p_t E(n+f_s-f_t )\)。
于是对应特征方程f(x)次数为\(2(f_k-f_1)\), 系数之和为0.
而且\(g(x)=\frac{f(x)}{x^{f_k-f_1}}\)满足\(g(x)=g(\frac1x)\),并且只有常数项为负数，其余项系数都是正数。
根据绝对值不等式，如果多项式f(x)有单位根r,那么必然对于所有\(f_s-f_t\), \(r^{f_s-f_t}\)全部相同，也就是r是单位\(d=gcd_{s,t=1}^k(f_s-f_t)\)次根。
而且如果我们记\(h(z^d)=g(z)\),也就是\(h(x)=\sum_{s=1}^k\sum_{t=1}^k p_sp_t x^{\frac{f_s-f_t}d}-1\), 那么\(h'(x)=\sum_{s=1}^{k-1}\sum_{t=s+1}^k \frac{p_sp_t(f_t-f_s)}d(x^{\frac{f_t-f_s}d-1}-x^{\frac{f_s-f_t}d-1})=\sum_{s=1}^{k-1}\sum_{t=s+1}^k \frac{p_sp_t(f_t-f_s)}d x^{\frac{f_s-f_t}d-1}(x^{\frac{2(f_t-f_s)}d}-1)\)
很显然1也是h'(x)的根，而且由于\(\frac{h'(x)}{x-1}\)所有系数显然大于0，所以1不是h'(x)的重根，由此得到1正好是h(x)的二重根。
此外由于如果r是h(x)的根，那么1/r也是h(x)的根，所以h(x)余下的根中一半范数小于1，一半范数大于1，也就是它的范数小于1的根的数目正好是\(\frac{f_k-f_1}d-1\)个。