On images and pre-images in a graph of the composition of independent uniform random mappings

V. O. Mironkin

Prikladnaâ diskretnaâ matematika, no. 3 (2020), pp. 5-17.

Résumé

We study the probability characteristics of the random mapping graph $ f_{\left[k\right]} $ — the composition of $k$ independent equiprobable random mappings $ f_1, \ldots, f_k $, where $f_i\colon \left\{1,\ldots,n\right\}\to \left\{1,\ldots,n\right\}$, $n,k\in\mathbb{N}$, $i=1,\ldots,n$. The following results are obtained. For any fixed $x,y\in S=\{1,\ldots,n\}$, $x\ne y$, \begin{equation*} \mathbf{P}\{f_{\left[k\right]}(x)=f_{\left[k\right]}(y)\}=\textstyle\sum\limits_{\begin{smallmatrix}s_1,\ldots,s_{k-1}\in\mathbb{N}\colon\\2\geqslant s_1\geqslant\ldots\geqslant s_{k-1} \end{smallmatrix}}\dfrac{q(2,s_{1})}{n^{s_{k-1}-1}}\prod\limits_{i=1}^{k-2}q(s_i,s_{i+1}), \end{equation*} where $q(a,b)=\text{C}_{n}^{n-b} \left(\dfrac{b}{n}\right)^a \sum\limits_{l=0}^{b}\text{C}_{b}^l(-1)^l\left(1-\dfrac{l}{b}\right)^a$. For any fixed $x\in S$, \begin{gather*} \mathbf{P}\{ x\in f_{\left[k\right]}(S)\}=\frac1{n}\textstyle\sum\limits_{l=1}^{n}{\left(\dfrac{(n)_l}{n^l} \right)^k}+\\ +\textstyle\sum\limits_{l=1}^{n-2}\sum\limits_{t=1}^{n-l-1}\sum\limits_{m=1}^{n-t-l}(-1)^{m-1}\text{C}_{n-1}^m\sum\limits_{\begin{smallmatrix}s_1,\ldots,s_{k-1}\in\mathbb{N}\colon\\m\geqslant s_1\geqslant\ldots\geqslant s_{k-1} \end{smallmatrix}}\dfrac{q(m,s_{1})}{n^{s_{k-1}}}\prod\limits_{i=1}^{k-2}q(s_i,s_{i+1})V^{\left\{k,m\right\}}_{s_1,\ldots,s_{k-1}}, \end{gather*} where \begin{gather*} V^{\left\{k,m\right\}}_{s_1,\ldots,s_{k-1}}=\mathbf{P}\{x\in H_{f_{\left[k\right]}}^{\left(t,l\right)}\bigm| D^{\left\{k\right\}}_{s_1,\ldots,s_{k-1},1}\left(y_1,\ldots,y_m\right),f_{\left[k\right]}\left(y_1\right)=x \}=\\ =\frac{1}{n}\textstyle\prod\limits_{i=m+1}^{t+l+m-1}{\left( 1-\dfrac{i}{n} \right)}\prod\limits_{i=1}^{k-1}\prod\limits_{j=s_i+1}^{t+l+s_i-2}{\left( 1-\dfrac{j}{n} \right)}\sum\limits_{v=0}^{k-1}\prod\limits_{u=1}^{v}{\left( 1-\dfrac{t+l+s_u-1}{n} \right)}, \end{gather*} $H_f^{\left(t,l\right)}$ is $t$-th layer of cycles of length $l$ in graph $G_f$, $D^{\left\{k\right\}}_{s_1,\ldots,s_{k}}(y_1,\ldots,y_m)=\textstyle\bigcap\limits_{i=1}^{k} \{|\{f_{\left[i\right]}(y_1),\ldots,f_{\left[i\right]}(y_m)\}|=s_i\}$, and $(n)_z=n(n-1)\dots(n-z+1)$. For any fixed $x\in S\setminus S'$ and for any $r\in \{1,\ldots,n-1\}$, $S'\subseteq S$, $|S'|=r$, $z\in \{1,\ldots,n\}$, \begin{gather*} \mathbf{P}\{\tau_{f_{\left[k\right]}}(x)=z,\mathcal{R}_{f_{\left[k\right]}}(x)\cap S'=\varnothing \}=\\ =\left(1-\left(1-\frac{z}{n}\right)\left( 1-\frac{z-1}{n} \right)^{k-1}\right)\left(\frac{\left(n\right)_{z-1}}{n^{z-1}} \right)^{k-1}\frac{\left(n\right)_{r+z}}{n^{z-1}\left(n\right)_{r+1}}, \end{gather*} where $\mathcal{R}_{f_{\left[k\right]}}(x)$ is the aperiodicity segment of vertex $x$ in the graph of mapping $f_{\left[k\right]}$, $\tau_{f_{\left[k\right]}}(x)=\min\{ t\in \mathbb{N}\colon {f_{\left[k\right]}}^t(x)\in \{ x,{f_{\left[k\right]}}(x),\dots,{f_{\left[k\right]}}^{t-1}(x) \}\}$. For any fixed $x,y\in S$, $x\ne y$, and for any $r\in\{1,\ldots,n\}$, \begin{equation*} \mathbf{P}\{y \in (f_{\left[k\right]})^{-r}(x)\}=\frac1n\left(1-\frac1{n-1}\textstyle\sum\limits_{z\in Q_r\setminus\{1\}}\left(\dfrac{(n)_z}{n^z}\right)^k\right), \end{equation*} where $Q_r=\{m\in \mathbb{N}\colon m|r\}$.

Détail

Keywords: equiprobable random mapping, composition of mappings, graph of a mapping, layer in a graph, aperiodicity segment, collision.
Mots-clés : image of a multitude, pre-image of a vertex, initial vertex

Bibliographie

[1] Mironkin V. O., “Distribution of the length of aperiodicity segment in the graph of independent uniform random mappings composition”, Mat. Vopr. Kriptogr., 10:3 (2019), 89–99 (in Russian) | MR

[2] 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) | MR

[3] Zubkov A. M., Serov A. A., “Limit theorem for the size of an image of subset under compositions of random mappings”, Discrete Math., 29:1 (2017), 17–26 (in Russian)

[4] Zubkov A. M., Serov A. A., “Estimates of the mean size of the subset image under composition of random mappings”, Discrete Math., 30:2 (2018), 27–36 (in Russian) | Zbl

[5] Serov A. A., “Images of a finite set under iterations of two random dependent mappings”, Discrete Math., 27:4 (2015), 133–140 (in Russian) | MR

[6] Dalal A., Schmutz E., “Compositions of random functions on a finite set”, Electr. J. Comb., 9:R26 (2002), 1–7 | MR | Zbl

[7] Fill J. A., On compositions of random functions on a finite set, 2002, 15 pp. http://www.mts.jhu.edu/f̃ill/

[8] Mironkin V. O., “On some probabilistic characteristics of key derevation function “CRYPTOPRO KEY MESHING””, Problemy Informacionnoj Bezopasnosti. Komp'yuternye Sistemy, 2015, no. 4, 140–146 (in Russian)

[9] Ahmetzyanova L. R., Alekseev E. K., Oshkin I. B., et al., “On the properties of the CTR encryption mode of Magma and Kuznyechik block ciphers with re-keying method based on CryptoPro Key Meshing”, Mat. Vopr. Kriptogr., 8:2 (2017), 39–50 | MR

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

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

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

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

[14] Kolchin V. F., Sevastyanov B. A., Chistyakov V. P., Random Assignments, Nauka Publ., M., 1976 (in Russian) | MR