Random permutation

• 4.1 Direct method
• 4.2 Fisher -Yates method

Definition

Is the symmetric group of all permutations of the set, then a random permutation is equal to a random variable, that is a picture of a probability space, so that

A random permutation of realizing each of the six permutations of the same probability

Is selected as the underlying probability space with for all, it can be represented by the identity map.

Properties

Random permutations associated variables such as the number of incorrect items or cycles, can also be interpreted as a discrete random variable. The probability distribution of these random variables is, however, not evenly distributed in general. An important tool in the analysis of these probability distributions are generating functions. If the probability function that the random variable takes the value, then the corresponding probability generating function is

Defined. It is here at an exponentially generating function. The expected value of the random variable is then given by

And its variance given accordingly by

The following probability distributions, expected values ​​and variances of some important characteristics of random permutations are given.

Number of fixed points

A fixed point of a permutation is a number that applies. The number of permutations with exactly the fixed points is given by the Rencontres numbers ( sequence A008290 in OEIS ). The probability generating function of the number of fixed points of a permutation has the form

Thus applies for the expected value and 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 slopes

An increase in the permutation is an integer for which holds. The number of permutations with exactly increases (analogous Downs ) is given by the Euler numbers ( sequence A008292 in OEIS ). The probability generating function of the number of rises in the form of a permutation

Thus applies for the expected value and variance of the number of ascents

And

The number of ascents in a random permutation is normally distributed with appropriate scaling for asymptotically.

The number of incorrect items

A false status in a permutation is a pair for which and apply. The number of permutations with exactly wrong items is given by the McMahon numbers ( sequence A008302 in OEIS ). The probability function of the number of the fixed points in the form of a permutation

Thus applies for the expected value and variance of the number of incorrect items

And

The number of failed items in a random permutation is normally distributed with appropriate scaling for asymptotically.

Number of cycles

A cycle in a permutation is a sequence of distinct numbers, for which it holds for and. Every permutation can be completely disassembled in cycles. The number of permutations with exactly cycles is given by the Stirling numbers of the first kind ( sequence A130534 in OEIS ). The probability generating function of the number of cycles is in the form of a permutation

Therefore applies to the mean and the variance of the number of cycles

Where the- th harmonic number, and

Where the- th harmonic number is second order. The number of cycles in a random permutation with appropriate scaling for asymptotically normally distributed with mean and variance.

Generation

An important task in the study of algorithms, such as sorting method, in the context of Monte Carlo simulations is the generation of random permutations on the computer. The basic idea is the use of uniform distributed pseudo-random numbers using appropriate random number generators. This pseudo-random numbers are then combined in a suitable manner, so that a pseudo-random permutation is formed.

Direct method

In a direct approach is first considered one of the numbers of up existing List. After a contraction of a uniform distributed random number between and (and including) the corresponding list element is noted as the first number of this element Ergebnispermutation and then deleted from the list. In the next step, a uniform distributed random number between and pulled, the corresponding list item is then listed as second number of Ergebnispermutation and this element also deleted again. This process continues until finally no longer present and therefore the number Ergebnispermutation is completely in the list. In pseudo-code, this method can be implemented as follows:

Randperm function (s)      Initialize P = zeroes ( n ) / / Ergebnispermutation with zeros      N = [1: n] / / array with the numbers from 1 to n      for i = 1 to n / / Loop over the entries of P          z = random ( n -i 1 ) / / Uniformly distributed random number between 1 and n -i 1          P ( i) = N ( z) / / Select the next entry in the z -th remaining number          N = setdiff (N, N ( z)) / / Remove this number from the remaining numbers      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 4 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 method, the seats are gone through in sequence, each course is assigned a randomly selected from each of the numbers still available number. Alternatively, the dual approach be followed, in which the numbers are successively gone through, each number is assigned a randomly selected free space left. In both cases, the efficiency of the method suffers from the fact that it is costly to remove a specific item from a list, or to find a particular free space. In a standard implementation, these tasks require the resources operations, so that the overall process a runtime complexity of order

Having. In the adjacent table there is an example of the operation of this method in generating a pseudo-random permutation of length six. The selected in each step and thus eliminated number is crossed out here.

Fisher -Yates method

An improvement is the Fisher -Yates method (after Ronald Fisher and Frank Yates ) dar. This method also works on the square, that is, for a given pre-initialized field with the numbers to these numbers are gradually rearranged such that at the end of a random permutation arises. To avoid the time-consuming search for a number not yet used, in each step, the selected number is placed at the end of the currently viewed subfield by being mixed up with the last not yet selected number. In pseudo-code this method is as follows:

Randperm function (s)      P = [1: n] / / Initialization with the identical permutation      for i = n downto 1 / / Loop over the entries of P          z = random ( i) / / Uniformly distributed random number between 1 and i          swap ( P (i ), P ( z )) / / Swap the numbers at the points i and z      end      return P area random number permutation 1-6 5 1 2 3 4 5 6 1-5 3 1 2 3 4 5 6 1-4 4 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 Initialization can, as in the example, be carried out with the identical permutation can here also be used in an arbitrary permutation, which is then rearranged accordingly. This makes the method particularly attractive for simulation applications, in which the Permutationsroutine is invoked iteratively. Since the interchange of two elements of an array of fixed size is done with a constant effort, the Fisher -Yates method has a runtime complexity of order

Which represents a significant improvement over the direct method. In the adjacent table, the method is also illustrated by an example in which again a pseudo-random permutation of length is generated six. The respective numbers are interchanged with each other underlined. The last step can be omitted, since it never held an exchange. The same random numbers used as the example for the direct process, however, is here Ergebnispermutation another.

This method is provided for example in the numerical software package MATLAB built-in function randperm available.