Next: Permutation Matrices and X_{n,a}
Up: Background About Permutations and
Previous: Cycles and Cycle Structure
Probability and Cycle Structure
At this point, one could ask various questions about cycle structure, such as ``How many
permutations are there with a given cycle structure?" or, ``What is the cycle structure of a
`typical' random permutation ?" That is, how many fixed points, how many 2cycles,
etc. will
have, on average?
When the phrase ``random permutation" is used in this paper, it means that each permutation
in S_{n} is equally likely to be chosen. Thus, the probability of picking any one permutation
is 1/n!. Using this, the mean, or expected value, of any random variable V defined on
S_{n} will be

(2) 
and the variance of V will be

(3) 
Notice that the values
for a permutation picked from S_{n} are
just random variables, and the expectation of these values might provide some insight into
the questions posed above. Using standard group theory arguments, it can be shown that the
probability of picking a permutation with a particular cycle structure, say
is

(4) 
This formula can be used to prove a number of facts about the random variables C_{k}. The
results below are due to Goncharov [1]. (Also see Diaconis and Shahshahani [3].)
E[C_{k}] 
= 

(5) 
E[C_{j} C_{k}] 
= 

(6) 
if ,
and

(7) 
Next: Permutation Matrices and X_{n,a}
Up: Background About Permutations and
Previous: Cycles and Cycle Structure
20000925