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?

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.

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

Do you mean a PRNG that returns the same string of numbers with different seeds?

Yeah. It sucks.

Quote:

---

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.

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

Quote:

---

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.

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

Quote:

---

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.

Quote:

---

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

Quote:

---

Originally Posted by iMalc

Except that perfect_uniformity == !random.

---

What do you mean by "perfect uniformity"?

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

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

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

Quote:

---

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?

---

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.

>> So why follow the link when I can explain it here?

Uh, because I didn't grok it, quite frankly! And besides, you've explained it much more clearly. Thanks. :)

Still, I'm going to focus on the uniform distribution calculation until I have that worked out first. But I will be sure to move on to the chi-squared test, eventually.

Ok, well i've come up with a function to test the uniform distribution *of sorts* (in the sense that I have no idea if it follows the standard convention or if the values even remotely correspond to the official function). I'm fairly happy with the output, but if anyone could point out how the conventional function would be designed I would appreciate it.

Code:

---

/*
        Returns a score on the interval (0, 1) where 0 == worst and 1 == perfect.
        Container is filled with the counts of each value where the values correspond
        to the logical index of that particular element. So for example data[ 11 ]
        contains a count of the value 11.
*/
template < typename Container >
double uniform_distribution( Container const& data )
{
        double
                result = 0,
                count = std::accumulate( data.begin( ), data.end( ) , double( 0 ) ),
                expected = count / data.size( );
        if( count == 0 )
                return std::numeric_limits< double >::quiet_NaN( );
        for
        (
                typename Container::const_iterator seq = data.begin( ), fin = data.end( );
                seq != fin;
                ++seq
        )
                result += fabs( *seq - expected );
        return 1.0 - ( result / count );
}

---

EDIT:
Ok, well the function is not actually implemented correctly. I'm working on a fix right now...

EDIT #2:
Fixed (thanks to Tabstop)!

EDIT #3:
Really fixed (thanks to Tabstop)!!

So, I have no idea what you're trying to make result do here, exactly; but the idea is you need to capture how far away your counts are from what you want them to be. You know how much you want them to be: that's what scale is. The important thing here is (value-scale) -- we want that to be 0, any deviation from that is bad (whether it be positive or negative) and the bigger it is the more heartburn it gives us. The canonical way to deal with that is to use sum-of-squares: it turns everything positive, so that no cancellation happens (we want all the errors to accumulate). So we would actually add up (value-scale)^2 to get our measure of how far away we are -- 0 is spot on, large is bad. To get some notion of scaling in, we could maybe divide at the end by scale and -- hey! that's Pearson's chi-square test!

Many thanks, Tabstop. I think it's working properly now. Now I'm going to give the chi-squared test a shot!

Cheers. :)

Quote:

---

Originally Posted by Sebastiani

Ok, well i've come up with a function to test the uniform distribution *of sorts* (in the sense that I have no idea if it follows the standard convention or if the values even remotely correspond to the official function). I'm fairly happy with the output, but if anyone could point out how the conventional function would be designed I would appreciate it.

Code:

---

/*
        Returns a score on the interval (0, 1) where 0 == worst and 1 == perfect.
        Container is filled with the counts of each value where the values correspond
        to the logical index of that particular element. So for example data[ 11 ]
        contains a count of the value 11.
*/
template < typename Container >
double uniform_distribution( Container const& data )
{
        double
                result = 0,
                size = double( data.size( ) ),
                count = std::accumulate( data.begin( ), data.end( ) , double( 0 ) ),
                expected = count / size;
        if( count == 0 )
                return std::numeric_limits< double >::quiet_NaN( );
        for
        (
                typename Container::const_iterator seq = data.begin( ), fin = data.end( );
                seq != fin;
                ++seq
        )
        {
                double
                        value = *seq;
                if( value )
                        result += value - expected;
        }
        return 1.0 - ( result / count );
}

---

EDIT:
Ok, well the function is not actually implemented correctly. I'm working on a fix right now...

EDIT #2:
Fixed (thanks to Tabstop)!

---

Do you find this always gives you one? I would think it would (unless there were some zeroes in the group), as adding (value-expected) is the same as adding (value) and then adding (expected) and subtracting -- and these should always give you the same. At the very least you'll want an absolute value on that I would think.

>> At the very least you'll want an absolute value on that I would think.

Doh! I was wondering why some generators were reporting results that were either better or worse than expected. Ok, so I've updated the function as necessary. Does it look correct?

Quote:

---

Originally Posted by laserlight

What do you mean by "perfect uniformity"?

---

I mean that if it wont ever generate an outcome that has been seen n times already while there are other outcomes that have been seen only n-1 times, then clearly each outcome is not equally likely on any given individual outcome produced.

You certainly can't call a generator biased if after generating n outcomes (where there are exactly n possible outcomes), that the outcomes are not all unique.
Another way of looking at it, Given enough possible outcomes, the chance that after a given outcome generation, all outcomes have been generated an equal number of times, is remote enough that it would probably mean the RNG is cheating, isn't really unbiased, or isn't truly random.
None of this is anything anyone here wouldn't already know, and lets not get into a discussion on true randomness.

Quote:

---

Originally Posted by iMalc

I mean that if it wont ever generate an outcome that has been seen n times already while there are other outcomes that have been seen only n-1 times, then clearly each outcome is not equally likely on any given individual outcome produced.

---

Just because the RNG does not produce exactly equal bucket counts doesn't mean it's not perfectly uniform. The estimate of the probability distribution based on frequencies of observed events is just that -- an estimate.

Honestly, I think you should look at the question in terms of mutual information between the bits of internal state of the RNG. The external state is not enough information to make a good decision on randomness. Unfortunately you may not have access to the internal state bits.

I wrote an experiment last night to measure this (mutual information between external state bits) for the rand() function of my platform (Ubuntu Linux), and found that the estimate of M.I. depends on the number of iterations performed. I did not collect enough data to see if the curve eventually levels off. However, after one billion observations, the estimate of mutual information between the first bit and the higher 15 bits (I limited the experiment to 16 bits of randomness) was somewhere around 2e-6.

For a perfect uniform random source, the MI should go to zero as the number of observations goes to infinity. 2e-6 isn't zero but it's pretty damn small (when compared to 1, the assumed entropy of each bit). Conclusion? My implementation of rand() is decent.

Quote:

---

Originally Posted by brewbuck

Just because the RNG does not produce exactly equal bucket counts doesn't mean it's not perfectly uniform. The estimate of the probability distribution based on frequencies of observed events is just that -- an estimate.

---

Exactly.

Well, it looks like there were flaws in both the uniform distribution function and the periodicity detector. But I think I've straightened them out. For the former, the problem was that I wasn't factoring in the maximum error in order to obtain a useful result. The corrected version:

Code:

---

template < typename Container >
double uniform_distribution( Container const& data )
{
        double
                one = 1,
                result = 0,
                size = data.size( ),
                count = std::accumulate( data.begin( ), data.end( ) , double( 0 ) ),
                expected = count / size,
                //maximum_error = ( size - one ) * ( expected + one ); // WRONG
                maximum_error = ( count - expected ) + ( expected * ( size - one ) );
        if( count == 0 )
                return std::numeric_limits< double >::quiet_NaN( );
        for
        (
                typename Container::const_iterator seq = data.begin( ), fin = data.end( );
                seq != fin;
                ++seq
        )
                result += fabs( *seq - expected );
        return one - ( result / maximum_error );
}

---

As for the latter, it was just plain broken. :p The updated version is much simpler and generic, and is much more rigorous in that it doesn't just check the pattern once but repeatedly until it reaches the end:

Code:

---

template < typename Iterator >
size_t period_of_sequence( Iterator begin, Iterator end )
{
    for( ; begin != end; ++begin )
    {
        Iterator
            found = begin;
        while( ( found = find( found + 1, end, *begin ) ) != end )
        {
            bool
                counting = true;
            size_t
                count = 1;
            Iterator
                next = begin,
                search = found;
            while( ++search != end )
            {
                if( *( ++next ) != *search )
                    break;
                if( next == found )
                    counting = false;
                if( counting )
                    ++count;
            }           
            if( search == end && !counting )
                return count;
        }
    }
    return 0;
}

template < typename Container >
inline size_t period_of_sequence( Container const& data )
{
    return period_of_sequence( data.begin( ), data.end( ) );
}

---

There are still a few cases where it could return a possible false positive. For instance if the pattern ends with two identical samples, it has no choice but to assume that the sequence repeats indefinitely. In that case, though, you could just expand the range and retest.

>> Just because the RNG does not produce exactly equal bucket counts doesn't mean it's not perfectly uniform.

Perfect uniformity *by definition* means a completely equal distribution of samples, doesn't it? Anyway, you wouldn't want it to be totally uniform but within a certain range. And at any rate, a test of uniformity has a limited relevance when considering the strengths and weakenesses of an RNG.

>> For a perfect uniform random source, the MI should go to zero as the number of observations goes to infinity. 2e-6 isn't zero but it's pretty damn small (when compared to 1, the assumed entropy of each bit). Conclusion? My implementation of rand() is decent.

Interesting. I haven't gotten quite that far yet, but it sounds like a useful test. I'm guessing that Ubuntu probably uses the Marsenne twister?

>> Another way of looking at it, Given enough possible outcomes, the chance that after a given outcome generation, all outcomes have been generated an equal number of times, is remote enough that it would probably mean the RNG is cheating, isn't really unbiased, or isn't truly random.

That's a good point. Would a good test for that be to sample the uniform distribution at certain intervals and calculate the relative entropy of the output?

Quote:

---

Originally Posted by Sebastiani

Perfect uniformity *by definition* means a completely equal distribution of samples, doesn't it?

---

Not really. For instance, if you had just a simple 50-50 (one bit) random number generator, that is truly random (say the theoretical perfect coin), and ran it 10 times, the probability of getting 5 1's and 5 0's is (approximately) 0.25. In fact anywhere from 3-7 of each would be considered "usual" (happen more often than 5% by chance).

>> Not really. For instance, if you had just a simple 50-50 (one bit) random number generator, that is truly random (say the theoretical perfect coin), and ran it 10 times, the probability of getting 5 1's and 5 0's is (approximately) 0.25. In fact anywhere from 3-7 of each would be considered "usual" (happen more often than 5% by chance).

Maybe we're talking about two different things here. Randomness aside, if you have an array of two counts, one for heads and the other for tails, and each element contains the value of 5, then the distribution is "perfect" (totally uniform), and any other configuration would not be. It has nothing to do with probability.

Quote:

---

Originally Posted by Sebastiani

Perfect uniformity *by definition* means a completely equal distribution of samples, doesn't it?

---

No. There is no reason why the observations should be precisely uniform even if the underlying process is uniform. Consider a perfectly balanced coin. You flip it once. It comes up heads. So based on this observation -- that the coin came up heads 1 time out of 1 -- you conclude that the coin will come up heads 100% of the time, which is obviously not a justifiable conclusion.

Or consider a RNG which distributes samples uniformly between 0 and 32767, and you generate an odd number of samples. Obviously, there must be at least one set of buckets whose counts are larger than any other bucket. Yet if you drew an even number of samples, you might have perfect buckets. So, does the uniformity of the distribution depend on how many observations you choose to make? No, clearly it's either uniform or not, regardless of your measurements.

Quote:

---

Originally Posted by Sebastiani

if you have an array of two counts, one for heads and the other for tails, and each element contains the value of 5, then the distribution is "perfect" (totally uniform), and any other configuration would not be. It has nothing to do with probability.

---

I think you need to be careful with the word "distribution." The distribution is a theoretical object which represents the actual probabilities of certain observations. But an array which tallies counts is only a measurement of this distribution, not the distribution itself. There are many ways to estimate the probability from a count of frequencies. The method of "take the number and divide by the total number of observations" is the maximum likelihood estimator which means among all consistent estimators it assigns the maximum probabilities to the observed events. But there are many other estimators you could use which are equally valid, depending on which assumptions you make on the underlying distribution. For instance, suppose you are estimating the likelihoods of particular words beginning a sentence. You might do this by scanning millions of sentences and incrementing a counter for each unique word you see. But this ignores the possibility that there are words which you have not seen, simply because your sample isn't big enough. Using the maximum likelihood estimator, you would assign these words a probability of zero, even though we know the true probability is not zero just because a given word didn't occur in the sample set.

>> The distribution is a theoretical object which represents the actual probabilities of certain observations. But an array which tallies counts is only a measurement of this distribution, not the distribution itself.

I was simply referring to the "frequency" distribution, then, I guess.

>> Consider a perfectly balanced coin. You flip it once. It comes up heads. So based on this observation -- that the coin came up heads 1 time out of 1 -- you conclude that the coin will come up heads 100% of the time, which is obviously not a justifiable conclusion.

If you're testing the uniformity of samples given a range of possibilities, I would think that you would have to supply some multiple of that range to obtain a useful indicator. Otherwise, the result would be practically meaningless. I mean, if you have an RNG that generates 16-bit numbers but only call it 5 times, you simply do not have enough information to make a judgement about the relative frequency distribution. Period.

>> For instance, suppose you are estimating the likelihoods of particular words beginning a sentence. You might do this by scanning millions of sentences and incrementing a counter for each unique word you see. But this ignores the possibility that there are words which you have not seen, simply because your sample isn't big enough. Using the maximum likelihood estimator, you would assign these words a probability of zero, even though we know the true probability is not zero just because a given word didn't occur in the sample set.

That's an interesting thought, but I honestly don't grok the import of the logic there. If you don't know what all of the possibilities are, then why factor them in at all? That's just seems illogical. Of course, probability never really made sense to me, *anyway*. It always seemed be a big much-to-do-about-nothing, personally. Perhaps if it had been given a more appropriate name, like "possibility theory", I would have given it more credence.

Quote:

---

Originally Posted by Sebastiani

>> The distribution is a theoretical object which represents the actual probabilities of certain observations. But an array which tallies counts is only a measurement of this distribution, not the distribution itself.

I was simply referring to the "frequency" distribution, then, I guess.

---

Well, okay, as long as you realize that's totally useless then we'll let you do so. A uniform prng means that every number is equally likely to show up on any given pull. Some methods (such as lcg, if I remember my theory correctly) do this by essentially shuffling all the numbers and giving them to you in that order, in which case then yes you will get exactly equal frequencies. Most other methods will not, I expect, but that doesn't mean they aren't uniform prngs. (I mean, head on over to random.org and get some random bits and look at them if nothing else.)

>> Well, okay, as long as you realize that's totally useless then we'll let you do so.

How so?

>> A uniform prng means that every number is equally likely to show up on any given pull.

OK, so then you are not simply referring to the actual distribution of values over a period of N samplings, but the relative "uniformity" of each sample within the given range "thus far". Is that correct?

>> Most other methods will not, I expect, but that doesn't mean they aren't uniform prngs.

I don't know, I guess my definition of uniformity is slightly different from the conventional meaning, but at any rate, from my observations most RNG produce a similar quality of uniformity, so to speak (in the context of the type of UD test I posted earlier). The Marsenne twister is interesting because it generally produces higher UD value and yet maintains a wide range, going from one value to another. I actually have a pretty promising candidate of my own that seems to perform comparable to the MT, but I still need to run a lot more tests to verify it's properties.

Quote:

---

Originally Posted by Sebastiani

>> Well, okay, as long as you realize that's totally useless then we'll let you do so.

How so?

---

Because prngs that guarantee that (say) every number is guaranteed to show up once in every n tries will yield uniform frequencies, but don't model a uniform distribution very well at all (a knowledge of the history gives you great information about the future, which it shouldn't).

Quote:

---

Originally Posted by Sebastiani

>> A uniform prng means that every number is equally likely to show up on any given pull.

OK, so then you are not simply referring to the actual distribution of values over a period of N samplings, but the relative "uniformity" of each sample within the given range "thus far". Is that correct?

---

Nope. Distributions have nothing to do with the past and everything to do with the future: the definition of a uniform PRNG is merely that every number in the range is equally likely to be the next number generated. We can test PRNGs by looking at the distributions they actually generate and seeing how likely it is that specific distribution could be generated by a properly-functioning PRNG; i.e., we can get a level of confidence in how well this is working; but since this test is working on the past history it can't actually tell us anything at all about how the PRNG will work in the future.

Note: If it is really a requirement that each number show up exactly the same number of times as every other number, then you're really looking for a shuffle and not RNG.

>> the definition of a uniform PRNG is merely that every number in the range is equally likely to be the next number generated. We can test PRNGs by looking at the distributions they actually generate and seeing how likely it is that specific distribution could be generated by a properly-functioning PRNG

Doh! But that's what *I'm* talking about! Look. If I run 65536 tests on a 16-bit RNG and obtain every possible value once then the distribution is perfectly uniform. We haven't considered the order that they were generated or anything else. Do we agree on that?

Quote:

---

Originally Posted by Sebastiani

>> the definition of a uniform PRNG is merely that every number in the range is equally likely to be the next number generated. We can test PRNGs by looking at the distributions they actually generate and seeing how likely it is that specific distribution could be generated by a properly-functioning PRNG

Doh! But that's what *I'm* talking about! Look. If I run 65536 tests on a 16-bit RNG and obtain every possible value once then the distribution is perfectly uniform. We haven't considered the order that they were generated or anything else. Do we agree on that?

---

No. I agree that the *observed frequency* is perfectly uniform. That adds credence to the claim that the original PRNG is uniform.

I guess what I'm doing is making clear the distinction between
"If the observed distribution is exactly equal, then the PRNG is very likely uniform"
and
"If the PRNG is uniform, then the observed distributions will be equal."
The first is true, the second is oh so very false, and (at least it seemed to me as I was reading) that you were starting to head down that second path.

If we had a "real" rng (ignoring what's practically possible with a computer -- something using white noise etc) that generated 16 bit random numbers uniformly, and we did your 65536 tests, the probability of getting each number exactly once is 4.1e-495 (yes, a decimal point, 494 zeros and then 41). And in fact, if we had such a "real" rng, then every possible distribution would be equally likely -- generating 65536 0's has the same probability. That is, after all, what uniform means -- each possibility is equally likely. The theoretical expected value for each frequency is one, to be sure, but with a standard deviation of 0.99999237, so there's some room for error here. What something like chi-squared is doing is measuring how far our observed distributions are from the theoretical expectations, and giving us a probability for being that far (or farther!) from the "true mean", assuming the distribution is correct.

>> No. I agree that the *observed frequency* is perfectly uniform. That adds credence to the claim that the original PRNG is uniform. I guess what I'm doing is making clear the distinction between "If the observed distribution is exactly equal, then the PRNG is very likely uniform" and "If the PRNG is uniform, then the observed distributions will be equal." The first is true, the second is oh so very false, and (at least it seemed to me as I was reading) that you were starting to head down that second path.

Well, naturally, the second statement would be very presumptuous and most likely incorrect. I think the confusion here is just a matter of terminology, where I have been using the statement "uniform distribution" in place of "observed frequency", which I realize now was clearly the wrong choice of words! So yes, basically, all I have been testing up to this point is the "overall" frequency distribution given a number of iterations, just to give me a ballpark idea how the algorithm performs. Even though we want an RNG to produce unpredictable values, we do want to make sure that it doesn't generate 65536 zeros, after all! Now of course this is just a minor test of an algorithm's "worthiness", but it can't be played down too much either.

Quote:

---

Originally Posted by Sebastiani

That's an interesting thought, but I honestly don't grok the import of the logic there. If you don't know what all of the possibilities are, then why factor them in at all? That's just seems illogical.

---

Because it's inherently wrong to assume that what you've seen so far is the only thing you'll ever see. Suppose I'm trying to estimate the zeroth order probability of a given sentence by multiplying the probabilities of the individual words. Suppose somebody gives me a sentence I haven't seen before, and it includes the word "gargantuan" which I have not seen before. According to my maximum likelihood estimate, the probability of this word is zero (I've never seen it) and so that zero propogates through the entire multiplication and I get a zero probability for the sentence. Yet the probability can't be zero, because somebody gave me the sentence.

So you need a way of estimating the probability that you will see a novel event, in a way that maintains consistency of the distribution. This means you HAVE to discount some of the frequency amounts. And there are multiple ways of doing this. For instance, the Laplace estimator, the Jeffreys-Perks estimator, Lidstone, Good-Turing discounting, etc...

>> According to my maximum likelihood estimate, the probability of this word is zero (I've never seen it) and so that zero propogates through the entire multiplication and I get a zero probability for the sentence. Yet the probability can't be zero, because somebody gave me the sentence.

The probability is unknown. You can't assign a value to that! Anyway, couldn't you just ignore the term if it was zero?

Quote:

---

Originally Posted by Sebastiani

>> According to my maximum likelihood estimate, the probability of this word is zero (I've never seen it) and so that zero propogates through the entire multiplication and I get a zero probability for the sentence. Yet the probability can't be zero, because somebody gave me the sentence.

The probability is unknown. You can't assign a value to that! Anyway, couldn't you just ignore the term if it was zero?

---

The probability is unknown, but you still need to estimate it. Ignoring the term is not correct either, because suppose you have two sentences which differ only by the addition of an unseen word. You would compute these two sentences as having equal probability, although you know that the sentence with the unseen word should have lower probability, precisely BECAUSE you have not seen that word before.

The real problem here is that if you are trying to construct an info-theoretic model of something, your model needs to do something reasonable when you are presented with new data. Consider a calculation of the KL-divergence between two joint probability distributions. There may be some joint events in one distribution that do not occur in the other, just by chance. But the KL divergence is defined in terms of RATIOS of probabilities, which means that you could end up dividing by zero, giving an estimate of the divergence as "INFINITE" when you know that the distributions are actually very similar, apart from some rare event which was seen in one but not the other.

Since the KL-divergence tells you the number of bits-per-symbol of redundancy between two perfect encodings, this means that you'd require an infinite number of bits to encode an unseen symbol. But that's WRONG, because you can always invent a coding scheme that requires fewer than an infinite number of bits to encode an unseen symbol.

Sorry for spewing. It's just too common that people measure frequency counts and say that this defined the actual distribution. This is merely one way of estimating the distribution, yet people give it high status over other methods, probably because it's simple.

>> The probability is unknown, but you still need to estimate it. Ignoring the term is not correct either, because suppose you have two sentences which differ only by the addition of an unseen word. You would compute these two sentences as having equal probability, although you know that the sentence with the unseen word should have lower probability, precisely BECAUSE you have not seen that word before.

Ah, true. Yeah, that definitely makes sense.

>> Sorry for spewing. It's just too common that people measure frequency counts and say that this defined the actual distribution. This is merely one way of estimating the distribution, yet people give it high status over other methods, probably because it's simple.

No worries, I really appreciate the clarification. I'll definitely look into these more advanced methods, eventually. They certainly appear to be powerful tools for analyzing this sort of thing.

To think of it another way, consider a perfect, uniform RNG which generates integers in the range [0, 2]. You draw three numbers from this range. The only possible combinations are:

Code:

---

0 0 0
0 0 1
0 0 2
0 1 0
0 1 1
0 1 2 *
0 2 0
0 2 1 *
0 2 2
1 0 0
1 0 1
1 0 2 *
1 1 0
1 1 1
1 1 2
1 2 0 *
1 2 1
1 2 2
2 0 0
2 0 1 *
2 0 2
2 1 0 *
2 1 1
2 1 2
2 2 0
2 2 1
2 2 2

---

I've marked the combinations which have uniform frequency counts -- there are 6 of them. According to these frequencies, given three draws of random numbers in the [0,2] range, only 6/27 combinations have a perfectly uniform distribution. This means that, given a combination of three values, it's more likely than not that the values drawn will be NON-uniform.

In other words, if I see a perfect set of counts, I actually have reason to believe that the RNG is not actually random, because this is actually less likely than drawing a set with unequal counts.

We're talking about pseudo-random number generators here, though, are we not? I think it's entirely reasonable to test a pseudo-random generator by generating its complete sequence and making sure that every possible number has been generated the same number of times. The fact that knowledge about the past gives you information about the future is inherent in the principle of a PRNG and is its distinguishing feature from real RNGs.
And if during its entire period, the PRNG does not emit every single number the same number of times, then it's not uniform, because if you have no knowledge of the PRNG's past, you can still use this statistic to predict that some numbers are more likely than others.

>> We're talking about pseudo-random number generators here, though, are we not? I think it's entirely reasonable to test a pseudo-random generator by generating its complete sequence and making sure that every possible number has been generated the same number of times. The fact that knowledge about the past gives you information about the future is inherent in the principle of a PRNG and is its distinguishing feature from real RNGs.

Well exactly. Uniformity is a good indicator of the spread of values that you can expect to obtain, and the higher value of uniformity, the better. Using the UD function I posted earlier I've been getting a score of roughly 0.80 (on a scale of 0.0 - 1.0) on most good RNG's (with the Marsenne twister scoring highest, generally), which is of course acceptable. The uniformity can also tell you something about the mathematical properties of the function, as some have a good spread overall but then exhibit peaks at regular intervals, which is not a very desirable property.

My next area of focus is in analyzing the relative randomness of the function (eg: amount of change from one value to the next). I thought about using some sort of classical entropy function, but another viable option would be to use Fourier and wavelet techniques, which is what I'm working on at the moment. Should be interesting!

Quote:

---

Originally Posted by CornedBee

We're talking about pseudo-random number generators here, though, are we not? I think it's entirely reasonable to test a pseudo-random generator by generating its complete sequence

---

I agree in theory, but most of the better RNGs have periods which are absurdly long, making it infeasible to test this way.

That is true.

>> I agree in theory, but most of the better RNGs have periods which are absurdly long, making it infeasible to test this way.

And of course, some may not be periodic at all!

Quote:

---

Originally Posted by Sebastiani

>> I agree in theory, but most of the better RNGs have periods which are absurdly long, making it infeasible to test this way.

And of course, some may not be periodic at all!

---

How would that work for a PRNG?

Quote:

---

Originally Posted by CornedBee

How would that work for a PRNG?

---

Perhaps not very random, and it might take an enormous amount of state, but it's probably possible to work something out where you have a "shuffle" of your range, and when you get to the end you reshuffle, and so on. You'd have to take care that your re-shuffles don't repeat, which means you do the same trick at a meta-level, and so on.

(For instance, a small example to see if what I'm saying even makes sense: let's say I have three numbers in my range; all the possible shuffles are 1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 1 2, 3 2 1. I can run them in that order (call that A1), then I can run them in a different order: maybe 1 2 3, then 2 1 3, then 3 1 2, then 1 3 2, then 2 3 1, then 3 2 1 (call that A2). I can rearrange those six shuffles in 6!=720 different ways, so now I have A1 through A720. That pattern of 720*18 numbers we'll call B1 -- I have 720! = a very large number of ways to reshuffle A1 through A720 into B1 through Bsomething large....)

But every time you change the random sequence based on a different random sequence, you're pretty much taking the cross product of two PRNGs, which will prolong the total sequence a lot, but it's still a finite sequence that eventually has to repeat.

Didn't say I was changing the random sequence based on another random sequence, or at least I don't think I did. Even if I did, the point (I think) is that I start by shuffling three things around, then six things (the six groups of three), then 720 things (the 720 groups of the six groups of three), then ....

You wouldn't necessarily have to shuffle anything. You would just need a set of transformations that could maintain an "out of sync" state indefinitely.

Quote:

---

Originally Posted by Sebastiani

>> I agree in theory, but most of the better RNGs have periods which are absurdly long, making it infeasible to test this way.

And of course, some may not be periodic at all!

---

All PRNGs are periodic. There are a finite amount of bits of memory, which means there are a finite number of states. So any PRNG will eventually either stop functioning (enter an invalid state), or come back to a state it has been in before, at which point it repeats itself.

Only on a machine with infinite memory can you have a PRNG which never repeats itself. I think people have invented several non-periodic PRNGs but they are not useful because they require infinite memory.

>> All PRNGs are periodic. There are a finite amount of bits of memory, which means there are a finite number of states. So any PRNG will eventually either stop functioning (enter an invalid state), or come back to a state it has been in before, at which point it repeats itself. Only on a machine with infinite memory can you have a PRNG which never repeats itself. I think people have invented several non-periodic PRNGs but they are not useful because they require infinite memory.

You're assuming that it all depends on memory, but in fact it is has more to do with symmetry than anything else. Most transformations, when coupled together, tend to generate repetitious and mutually reinforcing cycles. But if you could create a sufficently imbalanced system the sequence could concievably mutate without end. It's a very difficult problem, of course, which explains why memory is used to deal with this sort of thing, but I'm convinced that it is possible.

I could be wrong, though. :p

How do you intend to make or use a prng that doesn't have to store anything (no state)? I realize you're not really saying that, but that's really the only notion I have coming from what you've posted.

And sufficiently imbalanced might as well mean "totally random" because I don't think arithmetic works that way. I'm tired, but not that tired.

Quote:

---

Originally Posted by Sebastiani

You're assuming that it all depends on memory, but in fact it is has more to do with symmetry than anything else. Most transformations, when coupled together, tend to generate repetitious and mutually reinforcing cycles. But if you could create a sufficently imbalanced system the sequence could concievably mutate without end. It's a very difficult problem, of course, which explains why memory is used to deal with this sort of thing, but I'm convinced that it is possible.

---

How do you intend to create a state within the machine that is NOT represented by a configuration of bits? The state space is enormous, but FINITE.

I suppose you could design your PRNG to take advantage of memory errors caused by cosmic rays, but then, you could only ever switch to a state other than what the PRNG would have switched to, which is simply a "jump" in the cycle, not a move to another cycle entirely.

And if you're doing weird stuff like using cosmic rays, you probably ought to be a using a hardware RNG based on Johnson noise, or the nuclear breakdown of an unstable isotope, or something like that.