# Finding independence seq. of Random numbers

Discussion in 'Java' started by Judy, May 22, 2008.

1. ### JudyGuest

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, May 22, 2008

2. ### JudyGuest

On May 22, 7:13 am, rossum <> wrote:
> On Wed, 21 May 2008 23:35:45 -0700 (PDT), Judy <>
> wrote:
>
>
>
> > 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.

>
> 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.

Judy

Judy, May 22, 2008

3. ### jolzGuest

> 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, May 23, 2008
4. ### jolzGuest

> 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).

jolz, May 23, 2008
5. ### John B. MatthewsGuest

In article <>,
rossum <> wrote:

> On Fri, 23 May 2008 18:41:29 +0200, jolz <>
> 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.
>
> 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

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
--
John B. Matthews
trashgod at gmail dot com
home dot woh dot rr dot com slash jbmatthews

John B. Matthews, May 24, 2008
6. ### Arne VajhøjGuest

John B. Matthews wrote:
> In article <>,
> rossum <> wrote:
>> On Fri, 23 May 2008 18:41:29 +0200, jolz <>
>> 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.

Arne

Arne Vajhøj, May 24, 2008
7. ### John B. MatthewsGuest

In article <48384e7d\$0\$90268\$>,
Arne Vajhøj <> wrote:

> John B. Matthews wrote:
> > In article <>,
> > rossum <> wrote:
> >> On Fri, 23 May 2008 18:41:29 +0200, jolz <>
> >> 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.

John
--
John B. Matthews
trashgod at gmail dot com
home dot woh dot rr dot com slash jbmatthews

John B. Matthews, May 24, 2008
8. ### Arne VajhøjGuest

John B. Matthews wrote:
> In article <48384e7d\$0\$90268\$>,
> Arne Vajhøj <> wrote:
>
>> John B. Matthews wrote:
>>> In article <>,
>>> rossum <> wrote:
>>>> On Fri, 23 May 2008 18:41:29 +0200, jolz <>
>>>> 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.

Arne

Arne Vajhøj, May 24, 2008
9. ### John B. MatthewsGuest

In article <483864e7\$0\$90266\$>,
Arne Vajhøj <> wrote:
> John B. Matthews wrote:
> > In article <48384e7d\$0\$90268\$>,
> > Arne Vajhøj <> wrote:
> >> John B. Matthews wrote:
> >>> In article <>,
> >>> rossum <> wrote:
> >>>> On Fri, 23 May 2008 18:41:29 +0200, jolz <>
> >>>> 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

John
--
John B. Matthews
trashgod at gmail dot com
home dot woh dot rr dot com slash jbmatthews

John B. Matthews, May 25, 2008
10. ### Arne VajhøjGuest

John B. Matthews wrote:
> In article <483864e7\$0\$90266\$>,
> Arne Vajhøj <> wrote:
>> John B. Matthews wrote:
>>> In article <48384e7d\$0\$90268\$>,
>>> Arne Vajhøj <> wrote:
>>>> John B. Matthews wrote:
>>>>> In article <>,
>>>>> rossum <> wrote:
>>>>>> On Fri, 23 May 2008 18:41:29 +0200, jolz <>
>>>>>> 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.

Arne

Arne Vajhøj, May 25, 2008
11. ### John B. MatthewsGuest

In article <4839de84\$0\$90265\$>,
Arne Vajhøj <> wrote:

> John B. Matthews wrote:
> > In article <483864e7\$0\$90266\$>,
> > Arne Vajhøj <> wrote:
> >> John B. Matthews wrote:
> >>> In article <48384e7d\$0\$90268\$>,
> >>> Arne Vajhøj <> wrote:
> >>>> John B. Matthews wrote:
> >>>>> In article <>,
> >>>>> rossum <> wrote:
> >>>>>> On Fri, 23 May 2008 18:41:29 +0200, jolz <>
> >>>>>> 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
--
John B. Matthews
trashgod at gmail dot com
home dot woh dot rr dot com slash jbmatthews

John B. Matthews, May 26, 2008