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. // About Bees This article is about completely random and illogical things. ... In mathematics, especially in abstract algebra and related areas, a permutation is a bijection from a finite set X onto itself. ... A random variable is a mathematical function that maps outcomes of random experiments to numbers. ... A randomized algorithm or probabilistic algorithm is an algorithm which is allowed to flip a truly random coin. ... Coding theory is a branch of mathematics and computer science dealing with the error-prone process of transmitting data across noisy channels, via clever means, so that a large number of errors that occur can be corrected. ... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and γράφειν gráfein to write) is the study of message secrecy. ... Wooden mechanical horse simulator during WWI. A simulation is an imitation of some real thing, state of affairs, or process. ... The term shuffle can also refer to the act of dragging ones feet on the ground while walking, running, or dancing. ... Some typical modern playing 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 no repetition, and interpreting this sequence {x₁, ..., x_n} as the permutation In probability theory and statistics, the discrete uniform distribution is a discrete probability distribution that can be characterized by saying that all values of a finite set of possible values are equally probable. ... In mathematics, especially in abstract algebra and related areas, a permutation is a bijection from a finite set X onto itself. ...

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. In mathematics, computing, linguistics and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ... The term shuffle can also refer to the act of dragging ones feet on the ground while walking, running, or dancing. ... An identity function f is a function which doesnt have any effect: it always returns the same value that was used as its argument. ...

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. In mathematics and statistics, a probability distribution, more properly called a probability density, assigns to every interval of the real numbers a probability, so that the probability axioms are satisfied. ... In mathematics, a fixed point of a function f is an argument x such that f(x) = x; see fixed point (mathematics). ... In combinatorial mathematics, the rencontres numbers are a triangular array of integers that enumerate permutations of the set { 1, ..., n } with specified numbers of fixed points. ... In probability theory and statistics, the Poisson distribution is a discrete probability distribution. ... In probability theory the expected value (or mathematical expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects as the outcome of the random trial when identical odds are... In combinatorial mathematics, the inclusion-exclusion principle states that if A1, ..., An are finite sets, then where |A| denotes the cardinality of the set A. For example, taking n = 2, we get a special case of double counting: in words, we can count the size of the union of sets... -1...

See Ewens's sampling formula for a connection with population genetics. In population genetics, Ewenss sampling formula, introduced by Warren Ewens, states that under certain conditions (specified below), if a random sample of n gametes is taken from a population and classified according to the gene at a particular locus then the probability that there are a1 alleles represented once... Population genetics is the study of the distribution of and change in allele frequencies under the influence of the four evolutionary forces: natural selection, genetic drift, mutation, and migration. ...

See also

• perfect shuffle
• Random permutation statistics
• Shuffling algorithms — random sort method, iterative exchange method

The statistics of random permutations, such as the cycle structure of a random permutation are of fundamental importance in the analysis of algorithms, especially of sorting algorithms, which operate on random permutations. ... The riffle Shuffling is a procedure used to randomize a deck of playing cards to provide an element of chance in card games. ...

External links

• Random permutation at MathWorld
• Random permutation generation