Permutation Test

This test is also designed by Knuth in [8]. It relies on a property of non-overlapping $d$-dimensional points $(U_{nd+1}, U_{nd+2}, \ldots, U_{nd+d})$ for all $n \ge 0$. For each such point, there are $d!$ different relative orderings of its elements (assuming no two elements are identical.) For example, if $d=3$, the 6 possible relative orderings are $U_{3n+1} < U_{3n+2} < U_{3n+3}$ or $U_{3n+1} < U_{3n+3} < U_{3n+2}$ or $U_{3n+2} < U_{3n+1} < U_{3n+3}$ or $U_{3n+2} < U_{3n+3} < U_{3n+1}$ or $U_{3n+3} < U_{3n+1} < U_{3n+2}$ or $U_{3n+3} < U_{3n+2} < U_{3n+1}$.

If the samples are independent and uniform, we would expect each relative ordering to occur with the same probability $\frac{1}{d!}$. Obviously this is a discrete uniform distribution, and we can apply $\chi ^2$ test (with degree of freedom=$d!$) on it.

The interesting part of this test is how to quickly recognize the relative ordering of a $d$-tuple. The trick is to use a base-$d$ digit system. For example, the relative ordering of $U_{3n+3} < U_{3n+1} < U_{3n+2}$ can be encoded as 201 in base 3. To find the encoding, we use a simple algorithm similar to selection sort: Each time we pick the largest among the unsorted elements, exchange it with the rightmost unsorted element, then record its old position in an array. After $d$ exchanges we will have the encoding of its relative ordering in the array.