Thursday, October 6, 2011

Getting Past the Demons

The problems that were encountered with the random-number generator resulted from trying to simplify it for the last post. I had been using larger numbers at first and reduction past a certain point started introducing more regularity in the output of the generator. If one wants the generator to produce numbers varying from 0 to n-1, the choice for α and μ are related by the formulas below.


The "demons" disappear in this version of the generator. The mirror symmetry problem in the output seems to have moved elsewhere. The simpler version of the generator raises the question of what we mean by statistical independence? Are mirror images of sequences allowed? If we treat sequences of numbers as the ordered numbers found in a vectors then two sequences are related if they are multiples of each other or reflected versions of each other. The vector B = mA which results by multiplying the vector A by m is related to A. The vector (y,z,x) is a permutation of the elements of (x,y,z) and so also related. But we have to allow these sequences since they are valid outputs for the generator. The question is really one of the frequency with which these sets of numbers occur. One has to look at a set of output sequences and determine whether or not the set is statistically likely. In creating a set of sequences we can compare each new entry with the existing set and reject it if it is too closely related.

Correlation was used to compare sequences of numbers. It tells us how well two sets of numbers are aligned. If they are too closely aligned it raises doubts about their statistical independence.

A reference for this random-number generator is Hamming, R.W., Numerical Methods for Scientists and Engineers, pp. 137-42.

Supplemental: The random-number generator's mechanism appears to be closer to that of the urn problem than that of shuffling. Shuffling permutes the order of the cards in a deck. Picking a card at random is an urn problem.

No comments: