“组合余数随机生成”数学理论的表述如下：
定义1：设G为一个服务对象，N为一个大于1的整数，G在客户的请求下可以产生一个介于1到N的整数。则称G为N阶的数字生成器。如果生成的整数是随机的，则称其为随机的。如果随机生成的整数有确定的概率分布，则称其为概率确定的。如果其概率分布是均匀的，则称其为概率均匀的。
定义2：两个数字生成器如果其生成的数字之间没有任何数学关系，即不能通过某种确定的方法根据一个数字去确定另一个数字的特征。则称该两个数字生成器为数学不相关。
定义3：设G为一个N阶的(N>1)概率确定的数字生成器，其生成介于1到N的数字i 的概率为Pi 。定义G的概率均方差为：
D = Σ(i=1 to N) [ Pi – 1/N ] **2
它是概率分布偏离均匀分布及概率均匀度的一个度量。D越小，偏离均匀分布越小，均匀度越高。
组合余数生成之方法：设{Gi}( i =1, … , M, M>1)为一组N阶的(N>1)数字生成器，G为一个由该组生成器组合成的一个组合生成器。G生成的整数是该组所有生成器生成的整数之和除以N所得的余数加上1，则G也为一个N阶的数字生成器，称为M重的组合余数生成器，表示为 G = C(G1 , G2 , … , GM) 。
组合余数生成之交换律及结合律：设G1，G2及G3为三个N阶的(N>1) 数字生成器，则
C(G1, G2) = C(G2, G1)
C(C(G1, G2), G3) = C(G1, C(G2, G3))
组合余数随机生成之原理 : 设{Gi}( i =1, … , M, M>1) 为一组N阶的(N>1)数字生成器，G为其组合余数生成器。如果其中一个生成器Gk(k介于1到M) 与该组其他生成器均为数学不相关。则以下原理成立：
随机原理：如果Gk为随机的，则G也为随机的。
概率均匀原理：如果Gk为概率均匀的，则G也为概率均匀的。
概率均方差之极限原理：设G为一个N阶的(N>1)概率确定的数字生成器，D为其概率均方差，其极限为 :
0 ≤ D ≤ 1 – 1/N
如果概率分布是均匀的，则 D = 0 。如果生成某一个数字的概率为1而其余为 0，则 D = 1 – 1/N 。
组合余数随机生成之概率均方差之原理 : 设G1及G2为两个N阶的(N>1)数学互不相关的概率确定的数字生成器，G为其组合余数生成器，D1，D2和D分别为它们的概率均方差，则以下原理成立：
概率均方差之极限原理： D ≤ N*D1 *D2
近均匀生成器之组合均匀化原理 : 如果G1为一个近均匀生成器，即存在一个 d1 ≥ 0 使其所有概率均差 |Pi – 1/N| ≤ d1 /N, 则 D1 ≤ d1**2 /N, 因而 D ≤ d1**2 * D2 。如果 d1<< 1，则 D << D2 。
组合余数随机生成之概率均匀化原理 : 设{Gi}( i =1, … , M, M>1) 为一组N阶的(N>1)数学互不相关的概率确定的数字生成器，G为其组合余数生成器，D为G的概率均方差。设{G′i}( i =1, … , M′, M′>1)为{Gi}( i =1, … , M, M>1) 的一个子集，即{G′i} ∈ {Gi}，G′为其组合余数生成器，D′为G′的概率均方差， 则：
D ≤ D′
因而对于{Gi}中的任何一个生成器Gi及其概率均方差Di有：
D ≤ Di ( i =1, … , M)
数学证明： 从略。
注：本理论结合著名的“主控- 从属”(Master-Slave)及“组合”(Composite)软件设计模式在游戏软件中的应用被用作中国科学院研究生院计算与通信工程学院(原软件学院)软件工程硕士2006年春季《软件体系结构》课程的教学案例。此前，其中的“概率均匀化原理”原为一个未被普遍证明的数学猜想。该课程的部分学员对该数学理论表现出了极大的兴趣。其中陈更新同学所提供的思路使得这一猜想的普遍性在数学上得以证明。在此对参与讨论和交流的所有学员表示衷心的感谢。
计算验证：
利用电脑程序随机产生的概率分布，结合一些人为选择的特殊的概率分布，再利用电脑程序进行生成器组合及分析，可以对本理论的原理进行验证，并且直观了解组合生成器的特性 ( 如图所示) 。到目前为止验证的结果一直支持本理论而没有发现反例。
|
