Finding independence seq. of Random numbers

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

  1. Judy

    Judy Guest

    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
    #1
    1. Advertising

  2. Judy

    Judy Guest

    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.

    Thanks for your response.

    Judy
     
    Judy, May 22, 2008
    #2
    1. Advertising

  3. Judy

    jolz Guest

    > 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
    #3
  4. Judy

    jolz Guest

    > 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
    #4
  5. 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
    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
    --
    John B. Matthews
    trashgod at gmail dot com
    home dot woh dot rr dot com slash jbmatthews
     
    John B. Matthews, May 24, 2008
    #5
  6. Judy

    Arne Vajhøj Guest

    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
    #6
  7. 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
    #7
  8. Judy

    Arne Vajhøj Guest

    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
    #8
  9. 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
    #9
  10. Judy

    Arne Vajhøj Guest

    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
    #10
  11. 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
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. globalrev
    Replies:
    4
    Views:
    797
    Gabriel Genellina
    Apr 20, 2008
  2. Neal Becker

    #elements of seq A in seq B

    Neal Becker, Aug 20, 2009, in forum: Python
    Replies:
    2
    Views:
    270
    Raymond Hettinger
    Aug 21, 2009
  3. Jan Kaliszewski

    Re: #elements of seq A in seq B

    Jan Kaliszewski, Aug 20, 2009, in forum: Python
    Replies:
    4
    Views:
    295
    Jan Kaliszewski
    Aug 21, 2009
  4. Alex Willmer
    Replies:
    14
    Views:
    333
    Steven D'Aprano
    Feb 29, 2012
  5. VK
    Replies:
    15
    Views:
    1,287
    Dr J R Stockton
    May 2, 2010
Loading...

Share This Page