[104838] in Cypherpunks
Re: Shuffling
daemon@ATHENA.MIT.EDU (Anonymous)
Thu Oct 29 14:36:50 1998
Date: Thu, 29 Oct 1998 19:22:52 +0100
From: Anonymous <nobody@replay.com>
To: coderpunks@toad.com
Reply-To: Anonymous <nobody@replay.com>
For any N greater than two, the random-swap algorithm cannot produce
a perfectly smooth randomization of A[N].
A perfect randomization of A[N] would give equal probability to each of
the N! (N factorial) possible rearrangements of A. Note that for all N,
N! is a multiple of N-1.
Each iteration of the random-swap algorithm makes two choices of the N
values to swap. There are N^2 possible ways these two choices could go.
To calculate the probabilities after an iteration, we try all the N^2
choices and count how many instances of each arrangement are produced.
This gives each possible arrangement a probability in the form of
k/N^2, where k of the N^2 choices led to that arrangement.
After multiple iterations, we can calculate a similar probability, but the
denominator will be a power of N^2. After two iterations it is N^4, after
three iterations it is N^6, and after m iterations it is N^(2m).
If the result is to be perfectly random, each of the N factorial
arrangements must have equal probability. Suppose this happens after
m iterations. Let the probability of each arrangement be k/N^(2m).
These are all equal and there are N! arrangements, and they all add up
to 1 (since they are probabilities). Therefore (N! * k) / N^(2m) = 1,
and so N! * k = N^(2m). We see that The denominator of the fraction
must be a multiple of N factorial.
But for no N greater than two is any power of N a multiple of N factorial.
All such N are relatively prime to N-1. Therefore taking N to any power
will never produce a number which is a multiple of N-1, and so it cannot
be a multiple of N factorial. QED.
No matter how many times the swap is iterated, the result will never have
a perfectly even distribution over all N! possible arrangements. The
correct algorithm for randomizing an array is very simple and has already
been posted.
