|
Теоретические основы прикладной дискретной математики
Об образах и прообразах в графе композиции независимых равновероятных случайных отображений
В. О. Миронкин Национальный исследовательский университет «Высшая школа экономики», г. Москва,
Россия
Аннотация:
Изучаются вероятностные характеристики графа случайного отображения $f_{\left[k\right]}$ — композиции $k$ независимых равновероятных случайных отображений $f_1,\ldots,f_k$, где $f_i\colon \left\{1,\ldots,n\right\}\to \left\{1,\ldots,n\right\}$, $n,k\in\mathbb{N}$, $i=1,\ldots,n$. Получены формулы для распределения длины отрезка апериодичности произвольной вершины в графе отображения $f_{\left[k\right]}$ с учётом ряда ограничений. Выписаны формулы для вероятностей принадлежности вершины множеству $f_{\left[k\right]}(\{1,\ldots,n\})$ и множеству висячих вершин в графе отображения $f_{\left[k\right]}$. Вычислены вероятности инцидентности двух произвольных вершин одной компоненте связности, попадания произвольной вершины в множество прообразов другой вершины, а также появления коллизии в указанном графе.
Ключевые слова:
равновероятное случайное отображение, композиция отображений, граф отображения, образ множества, прообраз вершины, висячая вершина, слой в графе, отрезок апериодичности, коллизия.
Образец цитирования:
В. О. Миронкин, “Об образах и прообразах в графе композиции независимых равновероятных случайных отображений”, ПДМ, 2020, № 49, 5–17
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm710 https://www.mathnet.ru/rus/pdm/y2020/i3/p5
|
Статистика просмотров: |
Страница аннотации: | 122 | PDF полного текста: | 30 | Список литературы: | 15 |
|