5
$\begingroup$

What is the average length of a cycle in a permutation of $\{1,2,3,\dots ,n\}$?

$\endgroup$
  • $\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
3
$\begingroup$

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?
$\endgroup$
  • 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
4
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.