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

# Descriptors:

# Subject Categories:

- Statistics and Probability