Makes sense. Do you have any particular implementations in mind that work this way?
I think this depends on the random number generator. For a counter-based RNG, the "internal state" is just a counter, so adding 1 or 2 would result in reusing random numbers in different streams.
The complexity is because it is not a cryptographic pseudorandom generator.
If you have something cryptographic, than any basic operation on the internal state (ie. Increment by one) is enough to totally change the output stream in a way and outsider cannot predict.
You have to think about how your operations interact with other operations you might also do on the random state. Like what if you add one to the state, but someone else subtracts one from the state back to where you started, ooops! Or what if you create a new rng2 by adding one to the state of rng1. Then later you create rng3 by adding one to the state of rng1. Now rng2==rng3. Oops!
That's why I like the orignal idea you described of adding 1 and 2 and advancing each rng. This ensures that both streams are irreversibly altered which should make it very hard to accidentally misuse.
This seems like an area where a mutable API beats an immutable API. It's very easy to accidentally reuse old states when doing functional programming. On the other hand, if you need a way to serialize the RNG, (to send it to another task, perhaps) then the risk of reusing states comes back again.
The counter-based RNG I was looking at is an immutable API. It makes it easy to initialize generators in separate tasks by feeding each one a unique ID, but figuring out how to do a split operation is harder. Conceptually, the way to go is to multiply the key by 2 and add either 0 or 1 for each branch, to give them unique IDs. (This is called a pedigree.) However, for unbalanced trees, you will run out of bits. Figuring out how to do deal with that seems tricky?
The LXM generator paper (non-crypto) looks like good reading:
They initialize the new child with the next random values of the parent. There is an extra parameter that they use to add more input bits, to reduce the probability of overlap.
Comments
Makes sense. Do you have any particular implementations in mind that work this way?
I think this depends on the random number generator. For a counter-based RNG, the "internal state" is just a counter, so adding 1 or 2 would result in reusing random numbers in different streams.
Julia's random number generator does this. See https://github.com/JuliaLang/julia/blob/94a0ee8637b66ab67445...
That split function looks a lot more complicated. Thanks for the reference, though!
The SplitMix algorithm looks pretty useful. In Java, this is the built-in SplittableRandom class, and there seems to be an npm for it:
https://www.npmjs.com/package/splitmix
The complexity is because it is not a cryptographic pseudorandom generator.
If you have something cryptographic, than any basic operation on the internal state (ie. Increment by one) is enough to totally change the output stream in a way and outsider cannot predict.
You have to think about how your operations interact with other operations you might also do on the random state. Like what if you add one to the state, but someone else subtracts one from the state back to where you started, ooops! Or what if you create a new rng2 by adding one to the state of rng1. Then later you create rng3 by adding one to the state of rng1. Now rng2==rng3. Oops!
That's why I like the orignal idea you described of adding 1 and 2 and advancing each rng. This ensures that both streams are irreversibly altered which should make it very hard to accidentally misuse.
This seems like an area where a mutable API beats an immutable API. It's very easy to accidentally reuse old states when doing functional programming. On the other hand, if you need a way to serialize the RNG, (to send it to another task, perhaps) then the risk of reusing states comes back again.
The counter-based RNG I was looking at is an immutable API. It makes it easy to initialize generators in separate tasks by feeding each one a unique ID, but figuring out how to do a split operation is harder. Conceptually, the way to go is to multiply the key by 2 and add either 0 or 1 for each branch, to give them unique IDs. (This is called a pedigree.) However, for unbalanced trees, you will run out of bits. Figuring out how to do deal with that seems tricky?
The LXM generator paper (non-crypto) looks like good reading:
https://dl.acm.org/doi/pdf/10.1145/3485525
They initialize the new child with the next random values of the parent. There is an extra parameter that they use to add more input bits, to reduce the probability of overlap.