怪物力量值的最佳分布

KeyTo9_Fans

手机的各种app里经常能看到这样的广告：

主角的初始力量值是a，然后玩家把主角拖动到一个力量值为b（b≤a）的怪物旁边，



然后主角一刀把怪物杀了，主角的力量值升级为(a+b)。

然后玩家把主角拖动到下一个力量值小于等于主角力量值的怪物旁边，

然后主角继续杀怪，不断地把怪物的力量值加到主角的力量值里，

然后玩家故意失误，把主角拖动到一个力量值大于主角力量值的怪物旁边，



然后主角就被怪物杀了，然后显示挑战失败，



以此来激发手机用户的好胜心，引诱用户点开广告下载这个游戏。

下载下来之后发现根本就不是这个打怪的游戏，而是游戏开发公司急需推广的另一款游戏。

#####

基于上述设定，我们提出这样的数学问题：

假设玩家力量值a的初始值是1，每只怪物的力量值都是一个取值范围为正整数的相互独立的随机变量X，

问题1：

如果每次只允许查看1只怪物的力量值，打完它才能看下一只怪物，

那么应该如何设定怪物力量值X取到每一个正整数的概率，

才能使得玩家在打了n只怪之后，力量值的期望值达到最大呢？

问题2：

如果允许同时查看2只怪物的力量值，然后选择一只去杀，

杀掉之后，会有一只新的怪物进来，而另一只怪物则保持不变，

然后玩家可以继续从这2只怪物里选择一只去杀，依次类推，

那么在这样的设定之下，应该如何设定怪物力量值X取到每一个正整数的概率，

才能使得玩家在打了n只怪之后，力量值的期望值达到最大呢？

#####

注：如果玩家在打n只怪的途中被怪物杀死，则最终的力量值按0计算，否则最终的力量值等于n只怪的力量值之和加1。

例如，当n=1时，应令X=1的概率为1，方可使玩家在打了1只怪之后，力量值的期望值达到最大值2。

如果在问题1里令X=1和X=2的概率各为1/2，则玩家在打了1只怪之后，

有1/2的概率最终力量值为0，1/2的概率最终力量值为2，最终力量值的期望值为1，是小于上述最大值2的。

以下贴子讨论了X为连续型随机变量的情况：

https://bbs.emath.ac.cn/thread-15592-1-1.html

本贴讨论的是X为离散型随机变量的情况，

我想知道当n→∞时，怪物力量值的最佳分布是什么样子的，

在这个分布下，玩家的存活概率如何变化，力量值的极限增速有多快。

KeyTo9_Fans

我先来解决一下问题1：

--------------------

如果每次只允许查看1只怪物的力量值，打完它才能看下一只怪物，

那么应该如何设定怪物力量值X取到每一个正整数的概率，

才能使得玩家在打了n只怪之后，力量值的期望值达到最大呢？

--------------------

当n=1时，1楼已经给出了答案：

怪物力量值X应设置成

Pr(X=1)=1

才能使得玩家在打了1只怪之后，力量值的期望值达到最大值2。

--------------------

当n=2时，设

Pr(X=1)=p
Pr(X=2)=1-p

则玩家在打第1只怪时，有(1-p)的概率死掉，有p的概率力量值变成2。

如果没死，那么在打第2只怪时，有p的概率力量值变成3，有(1-p)的概率力量值变成4。

力量值的期望值是

0*(1-p)+3*p^2+4*p(1-p)=4p-p^2

上式在p=2时取得最大值4，

但p是概率，所以最大只能取1，不能取2，

把p=1代入4p-p^2，得到最终力量值的期望值的最大值是 4-1^2=3。

力量值的最佳分布是

Pr(X=1)=1
Pr(X=2)=0

--------------------

当n=3时，设

Pr(X=1)=p
Pr(X=2)=q
Pr(X=3)=r
Pr(X=4)=1-p-q-r

则玩家在打第1只怪时，有(1-p)的概率死掉，有p的概率力量值变成2。

如果没死，那么在打第2只怪时，有(1-p-q)的概率死掉，有p的概率力量值变成3，有q的概率力量值变成4。

如果没死，那么在打第3只怪时，有p*(1-p-q-r)的概率死掉，有p*p的概率力量值变成4，有2*p*q的概率力量值变成5，有(q*q+p*r)的概率力量值变成6，有q*r的概率力量值变成7，有q*(1-p-q-r)的概率力量值变成8，

力量值的期望值是

(1-p)*0+p*((1-p-q)*0+p*((1-p-q-r)*0+p*4+q*5+r*6)+q*(p*5+q*6+r*7+(1-p-q-r)*8))

=4ppp+2ppq+6ppr-2pqq-pqr+8pq

在p、q、r非负且p+q+r≤1的约束下，要取p=1、q=r=0，才能令上式取得最大值4。

所以力量值的最佳分布是

Pr(X=1)=1
Pr(X=2)=0
Pr(X=3)=0
Pr(X=4)=0

--------------------

由此可以猜想，问题1的结论是：

无论n是几，力量值的最佳分布都是

Pr(X=1)=1

最终力量值的期望值的最大值是(n+1)。

接下来可以验一下更大的n，上述猜想是否成立。

如果成立，应该如何证明这个猜想呢？

KeyTo9_Fans

假设怪物力量值只能取1和2，

那么设Pr(X=1)=p，Pr(X=2)=1-p，

则打n只怪的存活概率为p，在存活的前提下，期望力量值为

2+(n-1)*(p*1+(1-p)*2)
=2+(n-1)*(2-p)
=2n-(n-1)p

因此在所有情况下的期望力量值为

p*(2n-(n-1)p)
=2np-(n-1)p^2

上式在p=1+1/(n-1)时取得最大值，

但p是概率，不能比1大，因此只能取p=1，

方可使所有情况下的期望力量值达到最大，

这个最大值是1*(2n-(n-1)*1)=n+1。

因此在怪物力量值只能取1和2的前提下，

无论n是几，都是令

Pr(X=1)=1
Pr(X=2)=0

方可使玩家在打了n只怪之后，力量值的期望值达到最大值(n+1)。

--------------------

接下来假设怪物力量值只能取1、2和3，

然后设Pr(X=1)=p，Pr(X=2)=q，Pr(X=3)=1-p-q，

还能勉强证得无论n是几，都是在p=1、q=0时取得最大值。

--------------------

接下来假设怪物力量值只能取1、2、3和4，

然后设Pr(X=1)=p，Pr(X=2)=q，Pr(X=3)=r、Pr(X=4)=1-p-q-r，

然后将期望值展开之后，就不是齐次的了，我就不知道该怎么证了。

--------------------

我还尝试了假设Pr(X=1)=p，Pr(X=m)=1-p，

还是可以证得无论n、m是几，依然是当p=1时，期望值最大。

但假设Pr(X=1)=p，Pr(X=s)=q，Pr(X=t)=1-p-q，

我又不知道该怎么证p=1、q=0时取得最大值了。

--------------------

有没有巧妙一点的证明方法，一步到位地证明无论n是几，力量值的最佳分布都是

Pr(X=1)=1，
Pr(X=2)=0，
Pr(X=3)=0，
Pr(X=4)=0，
……

呢？

KeyTo9_Fans

由于长时间没有收到解答，我把这个问题发到MO上面去了：
https://mathoverflow.net/questio ... me-of-number-master

我还支付了50分的悬赏。