On the Cyclic Behavior of Random Transformations on a Finite Set.
STANFORD UNIV CA DEPT OF STATISTICS
Pagination or Media Count:
Let X be a finite set of elements and let tau be the set of all transformations from X into itself. For T epsilon tau we take T superscript k to have its usual meaning. Starting from a given x epsilon X consider the sequence T superscript j x, j 0,1,2... . since X is finite the sequence T superscript j must eventually encounter an element it had shown before. Thereafter it must repeat this intermediate sequence of elements. Such a sequence is called a cycle and the number of distinct elements in the cycle is called the cycle length. For a given T, not all xs must be on a cycle and, moreover, starting from differing xs may lead T into differing cycles. Hence we have the notion of a cycle space for T. It is the purpose of this paper to discuss a collection of exact and asymptotic results describing the cycle space of a randomly selected T. In particular, we examine such variables as the number of elements on a cycle of a specified length, the number of elements on cycles, the number of cycles and the length of a cycle.
- Statistics and Probability