随机模块如何在OCaml中进行测试？

Question

OCaml有一个Random module，我想知道它是如何测试自己的随机性。但是，我不知道他们到底在做什么。我知道它试图用另外两个依赖性测试来测试chi-square。下面是测试部分的代码：

卡方检验

(* Return the sum of the squares of v[i0,i1[ *) 
let rec sumsq v i0 i1 = 
    if i0 >= i1 then 0.0 
    else if i1 = i0 + 1 then Pervasives.float v.(i0) *. Pervasives.float v.(i0) 
    else sumsq v i0 ((i0+i1)/2) +. sumsq v ((i0+i1)/2) i1 
;; 

let chisquare g n r = 
    if n <= 10 * r then invalid_arg "chisquare"; 
    let f = Array.make r 0 in 
    for i = 1 to n do 
    let t = g r in 
    f.(t) <- f.(t) + 1 
    done; 
    let t = sumsq f 0 r 
    and r = Pervasives.float r 
    and n = Pervasives.float n in 
    let sr = 2.0 *. sqrt r in 
    (r -. sr, (r *. t /. n) -. n, r +. sr) 
;; 

Q1：，所以才写sum of squares这样呢？

它似乎只是总结所有方块。为什么不写，如：

let rec sumsq v i0 i1 = 
    if i0 >= i1 then 0.0 
    else Pervasives.float v.(i0) *. Pervasives.float v.(i0) + (sumsq v (i0+1) i1) 

Q2：，为什么他们似乎对卡方使用不同的方式？

从chi squared test维基，他们的公式是

但似乎他们使用不同的配方，有什么幕后？

---

其他两个依赖测试

(* This is to test for linear dependencies between successive random numbers. 
*) 
let st = ref 0;; 
let init_diff r = st := int r;; 
let diff r = 
    let x1 = !st 
    and x2 = int r 
    in 
    st := x2; 
    if x1 >= x2 then 
    x1 - x2 
    else 
    r + x1 - x2 
;; 

let st1 = ref 0 
and st2 = ref 0 
;; 

(* This is to test for quadratic dependencies between successive random 
    numbers. 
*) 
let init_diff2 r = st1 := int r; st2 := int r;; 
let diff2 r = 
    let x1 = !st1 
    and x2 = !st2 
    and x3 = int r 
    in 
    st1 := x2; 
    st2 := x3; 
    (x3 - x2 - x2 + x1 + 2*r) mod r 
;; 

Q3：我真的不知道这两个测试，可有人EN-轻我？

Answer 1

Q1：

它的内存使用量的问题。您会注意到对于大型阵列，您执行sumsq将失败，“评估期间堆栈溢出”（在我的笔记本电脑上，r = 200000时失败）。这是因为在将Pervasives.float v.(i0) *. Pervasives.float v.(i0)添加到(sumsq v (i0+1) i1)之前，您必须计算后者。所以直到你计算出sumsq最后一次调用的结果，你才能开始“上升”并添加所有内容。显然，sumsq在你的情况下将被称为r次，所以你将不得不跟踪r调用。

相比之下，他们的方法只需要跟踪log（r）调用，因为一旦summsq已经计算了一半数组，你只需要调用相应的结果（你可以忘记所有的你必须做的其他调用来计算）。

但是，还有其他方法可以实现这个结果，我不确定他们为什么选择这个（也许有人能够说出来？）。如果您想了解更多与递归和内存相关的问题，您应该检查the wikipedia article on tail-recursion。如果你想知道更多关于他们在这里使用的技术，你应该检查the wikipedia article on divide and conquer algorithms - 要小心，因为这里我们谈论的是内存，维基百科的文章可能会谈论很多关于时间复杂度（速度）的内容。

Q2：

你应该更仔细两个表达式。在这里，所有的E_i都等于n/r。如果在给出的表达式中替换它，您会发现它们使用的表达式相同：(r *. t /. n) -. n。虽然我没有检查边界的值，但由于你有一个卡方分布，参数r-减一个或两个自由度，r很大，看到他们使用这个并不奇怪一种置信区间。你提到的维基百科文章应该帮助你找出他们使用的置信区间的确切程度。

祝你好运！

编辑：糟糕，我忘了Q3。我也不知道这些测试，但我相信你应该能够通过搜索诸如“连续数字之间的线性依赖”或其他内容来找到更多关于它们的信息。 =）

编辑2：在答复有关的置信区间杰克逊故事的6月29日问题：

他们的确应该测试对卡方分布 - 或者说，用卡方分布找到置信区间。然而，由于中心极限定理，具有自由度的卡方分布收敛于平均值为k和方差2k的正态定律。一个经典的结果是，正态定律的95％置信区间约为[μ-1.96σ，μ+1.96σ]，其中μ是平均值，σ是标准偏差 - 因此大致为平均值±标准偏差的两倍。在这里，自由度的数量是（我认为）r-1〜r（因为r很大）所以我就说为什么我没有惊讶于表格的置信区间[r - 2 sqrt（r），r + 2 sqrt（r）]。然而，现在我想到了它，我不明白他们为什么不使用±2 sqrt（2 r）......但我可能错过了一些东西。无论如何，即使我是正确的，因为sqrt（2）> 1，他们得到更严格的置信区间，所以我想这不是一个真正的问题。但他们应该记录他们正在做的更多...我的意思是，他们使用的测试可能非常标准，所以大多数人阅读代码时都会知道他们在做什么，但仍然...

另外，你应该注意到，通常情况下，这种测试并不是确定性的：一般来说，你想表明某种东西有某种效果。所以你提出了两个假设：零假设，“没有效果”和另一种假设“有效果”。然后，你表明，根据你的数据，零假设的可能性非常低。所以你得出这样的结论：备选假设是（很有可能）是真实的 - 即是某种效应。这是决定性的。在这里，我们想要展示的是随机数发生器是好的。所以我们不想证明它产生的数字与某些法律不同，但它们符合。要做到这一点的唯一方法是执行尽可能多的测试，表明生成的数字与随机生成的数字具有相同的属性。但我们唯一可以得出的结论是“如果真的是随机产生的，我们无法找到实际数据与我们观察到的数据之间的差异”。但是，这并不是OCaml开发人员缺乏严密性：人们总是这样做（例如，很多测试需要比如说正常性，所以在执行这些测试之前，你会试着找到一个测试来证明你的变量是不正常分布。当你找不到任何东西时，你会说“哦，这个变量的正常性对我后续的测试来说可能足够了”） - 只是因为没有其他的方式来做它...

无论如何，我不是统计学家，上面的考虑只是我的两分钱，所以你应该小心。例如，我确信他们为什么使用这个特定的置信区间有更好的理由。我还认为，如果你仔细写下所有内容以确保他们确实做了什么，你应该能够弄清楚。