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

In summary, we are discussing the expected number of cycles when a length preserving bijection on n-bits is chosen uniformly at random. This is equivalent to finding the expected number of equivalent classes on a finite set X, where two elements are considered equal if they are part of the same cycle. The answer is equal to the n-th harmonic number.
  • #1
Dragonfall
1,030
4
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
 
Physics news on Phys.org
  • #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].
 
  • #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?
 
  • #4
Dragonfall said:
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

[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.
 
  • #5
Nice, thanks.
 

1. What is a random function?

A random function is a mathematical function that produces a random output for a given input. It is often used in computer science and statistics to generate random numbers or simulate natural processes.

2. What are cycles in a random function?

Cycles in a random function refer to repeating patterns or sequences of values that occur in the output of the function. These cycles may be periodic or non-periodic, and can be visualized as peaks and valleys in a graph of the function's output.

3. How do cycles affect the randomness of a function?

The presence of cycles can affect the randomness of a function by introducing predictability and reducing the overall randomness of the output. This can be a desirable or undesirable effect, depending on the application of the function.

4. Can cycles in a random function be controlled or eliminated?

In some cases, cycles in a random function can be controlled or eliminated through the use of specialized algorithms or techniques. However, completely eliminating all cycles in a random function may not always be possible.

5. What are some real-world examples of cycles in random functions?

Some examples of cycles in random functions include weather patterns, stock market fluctuations, and the behavior of complex systems such as the human brain. These cycles can be studied using mathematical models and simulations to gain insights into their underlying patterns and dynamics.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
332
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
366
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
436
  • Set Theory, Logic, Probability, Statistics
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
865
  • Set Theory, Logic, Probability, Statistics
Replies
15
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
390
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
821
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
887
Back
Top