On the distribution of cycle lengths in the graph of k-multiple iteration of the uniform random substitution
Миронкин Владимир Олегович · PRIKLADNAYa DISKRETNAYa MATEMATIKA · 2023
The influence of the iteration process on the structure of the graph Gπ of the uniform random substitution π : S → S is studied. Exact formulas are written out for the distribution of the length βπ (x) of the cycle Kπ (x) containing an arbitrary fixed vertex x ∈ S. An expression is written for the mathematical expectation of a random variable λπk (l) equal to the number of vertices in the graph Gπk lying on cycles of length l ∈ {1, . . . , |S|}. For k ∈ N and arbitrary fixed vertices x, y ∈ S, x ̸= y, the joint probability of their falling on cycles of fixed lengths in the graph Gπk is calculated.