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.