Оценки среднего размера образа подмножества при композиции случайных отображений

Пусть $\mathcal{X}_N$ — множество из $N$ элементов и $F_1,F_2,\ldots$ — последовательность случайных независимых равновероятных отображений $\mathcal{X}_N\to\mathcal{X}_N$. Для подмножества $S_0\subset \mathcal{X}_N$, $|S_0|=m$, рассматривается последовательность его образов $S_t=F_t(\ldots F_2(F_1(S_0))\ldots)$, $t=1,2\ldots$ Описан рекуррентный способ точного вычисления распределения $|S_t|$. Получены двусторонние неравенства для $\mathbf{M}\{|S_t|\,|\,|S_0|=m\}$, в которых разность между верхней и нижней оценками имеет порядок $o(m)$, если $m,t,N\to\infty,\,mt=o(N)$. Результаты представляют интерес для анализа алгоритмов балансировки времени и памяти.