Random permutation

A random permutation or random permutation in mathematics is a random arrangement of a set of objects . For example, shuffling the cards of a deck of cards is (ideally) a random permutation of the cards. In stochastics , random permutations are viewed as uniformly distributed random variables from a discrete probability space whose values are permutations. In this way, key figures of random permutations, such as the number of fixed points , deficiencies or cycles , can be viewed as discrete random variables, the distributions of which are then analyzed. In the computer, pseudorandom permutations can be efficiently generated using the FisherYates method. Random permutations are examined , among other things, in the analysis of sorting processes , in cryptography and coding theory, and in the context of randomized algorithms .
definition
If the symmetric group of all permutations of the set , then a random permutation is a uniformly distributed random variable , that is, a mapping of a probability space such that
holds for all permutations . More generally, permutations of any finite sets , for example alphabets , can also be considered. To analyze the mathematical properties, however, a restriction to the first natural numbers is possible.
example
The set consists of the six permutations of the numbers and , in tuple representation
 .
A random permutation realizes each of these six permutations with the same probability
 .
Is as the underlying probability space with all selected, can by the identity map are displayed.
properties
Variables assigned to random permutations, such as the number of errors or cycles , can also be interpreted as discrete random variables . However, the probability distribution of these random variables is generally no longer evenly distributed. Generating functions are an important tool in the analysis of these probability distributions . If the probability function is that the random variable assumes the value , then the associated probabilitygenerating function is carried out
Are defined. This is an exponentially generating function . The expected value of the random variable is then through
given and their variance accordingly
 .
In the following, probability distributions, expected values and variances of some important parameters of random permutations are given.
Number of fixed points
A fixed point in a permutation is a number for which applies. The number of permutations with exactly fixed points is given by the Rencontres numbers (sequence A008290 in OEIS ). The probabilitygenerating function of the number of fixed points in a permutation has the form
 .
The following applies to the expected value and the variance of the number of fixed points
and
 .
The number of fixed points in a random permutation is asymptotically Poisson distributed with intensity .
Number of climbs
An increase in a permutation is a number for which holds. The number of permutations with exact increases (analogous to descents) is given by the Euler numbers (sequence A008292 in OEIS ). The probability generating function of the number of rises in a permutation has the form
 .
The following applies to the expected value and the variance of the number of increases
and
 .
The number of increases in a random permutation is asymptotically normally distributed with appropriate normalization for .
Number of absenteeism
A fault in a permutation is a pair for which and holds. The number of permutations with exactly missing positions is given by the McMahon numbers (sequence A008302 in OEIS ). The probability function of the number of fixed points of a permutation has the form
 .
The following applies to the expected value and the variance of the number of deficiencies
and
 .
The number of errors in a random permutation is asymptotically normally distributed with appropriate normalization for .
Number of cycles
A cycle in a permutation is a sequence of different numbers for which for and holds. Each permutation can be completely broken down into cycles. The number of permutations with exactly cycles is given by the Stirling numbers of the first type (sequence A130534 in OEIS ). The probability generating function of the number of cycles of a permutation has the form
 .
The following applies to the expected value and the variance of the number of cycles
 ,
where is the th harmonic number , and
 ,
wherein the th harmonic number is the second order. The number of cycles in a random permutation is normally distributed asymptotically with the expected value and variance with the appropriate normalization .
generation
An important task in the investigation of algorithms , for example sorting processes, in the context of Monte Carlo simulations is the generation of random permutations on the computer. The basic idea here is the use of uniformly distributed pseudo random numbers with the help of suitable random number generators . These pseudorandom numbers are then combined in a suitable manner so that a pseudorandom permutation is created.
Direct procedure
In a direct approach, a list consisting of the numbers from to is considered first. After a uniformly distributed random number between and (inclusive) has been drawn, the corresponding list element is noted as the first number of the result permutation and this element is then deleted from the list. In the next step, a uniformly distributed random number is drawn between and , the corresponding list element is noted as the second number of the result permutation and this element is also deleted again. This procedure is continued until finally there are no more numbers in the list and the result permutation is complete. This procedure can be implemented in pseudocode as follows:
function randperm(n)
P = zeroes(n) // Ergebnispermutation mit Nullen initialisieren
N = [1:n] // Feld mit den Zahlen von 1 bis n
for i = 1 to n // Schleife über die Einträge von P
z = random(ni+1) // Gleichverteilte Zufallszahl zwischen 1 und ni+1
P(i) = N(z) // Wähle als nächsten Eintrag die zte verbleibende Zahl
N = setdiff(N,N(z)) // Entferne diese Zahl aus den verbleibenden Zahlen
end
return P
Area  Random number  selection  Result 

16  5  1 2 3 4 
5 
15  3  1 2 
5 3 
14  4th  1 2 4 
5 3 6 
13  1 

5 3 6 1 
12  2  2 
5 3 6 1 4 
11  1  5 3 6 1 4 2 
In this process, the places are passed through one after the other, with each place being assigned a random number selected from the numbers still available. Alternatively, the dual approach can be followed, in which the numbers are run through one after the other, with each number being assigned a randomly selected free space. In both cases, the efficiency of the method suffers from the fact that it is timeconsuming to remove a certain element from a list or to find a certain free space. In a standard implementation, these subtasks require operations on average , so that the overall process has a runtime complexity of order
having. The adjacent table shows an example of how this method works when generating a pseudorandom permutation of length six. The number selected and thus eliminated in each step is shown with a line through it.
FisherYates method
The FisherYates method (according to Ronald Fisher and Frank Yates ) represents an improvement . This method also works in place , that is, given a preinitialized field with the numbers from to , these numbers are gradually rearranged so that at the end a random one Permutation arises. The timeconsuming search for an unused number to avoid, in each step, the selected number will be the end of the currently considered subfield by the last remaining nonselected number swapped is. In pseudocode, this procedure is as follows:
function randperm(n)
P = [1:n] // Initialisierung mit der identischen Permutation
for i = n downto 1 // Schleife über die Einträge von P
z = random(i) // Gleichverteilte Zufallszahl zwischen 1 und i
swap(P(i),P(z)) // Vertausche die Zahlen an den Stellen i und z
end
return P
Area  Random number  permutation 

16  5  1 2 3 4 5 6 
15  3  1 2 3 4 6 5 
14  4th  1 2 6 4 3 5 
13  1  1 2 6 4 3 5 
12  2  6 2 1 4 3 5 
11  1  6 2 1 4 3 5 
As in the code example, the initialization can take place with the identical permutation , but any permutation can also be used here, which is then resorted accordingly. This makes the method particularly attractive for simulation applications in which the permutation routine is called iteratively . Since the interchanging of two elements of a field of fixed size takes place with constant effort, the FisherYates method has a runtime complexity of the order
 ,
which is a significant improvement over the direct method. In the adjacent table, the method is also illustrated using an example in which a pseudorandom permutation of length six is generated again. The numbers that have been swapped with one another are shown underlined. The last step can also be omitted, as there is never a change here. The same random numbers were used as in the example for the direct method, but the result permutation is different here.
This method is provided as a builtin function in the numerical software package MATLAB , for example randperm
.
See also
 100 Prisoners Problem , a mathematical puzzle based on random permutations
 RC4 , a stream encryption method that uses random permutations
 Bogosort , an inefficient sorting method that also uses random permutations
 Linear congruence generator , a random number generator that generates a pseudorandom permutation with a maximum period length
 GolombDickman constant , the expectation of the relative length of the longest cycle in a random permutation for
literature
 Miklós Bóna: Combinatorics of Permutations (= Discrete Mathematics and Its Applications . No. 72 ). 2nd Edition. CRC Press, 2012, ISBN 1439850518 .
 Philippe Flajolet , Robert Sedgewick : Analytic Combinatorics . Cambridge University Press, 2009, ISBN 1139477161 .
 Donald E. Knuth : The Art of Computer Programming . 3. Edition. Volume 2: Seminumerical Algorithms. AddisonWesley, 1997, ISBN 0201896842 .
 Donald E. Knuth: The Art of Computer Programming . 2nd Edition. Volume 3: Sorting and Searching. AddisonWesley, 1998, ISBN 0201896850 .
Web links
 Eric W. Weisstein : Random Permutation . In: MathWorld (English).
Individual evidence
 ^ Alan Camina, Barry Lewis: An Introduction to Enumeration . Springer, 2011, ISBN 0857296000 , pp. 140 .
 ^ Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics . Cambridge University Press, 2009, pp. 658 .
 ^ Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching . S. 1516 .
 ↑ Vladimir Nikolaevič Sačkov: Probabilistic Methods in Combinatorial Analysis . Cambridge University Press, 1997, pp. 30 .
 ^ Hosam M. Mahmoud: Sorting: A Distribution Theory . John Wiley & Sons, 2000, ISBN 0471327107 , pp. 48 .
 ↑ randperm. In: MATLAB Documentation Center. The MathWorks, archived from the original on January 28, 2013 ; Retrieved December 7, 2013 .