1955/09/01 by Leo Katz · 1 citation
Mathematics · #Functional Equations Stability Results #Point processes and geometric inequalities #Advanced Topology and Set Theory
paper · pdf · doi:10.1214/aoms/1177728496
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 Ω = ω1 + ω2 + ⋯ + ωk, where f(ωi) ⊂ ωi and f-1(ωi) ⊂ ωi.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.