A Random Question

[ttw]

One way to improve problems with pRNGs is to use very long cycle with a large state. The Fischer-Yates shuffle has the additional problem in that one needs to sample from various values of n. If shuffling a deck of cards, the first choice needs to sample from 51 items then from 50 items then from 49, 48,...3,2 items. There are four obvious choices.

First, one could use a big integer generator (Lehmer, shift-register, Fibonacci, etc.) which has a cycle length divisible by LCM(2*3*4*...50*51). This uses lots of big arithmetic.

Second, one could use 51 different RNGs with cycles divisible by a large multiple of the index of the generator. That is, the first is a multiple of a large power of 51, the second divisible by a large power of 50, and the last divisible by a large power of 2. The cycle length of each generator should be a multiple of a large different prime (perhaps 53,59,61,....) to keep each generator (sort of) independent of the others. This is probably the nicest in theory.

Third, one could use a very long cycle generator. The error from lack divisibility does decrease with cycle length. This is probably the most practical solution.

Fourth, one could use a simple RNG and not worry about the error. This I probably the most common solution.