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

Start by saving the first several random numbers, the first 10 should be enough.  Call them F1 thru F10.
Also start a counter from zero.

Next, keep a running list of the 10 most recent random numbers.  Call them R1 thru R10.

Compare the first 10 to the most recent 10 numbers, eg
  if F1=R1
  and if F2=R2
  ....
  then condition met:   you have a loop of repeating random numbers.

The counter will be the number of calls it took to produce the repeating pattern.

Modification:  if you want this to run along with the algorithm you are using in your program, then you would need to account for how many times you call for a random number each pass through the program.  If you call it 3 times for example, then skip 3 and just keep every 4th random number at the beginning when setting up F1 thru F10

Posted by Larry on 2005-02-11 17:30:43