数学研发论坛

 找回密码
 欢迎注册
查看: 1071|回复: 26

[原创] KeyTo9无限升级的概率

[复制链接]
发表于 2018-11-14 01:40:25 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
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$,情况比较复杂,期待高手的解答。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-14 08:49:29 | 显示全部楼层
题目转化一下就是说怪物的力量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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-14 09:35:13 | 显示全部楼层
记$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$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-14 11:32:53 | 显示全部楼层
方法如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]]
复制代码

`

点评

额,就是上面的代码,把$Probability$ 改成$NProbability$  发表于 2018-12-16 21:56
你用了什么算法?为什么你只计算了一小会儿,精度反而远高于我计算了$1$天的结果?  发表于 2018-12-16 20:40
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-14 17:56:16 | 显示全部楼层
本帖最后由 kastin 于 2018-11-14 18:45 编辑

随机变量 `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`,有点奇怪。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-14 21:02:37 | 显示全部楼层
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$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-14 22:11:08 | 显示全部楼层
本帖最后由 kastin 于 2018-11-14 22:12 编辑

考虑递推关系, `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}`.
有点难分析其对数值结果的影响。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-15 10:26:23 | 显示全部楼层
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, 见好就收。
这个递推公式对于游戏设计,已经很有启发意义了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-15 13:32:25 | 显示全部楼层
我想挖掘出这个计算复杂度的来源,是不是有可能是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)$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2018-11-15 20:50:50 | 显示全部楼层
可以试着离散化计算以下看看
由于\(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\)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-8-25 08:07 , Processed in 0.054653 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表