How to evaluate "quality" of set of attainable random permutations

Question

To randomly permute a list one has to select one of $n!$ possibilities, which quickly goes outside of the capabilities of conventional PRNGs. Even Mersenne Twister fails with a list of length greater than 2080 entries, and probably fails much sooner in practice because there's no guarantee that its state is used in a way that eliminates duplicate outcomes.

So, in the process of designing an algorithm to shuffle a list from inadequate state, and designing this as a library function (rather than as an application-specific solution), what would normally be the design criteria that should be met (or maximised or minimised) first, and what compromises are likely to be the most benign?

This is in the general case. Obviously some applications are oblivious to problems that others could turn into a catastrophic failure.

In other words, how do you evaluate the quality of a shuffle when you know in advance it must be imperfect (in the same way as you know a PRNG is imperfect)?

The reason I ask, and as an example of the sorts of things I'd like to detect, is that during development of a shuffle algorithm I got a couple of obviously-bad results but wasn't sure what the best way to formalise them as tests would be.

An acutely problematic shuffle, for example would be:

static uint32_t n;     // number of elements in list to shuffle
static uint32_t m;     // n rounded up to a power-of-two, minus one
static uint32_t state; // set to a random value to randomise order

void shuffle_seed(uint32_t seed) {
  state = s;
}

uint32_t next_index(void) {
  do {
    seed = (state * 1103515245 + 12345) & m;
  } while (state >= n);
  return state;
}

You can call this function n times and be guaranteed n unique results between 0 and n... so it's a permutation; but when you compare the result for one seed to that for another you find that they're the same sequence starting at different points. Also, every second index is odd and the others even.

Another, slightly more advanced design gave partial substring matches rather than the whole thing.

If you can choose only $n$ or $n^k$ (for smallish $k$) different permutations out of $n!$, ones containing similar sub-strings are probably the ones you'd want to eliminate first. I expect there are a variety of other kinds of poor choice that I haven't thought of.

Answer 1

You can do some spot checking. Testing for all $n!$ possibilities is impractical, but you can make some unit tests to make sure that after doing sufficiently many shuffles certain properties of the distribution are correct. For example, make the array $[1,2,\ldots,n]$ and check (for $x=2,5,7,12$)

• Is the mean value for the index of $x$ after shuffling approximately $n/2$?
• Is the variance of the index of $x$ after shuffling close to its theoretical moment?
• Is the average distance between $x_i$ and $x_j$ close the theoretical mean distance ($i$ and $j$ in the test set)
• Is $x_i>x_j$ (indices after shuffling) nearly half the time?

And you can keep going until you feel comfortable that it's achieving at least approximately the shuffle's theoretical statistics. (Is this what you were asking?)

Answer 2

To permute a list, there is no need to enumerate the n! possibilities. Shuffling the list should be sufficient. Pseudo code (from wiki article) for shuffling would be

for i from n−1 downto 1 do
    j ← random integer such that 0 ≤ j ≤ i
    exchange a[j] and a[i]

For c++11, std::shuffle along with a good RNG should work.

This wiki article was my source. The article does note the following in the "Pseudorandom generators" subsection

An additional problem occurs when the Fisher–Yates shuffle is used with a pseudorandom number generator or PRNG: as the sequence of numbers output by such a generator is entirely determined by its internal state at the start of a sequence, a shuffle driven by such a generator cannot possibly produce more distinct permutations than the generator has distinct possible states. Even when the number of possible states exceeds the number of permutations, the irregular nature of the mapping from sequences of numbers to permutations means that some permutations will occur more often than others. Thus, to minimize bias, the number of states of the PRNG should exceed the number of permutations by at least several orders of magnitude.

This problem can be avoided by using a true RNG that depends on processor noise such as std::random_device*.

* although I guess random_device also has caveats: http://www.pcg-random.org/posts/cpps-random_device.html