# Random permutation

*34,199*pages on

this wiki

Assessment |
Biopsychology |
Comparative |
Cognitive |
Developmental |
Language |
Individual differences |
Personality |
Philosophy |
Social |

Methods |
Statistics |
Clinical |
Educational |
Industrial |
Professional items |
World psychology |

**Statistics:**
Scientific method ·
Research methods ·
Experimental design ·
Undergraduate statistics courses ·
Statistical tests ·
Game theory ·
Decision theory

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 {*x*_{1}, ..., *x*_{n}} 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.

For an account of the probability distribution of the number of fixed points of a uniformly distributed random permutation, see rencontres numbers. That distribution 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 Edit

## External links Edit

This page uses Creative Commons Licensed content from Wikipedia (view authors). |