1. ## 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. 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. >> 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. Do you mean a PRNG that returns the same string of numbers with different seeds?

Yeah. It sucks. 5. Originally Posted by whiteflags 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. >> 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. Originally Posted by tabstop 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. >> 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. Originally Posted by Sebastiani >> 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. Originally Posted by tabstop 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.  11. Originally Posted by iMalc
Except that perfect_uniformity == !random.
What do you mean by "perfect uniformity"? 12. >> 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. 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. >> 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. Originally Posted by Sebastiani >> 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? Popular pages Recent additions 