Ilmari Karonen wrote:
> ["Followup-To:" header set to sci.math.]
> On 2010-07-30, Ron Shepard <ron-shep...@NOSPAM.comcast.net> wrote:
>> In article <i2tvn7$ld...@smaug.linux.pwf.cam.ac.uk>, n...@cam.ac.uk
>> wrote:
>>> Parallel random number generation is not easy, and 99% of the stuff
>>> published on it is somewhere between grossly misleading and complete
>>> nonsense.
>> I think in the parallel case, one would want to be able to generate
>> a seed to produce values that are guaranteed not to overlap with any
>> other node.  Maybe something like

>>    call RANDOM_NEW_SEED( old_seed, n, new_seed, my_node )

>> would be a sufficient interface.  new_seed(:) would depend on
>> my_node in such a way that the generated sequence would not overlap
>> with that produced by any other possible value of my_node (again,
>> assuming the cycle length is long enough to satisfy that request).

> Let me try to demonstrate, using a simplified (and admittedly somewhat
> artificial) counterexample, why lack of overlap is not a sufficient
> condition for independence:

> Assume we have a "random oracle" R: Z -> [0,1) which takes as its
> input an integer and returns a uniformly distributed random real
> number between 0 and 1, such that the same input always produces the
> same output, but that the outputs for different inputs are completely
> independent.

> Given such an oracle, we can construct a perfect PRNG P: Z -> [0,1)^N
> which takes as its input an integer k, and returns the sequence <R(k),
> R(k+1), R(k+2), ...>.  Obviously, the sequence generated by P would be
> indistinguishable from random (since it is indeed, by definition,
> random) and non-repeating.

> Now, what if we wanted several independent streams of random numbers?
> Obviously, we can't just pass different seed values to P, since we
> know that the streams would eventually overlap.  We could solve the
> problem by modifying P, e.g. to make it return the sequence
> <R(f(k,0)), R(f(k,1)), R(f(k,2)), ...> instead, where f is an
> injective function from Z^2 to Z.  But what if we wanted to do it
> _without_ modifying P?

> One _bad_ solution would be to define a new generator Q: Z -> [0,1)^N
> as Q(k)_i = frac(P(0)_i + ak), where a is some irrational number and
> frac: R -> [0,1) returns the part of a real number "after the decimal
> point" (i.e. frac(x) = x - floor(x)).

> Clearly, the sequences returned by Q for different seed values would
> never overlap, and, individually, they would each still be perfectly
> random.  Yet, just as clearly, all those sequences would be related by
> a very trivial linear relation that would be blatantly obvious if you,
> say, plotted two of them against each other.

> The _right_ solution, as I suggested above, would've been to redesign
> the underlying generator so that the different streams would be not
> just non-overlapping but actually statistically independent.  The same
> general advice holds for practical PRNGs too, not just for my
> idealized example.

> You can't just take any arbitrary PRNG, designed for generating a
> _single_ stream of random-seeming numbers, and expect the output to
> still look random if you get to compare several distinct output
> streams generated from related seeds.  It might turn out that it does
> look so, if the designer of the PRNG was careful or just lucky.  But
> designing a PRNG to satisfy such a requirement is a strictly harder
> problem than simply designing it to generate a single random-looking
> stream.