On the Cyclic Behavior of Random Transformations on a Finite Set.
Abstract
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 x's must be on a cycle and, moreover, starting from differing x's 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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 04, 1981
- Accession Number
- ADA109694
Entities
People
- Alan E. Gelfand
Organizations
- Stanford University