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

We don't have enough space to store all numbers, nor enough time to compare all numbers, but surely we have enough space and time to store a single number.

Perhaps we can store the first number, comparing all numbers afterwards.  After a certain number of iterations, we can replace the number.  The number of iterations we wait to store a new number starts with 1, then increases by 1 every time.  This will eventually work.  When we do find a repeat, we can see how many iterations occurred between the stored number and its repetition.  This will be the length of the repetition cycle.

However, this may take a long time.  Depending on the range of the random numbers, there's probably a way to optimize the number of iterations between storing new numbers.  Then, we could run several of these algorithms at once, each one replacing stored numbers at different intervals.  Sounds like a very difficult statistics problem...

Where does the repetition begin?  It doesn't seem possible with just this algorithm.  Maybe there is a way of running several of these algorithms at once that you would be able to know.

Posted by Tristan on 2005-02-12 17:48:58