In doing computer simulations, such as the one I wrote for simulating the results of part 2 of Rumor Mill, one often uses a random number generator that's built into the computer language. These generators are based on a seed (some arbitrary number) and are mixed up at each step that calls for a random number. There are only a finite number of seeds, and each one is based mechanically on the previous, so they necessarily repeat after a while.

The seed is kept internally, away from the programmer's view, so the programmer can't ask for, say, the next random number after .753372.

If one suspects that the repetition cycle is actually occuring within the length of the run that he needs, what algorithm can you put into the program to find the period with which your results are repeating (and are therefore no longer random, or rather no longer independent trials)? Assume you do not have room to store all the numbers as they arrive, nor can you afford the time it would take to compare each new number to all the preceding numbers.

Then also, how do you determine where the repetition cycle begins (after what iteration of the loop of trials).

Although there isn't room to store all the numbers, there should be room to store a picture, either on screen or an image file.  As the series of numbers is produced:  n1, n2, .....
consider graphing the point (n1,n2) then the point (n2,n3) etc.

Whether on screen or in an image file, there will obviously be some loss of information, since x and y coordinates with 6 significant figures are painted onto the nearest pixel; but each point will play a role in creating the picture.   Successive hits to a pixel bump it up to the next color.

This alone doesn't solve our problem, but it may be a start.

Maybe take a snapshot every 100,000 calls and compare visually to see how the picture is changing.  If it starts looping, the pattern of the hottest pixels might stay the same, like a fingerprint.

Maybe it's possible to have plotted points expire after N calls, then if you could tune N in real time, you could tune in a stable pattern that doesn't change at all.

Posted by Larry on 2005-02-12 16:12:12