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 $\sigma$?" That is, how many fixed points, how many 2-cycles, etc. will $\sigma$ 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

$$E[V] = {1 \over n!} \sum_{\sigma \in S_n} V(\sigma),$$ (2)

and the variance of V will be

$$Var[V] = {1 \over n!} \sum_{\sigma \in S_n} (V(\sigma)-E[V])^2.$$ (3)

Notice that the values $C_1,\,C_2,\,\ldots,\,C_n$ 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 $(\vartheta_1,\,\vartheta_2,\,\ldots,\vartheta_n),$ is

$$P(C_1=\vartheta_1,\,C_2=\vartheta_2,\,\ldots,C_n=\vartheta_n)... ...\sum_{k=1}^n k \vartheta_k = n$\space \cr 0 & otherwise. \cr}$$ (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].)

 

$$\cases{\frac{1}{k}$$ E[C_k] = (5)

$$\cases{\frac{1}{jk}$$ E[C_j C_k] = (6)

if $j\neq k$, and

$$Var[C_k] = \cases{\frac{1}{k} & if $k \le n/2$\space \cr \cr... ...}{k^2}& if $n/2 < k \le n$\space \cr \cr 0 & otherwise. \cr}$$ (7)