Probability of Indecomposability of a Random Mapping Function

Consider a finite set of N points and a single-valued function f (x) on into. In case the mapping is one-to-one, it is a permutation of the points of ; we shall be concerned with more general mappings. Any mapping function effects a decomposition of the set into disjoint, minimal, non-null invariant subsets, as = ₁ + ₂ + + ₖ, where f (ᵢ) ᵢ and f^-1 (ᵢ) ᵢ. These subsets have been referred to as trees and as components of the mapping; we shall say that f, as above, decomposes the set into k components. Metropolis and Ulam 1 defined a random mapping by a uniform probability distribution over the ^ sample points of f (x) and posed the problem of finding the expected number of components. Kruskal 2 subsequently solved this problem. In this paper, we consider a related problem, namely, what is the probability that a random mapping is indecomposable, i. e. , that the minimal non-null set for which f () = and f^-1 () =, is the whole set =? This problem is solved in general, as is, also, an analogous problem for a specialized random mapping of some interest in social psychology. Finally, we examine the asymptotic behavior of these probabilities.