What is the Expected Number of Cycles in a Random Function?

[Dragonfall]

Given a length preserving bijection on n-bits uniformly at random, what is the expected number of cycles? Cycles being f(f(...f(x)...)) = x

 

[economicsnerd]

If I understand correctly, you have a finite set $X$, and a group $S$ of permutations on $X$, and you want to find the expected cardinality of the set $$\{x\in X: \enspace \exists k\in\mathbb N \text{ with } f^k(x)=x\},$$ when $f\in S$ is chosen randomly. Is this correct?

If so, then the answer is $|X|$. By LaGrange's theorem for finite groups, $f^{|S|}=\text{id}_X$ (which has every $x\in X$ as a fixed point) for every $f\in S$.

 

[Dragonfall]

No I'm asking for the expected number of such cycles, not the number of elements that are part of a cycle (which is obviously |X|).

In other words, define equivalent classes on X such that two elements are equal if they are part of the same cycle. How many such classes are expected when f is chosen uniformly at random?

 

[willem2]

No I'm asking for the expected number of such cycles, not the number of elements that are part of a cycle (which is obviously |X|).

In other words, define equivalent classes on X such that two elements are equal if they are part of the same cycle. How many such classes are expected when f is chosen uniformly at random?

It's equal to

$$\sum_{i=1}^{n} \frac {1}{n}$$ also known as the n-th harmonic number. See:

http://www.cs.berkeley.edu/~jfc/cs174/lecs/lec2/lec2.pdf

at the bottom of page 3.

 

[Dragonfall]

Nice, thanks.