next up previous
Next: Permutation Matrices and Xn,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 $\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 Sn 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 Sn will be

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

and the variance of V will be

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

Notice that the values $C_1,\,C_2,\,\ldots,\,C_n$ for a permutation picked from Sn 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

 \begin{displaymath}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}
\end{displaymath} (4)

This formula can be used to prove a number of facts about the random variables Ck. The results below are due to Goncharov [1]. (Also see Diaconis and Shahshahani [3].)
 
E[Ck] = $\displaystyle \cases{\frac{1}{k}$ (5)
E[Cj Ck] = $\displaystyle \cases{\frac{1}{jk}$ (6)

if $j\neq k$, and

 \begin{displaymath}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}
\end{displaymath} (7)


next up previous
Next: Permutation Matrices and Xn,a Up: Background About Permutations and Previous: Cycles and Cycle Structure

2000-09-25