[Caml-list] How does OCaml std test Random

[Caml-list] How does OCaml std test Random

[Dan Stark]

[-- Attachment #1: Type: text/plain, Size: 1366 bytes --]

Hi all

I am looking at the source of Random module

https://github.com/ocaml/ocaml/blob/master/stdlib/random.ml

I found that it is tested via chi-square test, here is the test code inside:


(* 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)
;;


I understand how the chi-square is calculated there.

What I don't understand is this comment:

(* Test functions.  Not included in the library.
   The [chisquare] function should be called with n > 10r.
   It returns a triple (low, actual, high).
   If low <= actual <= high, the [g] function passed the test,
   otherwise it failed.
*)


From my knowledge, if I get a chi-square value, I should check it against a
table with the degree of freedom and then decide whether the null
hypothesis fails or not.

Why (r -. sr, (r *. t /. n) -. n, r +. sr) can be used to check? What's the
theory behind?

thanks

Dan

[-- Attachment #2: Type: text/html, Size: 6472 bytes --]

Re: [Caml-list] How does OCaml std test Random

[Damien Doligez]

Hi,
> I am looking at the source of Random module 
> 
> https://github.com/ocaml/ocaml/blob/master/stdlib/random.ml
> 
> I found that it is tested via chi-square test, here is the test code inside:
[...]
> From my knowledge, if I get a chi-square value, I should check it against a table with the degree of freedom and then decide whether the null hypothesis fails or not.
> 
> Why (r -. sr,   (r *. t /. n) -. n,   r +. sr) can be used to check? What's the theory behind? 

You'll have to ask someone who knows about statistics and random numbers. IIRC, we implemented this chisquare test by copying from some book (possibly Sedgewick's "Algorithms") and the criterion was taken from the same source.

In fact, I'm almost sure the test results included in the comments were not updated with the latest changes to the code.

You should also pay attention to the comment about the Diehard tests at the beginning of the file: these tests are much more thorough than chisquare, and the current version passes them all.

-- Damien