Generating random generators

Generating random generators

[Lauri Alanko]

To parallelize a probabilistic algorithm while retaining
reproducibility, it is often useful to have several independent
streams of pseudo-random numbers. In Haskell, there is a standard
operation Random.split, which takes a PRNG state and produces two
new PRNG states which should hopefully produce two seemingly
unrelated number streams.

OCaml's random library works in an imperative setting where each
generation operation implicitly updates the state of the
generator, so the corresponding operation would simply be
generating a new random generator:

val spawn : Random.State.t -> Random.State.t

Alas, such an operation is not provided by the library. The most
straightforward implementation would be the following:

let spawn s =
  Random.State.make (Array.init 55 (fun _ -> Random.State.bits s))

However, random numbers are tricky, and I'm suspicious of just
adding a new operation ad hoc when I don't understand how the
underlying PRNG works. Hence, I'd appreciate if anyone could
offer some insight on whether the above approach has any hidden
pitfalls (i.e. some sort of regularity that might appear when the
values from two generated streams are combined in a particular
fashion), or if there is a faster way of generating new
generators robustly. Random.State.make invokes Digest.string for
every int of the seed, so it seems like overkill.

Thanks in advance.


Lauri

Re: [Caml-list] Generating random generators

[Dario Teixeira]

Hi,

> However, random numbers are tricky, and I'm suspicious of just
> adding a new operation ad hoc when I don't understand how the
> underlying PRNG works. Hence, I'd appreciate if anyone could
> offer some insight on whether the above approach has any hidden
> pitfalls (i.e. some sort of regularity that might appear when the
> values from two generated streams are combined in a particular
> fashion), or if there is a faster way of generating new generators
> robustly. Random.State.make invokes Digest.string for every int of
> the seed, so it seems like overkill.

Have you considered using Cryptokit's Random module?  It offers
many generators, one of which meets your determinism criteria.

Cheers,
Dario Teixeira