Geodesic
Images of a finite set under iterations of two random dependent mappings
Diskretnaya Matematika, Tome 27 (2015) no. 4, pp. 133-140.

Voir la notice de l'article provenant de la source Math-Net.Ru

Let $\mathcal{N}$ be a set of $N$ elements and $\left(F_1,G_1\right),\left(F_2,G_2\right),\ldots$ be a sequence of independent pairs of random dependent mappings $\mathcal{N}\to\mathcal{N}$ such that $F_k$ and $G_k$ are random equiprobable mappings and $\mathbf{P}\{F_k(x)=G_k(x)\}=\alpha$ for all $x\in \mathcal{N}$ and $k=1,2,\ldots$ For a subset $S_0\subset \mathcal{N},\,|S_0|=n$, we consider a sequences of its images $S_k=F_k(\ldots F_2(F_1(S_0))\ldots)$, $T_k=G_k(\ldots G_2(G_1(S_0))\ldots)$, $k=1,2\ldots$, and a sequences of their unions $S_k\cup T_k$ and intersections $S_k\cap T_k$, $k=1,2\ldots$ We obtain two-sided inequalities for $\mathbf{M}|S_k\cup T_k|$ and $\mathbf{M}|S_k\cap T_k|$ such that upper and lower bounds are asymptotically equivalent if $N,n,k\to\infty$, $nk=o(N)$ and $\alpha=O\left(\tfrac1N\right)$.
Keywords: random mappings of finite sets, joint distributions, iterations of random mappings, Markov chain. 
@article{DM_2015_27_4_a9,
     author = {A. A. Serov},
     title = {Images of a finite set under iterations of two random dependent mappings},
     journal = {Diskretnaya Matematika},
     pages = {133--140},
     publisher = {mathdoc},
     volume = {27},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2015_27_4_a9/}
}
TY  - JOUR
AU  - A. A. Serov
TI  - Images of a finite set under iterations of two random dependent mappings
JO  - Diskretnaya Matematika
PY  - 2015
SP  - 133
EP  - 140
VL  - 27
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2015_27_4_a9/
LA  - ru
ID  - DM_2015_27_4_a9
ER  - 
%0 Journal Article
%A A. A. Serov
%T Images of a finite set under iterations of two random dependent mappings
%J Diskretnaya Matematika
%D 2015
%P 133-140
%V 27
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2015_27_4_a9/
%G ru
%F DM_2015_27_4_a9
A. A. Serov. Images of a finite set under iterations of two random dependent mappings. Diskretnaya Matematika, Tome 27 (2015) no. 4, pp. 133-140. http://geodesic.mathdoc.fr/item/DM_2015_27_4_a9/

[1] Kolchin V. F., Sluchainye otobrazheniya, Nauka, M., 1984, 208 pp. | MR

[2] Kolchin V. F., Sevastyanov B. A., Chistyakov V. P., Sluchainye razmescheniya, Nauka, M., 1976, 224 pp. | MR

[3] Gantmakher F. R., Teoriya matrits, Nauka, M., 1966, 576 pp. | MR

[4] Zubkov A.M., Serov A.A., “Sovokupnost obrazov podmnozhestva konechnogo mnozhestva pri iteratsiyakh sluchainykh otobrazhenii”, Diskretnaya matematika, 26:4 (2014), 43–50 | DOI | MR

[5] Stepanov V. E., “O raspredelenii chisla vershin v sloyakh sluchainogo dereva”, Teoriya veroyatn. i primen., 14:1 (1969), 64–77 | MR

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

[7] Flajolet P., Odlyzko A. M., “Random mapping statistics”, Lect. Notes Comput. Sci., 434, 1990, 329–354 | DOI | MR | Zbl

[8] Goh W. M. Y., Hitczenko P., Schmutz E., Iterating random functions on a finite set, 2014, 7 pp., arXiv: math/0207276v2

[9] Kingman J. F. C., “The coalescent”, Stoch.Proc. Appl., 13 (1982), 235–248 | DOI | MR | Zbl