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:
“poor Felix Randal;
How far from then forethought of, all thy more boisterous years,
When thou at the random grim forge, powerful amidst peers,
Didst fettle for the great gray drayhorse his bright and battering
sandal!”
—Gerard Manley Hopkins (1844–1889)
“July 4. Statistics show that we lose more fools on this day than in all the other days of the year put together. This proves, by the number left in stock, that one Fourth of July per year is now inadequate, the country has grown so.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)