Answers are grounded in this paper and cite their sources.
For f, a random single-valued mapping of an n-element set X into itself, let f⁻¹ be the inverse mapping, and f^ be such that f⁽x) = (x)\ ∪ f⁻¹(x), x ∈ X. For a given subset A ⊂ X, introduce three random variables ξ(A) = | f(A)|, η(A) = | f⁻¹(A)|, and ζ(A) = | f⁽A)|, where f, f⁻¹, f^ stand for transitive closures of f, f⁻¹, 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)⁻¹ 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.
No takes yet. Share an insight, caveat, or question.
Boris Pittel (1983) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: