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

Пусть $\mathcal{N}$ — множество из $N$ элементов и $F_1,F_2,\ldots$ — последовательность случайных независимых равновероятных отображений $\mathcal{N}\to\mathcal{N}$. Для подмножества $S_0\subset \mathcal{N},\,|S_0|=n$, рассматриваются последовательность его образов $S_k=F_k(\ldots F_2(F_1(S_0))\ldots),\,k=1,2\ldots$, и последовательность их объединений $\Psi_k=S_1\cup\ldots\cup S_k,\,k=1,2\ldots$ Описан способ точного вычисления распределений $|S_k|$ и $|\Psi_k|$ при умеренных значениях $N$. Получены двусторонние неравенства для $\mathbf{M}|S_k|$ и $\mathbf{M}|\Psi_k|$, в которых верхние оценки асимптотически эквивалентны нижним, если $N,n,k\to\infty, nk=o(N)$. Результаты представляют интерес для анализа алгоритмов балансировки времени и памяти.