If the samples are independent and uniform, we would expect each relative
ordering to occur with the same probability . Obviously this
is a discrete uniform distribution, and we can apply
test (with
degree of freedom=
) on it.
The interesting part of this test is how to quickly recognize the relative
ordering of a -tuple. The trick is to use a base-
digit system. For example,
the relative ordering of
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
exchanges we will have the encoding of its
relative ordering in the array.