On Distributions Related to Transitive Closures of Random Finite Mappings
Pittel, Boris
Ann. Probab., Tome 11 (1983) no. 4, p. 428-441 / Harvested from Project Euclid
For $f$, a random single-valued mapping of an $n$-element set $X$ into itself, let $f^{-1}$ be the inverse mapping, and $f^\ast$ be such that $f^\ast(x) = \{f(x)\} \cup f^{-1}(x), x \in X$. For a given subset $A \subset X$, introduce three random variables $\xi(A) = |\hat f(A)|, \eta(A) = |\hat f^{-1}(A)|$, and $\zeta(A) = |\hat f^\ast(A)|$, where $\hat f, \hat f^{-1}, \hat f^\ast$ stand for transitive closures of $f, f^{-1}, f^\ast$. The distributions of $\xi(A)$ and $\zeta(A)$ are obtained. ($\eta(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 $\xi(A)$ is asymptotically normal with mean $(2mn)^{1/2}$ and variance $n/2$, and $(n - \zeta(A))(n/m)^{-1}$ is asymptotically $\mathscr{U}^2/2$ ($\mathscr{U}$ being the standard normal variable), provided $m \rightarrow \infty, m = o(n)$. The results are interpreted in terms of epidemic processes on random graphs introduced by I. Gertsbakh.
Publié le : 1983-05-14
Classification:  Random mappings and graphs,  enumeration,  generating functions,  distributions,  limit laws,  epidemic processes,  60C05,  60F05,  60J80,  05C30
@article{1176993608,
     author = {Pittel, Boris},
     title = {On Distributions Related to Transitive Closures of Random Finite Mappings},
     journal = {Ann. Probab.},
     volume = {11},
     number = {4},
     year = {1983},
     pages = { 428-441},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1176993608}
}
Pittel, Boris. On Distributions Related to Transitive Closures of Random Finite Mappings. Ann. Probab., Tome 11 (1983) no. 4, pp.  428-441. http://gdmltest.u-ga.fr/item/1176993608/