Geodesic
On the distribution of cycle lengths in the graph of $k$-multiple iteration of the uniform random substitution
Prikladnaâ diskretnaâ matematika, no. 4 (2023), pp. 5-12
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The influence of the iteration process on the structure of the graph $G_\pi$ of the uniform random substitution $\pi\colon S\to S$ is studied. Exact formulas are written out for the distribution of the length $\beta_{\pi}\left(x\right)$ of the cycle $\mathcal{K}_{\pi}\left(x\right)$ containing an arbitrary fixed vertex $x\in S$. An expression is written for the mathematical expectation of a random variable $\lambda_{\pi^k}\left(l\right)$ equal to the number of vertices in the graph $G_{\pi^k}$ lying on cycles of length $l\in \{1,\ldots,|S|\}$. For $k\in\mathbb{N}$ and arbitrary fixed vertices $x,y\in S$, $x\ne y$, the joint probability of their falling on cycles of fixed lengths in the graph $G_{\pi^k}$ is calculated.
Keywords: uniform random substitution, iteration of a substitution, graph of a substitution, distribution of cycle lengths, fixed points. 
@article{PDM_2023_4_a0,
     author = {V. O. Mironkin},
     title = {On the distribution of cycle lengths in the graph of~$k$-multiple iteration of~the uniform random substitution},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {5--12},
     year = {2023},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2023_4_a0/}
}
TY  - JOUR
AU  - V. O. Mironkin
TI  - On the distribution of cycle lengths in the graph of $k$-multiple iteration of the uniform random substitution
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2023
SP  - 5
EP  - 12
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/PDM_2023_4_a0/
LA  - ru
ID  - PDM_2023_4_a0
ER  - 
%0 Journal Article
%A V. O. Mironkin
%T On the distribution of cycle lengths in the graph of $k$-multiple iteration of the uniform random substitution
%J Prikladnaâ diskretnaâ matematika
%D 2023
%P 5-12
%N 4
%U http://geodesic.mathdoc.fr/item/PDM_2023_4_a0/
%G ru
%F PDM_2023_4_a0
V. O. Mironkin. On the distribution of cycle lengths in the graph of $k$-multiple iteration of the uniform random substitution. Prikladnaâ diskretnaâ matematika, no. 4 (2023), pp. 5-12. http://geodesic.mathdoc.fr/item/PDM_2023_4_a0/

[1] Kolchin V. F., Random Mappings, Nauka Publ., M., 1984 (in Russian)

[2] Sachkov V. N., Probabilistic Methods in Combinatorial Analysis, Nauka Publ., M., 1978 (in Russian) | MR

[3] Flajolet P. and Odlyzko A., “Random mapping statistics”, LNCS, 434, 1989, 329–354 | MR

[4] Harris B., “Probability distributions related to random mapping”, Ann. Math. Statist., 31:4 (1960), 1045–1062 | DOI | MR | Zbl

[5] Mironkin V. O., “On the layers in the graph of $k$-fold iteration of uniform random mapping”, Mat. Vopr. Kriptogr., 10:1 (2019), 73–82 (in Russian) | DOI | MR | Zbl

[6] Mironkin V. O., “Layers in a graph of the composition of independent uniform random mappings”, Mat. Vopr. Kriptogr., 11:1 (2020), 101–114 (in Russian) | DOI | MR | Zbl