Unsorting(randomizing) a sequence

[Charles G Waldman]

Dan Schmidt writes:
 > 
 > Skip's method is fine if choice is allowed to equal i.  With that
 > change, element exchange is no longer forced.  You can prove that
 > it's a perfect shuffle by induction: the last element in the shuffled
 > sequence has an equal chance of being any of the original elements,
 > and so on.
 > 

Correct.  However, I'm curious, what is the definition of a "perfect
shuffle"?  Just that each element of the permuted sequence has an
equal chance of being any of the original elements?  As I tried to
point out in my earlier posting, there are plenty of ways of choosing
permutations for which this condition holds, but still don't uniformly
sample the symmetric group (set of all permutations).  For instance,
if you cyclically permute a list by a random amount, the above
equidistribution property holds, but you wouldn't say the sequence is
well-randomized.  There must be stronger criteria.  I almost think you
have to look at the expectation values of all the characters
corresponding to all of the irreducible representations of Sym(N).  I
looked at this for the non-trivial 1-dimensional representation given
by 'sign', but even that is not enough - you could have degenerate
methods of sampling from Sym(N) which gave a mean of 0 on this
character but had some bias on one of the higher-dimensional
characters - such an example might be a little hard to construct,
though.

Another, more straightforward way to test sampling strategies is just
to keep track of how many times each permutation comes up.  However,
since N! gets so large, it takes too long to build up decent
statistics this way.