Estimates of the mean size of the subset image under composition of random mappings

Let $\mathcal{X}_N$ be a set of $N$ elements and $F_1,F_2,\ldots$ be a sequence of random independent equiprobable mappings $\mathcal{X}_N\to\mathcal{X}_N$. For a subset $S_0\subset\mathcal{X}_N$, $|S_0|=m$, we consider a sequence of its images $S_t=F_t(\ldots F_2(F_1(S_0))\ldots)$, $t=1,2\ldots$ An approach to the exact recurrent computation of distribution of $|S_t|$ is described. Two-sided inequalities for $\mathbf{M}\{|S_t|\,|\,|S_0|=m\}$ such that the difference between the upper and lower bounds is $o(m)$ for $m,t,N\to\infty,\,mt=o(N)$ are derived. The results are of interest for the analysis of time-memory tradeoff algorithms.