Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cycles in random function

  1. Aug 17, 2013 #1
    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
     
  2. jcsd
  3. Aug 17, 2013 #2
    If I understand correctly, you have a finite set [itex]X[/itex], and a group [itex]S[/itex] of permutations on [itex]X[/itex], and you want to find the expected cardinality of the set [tex]\{x\in X: \enspace \exists k\in\mathbb N \text{ with } f^k(x)=x\},[/tex] when [itex]f\in S[/itex] is chosen randomly. Is this correct?

    If so, then the answer is [itex]|X|[/itex]. By LaGrange's theorem for finite groups, [itex]f^{|S|}=\text{id}_X[/itex] (which has every [itex]x\in X[/itex] as a fixed point) for every [itex]f\in S[/itex].
     
  4. Aug 17, 2013 #3
    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?
     
  5. Aug 17, 2013 #4
    It's equal to

    [tex] \sum_{i=1}^{n} \frac {1}{n} [/tex] 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.
     
  6. Aug 18, 2013 #5
    Nice, thanks.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook