1
$\begingroup$

Overview of the problem

Before this gets immediately flagged as duplicate, I'm not interested in testing the Fisher-Yates shuffle for randomness, since this can simply be done by testing the underlying RNG. I'm interested in testing the quality of any function that generates random permutations.

How can one test the quality of a random shuffle function, of which I don't know the underlying implementation?

My specific problem

To be a bit more specific to my conundrum, I'm currently trying to implement a 64 bit version of a permutation algorithm from this blog post.

TLDR: You can use a hash function, that is invertible for a given power-of-two sized domain, to generate random permutations, by rounding up the range to the next power-of-two and excluding and indexes generated that are smaller than the range.

A hacky solution

I came up with a hacky solution, but I'm not sure if there are better ones and how to calculate the bias introduced by this solution:

One thing that comes to mind when evaluating random permutations is what happens if we shuffle an array that contains consecutive integers and just use the first index as a randomly generated number, which can now be tested for randomness using test suites like PractRand.

This approach has an obvious problem though, since we are interested in the correlation of a single permutation and not between different permutations, since e.g. in the algorithms from above the initial index is always properly random.

Now the next idea would be to use the first k indexes as random numbers, but this also has a problem since once a number is generated it can't occur again.

This can be elevated to an extent, by storing the consecutive integers multiple times each in the array. So every integer in [0,n] is stored m times in the array and k shuffled integers are used for testing. With an increased m the bias in getting repeated integers would go down, and thus this is a theoretically useable solution.

This would require a huge amount of memory though, but fortunately the algorithm I'm interested in testing generates one random index at a time and thus this can be done quite efficiently, by using the mod n of the indexes generated.

Edit: To clarify what I'm talking about on a smaller scale: Say I had an array that contains m zeros and m ones (so n=1). I now shuffle the array and write the first k zeros and ones as bits to a testsuite like PractRand and then repeat this process. With a very large m (e.g. 2^50) and a smaller k (e.g. 2^8) the bias of repetitions should be so small that it's negligible.

I don't know though what values for k, n and m to choose and what the corresponding bias is.

Questions

  1. Are there other methods of testing a function than shuffles an array for randomness, without knowing the underlying implementation of the function?
  2. Is there anything wrong with my proposed method?
  3. How do I calculate the bias my method introduces for given values of k, n and m?
$\endgroup$
1
0
$\begingroup$

One thing that comes to mind when evaluating random permutations is what happens if we shuffle an array that contains consecutive integers and just use the first index as a randomly generated number, which can now be tested for randomness using test suites like PractRand.

No, you can't do that, but almost. A pseudo/truly random sequence has multiple same values, repetitions and +/- runs of digits. Your solely incremental sequence will easily fail the test even when perfectly permuted, probably even fail something as simple as ent.

You test the shuffle algorithm by inference.

  1. Generate a large file from something like /dev/urandom or the windows equivalent.

  2. Sort it into order, either rising or falling.

  3. Then permute that.

  4. Then test for randomness.

The test hypothesis is that since the original sequence was cryptographically random with the correct $\chi^2$ distribution, a proper shuffle will not make it worse. And it will space out the values into random positions. So the standard randomness tests should then pass it.

$\endgroup$
6
  • $\begingroup$ Yes a truly random sequence has multiple same values, this is why I said that I'd use the first index as a randomly generated number and deal in the second part with minimizing the bias when using multiple indexes. I think one of us misunderstood the other. Imagine I had an array [0, 1] and I were to shuffle it. You can't seriously tell me that if I write the first index of the array as the first bit to PractRand and then shuffle it again and write the first index to PractRand again and repeat this, that the generated sequence isn't as random as the underlying shuffle implementation. $\endgroup$ – camel-cdr Apr 5 at 11:09
  • $\begingroup$ The second par of your answer sound roughly like my solution, but what I'm asking is how I can calculate the bias that is still present. Say I were to test a 2GB file against PractRand, and it fails after 1.6GB, how would I know that the bias is introduced from the shuffle or from the fact that integers that have already occurred are less likely to occur again. Starting off with a random file might help, but it's not trivial for me to see why. $\endgroup$ – camel-cdr Apr 5 at 11:20
  • $\begingroup$ @camel-cdr Never used PractRand as it's not one of the mainstream randomness tests, but if it runs anything like the mainstream ones, they don't fail after some portion of the test file. The whole file is sucked in and then analysed with myriad tests. So there's no concept of bias. I can't imagine what a shuffle bias could actually look like in detail. There is though a $p$ value confidence that the file is random. But that's not really a bias metric. $\endgroup$ – Paul Uszak Apr 5 at 11:49
  • $\begingroup$ The reason to use a random file is that it has the correct distribution of digits for being random. You then break it by sorting, and try to fix it with your algorithm. And it's an easy method to implement. $\endgroup$ – Paul Uszak Apr 5 at 11:50
  • 1
    $\begingroup$ PractRand is rather new, but now commonly used in testing PRNGs. It tests power of two bytes at a time and usually runs on direct input from a PRNG (see this blog post). (Also from what I can tell PractRand is currently the most advance test suite). The bias I'm talking about is that you don't get repeated numbers, or with my solution you'd the probability of getting a repeated number is lower than getting one that hasn't been generated. I'll try the randomized file method though. $\endgroup$ – camel-cdr Apr 5 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.