Xref: utzoo sci.math:17449 comp.lang.c:39322
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!elroy.jpl.nasa.gov!sdd.hp.com!wuarchive!udel!rochester!raman
From: raman@cs.rochester.edu (Rajeev Raman)
Newsgroups: sci.math,comp.lang.c
Subject: Re: Shuffle generation
Message-ID: <1991May16.155402.19637@cs.rochester.edu>
Date: 16 May 91 15:54:02 GMT
References: <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric@snark.thyrsus.com> <8c=sAju00Vp_Ihxl4r@andrew.cmu.edu> <1991May15.183447.1437@proto.com>
Organization: Computer Science Department University of Rochester
Lines: 42

>In article <1bQCYz#6lHOhh7Jxk2b4WjLh65vrXpL=eric@snark.thyrsus.com>
>eric@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@cs.rochester.edu  
UUCP: ...!rutgers!rochester!raman