Finding independence seq. of Random numbers

[Judy]

Hello all,

I'm trying to make multiple sequences of random numbers that are
independent.
For example, I would like to have 3 sequences of RNs each containing
100 RNs, and each sequences has to be independent.

Are there any good generators for this end? LCG's with guaranteed
seed will be the best option for me,
but if you have any idea or thought, please share with me.

Thanks.

 

[Judy]

How independent do you want them? You could take every third number
from a single LCG to make a sequence. You could use three copies of
the same LCG with three different seeds. You could use three
different LCGs. You could use alternative types of RNG: Mersenne
Twister or one of the cryptographic RNGs.

Do you need to be able to restart one or all of the sequences so you
can repeat a run exactly?

rossum

As much as independence could get within the doable range.
And Yes, I would need to be able to restart those sequences.

However, using three different seeds will generally be independent,
but it has the risk of making those
random numbers overlap.
I was wondering if simply using the different LCGs will guarantee the
independence.

Thanks for your response.

Judy

 

[jolz]

Random rand1 = new Random(seed);

Random rand2 = new Random(rand1.nextInt());
Random rand3 = new Random(rand1.nextInt());

This can result in all generators having the same seed.

 

[jolz]

How so? Assuming that Random is reasonably good, which the default

Random is, then the seed, the first int generated and the second int
generated are all different.

Assuming that Random is reasonably good, then there is no correlation
between consecutive samples. No correlation means no guarantee of
different values, so they may be all equal (however probability is low,
because there's much more different values).

 

[John B. Matthews]

How so? Assuming that Random is reasonably good, which the default
Random is, then the seed, the first int generated and the second int
generated are all different.

rossum

All implementations use a particular linear congruential pseudorandom
number generator, as required by the class's contract. Even though
nextInt() is optimized to select from the high-order bits, a repeat
could occur. Instead, use nextLong():

Random rand1 = new Random(seed);
Random rand2 = new Random(rand1.nextLong());
Random rand3 = new Random(rand1.nextLong());

Would this ever repeat for period > 2?

Of course, with a constant seed, the three sequences will each be the
same from run-to-run.

John

 

[Arne Vajhøj]

All implementations use a particular linear congruential pseudorandom
number generator, as required by the class's contract. Even though
nextInt() is optimized to select from the high-order bits, a repeat
could occur. Instead, use nextLong():

Random rand1 = new Random(seed);
Random rand2 = new Random(rand1.nextLong());
Random rand3 = new Random(rand1.nextLong());

Would this ever repeat for period > 2?

The docs state that:

The method nextLong is implemented by class Random as if by:

public long nextLong() {
return ((long)next(32) << 32) + next(32);
}

so it is not obvious that it could not happen.

You will need to either consult a good mathematician or
try for all values of seed whether it happens.

Arne

 

[John B. Matthews]

The docs state that:

The method nextLong is implemented by class Random as if by:

public long nextLong() {
return ((long)next(32) << 32) + next(32);
}

so it is not obvious that it could not happen.

You will need to either consult a good mathematician or
try for all values of seed whether it happens.

Ah, I see your point. So the probability is very low (1 in 2^32), but
not zero. Then the question is why one might need three uncorrelated
sequences.

John

 

[Arne Vajhøj]

Ah, I see your point. So the probability is very low (1 in 2^32), but
not zero. Then the question is why one might need three uncorrelated
sequences.

The probability is either very low or zero. The algorithm of
java.util.Random isgiven. You will need to either consult
someone that really understand the math behind LCG or
simply try it with 2^64 (or 2^48 if you can reduce to that)
seed values to know for sure.

Arne

 

[John B. Matthews]

The probability is either very low or zero. The algorithm of
java.util.Random isgiven. You will need to either consult
someone that really understand the math behind LCG or
simply try it with 2^64 (or 2^48 if you can reduce to that)
seed values to know for sure.

I have to agree. The given lcg [x = a + bx (mod m); a = 11, b =
25214903917, m = 2^48] is known to have period 2^48. The difficulty here
is that it's also known to have problems when used to get parallel
streams of pseudorandom numbers, as the op proposed. My point would be
that parallel sequences are a bigger problem than the probability of
hitting the cycle length.

In fact, running two generators in parallel is the basis of Floyd's
cycle length algorithm. Knowing the period is 2^48, at 2Ghz... Looks
like trying it might take a while

John

 

[Arne Vajhøj]

The probability is either very low or zero. The algorithm of
java.util.Random isgiven. You will need to either consult
someone that really understand the math behind LCG or
simply try it with 2^64 (or 2^48 if you can reduce to that)
seed values to know for sure.

I have to agree. The given lcg [x = a + bx (mod m); a = 11, b =
25214903917, m = 2^48] is known to have period 2^48. The difficulty here
is that it's also known to have problems when used to get parallel
streams of pseudorandom numbers, as the op proposed. My point would be
that parallel sequences are a bigger problem than the probability of
hitting the cycle length.

In fact, running two generators in parallel is the basis of Floyd's
cycle length algorithm. Knowing the period is 2^48, at 2Ghz... Looks
like trying it might take a while

My 3 year old PC can do 2.5 million tests per second.

That gives 3.5 year for 2^48 tests.

But if one has access to a bunch of PC's then it would
not be that hard to check.

Arne

 

[John B. Matthews]

John B. Matthews wrote:
Random rand1 = new Random(seed);
Random rand2 = new Random(rand1.nextInt());
Random rand3 = new Random(rand1.nextInt());
This can result in all generators having the same seed.
How so? Assuming that Random is reasonably good, which the default
Random is, then the seed, the first int generated and the second int
generated are all different.
All implementations use a particular linear congruential pseudorandom
number generator, as required by the class's contract. Even though
nextInt() is optimized to select from the high-order bits, a repeat
could occur. Instead, use nextLong():

Random rand1 = new Random(seed);
Random rand2 = new Random(rand1.nextLong());
Random rand3 = new Random(rand1.nextLong());

Would this ever repeat for period > 2?
The docs state that:

The method nextLong is implemented by class Random as if by:

public long nextLong() {
return ((long)next(32) << 32) + next(32);
}

so it is not obvious that it could not happen.

You will need to either consult a good mathematician or
try for all values of seed whether it happens.
Ah, I see your point. So the probability is very low (1 in 2^32), but
not zero. Then the question is why one might need three uncorrelated
sequences.
The probability is either very low or zero. The algorithm of
java.util.Random isgiven. You will need to either consult
someone that really understand the math behind LCG or
simply try it with 2^64 (or 2^48 if you can reduce to that)
seed values to know for sure.

I have to agree. The given lcg [x = a + bx (mod m); a = 11, b =
25214903917, m = 2^48] is known to have period 2^48. The difficulty here
is that it's also known to have problems when used to get parallel
streams of pseudorandom numbers, as the op proposed. My point would be
that parallel sequences are a bigger problem than the probability of
hitting the cycle length.

In fact, running two generators in parallel is the basis of Floyd's
cycle length algorithm. Knowing the period is 2^48, at 2Ghz... Looks
like trying it might take a while

My 3 year old PC can do 2.5 million tests per second.

That gives 3.5 year for 2^48 tests.

But if one has access to a bunch of PC's then it would
not be that hard to check.

No, but the result already known!

John