Images of a finite set under iterations of two random dependent mappings

A. A. Serov

Diskretnaya Matematika, Tome 27 (2015) no. 4, pp. 133-140

Résumé

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)$.

Détail

Keywords: random mappings of finite sets, joint distributions, iterations of random mappings, Markov chain.