On the distribution of cycle lengths in the graph of~$k$-multiple iteration of~the uniform random substitution

V. O. Mironkin

Prikladnaâ diskretnaâ matematika, no. 4 (2023), pp. 5-12

Résumé

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.

Détail

Keywords: uniform random substitution, iteration of a substitution, graph of a substitution, distribution of cycle lengths, fixed points.