Random permutation

from Wikipedia, the free encyclopedia
Playing card spade 7 - vertical cut.pngPlaying card spade 3 - vertical cut.pngPlaying card spade J - vertical cut.pngPlaying card spade 5 - vertical cut.pngPlaying card spade 9 - vertical cut.pngPlaying card spade A - vertical cut.pngPlaying card spade Q - vertical cut.pngPlaying card spade 2 - vertical cut.pngPlaying card spade 6 - vertical cut.pngPlaying card spade 10 - vertical cut.pngPlaying card spade K - vertical cut.pngPlaying card spade 8 - vertical cut.pngPlaying card spade 4.svg
A realization of a random permutation of the playing cards of one suit

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, pseudo-random permutations can be efficiently generated using the Fisher-Yates 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 probability-generating 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

Frequency distribution of the number of fixed points in a random permutation of length 7

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 probability-generating 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

Frequency distribution of the number of climbs in a random permutation of length 7

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

Frequency distribution of the number of errors in a random permutation of length 7

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

Frequency distribution of the number of cycles in a random permutation of length 7

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 pseudo-random numbers are then combined in a suitable manner so that a pseudo-random 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(n-i+1)    // Gleichverteilte Zufallszahl zwischen 1 und n-i+1
    P(i) = N(z)          // Wähle als nächsten Eintrag die z-te verbleibende Zahl
    N = setdiff(N,N(z))  // Entferne diese Zahl aus den verbleibenden Zahlen
  end
  return P
Area Random number selection Result
1-6 5 1 2 3 4 5 6 5
1-5 3 1 2 3 4 6 5 3
1-4 4th 1 2 4 6 5 3 6
1-3 1 1 2 4 5 3 6 1
1-2 2 2 4 5 3 6 1 4
1-1 1 2 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 time-consuming 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 pseudo-random permutation of length six. The number selected and thus eliminated in each step is shown with a line through it.

Fisher-Yates method

The Fisher-Yates 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 time-consuming 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 non-selected 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
1-6 5 1 2 3 4 5 6
1-5 3 1 2 3 4 6 5
1-4 4th 1 2 6 4 3 5
1-3 1 1 2 6 4 3 5
1-2 2 6 2 1 4 3 5
1-1 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 re-sorted 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 Fisher-Yates 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 pseudo-random 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 built-in 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 pseudo-random permutation with a maximum period length
  • Golomb-Dickman constant , the expectation of the relative length of the longest cycle in a random permutation for

literature

Web links

Individual evidence

  1. ^ Alan Camina, Barry Lewis: An Introduction to Enumeration . Springer, 2011, ISBN 0-85729-600-0 , pp. 140 .
  2. ^ Philippe Flajolet, Robert Sedgewick: Analytic Combinatorics . Cambridge University Press, 2009, pp. 658 .
  3. ^ Donald E. Knuth: The Art of Computer Programming, Volume 3: Sorting and Searching . S. 15-16 .
  4. Vladimir Nikolaevič Sačkov: Probabilistic Methods in Combinatorial Analysis . Cambridge University Press, 1997, pp. 30 .
  5. ^ Hosam M. Mahmoud: Sorting: A Distribution Theory . John Wiley & Sons, 2000, ISBN 0-471-32710-7 , pp. 48 .
  6. randperm. In: MATLAB Documentation Center. The MathWorks, archived from the original on January 28, 2013 ; Retrieved December 7, 2013 .