On Distributions Related to Transitive Closures of Random Finite Mappings

For f, a random single-valued mapping of an n-element set X into itself, let f^-1 be the inverse mapping, and f^ be such that f^ (x) = \f (x) \ f^-1 (x), x X. For a given subset A X, introduce three random variables (A) = | f (A) |, (A) = | f^-1 (A) |, and (A) = | f^ (A) |, where f, f^-1, f^ stand for transitive closures of f, f^-1, f^. The distributions of (A) and (A) are obtained. ( (A) was earlier studied by J. D. Burtin. ) For large n, the asymptotic behavior of those distributions is studied under various assumptions concerning m = |A|. For instance, it is shown that (A) is asymptotically normal with mean (2mn) ^1/2 and variance n/2, and (n - (A) ) (n/m) ^-1 is asymptotically U²/2 (U being the standard normal variable), provided m, m = o (n). The results are interpreted in terms of epidemic processes on random graphs introduced by I. Gertsbakh.