Cycle length in a random function
Cycle length in a random function
复制标题
随机函数中的循环长度
DOI：
10.1090/s0002-9947-1968-0228032-3
复制
发表时间：
1968
影响因子：
1.3
通讯作者：
J. H. Williams
中科院分区：
文献类型：
--
作者：
P. Purdom;J. H. Williams
设X是n个点的有限集，Fn是从X到X的nn个函数类.对于任意f ∈ Fn和xo ∈ X，序列x 0，x1 =f（x 0），x2 =f（x1），. . .,最终是循环的，即存在J和存在1使得j>J意味着xj = xj + 1。我们将1个不同的点称为xi，xi + 1，.。. .,如果xj + 1 =f（xj）（i<j< i +1 -2）并且f（xi + -1）= xi，则xi + 1 1是循环。显然，对起始值x 0的不同选择可能导致不同的循环。函数中最长循环的长度在伪随机数的生成中很有意义[1]。我们考虑随机选取函数fe Fn的第i个最长循环的长度的期望值和长度的m阶矩。给定f E Fn，设Y是X的由圈中所有点组成的子集，则限制于Y的f是置换。设a是函数f E Fn的循环结构的任何特征（例如a -最长的循环长度为1），我们首先找到一个将具有特征a的函数的数量与具有特征a的置换的数量相关联的公式。然后，我们使用Shepp和Lloyd [2]的结果，给出置换中周期长度的各种矩的期望值的渐近表达式，以找到函数的这些值的渐近表达式。如果xj =f（xi），我们说函数f直接连接xi和xj，如果有一系列从xi开始到xj的直接连接点，那么f连接xi和xj。那么子集Y只由那些与自身相连的点组成。我们说一个子集Zc X是一个以点xm为根的树，如果：（1）xm c X-Z，（2）xc Z意味着x与xm相连，（3）X-Z中没有点与Z中的点相连。显然，anyf E Fn将一些点连接成圈，将其余的点连接成以圈中的点为根的树。设T（n，m）表示将n个点连接成以m个点为根的树的方法的数目。由于Cn，m是根点可以被选择的方式的数量，并且miT（n-m，i）是剩余点可以被连接的方式的数量，如果它们中的恰好i个直接连接到m个根，则我们具有递归关系，
Let X be a finite set of n points and Fn be the class of nn functions from X into X. For anyf E Fn and xo E X, the sequence, x0, xl =f(xO), x2 =f(xl), . . ., is eventually cyclic, i.e. there exists J and there exists 1 such that j>J implies xj = xj + 1. We will call 1 distinct points xi, xi + 1, . . ., xi + 1 1 a cycle if xj + 1 =f(xj) (i<j< i + l-2) and f(xi + -1) = xi. Clearly different choices of the starting value, xo, may lead to different cycles. The length of the longest cycle in a function is of interest in the generation of pseudo-random numbers [1]. We consider the expected value of the length and the mth moment of the length of the ith longest cycle where the function fe Fn is selected at random. Given f E Fn, let Y be the subset of X consisting of all the points in cycles; then f restricted to Y is a permutation. Letting a be any characteristic of the cycle structure of a functionf E Fn (e.g. a -the longest cycle is of length 1), we first find a formula relating the number of functions with characteristic a to the number of permutations with characteristic a. We then use the results of Shepp and Lloyd [2] giving asymptotic expressions for the expected values of the various moments of cycle lengths in permutations to find the asymptotic expressions for these values for functions. We say that a function f directly connects xi to xj if xj =f(xi) and that f connects xi to xj if there is a sequence of directly connected points starting with xi going to xj. Then the subset, Y, consists of just those points that are connected to themselves. We say that a subset Zc X is a tree rooted on a point xm if: (1) xm c X-Z, (2) x c Z implies x is connected to xm, and (3) no point in X-Z is connected to a point in Z. Clearly anyf E Fn connects some of the points into cycles and the remainder of the points into trees rooted on points in cycles. Let T(n, m) denote the number of ways of connecting n points into trees rooted on m of the n points. Since Cn,m is the number of ways the root points may be chosen and miT(n-m, i) is the number of ways the remaining points may be connected if exactly i of them are directly connected to the m roots, we have the recurrence relation,