玩家装备更新次数上限定理

哈耶克

前言

马甲兄发过一篇帖子：http://bbs.gameres.com/showthread.asp?threadid=135420   我在里面提出一个问题，那就是玩家装备更新次数和装备掉率设定间的关系，我当时没有找到问题的答案。最近我翻阅随机过程的一些书籍，尤其是读到关于顺序统计量的相关论著时，终于找到解决问题的思路，下面就是对整个问题的较为详尽的解析，不过要想顺畅读完全文，需要点数学分析基础，熟悉概率论和组合数学知识，尤其最好读过R.Stanley的名著《计数组合学》上下卷（强烈推荐此书，我认为它是神作，写得很有趣味性和系统性）。最后说一句，下面的内容纯属娱乐，不能产生任何实际利益，在这个意义上，可以说是无用的。


概要

简单的说来，本文的结论用一句话概括就是：

定理： 如果每次玩家的掉落物品的品质和数量这个随机变量是独立同分布的，而且某个部位的各个物品的质量可以排序，那么玩家打n次boss,玩家在这个过程中，某个部位平均更换次数最多为H_n次，这里H_n=1+1/2+1/3+...+1/n，也就是著名的调和级数。上限当该部位的各个物品的质量出现相等的概率等于0时取得（也就是说几乎不可能两次出现质量相同的物品）。

这个结论具有一定的普适性，通常的游戏设定条件下，每次打boss掉落物品品质是独立同分布的随机变量这个条件是满足，因此不论掉落列表如何设定，玩家更新装备的次数的数学期望是有上限的，而且根据定理也知道如何提高数学期望，那就是减少物品质量重合这个可能性，给物品加上随机属性变量就是一个方法。

一，问题的进一步形式化的表述

玩家要更新某一部位装备（以下省略“某一部位”这个词，减少赘语），必须是现在拿到的装备比以往的装备都要强，如果记玩家第1，2，...，n次获得的装备的质量分别为X1,X2,...,Xn,根据上面的假定，第k次更换装备的充要条件是Xk>max{X1,...,X(k-1)}。

先证明下面的命题，

命题1：如果两次掉落出现相同物品质量的概率不是0，比如物品质量是取得X的概率不为0，如果能给X附加一个微小的随机误差e，使得X+e不与其他物品质量交叉。那么不再掉落X,而是掉落X+e，这样形成了新掉落列表，在新的列表情况下，玩家更新物品的平均次数不小于原来的平均更新次数.

这是因为，新情况下，我们记录两个值，一个值就是即使一次掉落X+e1,一次掉落X+e2,可能构成两次更新，但我们也把它们看作相同质量，算作一次更新，这样我们得到总的“更新次数”s1;另一个值是把e1和e2的不同考虑进去了，如果构成两次更新，我们就算成两次更新，这样我们得到总的更新次数s2.显然，s1就是原来的更新次数，s2是新的更新次数，我们有s1<=s2,从而它们的数学期望也有关系E(s)=E(s1)<=E(s2),这里E(s)代表最开始的更新次数的数学期望，于是结论得证

命题1的作用是，帮助我们把离散随机变量通过连续化的方法变为连续性变量来考虑，而从后面可以知道，所有连续性随机变量情形下的更新次数的数学期望是相同的，这样就能得到上限了

举个例子，boss只掉落物品质量为1，2，3，4，5这5种物品，概率都是0.2，打10次，玩家平均更新次数是多少？我们对每个物品质量都给[0,0.2]这样的一个均匀分布的随机误差，也就是掉落1时，我们还需要附加一个随机误差，随机到了0.1111..那么结果就是1.1111..，而不只是1，这样可以把两次都是1的情形区分出来，它们就不再相等了。

实例1：掉落序列是2，1，1，1，2，3，5，2，3，4         
更新序列：2，3，5
更新次数：3


实例2：掉落序列是2.11..，1.02..，1.05..，1.16..，2.13..，3.06..，5.09..，2.14..，3.15..，4.05..         
更新序列：2.11..，2.13..，3.06..，5.09..  
更新次数：4

用类似的思想，可以证明离散与连续混合型的变量的更新次数的数学期望也不大于连续型的随机变量的更新次数的数学期望


二，连续型随机变量序列更新次数的数学期望
如果X1,X2,X3,...,Xn取自一个独立同分布的连续型随机变量，我们根据从小到大顺序重新排列一下它们，它们各自的下标构成一个[1..n]上的一个排列。组合学的基础知识告诉我们这样的排列有n!个，可以证明序列X1,..,Xn根据上面的方法构成的排列取到具体某一个排列的概率全部都相等，即都是1/n!.这也就是说上面序列出现k个更新的概率和n全排列里出现k个更新的概率是相等的.

这相当吊诡，我们刚把离散情形连续化了，现在这个连续化情形下的更新次数问题又等效于n全排列里的更新次数问题

只是这次问题变得相当简单了，我们只要计数n全排列里出现k次更新的排列个数就可以了，乘以1/n!就是k次更新的概率了

这个计数问题，我下面采用符号组合数学的方法来计算，关于符号组合数学的介绍，可以参看下面的资料：http://en.wikipedia.org/wiki/Symbolic_combinatorics

首先考虑最大数在开头的n全排列这个组合类Q的指数生成函数EGF,因为
Q=z^b*P
^b*代表框乘，也就是z这个单元素必须取最大值，P是全排列组合类
把上面这个简单的常识翻译成生成函数语言就是
Q(z)=int_0^z(1/(1-t)*(d/dt)t)dt=log(1/(1-t))
因此Q_n=(n-1)!，这与我们的预见是相符的

而有k次更新的排列可以写成
P^(k)=SET_k(Q)
这是因为我们可以把集合里每个Q的最大值提出来，按从小到大顺序排列，再脱掉括号，就得到从1到n的更新次数为k的全排列，而且容易看出这个映射是一一对应的

由此就可知
P^(k)(z)=(1/k!)*(log(1/(1-t)))^k

再记二元生成函数
P(z,u)=sum_{r=0}^{+infinity}P^(k)(z)*u^r
=sum_{r=0}^{+infinity}(1/k!)*(log(1/(1-t)))^k*u^r
=exp()ulog(1/(1-t))
=(1-z)^(-u)

从牛顿二项式定理可知P(z,u)里的z^n项前面的系数是
C(-u,n)*(-1)^n
C(-u,n)是二项式系数

若P_n^(k)是P^(k)(z)的第n项系数，记s(n,k)=n!*P_n^(k),它就是n全排列中出现k次更新的排列个数，而且实际上也是所谓的第一类stirling数

考虑P(z,u)里的z^n项前面的系数，则有关系式

sum_{k=0}^n(s(n,k)*u^k)=u(u+1)*...*(u+n-1)

为了计算n全排列中出现更新次数的数学期望值，必须计算sum_{k=0}^n(s(n,k)*k)，采用对数微分法，不难得出

sum_{k=0}^n(s(n,k)*k)=n!*(1+1/2+1/3+...+1/n)=n!*H_n

从而n全排列中出现更新次数的数学期望值就是H_n

比如当n=100时,n全排列中出现更新次数的数学期望值为H_100=5.18738..，也就是大约更新5次

当n较大时，H_n近似于log(n)，这可以减少计算量

综上，开始提的结论得证


后记：这个论坛上写数学公式太累，而且不容易看清楚。看得吃力也算正常。如果觉得有不清楚的地方的话，可以直接问我

下面的资料也有参考价值，通过它可以进一步了解到随机全排列的很多性质，也包含本文里的一些知识：

http://en.wikipedia.org/wiki/Random_permutation_statistics

哈耶克

一个很奇怪的事实是：
如果boss掉落的物品质量是连续型随机变量，假定你第m次更新装备是刷第t(m)次boss时，下一次更新装备是第t(m+1)次，可以证明，当m较大时，t(m)/t(m+1)近似服从[0，1]上的均匀分布，因此有

给定t(m+1)，t(m)的数学期望是t(m+1)*int_{0}^{1}(u du)=t(m+1)/2
给定t(m),t(m+1)的数学期望是t(m)*int_{0}^{1}(1/u du)=+infinity

这就是说，第m次更新装备后，再刷一件更好的装备所需要的平均次数是无穷大！这个结论甚至对m=1也成立，这个事实可以简单证明如下：

如果物品质量这个随机变量的概率密度函数是p(x),累计分布函数是F(x),第一次刷出来装备的质量是t,那么随机再刷一次，出现更好装备的概率是1-F(t),根据几何分布的数学期望性质可以知道，刷出比第一件更好装备的期望次数是n=1/（1-F(t)）,因此
n的数学期望是
E(n)=int_{-infinity}^{+infinity}((1/(1-F(t)))p(t)dt)
=int_{-infinity}^{+infinity}((1/(1-F(t)))d(1-F(t)))
进行积分变量代换u=1-F(t)，则上式变为
int_{0}^{1}((1/u)du)
该积分发散，所以数学期望是正无穷大

这是说，打出第一件装备后，再刷到更好的装备所需的平均次数是无穷大，这个结论对于任意的连续型随机变量均成立。事实上，离散型情形下，这个结论也成立（而且是很显然的成立），因为如果取到最大值的概率不为0，那么如果第一次取到最大值，后面就再无超越的可能，从而刷出更好装备的平均次数是无穷大

11月11日

LZ，我不知道你写了什么，也不想知道。

作为数值，最基本的，让程序很明了你的想法，很快知道自己该干什么。

但是您让程序完全不知道自己要干什么。

就算你要和数值讨论数值，但是

最近我翻阅随机过程的一些书籍，尤其是读到关于顺序统计量的相关论著时，终于找到解决问题的思路，下面就是对整个问题的较为详尽的解析，不过要想顺畅读完全文，需要点数学分析基础，熟悉概率论和组合数学知识，尤其最好读过R.Stanley的名著《计数组合学》上下卷

你把数值引导神秘上，也算数值认识上的一个极端。

我不知道您有没有真正全程参与一个项目，全程负责数值。

但是，您真的把数值引向一个误区，对新手，或没有全程开放经验的数值，有很大的误导性。

学过的知识拿来用，没错。但是乱用就不好了。

你的文章，我想没几个可以看懂，当然有人较真，当然可以去查书看懂。

但是已经失去数值的表达简单，思想简单的目的。

需求产生系统；
系统产生模型；
模型产生规律；
规律产生数据；
数据产生测试；
测试产生结果；
结果满足需求？

这个马甲说的，还有点道理。

如果LZ您真的全程跟过数值，应该有体会。

你只要告诉我们，你做玩家装备更新次数和装备掉率设定间的关系需求是什么，它产生了什么系统或模块，你的模型是什么，公式，数据，随便我们自己给。

最后一点： 数值策划不是数学家，他其实就是主策的数值工具，用最简单的方法实现主策的构思和需求。

Mr_I

不错不错。
等我们研发部门分为研究部门和开发部门并且我被划到研究部门了，我一定想办法挖LZ来做同事。

哈耶克

回复 11月11日

本文不是提高 数值策划 能力的一篇工作总结，纯属工作以外的爱好，我承认自己学的数学根本在开发过程中很少用到，但我业余还是保留阅读数学论文和论著的习惯，不是为了任何别的，和别人业余玩 游戏 没什么区别

之所以发在这里，我想可能这里有我同样爱好的人可能会多一点而已，要是没人和我相同爱好也没关系，自娱自乐而已。当然数值策划的数学水平完全可以很低，就好比前不久某人所说的，我对此也没任何意见，而且我也同意很多数学知识其实对提高策划能力是 无用的...

所以要是讨论该文，我还是希望就文中的细节展开讨论，而不是就 文章的 “实用性”“价值”展开讨论。我早就说过了，该文没有“实际利益价值”，最多如果有同好的话，有“娱乐价值”

sorceryone

首先 （掉落物品的品质和数量（整体掉落率）的随机数是独立同分布的） 我不认同。
就算满足玩家任何一次物品掉落全部包含所有品质的物品条件下，（如果说这里所说的品质和 玩家只更换更好品质的装备是同一个的话） 假定品质为 1----N（N无限大） 掉落物品品质和数量的随机数是独立非同分布的。掉落数量的随机数不会安品质高低来决定，我不认为品质100的物品掉落数量一定会比品质200的物品多。所以说掉落数量的随机数分布一般都是分段的不连续的。虽然在某段内可能符合情况。
其实楼主想表达的意思就是 用不同的方法 拉大品质差距，来实现增加玩家更换装备的次数。
比如玩家在10级的时候 能穿的装备品质为 1 2 3 4 5 6 7 8 9 10
如果能将品质扩大 100倍 1 。。。。。1000，那么更换次数将大大增加
当然你也可以通过楼主的方式
中间可以使用一个偏差值， 用小数增加 1.01 1.02 。。。。。。 9.99 。10.00.。
每次随机到一个数 比如说5，增加偏差 0.01 那么就变成5.01 也可以4.99.
总结：通过不同的方式 增加品质的长度来延长玩家的装备更换频率。

哈耶克

回楼上的，

我这篇文章的目的就是想证明“总结：通过不同的方式 增加品质的长度来延长玩家的装备更换频率。”这个美好的幻想是不可能实现的

以前我也有类似的想法，这篇文章否定了这种可能性

我说的 品质和数量是独立同分布，指的不是“品质”“数量”这两个随机变量间的关系，而是指不同时候杀掉boss,比如时刻t1,时刻t2,对应的掉落物品的品质q1,q2；我说的独立同分布指的就是q1与q2是独立同分布，数量的含义类似于品质.

你误解了我的假定

terrydc1983

现在大家知道 为什么应用科学很难拿到诺贝尔奖了吧= =!