KeyTo9无限升级的概率

KeyTo9_Fans

KeyTo9一开始的力量值为$2$，他通过打怪来不断提高自己的力量值。

怪物是一只一只地打的，打完一只再打下一只。

每只怪物也有一个力量值，该力量值是一个随机实数，记为$r$，该随机实数满足$1/r$在$(0,1)$区间均匀分布。

记$p$为KeyTo9当前的力量值、$r$为KeyTo9当前遇到的怪物的力量值，

如果$p\leq r$，那么KeyTo9就会被这只怪物打死，然后就Game Over了；否则KeyTo9就会把这只怪物打死。

KeyTo9每打死一只怪物，力量值都会提升，提升后的力量值为两者的力量值之和$p+r$。

问题$1$：

KeyTo9被第$n$（$n=1,2,3,...$）只怪物打死的概率是多少？

问题$2$：

KeyTo9可以无限升级的概率是多少？

#####

$n=1$是最简单的情形，KeyTo9被打死的概率是$0.5$；

对于较大的$n$，情况比较复杂，期待高手的解答。

mathe

题目转化一下就是说怪物的力量r满足$r>=1$,而密度函数为$1/r^2$,
显然第一次K29大难不死后余下力量为$f_1=2+r$,其中$3<=f_1<=4$,概率密度为$1/{(f_1-2)^2}$ (积分只有$1/2$,另外一半属于挂掉的情况）
下一轮，要求$1<=r<=f_1$，余下力量为$f_2=f_1+r$,即$f_1+1<=f_2+2f_1$,相对$f_1$的条件密度为$1/{(f_2-f_1)^2}$
所以联合密度为$1/{(f_1-2)^2(f_2-f_1)^2}$,计算$\int_3^4df_1\int_{f_1+1}^{2f_1}\frac{df_2}{(f_1-2)^2(f_2-f_1)^2}$后就可以得出K29幸存的概率为$1/4(1+\ln(3/2))$,可以看出计算出来的表达式已经不够友好了。
继续下一轮，类似，我们需要计算积分$\int_3^4df_1\int_{f_1+1}^{2f_1}df_2\int_{f_2+1}^{2f_2}\frac{df_3}{(f_1-2)^2(f_2-f_1)^2(f_3-f_2)^2}$这个计算解析形式已经有点困难了,数值结果是0.281593

mathe

记$f_0(x)=1 (x>=1)$
$f_n(x)=\int_1^x \frac{f_{n-1}(t+x)}{t^2}dt$
显然$f_n(x)$在$x>1$时有$0<f_n(x)<1$而且对于给定的x,$f_n(x)<f_{n-1}(x)$,而对于给定的n,$f_n(x)$是单调增函数，所以极限$\bar{f}(x)=\lim_{n->\infty} f_n(x)$,
而无限升级的极限概率为$\bar{f}(2)=\int_3^4\frac{\bar{f}(x)}{(x-2)^2}dx$
而$\bar{f}$满足$\bar{f}(x)=\int_1^x \frac{\bar{f}(t+x)}{t^2}dt$以及边界条件$\bar{f}(1)=0,\bar{f}(+\infty)<=1$

wayne

方法如mathe所言，计算了一下:
被第 $1$只怪物打死的概率是 $0.50000000000000000000000000000000000000000000000000$,解析表达是$1/2$
被第 $2$只怪物打死的概率是 $0.14863372297295890450549672113391271585700239413438$,解析表达是$\frac{1}{4} \left(1-\log \left(\frac{3}{2}\right)\right)$
被第 $3$只怪物打死的概率是 $ 0.069772992972711833525498359819456801555788139887006$,解析表达是$\frac{1}{48}(6 \text{Li}_2(\frac{1}{4})+12 \text{Li}_2(-\frac{1}{5})-12 \text{Li}_2(-\frac{1}{8})+5+12 \log (3)+\log (2) (-85-30 \log (2)+48 \log (3))+\log (5) (25+6 \log (5)-12 \log (6))) $
被第 $4$只怪物打死的概率是$0.04039926459846329$,解析表达是
被第 $5$只怪物打死的概率是$0.02641523133930169$,
被第 $6$只怪物打死的概率是$0.018694364381338542$,
被第 $7$只怪物打死的概率是$0.013984464310538857$,
被第 $8$只怪物打死的概率是$0.01089754978934694$,
被第 $9$只怪物打死的概率是$0.008761895568017947$,
被第$10$只怪物打死的概率是$0.007220671168228464$,


浮点数计算，精度不确定，仅供参考。
===========补上代码，Sun Dec 16 16:49:14 CST 2018=================

1. p = 2; Probability[p > 1/x && p + 1/x > 1/y && p + 1/x + 1/y < 1/z , {x, y, z} \[Distributed] UniformDistribution[3]]

复制代码

`

kastin

随机变量 `1/r\sim \mathrm U(0,1) `，因此`P(0<1/r\leqslant x)=x`，即 `P(r< 1/x)=1-x`. 故CDF为`F_r(x)=1-1/x\; (x\geqslant 1)`，PDF为 `f_r(x)=1/x^2\; (x\geqslant 1)`.
当 `n=1` 时，`P(r_1\geqslant 2)=1-1 / 2=1/2`.
当 `n=2` 时，前面一次必然是 `r_1< 2`，否则游戏结束。 由于 `P(r_1<1)=1-1=0`，从而 `1\leqslant r_1 < 2`，于是 `p_2=2+r_1=3\sim4`. 故发生这种事件的概率为 \[P(1\leqslant  r_1< 2，r_2\geqslant p_2)=\int_{y\geqslant x}\frac{1}{(x-2)^2}\frac{1}{y^2}\dif y\dif x=\int_3^4\frac{1}{x(x-2)^2}\dif x=\frac{1}{4}(1-\ln\frac{3}{2}) \]在此后就变得复杂了，因为 `p_3,p_4\cdots`都是随机的，故需要使用条件概率，运用全概率公式。剩余步骤和公式大致类似2楼的计算过程，这里就不再继续重复了。
其实按照题意，`r_1` 是不能等于2的（即2楼中的`f_1\neq 4`)，虽然积分不影响，但是上面的 `P(r_1\geqslant 2)=1/2`，`F_r(2)=1/2`，这就得到 `P(r_1=2)=1/2+1/2-1=0`，有点奇怪。

mathe

K29是存在存活概率的，我们前面定义过
$f_n(x)=\int_1^x \frac{f_{n-1}(t+x)}{t^2}dt$
定义$g_n(x)=1-f_n(x), g_0(x)=0$
于是$g_n(x)=\int_1^{+\infty} \frac1{t^2}dt-\int_1^x \frac{f_{n-1}(t+x)}{t^2}dt=\int_x^{+\infty}\frac1{t^2}dt+\int_1^x\frac{1-f_{n-1}(t+x)}{t^2}dt=1/x+\int_1^x\frac{g_{n-1}(t+x)}{t^2}dt$
记$h_1(x)=1/x$, $h_n(x)=\int_1^x \frac{h_{n-1}(x+t)}{t^2}dt$
于是对于$n>=1$有$g_n(x)=\sum_{k=1}^n h_k(x)$,而$h_n(2)$就是被第n只怪物打死的概率，另外我们需要证明$g_n(2)<1$

kastin

考虑递推关系， `1\leqslant r_{k-1} < p_{k-1}`（上一次打死怪），`p_k=p_{k-1}+r_{k-1}`（升级）， `r_{k}\geqslant p_k`（这次被怪打死）
于是得到第一问的结果\[\varphi_k=\int_{p_k}^{\oo}\frac{\dif r_k}{r_k^2}\int_{p_{k-1}+1}^{2p_{k-1}}\frac{\dif p_k}{(p_k-p_{k-1})^2}\cdots\int_{p_2+1}^{2p_2}\frac{\dif p_3}{(p_3-p_2)^2}\int_3^4\frac{\dif p_2}{(p_2-2)^2}\\
=\int_{p_{k-1}+1}^{2p_{k-1}}\frac{\dif p_k}{ p_k(p_k-p_{k-1})^2}\cdots\int_{p_2+1}^{2p_2}\frac{\dif p_3}{(p_3-p_2)^2}\int_3^4\frac{\dif p_2}{(p_2-2)^2}\]从wayne数值计算的结果来看，被怪物打死的概率越来越小，似乎趋向一个极限：若该极限为零，那么总能无限升级；否则只能以较大的概率升级有限次后被终结。
当上面最后一个条件改成 `1\leqslant r_k < p_k` （这次怪被打死），于是可得到第 `k`次打死怪的概率为\[\phi_k=\int_1^{p_k}\frac{\dif r_k}{r_k^2} \int_{p_{k-1}+1}^{2p_{k-1}}\frac{\dif p_k}{(p_k-p_{k-1})^2}\cdots\int_{p_2+1}^{2p_2}\frac{\dif p_3}{(p_3-p_2)^2}\int_3^4\frac{\dif p_2}{(p_2-2)^2}\\
=\int_{p_{k-1}+1}^{2p_{k-1}}\left(1-\frac{1}{p_k}\right)\frac{\dif p_k}{(p_k-p_{k-1})^2}\cdots\int_{p_2+1}^{2p_2}\frac{\dif p_3}{(p_3-p_2)^2}\int_3^4\frac{\dif p_2}{(p_2-2)^2}\]于是 \[\phi_{k+1}=\int_{p_k+1}^{2p_k}(1-\frac{1}{p_{k+1}})\frac{\dif p_{k+1}}{(p_{k+1}-p_k)^2}\int_{p_{k-1}+1}^{2p_{k-1}}\frac{\dif p_k}{(p_k-p_{k-1})^2}\cdots\int_{p_2+1}^{2p_2}\frac{\dif p_3}{(p_3-p_2)^2}\int_3^4\frac{\dif p_2}{(p_2-2)^2}\]比较可发现 `\phi_{k+1}`  中第一个积分的结果多出一个因子，且为`\D\frac{(p_k-1)^2+\ln(1+p_k)-\ln 2}{p_k^2}`.
有点难分析其对数值结果的影响。

wayne

mathe 7楼的解答,跟前面的计算结果是吻合的，设最初的体力值为$x$,那么被第$n$只怪物打败的概率是$h_n(x)$,那么存在递推公式 记$h_1(x)=1/x$, $h_n(x)=\int_1^x \frac{h_{n-1}(x+t)}{t^2}dt$，计算得知：
$h_1(x)=1/x$
$h_2(x) = \frac{x-\log (x+1)-1+\log (2)}{x^2}$
\(h_3(x) = -\frac{-4 x \text{Li}_2\left(-\frac{1}{x+1}\right)+4 x \text{Li}_2\left(-\frac{x}{x+1}\right)+4 (x+1) \text{Li}_2(-x-1)-4 (x+1) \text{Li}_2(-2 x)-4 \text{Li}_2\left(-\frac{1}{x+1}\right)+4 \text{Li}_2\left(-\frac{x}{x+1}\right)-2 x^3+2 x^2+x^2 \log (4)-x^2 \log (16)+2 x^2 \log (x)+4 x^2 \log (x+2)-2 x^2 \log (2 x+1)+3 x+x \log (2)+x \log (4)-x \log (2) \log (16)+4 x \log (x)+x \log (16) \log (x+1)-4 x \log (x) \log (x+1)-4 x \log (x+1)+8 x \log (x+2)-7 x \log (2 x+1)+\log (16) \log (x+1)-4 \log (x) \log (x+1)-4 \log (x+1)-3 \log (2 x+1)-3-\log (2) \log (16)+\log (128)}{2 x^3 (x+1)}\)
再往下 表达式非常非常的庞杂，贴出来意义不大。所以就这样吧，@KeyTo9_Fans， 见好就收。
这个递推公式对于游戏设计，已经很有启发意义了。
。

wayne

我想挖掘出这个计算复杂度的来源,是不是有可能是KeyTo9_Fans的怪物体力值的生成函数$1/r$没有选漂亮导致的，我可不想见坑就跳。
我们来试一试看能不能找个比$1/r$更好的函数，使得后面的关于怪物打败的概率的计算变得容易一点.


///////////////////////////////
假设存在$\phi(x)$, 存在递推公式 $h_1(x)=\phi(x)$, $h_n(x)=\int_a^x \h_{n-1}(x+t)\phi'(t)dt$
为了能将递推公式化解开，$\phi(x)$有必要具备二元分解的性质，即能将$\phi(x+y)$拆分成$\phi(x)$和$\phi(y)$的代数和。于是最佳候选的类型是指数函数和三角函数。
///////////////////////////////
如果将体力值的值域设定在整个区间 $(0,+\infty)$，那么可以选择正切函数，如 $tan(\frac{\pir}{2})$比较合适
如果将体力值的值域设定在整个区间 $(0,1)$，那么可以选择三角函数，比如$cos(r),sin(r)$

mathe

可以试着离散化计算以下看看
由于\(f_n(x)=\int_1^x \frac{f_{n-1}(x+t)}{t^2}dt\)
如果我们将\(f_{n-1}(x)\)用一个较小的函数\(\widehat{f_{n-1}}(x)\)替换，那么只要得出
\(\widehat{f_n}(x)\le \int_1^x \frac{\widehat{f_{n-1}}(x+t)}{t^2}dt\le f_n(x)\)
就可以给出\(f_n(x)\)的下界了，
为了便于离散化计算，我们选择\(x_0=1,x_1=1+h,x_2=1+2h,...,x_t=1+th,...\),$h=1/H$充分小,$H$是整数
由于\(f_1(x)=1-\frac1x\),我们选择\(\widehat{f_1}(x_t)=1-f_1(x_t)=1-\frac1{x_t}\),但是在区间\((x_t,x_{t+1})\)上\(\widehat{f_1}(x)\)是线性函数（就是直线段）,由于\(f_1(x)\)是上凸函数，所以\(\widehat{f_1}(x)\le f_1(x)\)
现在我们假设 \(\widehat{f_{n-1}}(x)\le f_{n-1}(x)\)同样在区间\((x_t,x_{t+1})\)上是线性函数而且它是连续单调增上凸函数，满足
\(\widehat{f_{n-1}}(x_0)=0,\widehat{f_{n-1}}(+\infty)=1\),并且设\(\widehat{f_{n-1}}(x_t)=a_{n-1,t}\)
于是在区间\((x_t,x_{t+1})\)上有\(\widehat{f_{n-1}}(x)=a_{n-1,t}+(a_{n-1,t+1}-a_{n-1,t})\frac{x-x_t}{x_{t+1}-x_t}=c_{n-1,t}+b_{n-1,t}x\)