|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Estimates of the mean size of the subset image under composition of random mappingsстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 10 декабря 2018 г.
- Авторы: Zubkov A.M., Serov A.A.
- Журнал: Discrete Mathematics and Applications
- Том: 28
- Номер: 5
- Год издания: 2018
- Издательство: de Gruyter
- Местоположение издательства: Germany
- Первая страница: 331
- Последняя страница: 338
- DOI: 10.1515/dma-2018-0029
- Аннотация: 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.
- Добавил в систему: Зубков Андрей Михайлович