Random Permutation Statistics
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. Suppose, for example, that we are using quickselect (a cousin of quicksort) to select a random element of a random permutation. Quickselect will perform a partial sort on the array, as it partitions the array according to the pivot. Hence a permutation will be less disordered after quickselect has been performed. The amount of disorder that remains may be analysed with generating functions. These generating functions depend in a fundamental way on the generating functions of random permutation statistics. Hence it is of vital importance to compute these generating functions.
The article on random permutations contains an introduction to random permutations.
Read more about Random Permutation Statistics: The Fundamental Relation, Number of Permutations That Are Involutions, Number of Permutations That Are mth Roots of Unity, Number of Permutations That Are Derangements, Derangements Containing An Even and An Odd Number of Cycles, One Hundred Prisoners, Number of Permutations Containing Cycles, Expected Number of Cycles of A Given Size m, Moments of Fixed Points, Expected Number of Fixed Points in Random Permutation Raised To Some Power, Expected Number of Cycles of Any Length of A Random Permutation, Number of Permutations With A Cycle of Length Larger Than, Expected Number of Transpositions of A Random Permutation, Expected Cycle Size of A Random Element, Probability That A Random Element Lies On A Cycle of Size m, Probability That A Random Subset of Lies On The Same Cycle, Number of Permutations Containing An Even Number of Even Cycles, Permutations That Are Squares, Odd Cycle Invariants, A Problem From The 2005 Putnam Competition, See Also
Famous quotes containing the words random and/or statistics:
“Man always made, and still makes, grotesque blunders in selecting and measuring forces, taken at random from the heap, but he never made a mistake in the value he set on the whole, which he symbolized as unity and worshipped as God. To this day, his attitude towards it has never changed, though science can no longer give to force a name.”
—Henry Brooks Adams (1838–1918)
“He uses statistics as a drunken man uses lamp-posts—for support rather than illumination.”
—Andrew Lang (1844–1912)