On images and pre-images in a graph of the composition of independent uniform random mappings
We study the probabilistic characteristics of the graph of a random mapping f [k] - a composition of k independent equiprobable random mappings f1, ....., fk, where fi: {1, ..., n} → {1, ..., n}, n, k ∈ ℕ, i = 1, ..., n. Formulas are obtained for the distribution of the length of the aperiodicity segment of an arbitrary vertex in the graph of the mapping f [k], taking into account a number of restrictions. Formulas are written for the probabilities of a vertex belonging to the set f [k] ({1, ..., n}) and to the set of pendant vertices in the graph of the mapping f [k]. The probabilities of the incidence of two arbitrary vertices to one connected component, the occurrence of an arbitrary vertex in the set of inverse images of another vertex, and the appearance of a collision in the indicated graph are calculated.