Shuffle generation

[Rajeev Raman]

>In article <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric at snark.thyrsus.com>
>eric at snark.thyrsus.com (Eric S. Raymond) writes:
> In one of my programs, I have a requirement to generate random shuffles
> of arbitrary size.  I am using the obvious method, as follows:
>  [exchange a random pair of elements]

Persi Diaconis and Mehrdad Shahshahani (Z. Wahrscheinlichkeitstheorie
und verwandte Gebiete, 57:159-179, (1981)) show the following:

Let T_k(P) be the probability that permutation P is generated
		after k such random transpositions. 
Let D_k = \sum_{all permutations P} | T_k(P) - 1/n! |

Let k = cn + (n ln n)/2. Then

D_k <= b e^{-2c}, for some constant b.

A remark from their paper:

"The problem studied here arose from two independent sources. The first
source involved computer generation of a random permutation. [Knuth (1969)
pp 124--126 shows that the method mentioned on the net involving n-1 
transpositions produces exactly a uniform distribution.] One of us had
a programmer who used the measure [T_k] to generate random permutations.
It is not hard to see that for n > 2, [T_k] is never exactly uniform.
A discussion arose about how large k should be to make [T_k]
exactly uniform."

Another remark (which they also make) to achieve a close to uniform
distribution, the algorithm should do the following: pick i and j
at random, and transpose regardless of whether i=j or not. (Ie, count
as a transposition even the identity transposition.) Otherwise, for
even k you get only even permutations, &c. This also can be used
to prove that after k transpositions (even k) the probability that
you get an even permutation is 1/2 (+/-) some finite quantity, for
n > 2. Thus the distribution is never exactly uniform.

Rajeev.
-- 
Rajeev Raman 	
ARPA: raman at cs.rochester.edu  
UUCP: ...!rutgers!rochester!raman