测试中的随机性(2)

　　在后台，重载的 Random.Next 方法将使用 Knuth 伪随机数字生成方法。这也称作“相减法”。Knuth 在《The Art of Computer Programming》(计算机程序设计艺术)(Addison-Wesley, 1981) 第 2 卷的“Seminumerical Algorithms”(半数值算法)中发表了此算法。生成统一的伪随机数字相当有难度，但幸好 .NET Framework 会负责为您实现 Knuth 算法。

　　大约在首次开发 .NET Framework 时，Matsumoto 和 Nishimura 就发现了一种新的伪随机数字生成算法。他们的算法一般被称作 Mersenne Twister(马其赛特旋转)方法，并正因其通常所具有的卓越性能和数学特性而迅速取代原来的伪随机数字生成算法。请参阅“Mersenne Twister:A 623-Dimensionally Equidistributed Uniform Pseudo-Random Number Generator”，《ACM Transactions on Modeling and Computer Simulation》(美国计算机学会模型和计算机仿真汇刊)，第 8 卷，第 1 号，1998 年 1 月。

　　生成伪随机浮点数与生成伪随机整数类似。假定有以下代码：

　　对 Random.NextDouble 的调用将返回一个大于或等于 0.0 且绝对小于 1.0 的数字。要生成在值域 [下限值，上限值) 之内(其中，两个括号符号表示大于或等于“下限值”且绝对小于“上限值”)的浮点型数字，则可使用小型公式：

　　因为除 0.0 外，大多数浮点型数值都为近似值，所以从技术上说，您不能在包含端点值的值域 [下限值，上限值] 内生成浮点型数字，而必须将其改为不包含端点值的值域 [下限值，上限值)。该公式与接受完整值域的 Next 重载中所用的公式几乎相同，只不过转换为整数的结果不同。

　　分析模式随机性

　　有时候，您可能需要检查某个测试用例输入或输出模式，以证明它是随机生成的(例如，检验并确定某一赌博模拟事实上正输出随机结果)。有几个统计方法可用于实现此目的，但最简单的是 Wald-Wolfowitz 检验。该检验有时称为单样本游程检验(其中，“游程”为一连串相同数字或字符)。Wald-Wolfowitz 检验适用于由两个符号组成的序列，例如：

　　A B B A A A B B B A B B

　　其中的原理是，对于模式中指定数量的每个符号类型(共两个符号类型)，如果符号为随机生成(在本例中，意味着模式中每个位置出现 A 或 B 的几率各为 50%)，则您可计算该模式中的预期游程数。模式游程是一个由相同符号类型组成的序列。因此，在刚才所示的模式中，共有六个游程：A、BB、AAA、 BBB、A、BB。如果模式中的实际游程数过大或过小，则证明该模式不是随机生成。

　　尽管 Wald-Wolfowitz 检验仅适用于只包含两种符号类型的模式，但您通常可以将任意模式映射为 Wald-Wolfowitz 形式。例如，如果您有一个 {7, 9, 3, 4, 1, 6} 之类的整数序列，则可以算出其平均值为 (5.0)，然后将该序列映射到符号 H 和 L，其中 H 代表大于该平均值的数，而 L 代表小于该平均值的数：H H L L L H。如果您需要分析更复杂的模式，则可以使用 Chi-Square 检验或 Kolmogorov 检验之类的一些检验方法。

　　现在，让我们假设 n1 是某模式中第一种符号的数量，而 n2 是第二种符号的数量。则随机生成模式中的预期游程数 μ 为：

　　而方差 α2 由下式算出：

　　这两个公式均根据概率论得出。我们可以用平均值和方差来确定某个特定模式是随机过程结果的概率。假设我们以两个符号的模式开始，该模式表示为以下字符串：

　　尽管可以手动计算该模式中 X 和 O 的数量以及游程数，但让我的程序代劳会更轻松。首先，我将确定该模式字符串中的两个符号类型：

原文转自：http://www.uml.org.cn/Test/200611225.htm