31 bit pseudo-random number gen in C, C++ & dsPIC assembly code

Carlos Moreno wrote:
> Bevan Weiss wrote:
>> onyx49@juno.com wrote:
>>
>>> Are there measures of "randomness" or should I say "non-randomness"?
>>> Or do people just hold there noses and say
>>> "Ewww, this is a pseudo raandom number"?
>>>
>>> Dave
>>
>>
>> The autocorrelation in this case would be it...
>> If you perform the autocorrelation over a sufficient length of output 
>> from the PRNG then you would note that it has several spikes at the 
>> cyclic length of the PRNG (ie the length it starts to repeat at).  
>> This shows that it's not truly random. 
> 
> Is this the only defect that one usually finds in actual PRNGs??
> I'm surprised;  I would have expected that the non-top-quality
> PRNGs would exhibit some noticeable correlation between nearby
> samples...  Am I overestimating the complexity of the problem?
> 
> Carlos
> -- 

This will show in the autocorrelation as less initial fall off.  The 
autocorrelation applies over a large number of outputs, and so won't 
show any detail concerning whether two or more adjacent samples were the 
same.  However it will show if an excessive number are similar, as the 
floor from the autocorrelation will increase.
You've got to think in terms of actual noise here.  It's not totally 
uncommon to have the same measure of noise for two adjacent 
measurements.  This doesn't give you any more information about what the 
next measurement will be however
-- 
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line.  Sorry.

Bevan Weiss wrote:
> onyx49@juno.com wrote:
> > Are there measures of "randomness" or should I say "non-randomness"?
> > Or do people just hold there noses and say
> > "Ewww, this is a pseudo raandom number"?
> >
> > Dave
>
> The autocorrelation in this case would be it...

I think this raises a question:

Assume we wanted to test whether the sequence {3, 1, 4, 1, 5, 9, 2, 6,
....} is uniformly and independently distributed (on the digits
{0,1,...,9}). What are histograms (or any other statistical measures)
and correlation tests going to tell us about this sequence? And what
does this tell us about how well suited histograms and correlation
tests are for measuring "randomness"?

While we are at it, what exactly _is_ randomness? When trying to answer
that last question, remember that _every_ sequence of digits has equal
probability of having been emitted by a uniform iid source. If that is
the case, how can we ever test whether any given sequence is indeed a
realization of an iid uniform random process, or whether in fact it is
a comletely deterministic sequence (as are generated by PRNGs, or as
the one above)? And finally, even if we found a deterministic algorithm
for generating any particular sequence under test, could we be sure
that the sequence was in fact not a realization of a random process?
After all, it has equal probability of appearance as any other sequence
for which no deterministic generating algorithm exists (for example,
the decimal digit sequence of an uncomputable number).
-- 
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line.  Sorry.

I wrote:
...
> And finally, even if we found a deterministic algorithm
> for generating any particular sequence under test, could we be sure
> that the sequence was in fact not a realization of a random process?
> After all, it has equal probability of appearance as any other sequence
> for which no deterministic generating algorithm exists (for example,
> the decimal digit sequence of an uncomputable number).

Oddly, I wrote this post about a week ago, and only now has Google
Groups passed it on. Anycase, about that last statement: while it is
true that any sequence has equal probability under a iid uniform random
process, the probability of there existing a deterministic algorithm
which computes that sequence is, in fact, zero. This is because there
are only countably infinity many computable numbers (or equivalently,
computable digit sequences), but uncountably many uncomputable numbers.
So if a deterministic rule were found, we could be _almost_ sure that
the sequence was not random (we can't be completely sure, because the
computable sequences might have zero probability, but that set is
definitely not empty).

So to answer my own question, a "randomness" test can only return an
answer which is correct with probability one when it returns a
negative, ie. when a deterministic rule for computing a given sequence
is found. If no such rule is found, we can't really be sure.

Regards,
Andor

abariska@student.ethz.ch wrote:
> Assume we wanted to test whether the sequence {3, 1, 4, 1, 5, 9, 2, 6,
> ....} is uniformly and independently distributed (on the digits
> {0,1,...,9}). What are histograms (or any other statistical measures)
> and correlation tests going to tell us about this sequence? And what
> does this tell us about how well suited histograms and correlation
> tests are for measuring "randomness"?

Last I heard, the digits of pi are not individually distributed
significantly differently from uniform, according to the standard
statistical tests.

> While we are at it, what exactly _is_ randomness?

There are several reasonable definitions, the main two families
of which are (a) unpredictability and (b) compressibility.
Chaitin's web site has leads to approach (b).  Obviously the
digits of pi are not very "random" according to view (b).

> ... how can we ever test whether any given sequence is indeed a
> realization of an iid uniform random process, ...

That's not the right hypothesis to be testing.

Theories of randomness is discussed in many works, including
Knuth's AOCP (which should be in your technical library if not
on your desktop).

There is a net newsgroup sci.crypt.random-numbers where this
discussion would be more appropriate.
-- 
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line.  Sorry.

Douglas A. Gwyn wrote:
> abariska@student.ethz.ch wrote:
> > Assume we wanted to test whether the sequence {3, 1, 4, 1, 5, 9, 2, 6,
> > ....} is uniformly and independently distributed (on the digits
> > {0,1,...,9}). What are histograms (or any other statistical measures)
> > and correlation tests going to tell us about this sequence? And what
> > does this tell us about how well suited histograms and correlation
> > tests are for measuring "randomness"?
>
> Last I heard, the digits of pi are not individually distributed
> significantly differently from uniform, according to the standard
> statistical tests.

That's why I started with this example: it is a computable sequence
(ie. not random at all) which should pass the  "standard statistical
tests" for a iid uniform distributed random sequence (if you found a
test which disproves this, you have a counter-example to the normality
conjecture of pi).


> > While we are at it, what exactly _is_ randomness?
>
> There are several reasonable definitions, the main two families
> of which are (a) unpredictability and (b) compressibility.
> Chaitin's web site has leads to approach (b).  Obviously the
> digits of pi are not very "random" according to view (b).

And also in view (a)!

> > ... how can we ever test whether any given sequence is indeed a
> > realization of an iid uniform random process, ...
>
> That's not the right hypothesis to be testing.
>
> Theories of randomness is discussed in many works, including
> Knuth's AOCP (which should be in your technical library if not
> on your desktop).
>
> There is a net newsgroup sci.crypt.random-numbers where this
> discussion would be more appropriate.

I didn't have any cryptographic application in mind, rather a much more
basic setup: Assume you are given a sequence of digits (ie. you can
have any arbitrary but finite number of digits from that sequence). You
know that the sequence was produced by either

i) a uniform iid random digit generator

or

ii) a deterministic Turing machine.

The random sequence decision question: does there exist a Turing
machine that, given as input the finite segment of the sequence, can
correctly determine the source (i or ii) with a probability of 1-delta,
for any given delta > 0?

(Much like the probabilistic prime number tests, except now for random
and pseudo-random sequences.)

The concept of a Turing machine is more general than a statistical
test, as any statistical test can be computed by a Turing machine. So
I'm not asking if there exists a statistical procedure to answer the
decision question. Instead, I'm wondering if the answer to the random
sequence decision quesion is at all decidable.

I tried to answer part of that question in a follow up (to comp.dsp
only), about a week ago. If the Turing machine somehow came up with a
procdure to compute the given segment of the digit sequence, it could
generate new digits and compare the new digits with digits from the
sequence (remember, we are allowed as many digits from the sequence as
we wish). With each matching digit, the probabiliy that the sequence is
not computable with the found procedure goes down by an order of
magnitude until it falls below delta. At this point, we have shown that
the sequence was generated by a Turing machine with probability 1-delta
(because an iid uniform digit generator issues a non-computable digit
sequence with probability 1).

Unfortunately, for this to work, one would have to go through all
countably infinite many possible procedures to compute digit sequences.
While waiting for the TM to halt, one never knows if the TM was still
searching for a procedure, or if no such procedure existed. This
approach doesn't work.

Perhaps some other method exists to answer the decision question? Not
having Knuth's books, I don't know if this topic is discussed there -
it seems, Knuth would rather be interested in what is computable, and I
have the feeling that the random sequence decision question is
uncomputable.

Regards,
Andor
-- 
comp.lang.c.moderated - moderation address: clcm@plethora.net -- you must
have an appropriate newsgroups line in your header for your mail to be seen,
or the newsgroup name in square brackets in the subject line.  Sorry.

It seems that the long time for these posts to show up is due to the
moderating in "comp.lang.c.moderated", so I'm taking this cross-post
out.

abariska@student.ethz.ch wrote:
....
> The random sequence decision question: does there exist a Turing
> machine that, given as input the finite segment of the sequence, can
> correctly determine the source (i or ii) with a probability of 1-delta,
> for any given delta > 0?

The above should have read "given as input the (infinite) sequence,
..." because I don't want to limit the Turing machine in its access to
the sequence. Anycase, it seems that there is no such Turing machine.
Idea of proof:

Assume there was, then you could feed it the input of a iid random
digit generator. After the Turing machine has accessed a finite segment
of the sequence (as it must if it is to decide the question in a finite
number of steps), it reaches the conclusion that the sequence is from
the random digit generator. If not (this happens with probability
delta), I simply run the test again until it answers correctly. With
probability 1 I only have to repeat the procedure a finite number of
times.

While it accessed the sequence, I jotted down every digit from the
sequence that it read. So I have all finite digits which the Turing
machine required to decide the question. Next, I simply construct
another Turing machine that reads out the tabulated digits. Because the
deciding Turing machine is deterministic, when faced with the output of
the table-reading Turing machine, it will again reach the conclusion
that the sequnce was from the random digit generator (and it won't
require more than the tabulated digits for this decision ). So, if
there was a Turing machine that could determine the correct answer with
probabiliy 1-delta for any delta > 0, I could construct another Turing
machine that resulted in a probability of error = 1, which is a
contradiction. Therefore no such deciding Turing machine can exist.

Regards,
Andor