Probability Distributions Related to Random Mappings

A Random Mapping Space (X, J, P) is a triplet, where X is a finite set of elements x of cardinality n, J is a set of transformations T of X into X, and P is a probability measure over J. In this paper, four choices of J are considered (I) J is the set of all transformations of X into X. (II) J is the set of all transformations of X into X such that for each x X Tx x. (III) J is the set of one-to-one mappings of X onto X. (IV) J is the set of one-to-one mappings of X onto X, such that for each x X, Tx x. In each case P is taken as the uniform probability distribution over J. If x X and T J, we will define Tᵏx as the kth iteration of T on x, where k is an integer, i. e. Tᵏx = T (T^k-1x), and T⁰x = x for all x. The reader should note that, in general, Tᵏx, k 0, such that Tᵐx = x, then x is a cyclical element of T and the set of elements x, Tx, T²x, , T^m-1x is the cycle containing x, CT (x). If m is the smallest positive integer for which Tᵐ x = x, then CT (x) has cardinality m. We note further an interesting equivalence relation induced by T. If there exists a pair of integers k₁, k₂ such that T^k₁x = T^k₂y, then x y under T. It is readily seen that this is in fact an equivalence, and hence decomposes X into equivalence classes, which we shall call the components of X in T; and designate by KT (x) the component containing x. We define sT (x) to be the number of elements in ST (x), pT (x) to be the number of elements in PT (x), and lT (x) to be the number of elements in the cycle contained in KT (x) (i. e. l (x) = the number of elements in CT (x) if x is cyclical). We designate by qT the number of elements of X cyclical in T, and by rT the number of components of X in T. Rubin and Sitgreaves 9 in a Stanford Technical Report have obtained the distributions of s, p, l, q, and have given a generating function for the distribution of r in case I. Folkert 3, in an unpublished doctoral dissertation has obtained the distribution of r in cases I and II. The distribution of r in case III is classical and may be found in Feller 2, Gontcharoff 4, and Riordan 8. In the present paper, a number of these earlier results are rederived and extended. Specifically, for cases I and II, we compute the probability distributions of s, p, l, q and r. In cases III and IV the distributions of l and r are given. In addition some asymptotic distributions and low order moments are obtained. For the convenience of the reader, an index of notations having a fixed meaning is provided in the appendix to the paper.