Doubts about detecting the periodicity of psuedo random functions

This is a discussion on Doubts about detecting the periodicity of psuedo random functions within the C++ Programming forums, part of the General Programming Boards category; I'm trying to measure the periodicity of a random generator, but I've run into a theoretical problem. Basically, I was ...

  1. #1
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,655

    Doubts about detecting the periodicity of psuedo random functions

    I'm trying to measure the periodicity of a random generator, but I've run into a theoretical problem. Basically, I was going on the assumption that if a generator repeated a sequence then the period was certain. And so far, this has been the case. But now that I think of it, a sufficiently complex generator could possibly repeat itself but not actually be stuck in a periodic cycle, couldn't it? If so, the only way I can think to handle it is to increase the number of passes and return some sort of probablistic "certificate" of periodicity. Am I way off base here?

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Many fancy random number generators have more "state" to them than just one number like rand() does, and I would expect you would need for the entire state to be duplicated before you get periodic behavior.

  3. #3
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,655
    >> Many fancy random number generators have more "state" to them than just one number like rand() does, and I would expect you would need for the entire state to be duplicated before you get periodic behavior.

    Yes, of course. My brain is fried right now so it just didn't seem so obvious. Thanks for setting that straight.

    Well, if nothing else I can use the function for testing purposes to let me know if a function is *not* periodic within a certain range of iterations. But then again, let's say we have a function that returns the same period 5 times in a row. Although we don't really know if it is in fact the period of the function, we could in fact make a subjective judgement about the the relative "quality" of the function, right?

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,627
    Do you mean a PRNG that returns the same string of numbers with different seeds?

    Yeah. It sucks.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by whiteflags View Post
    Do you mean a PRNG that returns the same string of numbers with different seeds?

    Yeah. It sucks.
    I'm pretty sure he means that the first number is seen again as (say) #1001, and then again at #2001, and then again at #3001, and then again at #4001, and then again at #5001, at which point the claim that the period of the prng = 1000 looks pretty good.

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,655
    >> I'm pretty sure he means that the first number is seen again as (say) #1001, and then again at #2001, and then again at #3001, and then again at #4001, and then again at #5001, at which point the claim that the period of the prng = 1000 looks pretty good.

    Right, well the entire sequence inclusive. So for example:

    (27)(68)(27)(36)(27)(31)(27)(24)(27)(17)

    Even though the value 27 occurs regularly this would not be considered a periodic sequence. But now let's say we have this:

    (22)(68)(13)(27)(21)(31)(12)(83)(36)(27)

    Still fine, but now we can see that after generating the last number in the sequence that it is also present in the 4th position. So to test for periodicity, we "walk" the length of the sequence up to and including the last one shown, invoking the generator at every step and testing it against the number in that position. If we reach the end we assume that the sequence is periodic and return the length of the period. Otherwise, we append all of the numbers that were generated during the comparison onto the original sequence and continue the process. To make it more clear, this is the actual function:

    Code:
    /*
        Returns either the period of the generator or zero if none 
        was found within the maximum number of iterations allowed
    */
    template < typename Type, typename Generator >
    size_t period_of_generator( Generator generator, size_t iterations )
    {
        vector< Type >
            buffer, 
            saved;
        for( ;; )
        {
            if( iterations-- == 0 )
                return 0;    
            Type
                value = generator( );
            typename vector< Type >::const_iterator
                begin = buffer.begin( ),
                end = buffer.end( ),
                found = find( begin, end, value );
            if( found == end )
                buffer.push_back( value );
            else
            {            
                saved.push_back( value );
                while( ++found != end )
                {
                    if( iterations-- == 0 )
                        return 0;
                    value = generator( );
                    saved.push_back( value );
                    if( value != *found )
                        break;
                }
                if( found == end )
                    return saved.size( );
                buffer.insert( buffer.end( ), saved.begin( ), saved.end( ) );
                saved.clear( );
            }
        }
        return 0;
    }
    Of course I can see now that this isn't really a true test of periodicity, and it would probably be more useful if it had an option to make several passes and return "a degree of certainty". But even as is, when used on really good random number generators at several million iterations it is a reliable test of the function's *lack* of periodicity, anyway - which is helpful.

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,294
    Quote Originally Posted by tabstop View Post
    Many fancy random number generators have more "state" to them than just one number like rand() does, and I would expect you would need for the entire state to be duplicated before you get periodic behavior.
    tabstop is onto it here.
    In fact you may only have to check for the internal state of the PRNG becoming equal to a copy of it's initial internal state. That's assuming there isn't any redundancy in its internal state.
    It's enough for an LCG and would be for Mersenne twister too anyway.
    Of course you'd need complete access to the internal state of the PRNG.

  8. #8
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,655
    >> In fact you may only have to check for the internal state of the PRNG becoming equal to a copy of it's initial internal state. That's assuming there isn't any redundancy in its internal state. It's enough for an LCG and would be for Mersenne twister too anyway. Of course you'd need complete access to the internal state of the PRNG.

    That makes perfect sense. Thanks. Well in that case, I could probably use a function similar to this as applied to the internal state, then?

    One more question. I've read a lot about uniform distribution functions but I can't seem to wrap my head around it algorithmically. I've always had trouble translating advance mathematical nomenclature into concrete ideas, for some reason. Anyone have any insight into that?

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Sebastiani View Post
    >> In fact you may only have to check for the internal state of the PRNG becoming equal to a copy of it's initial internal state. That's assuming there isn't any redundancy in its internal state. It's enough for an LCG and would be for Mersenne twister too anyway. Of course you'd need complete access to the internal state of the PRNG.

    That makes perfect sense. Thanks. Well in that case, I could probably use a function similar to this as applied to the internal state, then?

    One more question. I've read a lot about uniform distribution functions but I can't seem to wrap my head around it algorithmically. I've always had trouble translating advance mathematical nomenclature into concrete ideas, for some reason. Anyone have any insight into that?
    What exactly is the question? A uniform distribution (assuming a discrete range, which any prng has) just means that every outcome is equally likely. Any algorithm that generates (say) each output value exactly once during a period would be uniform.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,294
    Quote Originally Posted by tabstop View Post
    What exactly is the question? A uniform distribution (assuming a discrete range, which any prng has) just means that every outcome is equally likely. Any algorithm that generates (say) each output value exactly once during a period would be uniform.
    Except that perfect_uniformity == !random.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,423
    Quote Originally Posted by iMalc
    Except that perfect_uniformity == !random.
    What do you mean by "perfect uniformity"?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,655
    >> Except that perfect_uniformity == !random.

    True, but a test of uniform distribution *would* tell us if a random function generates a good range of values. At any rate, I'm not exactly sure how the algorithm would work!

    >> What exactly is the question? A uniform distribution (assuming a discrete range, which any prng has) just means that every outcome is equally likely. Any algorithm that generates (say) each output value exactly once during a period would be uniform.

    For example, lets say I want to test a function within the range of 16-bit unsigned numbers. So each value in the range has a probability of 1/65535. Do I need to set up an array of 65535 values an "fill" it with the function? Then what?

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    You mean if you want to test whether a prng is giving you a uniform distribution? I would divide my range into equal-sized bins and then use everybody's favorite, Pearson's chi-square test of expected vs. observed proportions. (For instance, you could split up your 65535 numbers into 15 groups of 4369 numbers each, count how many times you land in each bin for a histogram, and off you go.)

  14. #14
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,655
    >> You mean if you want to test whether a prng is giving you a uniform distribution? I would divide my range into equal-sized bins and then use everybody's favorite, Pearson's chi-square test of expected vs. observed proportions. (For instance, you could split up your 65535 numbers into 15 groups of 4369 numbers each, count how many times you land in each bin for a histogram, and off you go.)

    Hmm, so what is the purpose of grouping the numbers into bins? Moreover, what to do with the histogram to calculate a meaningful value? Would I multiply each bin result with the expected probability and then accumulate the sum?

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by Sebastiani View Post
    >> You mean if you want to test whether a prng is giving you a uniform distribution? I would divide my range into equal-sized bins and then use everybody's favorite, Pearson's chi-square test of expected vs. observed proportions. (For instance, you could split up your 65535 numbers into 15 groups of 4369 numbers each, count how many times you land in each bin for a histogram, and off you go.)

    Hmm, so what is the purpose of grouping the numbers into bins? Moreover, what to do with the histogram to calculate a meaningful value? Would I multiply each bin result with the expected probability and then accumulate the sum?
    So why follow the link when I can explain it here?

    The chi-square test compares the observed frequencies of some event happening with the expected frequencies of that event happening; you find the value of the chi-square statistic by adding up ((O-E)^2)/E for each event, where O is the observed count and E is the expected count. Then you look it up in the chi-square table that you find online (or in a statistics book if you have one), where the degrees of freedom is the number of events, minus one. My chi-square table goes to df=100, so that rather limits how many events you can do. (Also from a theoretical perspective, if we are trying to model a distribution that is actually continuous, the expected number of times we get any exact value is zero. Admittedly there are both discrete and continuous versions of the uniform distribution.) The chart will give us, for our degrees of freedom, some "critical values" for given significance; for instance, with df=14 the critical value at 5% is 23.685; this means there's only a 5% chance of getting a chi-square value of 23.685 or higher by "luck" if the distribution really matches what we think it is. This gives us a level of confidence in our results.

Page 1 of 4 1234 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. time Delays and Random functions
    By markphaser in forum C++ Programming
    Replies: 17
    Last Post: 02-20-2006, 06:10 PM
  2. random functions, is it possible?
    By sreetvert83 in forum C++ Programming
    Replies: 8
    Last Post: 09-02-2005, 11:50 AM
  3. How do I restart a random number sequence.
    By jeffski in forum C Programming
    Replies: 6
    Last Post: 05-29-2003, 02:40 PM
  4. Random function's application:Dice Roller
    By angeljicu in forum C Programming
    Replies: 0
    Last Post: 11-02-2002, 04:29 AM
  5. random functions
    By bluehead in forum C++ Programming
    Replies: 5
    Last Post: 11-09-2001, 03:04 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21