[Haskell-cafe] Splittable random numbers

[Lauri Alanko]

On Thu, Nov 04, 2010 at 05:38:12PM +0000, Simon Peyton-Jones wrote:
> There's lots of material on generators that generate a linear
> sequence of random numbers, but much less on how to generate a tree
> of random numbers, which is what Haskell's System.Random API
> requires.

I'd like to understand what the fundamental difficulty is. I thought
that e.g. cryptographic PRNGs have the requirement that the output of
the PRNG cannot be used to guess its internal state (and thus the
future output). Hence one would think that a sufficiently strong PRNG
can be used to generate the seed for a new PRNG, which then shouldn't
have any observable similarity to the old PRNG.

So a naive implementation of split would be:

split g = (mkGen seed, g')
  where (seed, g') = random g

(Where mkGen creates a new state from some sufficiently big seed
data.)

So what is the problem here? What kinds of observable
interdependencies between split streams would come up with the above
definition using common PRNGs? Are my assumptions about the security
of cryptographic PRNGs incorrect, or is the issue simply that they are
too expensive for "ordinary" random number generation?


Lauri