Accession Number:

ADA109694

Title:

On the Cyclic Behavior of Random Transformations on a Finite Set.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CA DEPT OF STATISTICS

Personal Author(s):

Report Date:

1981-08-04

Pagination or Media Count:

31.0

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

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE