A random permutation is a random ordering of a set of objects, that is, a permutation-valued random variable. The use of random permutations is often fundamental to fields that use randomized algorithms such as coding theory, cryptography, and simulation. A good example of a random permutation is the shuffling of a deck of cards: this is ideally a random permutation of the 52 cards.
Generating random permutations
Entry-by-entry brute force method
One method of generating a random permutation of a set of length n uniformly at random (i.e., each of the n! permutations is equally likely to appear) is to generate a sequence by taking a random number between 1 and n sequentially, ensuring that there is no repetition, and interpreting this sequence (x1, ..., xn) as the permutation
\( {\begin{pmatrix}1&2&3&\cdots &n\\x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\end{pmatrix}}, \)
shown here in two-line notation.
This brute-force method will require occasional retries whenever the random number picked is a repeat of a number already selected. This can be avoided if, on the ith step (when x1, ..., xi − 1 have already been chosen), one chooses a number j at random between 1 and n − i + 1 and sets xi equal to the jth largest of the unchosen numbers.
Fisher-Yates shuffles
A simple algorithm to generate a permutation of n items uniformly at random without retries, known as the Fisher–Yates shuffle, is to start with any permutation (for example, the identity permutation), and then go through the positions 0 through n − 2 (we use a convention where the first element has index 0, and the last element has index n − 1), and for each position i swap the element currently there with a randomly chosen element from positions i through n − 1 (the end), inclusive. It's easy to verify that any permutation of n elements will be produced by this algorithm with probability exactly 1/n!, thus yielding a uniform distribution over all such permutations.
unsigned uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m-1 with uniform distribution */
unsigned uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m-1 with uniform distribution */
void initialize_and_permute(unsigned permutation[], unsigned n)
{
unsigned i;
for (i = 0; i <= n-2; i++) {
unsigned j = i+uniform(n-i); /* A random integer such that i ≤ j < n */
swap(permutation[i], permutation[j]); /* Swap the randomly picked element with permutation[i] */
}
}
Note that if the uniform() function is implemented simply as random() % (m) then a bias in the results is introduced if the number of return values of random() is not a multiple of m, but this becomes insignificant if the number of return values of random() is orders of magnitude greater than m.
Statistics on random permutations
Fixed points
Main article: Rencontres numbers
The probability distribution of the number of fixed points in a uniformly distributed random permutation approaches a Poisson distribution with expected value 1 as n grows. In particular, it is an elegant application of the inclusion–exclusion principle to show that the probability that there are no fixed points approaches 1/e. When n is big enough, the probability distribution of fixed points is almost the Poisson distribution with expected value 1.[1] The first n moments of this distribution are exactly those of the Poisson distribution.
Randomness testing
As with all random processes, the quality of the resulting distribution of an implementation of a randomized algorithm such as the Knuth shuffle (i.e., how close it is to the desired uniform distribution) depends on the quality of the underlying source of randomness, such as a pseudorandom number generator. There are many possible randomness tests for random permutations, such as some of the Diehard tests. A typical example of such a test is to take some permutation statistic for which the distribution is known and test whether the distribution of this statistic on a set of randomly generated permutations closely approximates the true distribution.
See also
Ewens's sampling formula — a connection with population genetics
Faro shuffle
Golomb–Dickman constant
Random permutation statistics
Shuffling algorithms — random sort method, iterative exchange method
References
Durstenfeld, Richard (1964-07-01). "Algorithm 235: Random permutation". Communications of the ACM. 7 (7): 420. doi:10.1145/364520.364540.
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
