Lecture
A random permutation — is a random ordering of a set of objects, that is, a random variable whose elementary events are permutations. The use of random permutations is often the basis in fields that rely on randomized algorithms. Such fields include coding theory, cryptography and simulation. A good example of a random permutation is shuffling a deck of cards.
One of the methods for generating a random permutation of a set of n elements is to use the uniform distribution, for which random numbers between 1 and n are chosen successively, while ensuring that there are no repetitions. The resulting sequence (x1, …, xn) is interpreted as the permutation
The direct method of generation requires repeating the choice of a random number if the drawn number is already in the sequence. This can be avoided if, at the i-th step (when x1, …, xi − 1 have already been chosen), one chooses a random number j between 1 and n − i + 1 and then chooses xi to be the j-th unchosen number.
A simple algorithm for generating random permutations of n elements (with a uniform distribution) without repetitions, known as the Knuth shuffle, starts with an arbitrary permutation (for example, the identity — with no rearrangement of elements), and proceeds from position 1 to position n − 1, swapping the element at position i with a randomly chosen element at positions from i to n inclusive. It is easy to show that in this way we obtain all permutations of n elements with probability exactly 1/n!.
A simple algorithm for generating a permutation of n elements uniformly at random without repeated attempts, known as the Fisher–Yates shuffle, is to start with any permutation (for example, the identity permutation) and then go through positions from 0 to n − 2 (we use the convention where the first element has index 0 and the last element has index n − 1), and for each position i swap the current element with a randomly chosen element from positions i through n − 1 (the end) inclusive. Any permutation of n elements will be produced by this algorithm with probability exactly 1/n!, thus yielding a uniform distribution of permutations.
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] */
}
}
If the uniform() function is implemented simply as random() % (m), then a bias will arise in the distribution of permutations if the number of values returned by random() is not a multiple of m. However, this effect is small if the number of values returned by random() is orders of magnitude greater than m.
The probability distribution of the number of fixed points in uniformly distributed random permutations of n elements approaches the Poisson law as n grows. Counting the number of fixed points is a classic example of the use of the inclusion–exclusion formula, which shows that the probability of having no fixed points approaches 1/e. At the same time, the expected number of fixed points is equal to 1 for any size of permutation.
As in all other random processes, the quality of a permutation-generation algorithm, in particular the Knuth shuffle algorithm, depends on the underlying random number generator, such as a pseudorandom number generator. There are a large number of possible randomness tests, for example, the diehard tests. A typical example of such a test consists of choosing some statistic whose distribution is known, and checking whether the distribution of this statistic over the set of obtained permutations is indeed close enough to the true distribution.
Comments