- #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
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?
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.
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.
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.
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.
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.