|
Эта публикация цитируется в 11 научных статьях (всего в 11 статьях)
Совокупность образов подмножества конечного множества при итерациях случайных отображений
А. М. Зубков, А. А. Серов Математический институт им. В. А. Стеклова Российской академии наук
Аннотация:
Пусть $\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)$. Результаты представляют интерес для анализа алгоритмов балансировки времени и памяти.
Статья поступила: 20.06.2014
Образец цитирования:
А. М. Зубков, А. А. Серов, “Совокупность образов подмножества конечного множества при итерациях случайных отображений”, Дискрет. матем., 26:4 (2014), 43–50; Discrete Math. Appl., 25:3 (2015), 179–185
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm1303https://doi.org/10.4213/dm1303 https://www.mathnet.ru/rus/dm/v26/i4/p43
|
Статистика просмотров: |
Страница аннотации: | 527 | PDF полного текста: | 191 | Список литературы: | 75 | Первая страница: | 61 |
|