From: kramsay@aol.com (KRamsay)
Newsgroups: sci.math
Subject: Re: Shuffling a deck of cards
Date: 13 Aug 1998 06:54:13 GMT

In article <6qqvmt$m9g$1@math.usc.edu>, bruck@math.usc.edu (Ronald Bruck)
writes:
|Look up the papers by Persi Diaconis.  A suitable measure is given, and he
|solved the problem of how many shuffles it takes.  

For a given method of shuffling, starting from a sorted deck say, we 
have a probability distribution over the 52! possible permutations. 
One good measure of randomness he described was the maximum over all 
subsets A of those 52! permutations of the difference between the 
probability of landing in A if a perfect shuffle is made (i.e., 
(# of elements of A)/52!) and the probability of the imperfect 
shuffling method is used. The maximum difference occurs of course for 
A taken to be the set of all permutations which come up too frequently 
if we use our method of shuffling. Likewise if we take A to be the 
complement, the set of permutations which occur too infrequently. Thus
the measure is the same as 1/2 of the sum over all permutations of the 
absolute value of the difference between the actual probability of
getting it, and what it should be, 1/52!. This sum of absolute values
of differences is what somebody else called the L^1 norm.

|Seven?  I don't recall exactly.

Seven. It's reasonably sharp too. There appears to be good enough
reason not to worry about the deviation of a real-world shuffle from
Diaconis' model of a shuffle. (Unless of course one is dealing with
someone who is able to do a "perfect riffle-shuffle", alternating 
cards from two equal-sized halves, which returns the deck to a 
shuffled state after some small number of iterations.)

One feature of a permutation which is sensitive to the defects of 
shuffling only 5 or 6 times is the too frequent presence of relatively
long "rising sequences". Find each successive card (in the original 
sorted order), and see how long the strings of consecutive cards are, 
in which the cards appear in the same order in the deck. For example, 
if we had a deck of just 8 cards, and they were shuffled to

  1 5 2 7 6 3 8 4

the rising sequences would be 1234, 56, and 78. Shuffling just once
leaves you with two very long rising sequences. Successive shuffles
roughly halve the lengths of rising sequences for awhile, but not
perfectly of course. It's possible to create them as you shuffle, but 
in a perfectly shuffled deck they tend to be short. It's not until 
you've shuffled 7 times that they are well enough "chopped up" in
general.

Diaconis has a magic trick based on this. Take a card out of a sorted
deck. Shuffle it too few times-- I seem to remember 5 is okay. Put it 
back. Give Diaconis the deck, and he can often tell you which card you
took out. It's because the missing card often breaks up a rising 
sequence when you put it back.

There was some card game-- poker, perhaps-- the tournaments of which
went noticably differently once computers were used to produce ideal
shuffles. The "unusual" hands appeared more commonly.

The representation theory of S_n is helpful for solving problems like
this. Each element of S_n is a permutation, and multiplication of
elements is successive application of the permutations. We consider
the group algebra of S_n, which is the set of formal linear 
combinations of elements; if g1,...,gk are permutations, we can 
write r1*g1+...+rk*gk where r1,...,rk are complex numbers. A blind
method of shuffling the deck (i.e., not looking at the cards!) is
associated with an element of this group algebra over S_n, where the 
coefficients are the probabilities of various permutations being 
applied. Applying successive such methods corresponds to multiplying 
the associated elements of the group algebra.

The powers of the "one shuffle" element z of the group algebra 
converge to the "perfectly shuffled" element P, and the problem is to
see how.

The group algebra decomposes into a product of matrix algebras, one
for each irreducible representation of the group.

Keith Ramsay     "Thou Shalt not hunt statistical significance with
kramsay@aol.com   a shotgun." --Michael Driscoll's 1st commandment