HOME

TheInfoList



OR:

A random permutation is a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
where any order of its items is equally likely at
random In common usage, randomness is the apparent or actual lack of definite pattern or predictability in information. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. ...
, that is, it is a
permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...
-valued
random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a Mathematics, mathematical formalization of a quantity or object which depends on randomness, random events. The term 'random variable' in its mathema ...
of a set of objects. The use of random permutations is common in
games of chance A game of chance is in contrast with a game of skill. It is a game whose outcome is strongly influenced by some randomizing device. Common devices used include dice, spinning tops, playing cards, roulette wheels, numbered balls, or in the case ...
and in
randomized algorithm A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic or procedure. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performan ...
s in
coding theory Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and computer data storage, data sto ...
,
cryptography Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
, and
simulation A simulation is an imitative representation of a process or system that could exist in the real world. In this broad sense, simulation can often be used interchangeably with model. Sometimes a clear distinction between the two terms is made, in ...
. A good example of a random permutation is the fair
shuffling Shuffling is a technique used to randomize a deck of playing cards, introducing an element of chance into card games. Various shuffling methods exist, each with its own characteristics and potential for manipulation. One of the simplest shuf ...
of a standard deck of cards: this is ideally a random permutation of the 52 cards.


Computation of random permutations


Entry-by-entry methods

One algorithm for generating a random permutation of a set of size ''n'' uniformly at random, i.e., such that each of the ''n''!
permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...
s is equally likely to appear, is to generate a
sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
by uniformly randomly selecting an integer between 1 and ''n'' (inclusive), sequentially and without replacement ''n'' times, and then to interpret this sequence (''x''1, ..., ''x''''n'') as the permutation : \begin 1 & 2 & 3 & \cdots & n \\ x_1 & x_2 & x_3 & \cdots & x_n \\ \end, shown here in two-line notation. An inefficient brute-force method for sampling without replacement could select from the numbers between 1 and ''n'' at every step, retrying the selection whenever the random number picked is a repeat of a number already selected until selecting a number that has not yet been selected. The expected number of retries per step in such cases will scale with the inverse of the fraction of numbers already selected, and the overall number of retries as the sum of those inverses, making this an inefficient approach. Such retries can be avoided using an algorithm where, on each ''i''th step when ''x''1, ..., ''x''''i'' − 1 have already been chosen, one chooses a uniformly random number ''j'' from between 1 and ''n'' − ''i'' + 1 (inclusive) and sets ''x''''i'' equal to the ''j''th largest of the numbers that have not yet been selected. This selects uniformly randomly among the remaining numbers at every step without retries.


Fisher-Yates shuffles

A simple
algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
to generate a permutation of ''n'' items uniformly at random without retries, known as the Fisher–Yates shuffle, is to start with any permutation (for example, the
identity permutation In mathematics, a permutation group is a group ''G'' whose elements are permutations of a given set ''M'' and whose group operation is the composition of permutations in ''G'' (which are thought of as bijective functions from the set ''M'' to its ...
), and then go through the positions 0 through ''n'' − 2 (we use a convention where the first element has index 0, and the last element has index ''n'' − 1), and for each position ''i'' swap the element currently there 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 the 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) If the uniform() function is implemented simply as random() % (m) then there will be a bias in the distribution of permutations if the number of return values of random() is not a multiple of m. However, this effect is small if the number of return values of random() is orders of magnitude greater than m.


Randomness testing

As with all computational implementations of random processes, the quality of the distribution generated by an implementation of a randomized algorithm such as the Fisher-Yates shuffle, i.e., how close the actually generated distribution is to the desired distribution, will depend on the quality of underlying sources of randomness in the implementation such as pseudorandom number generators or hardware random number generators. There are many
randomness test A randomness test (or test for randomness), in data evaluation, is a test used to analyze the distribution of a set of data to see whether it can be described as random (patternless). In stochastic modeling, as in some computer simulations, the ...
s for random permutations, such as the "overlapping permutations" test of the Diehard tests. A typical form of such tests is to take some permutation statistic for which the distribution is theoretically known and then test whether the distribution of that statistic on a set of randomly generated permutations from an implementation closely approximates the distribution of that statistic from the true distribution.


Statistics on random permutations


Fixed points

The
probability distribution In probability theory and statistics, a probability distribution is a Function (mathematics), function that gives the probabilities of occurrence of possible events for an Experiment (probability theory), experiment. It is a mathematical descri ...
for the number of
fixed points Fixed may refer to: * ''Fixed'' (EP), EP by Nine Inch Nails * ''Fixed'' (film), an upcoming animated film directed by Genndy Tartakovsky * Fixed (typeface), a collection of monospace bitmap fonts that is distributed with the X Window System * Fi ...
of a uniformly distributed random permutation of ''n'' elements approaches a
Poisson distribution In probability theory and statistics, the Poisson distribution () is a discrete probability distribution that expresses the probability of a given number of events occurring in a fixed interval of time if these events occur with a known const ...
with
expected value In probability theory, the expected value (also called expectation, expectancy, expectation operator, mathematical expectation, mean, expectation value, or first Moment (mathematics), moment) is a generalization of the weighted average. Informa ...
1 as ''n'' grows. The first ''n'' moments of this distribution are exactly those of the Poisson distribution. In particular, the probability that a random permutation has no fixed points (i.e., that the permutation is a derangement) approaches 1/''e'' as ''n'' increases.


See also

* Ewens's sampling formula — a connection with
population genetics Population genetics is a subfield of genetics that deals with genetic differences within and among populations, and is a part of evolutionary biology. Studies in this branch of biology examine such phenomena as Adaptation (biology), adaptation, s ...
*
Faro shuffle The faro shuffle (American), weave shuffle (British), or dovetail shuffle is a method of shuffling playing cards, in which half of the deck is held in each hand with the thumbs inward, then cards are released by the thumbs so that they fall to the ...
* Golomb–Dickman constant * Random permutation statistics * Shuffling algorithms — random sort method, iterative exchange method *
Pseudorandom permutation In cryptography, a pseudorandom permutation (PRP) is a function that cannot be distinguished from a random permutation (that is, a permutation selected at random with uniform probability, from the family of all permutations on the function's domai ...


References

{{Reflist


External links


Random permutation
at
MathWorld ''MathWorld'' is an online mathematics reference work, created and largely written by Eric W. Weisstein. It is sponsored by and licensed to Wolfram Research, Inc. and was partially funded by the National Science Foundation's National Science ...

Random permutation generation
-- detailed and practical explanation of Knuth shuffle algorithm and its variants for generating ''k''-permutations (permutations of ''k'' elements chosen from a list) and ''k''-subsets (generating a subset of the elements in the list without replacement) with pseudocode Permutations Randomized algorithms