Are some pseudo-random number generators unpredictable?

[bbbeard]

The topic here is pseudo-random number generators (PRNGs), i.e. the kind of algorithm you implement on a computer to do Monte Carlo calculations.

All the PRNGs I know require a "seed" to start a sequence. Given the same seed, the algorithm, which is of course deterministic, will produce the same sequence of numbers.

Some PRNGs have the property that if you know the current output, you can predict what the next output value will be if you know what the algorithm is. I think simple linear congruential generators are in this class.

My question is, are there PRNGs which are not like this? I'm pretty sure there are; I think the Luscher-Marsaglia-Zaman PRNG is, because it actually updates some number of registers N>>1 at each step and only outputs a 32-bit current value. But I think if you know a sufficiently long sequence of outputs, you can reconstruct the contents of the registers, even if you don't know the seed, and then you could predict the next output.

Are some PRNGs intrinsically unpredictable? That is, even given a long sequence of outputs, you cannot predict the next output unless you know the seed? I am imagining some hybrid of RSS encryption and a PRNG -- or maybe mostly just RSS, since it somehow generates random-ish outputs in the course of doing its work. Is there a name for this class of PRNG?

BBB

 

[Simon Bridge]

What is the difference between a pseudo-random number generator and an actual ideal random number generator?

You get intrinsic unpredictability where you don't know the algorithm - like if you take the lowest place-value number in a rapidly changing natural measurement like wind speed as part of your number generation.

The size of the output you need before you can work out the seed is a measure of the randomness of the generator (iirc).

 

[Stephen Tashi]

Are some PRNGs intrinsically unpredictable? That is, even given a long sequence of outputs, you cannot predict the next output unless you know the seed?

To define the prediction problem precisely, you have to say what we are "given" about the possible PRNG's to consider. If you have an output of size N and all you know is that it comes from a recursive function, then my intuition is that there are infinitely many recursive functions that can produce that output - after all, we aren't given anything to limit the depth of the recursion. As a trivial example, one could have a recursive function that required N seeds to start it.

 

[bbbeard]

To define the prediction problem precisely, you have to say what we are "given" about the possible PRNG's to consider. If you have an output of size N and all you know is that it comes from a recursive function, then my intuition is that there are infinitely many recursive functions that can produce that output - after all, we aren't given anything to limit the depth of the recursion. As a trivial example, one could have a recursive function that required N seeds to start it.

I'm not sure whether the LMZ PRNG is like this, but it would be easy to write a PRNG where the output at each step is a function of the values in N seeded registers, but is not itself stored internally. So one would not be able to "re-seed" the generator using N consecutive outputs.

In my own coding I have abused the LMZ generator by seeding it with a single 32-bit seed, which I used to seed the system call to fill the 24 registers. This means I only generated 2^32 different series of numbers, instead of a potentially much larger space, But for what I was doing that was sufficient.

My question is really just a curiosity about whether there is a difference between linear congruential generators (where the current output tells you all you need to know to predict the future outputs) and other PRNGs. As far as I know, all useful PRNGs have the property that if you know the seed(s), you can reproduce the entire sequence of outputs, and obviously there are PRNGs where knowing the current output let's you predict future outputs without knowing the seeds. But I'm wondering if there are PRNGs where knowing N consecutive outputs is still not enough to predict future outputs, for any N.

BBB

 

[bbbeard]

What is the difference between a pseudo-random number generator and an actual ideal random number generator?

A PRNG is an algorithm on a computer. A real random number generator uses some physical process believed to be random to generate numbers -- for example, the radiation-based products offered by http://www.aw-el.com/" . PRNGs can mimic the behavior of real RNGs but all have shortcomings of one sort or another.

 

[Simon Bridge]

Good - now can you put that answer in terms of intrinsic unpredictability.