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