What is the average length of a cycle in a permutation of $\{1,2,3,\dots ,n\}$?
-
$\begingroup$ What did you try? $\endgroup$ – Ittay Weiss Aug 26 '15 at 3:13
-
$\begingroup$ do you count cycles of length $1$? $\endgroup$ – Jorge Fernández-Hidalgo Aug 26 '15 at 3:15
HINT: The expected number of $k$-cycles in a random permutation of $[n]$ is $\frac1k$. Thus, the expected number of cycles in a random permutation of $[n]$ is $\sum_{k=1}^n\frac1k=H_n$, the $n$-th harmonic number.
- How many cycles are there altogether in all permutations of $[n]$?
- What is the total length of all of these cycles?
- What is their mean length?
-
1$\begingroup$ Thanks Brian! Please let me know if my further analysis is incorrect. Total number of k-cycles (in all permutations) is $n!/k$ and total number of cycles (in all permutations) is $n! \cdot H_n$. Hence, $p(length=k \mid cycle)$ (probability that a random cycle has length k) is $\frac{n!/k}{n! \cdot H_n}=\frac{1}{k \cdot H_n}$. From here, avg cycle length=$\sum_{k=1}^{n}k\cdot p(length=k | cycle)=\sum_{k=1}^{n}k\cdot \frac{1}{k\cdot H_n}=\frac{n}{H_n}$ $\endgroup$ – talegari Aug 26 '15 at 6:46
-
1$\begingroup$ @talegari: You're welcome! I had in mind a slightly different calculation, but yours works too. (I was calculating the total length of all cycles as $n\cdot n!$ and dividing by $n!H_n$.) $\endgroup$ – Brian M. Scott Aug 26 '15 at 7:15
-
$\begingroup$ @brian-m-scott : It would be great to hear about the approach you had on mind. $\endgroup$ – talegari Aug 26 '15 at 7:17
-
$\begingroup$ Proof of the fact: The expected number of k-cycles in a random permutation of $[n]$ is $\frac{1}{k}$. Let $x_i=1$ if $i$ is a part of a k-cycle, else 0. $\frac{\sum_{i=1}^{n}x_i}{k}$ counts the number of k-cycles of $[n]$. We have $E \left( \frac{\sum_{i=1}^{n}x_i}{k} \right)=\frac{1}{k} \sum_{i=1}^{n}E(x_i)=\frac{1}{k} \sum_{i=1}^{n}\frac{1}{n}=\frac{1}{k}$ Proof of the fact: Probability that 1 belongs to a k-cycle is 1/n (independent of k). Apart from one, a k-cycle can be constructed in $\binom{n-1}{k-1}(k-1)!(n-k)!$ . Dividing by $n!$ gives $\frac{1}{n}$ $\endgroup$ – talegari Aug 26 '15 at 11:21
By way of enrichment here is an alternate formulation using combinatorial species. The species of permutations with cycle length marked is
$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{U}^2\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{U}^3\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{U}^4\mathfrak{C}_{=4}(\mathcal{Z}) + \cdots).$$
This gives the generating function $$G(z, u) = \exp\left(uz + u^2\frac{z^2}{2} + u^3\frac{z^3}{3} + u^4\frac{z^4}{4} + u^5\frac{z^5}{5} + \cdots\right)$$ which is $$G(z, u) = \exp\left(\log\frac{1}{1-uz}\right) = \frac{1}{1-uz}.$$
As this is an EGF to get the OGF of the total cycle length in all permutations we must compute $$\left.\frac{\partial}{\partial u} G(z, u)\right|_{u=1}.$$
This is $$\left. (-1) \times \frac{1}{(1-uz)^{2}} \times (-z)\right|_{u=1} = \frac{z}{(1-z)^{2}}.$$
This yields $$n! [z^n] \frac{z}{(1-z)^{2}} = n! \times n.$$
This could have been obtained trivially by noting that the cycle lengths in each permutation sum to $n$ and there are $n!$ permutations.
On the other hand the species of permutations with cycle count marked is
$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=2}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=3}(\mathcal{Z}) + \mathcal{U}\mathfrak{C}_{=4}(\mathcal{Z}) + \cdots)$$
This gives the generating function $$G(z, u) = \exp\left(uz + u\frac{z^2}{2} + u\frac{z^3}{3} + u\frac{z^4}{4} + u\frac{z^5}{5} + \cdots\right)$$ which is
$$G(z, u) = \exp\left(u\log\frac{1}{1-z}\right).$$
Proceding as before to get the total number of cycles we obtain $$\left. \exp\left(u\log\frac{1}{1-z}\right) \log\frac{1}{1-z} \right|_{u=1} = \frac{1}{1-z} \log\frac{1}{1-z}.$$
This gives $$n! [z^n] \frac{1}{1-z} \log\frac{1}{1-z} = n! H_n.$$
It follows that the average is $$\frac{n}{H_n} \sim \frac{n}{\log n}.$$
The following Maple program shows how to compute this statistic using the cycle index $Z(S_n)$ of the symmetric group.
pet_cycleind_symm := proc(n) local p, s; option remember; if n=0 then return 1; fi; expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n)); end; v := proc(n) option remember; local part, src, idx, totcyc; totcyc := 0; if n=1 then idx := [a[1]]; else idx := pet_cycleind_symm(n); fi; for part in idx do totcyc := totcyc + lcoeff(part)*degree(part); od; n/totcyc; end;
We get the sequence $$1,4/3,{\frac {18}{11}},{\frac {48}{25}},{\frac {300}{137}}, {\frac {120}{49}},{\frac {980}{363}},{\frac {2240}{761}},\ldots$$