Random permutation

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₁, ..., x_n} as the permutation

${\begin{pmatrix}1&2&3&\cdots &n\\x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\end{pmatrix}}.$

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

• perfect shuffle
• Knuth shuffle

External links

• Random permutation at MathWorld
• Random permutation generation