Suppose that we shuffle a pack of cards by choosing uniformly at random two numbers from . If the numbers are the same, we do nothing; otherwise we swap the cards in the indicated positions. The corresponding probability distribution on the symmetric group is defined by and if is a transposition. If we perform the shuffle times, then the probability that the cards are permuted according to the permutation is . Here is the -th convolution of , as defined by and

for each .

The first part of Exercise 13 in Diaconis’ book outlines a proof that if and where then the total variation distance between and the uniform distribution is non-negligible. The proof depends on looking at the number of fixed points of a permutation. Since is the character of an irreducible representation of , it is possible to compute its expected value and variance under and using representation theory.

For a full solution to the exercise, see here. In outline, one shows that

and that

It follows that if where , then and as . One can then use Chebychev’s inequality to show that, when and are in this relationship, the number of fixed points of a permutation selected according to is likely to be rather large: of order . Under the uniform distribution the number of fixed points of a permutation is approximately distributed according to the Poisson distribution with parameter , so in particular, permutations with many fixed points are very rare. This gives a bound on the variation distance .

More precisely, if then

This shows that steps do not suffice to give a good shuffle. Therefore the immediately preceding result in the book, that steps are sufficient to make small, is sharp.

One interesting feature is that if the probability of choosing the identity is reduced from then it can take more steps to make small. The reason is that if after steps there is a good chance that the identity has never been chosen, then the parity of the shuffle must be even if is even, and odd if is odd. In these cases the bound on the variation distance given by parity is stronger than the bound coming from fixed points.

Advertisements

Like this:

LikeLoading...

Related

This entry was posted on Monday, March 28th, 2011 at 2:19 pm and is filed under Diaconis book. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.