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 fields include 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.
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 not repetition, and interpreting this sequence {x1, ..., xn} as the permutation
-
The above brute-force method will require occasional retries whenever the random number picked is a repeat of a number already selected. A simple algorithm to generate a permutation of n items uniformly at random without retries, known as the Knuth shuffle, is to start with the identity permutation, and then go through the positions 1 through n, and for each position i swap the element currently there with an arbitrarily chosen element from positions i through n, 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.
The probability distribution of the number of fixed points of 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. The first n moments of this distribution are exactly those of the Poisson distribution.
See Ewens's sampling formula for a connection with population genetics.
See also
External links
