?
Об образах и прообразах в графе композиции независимых равновероятных случайных отображений
Изучаются вероятностные характеристики графа случайного отображения $f_{\left[k\right]}$ --- композиции $k\in\mathbb{N}$ независимых равновероятных случайных отображений $f_1,\ldots,f_k$, где $f_i\colon \left\{1,\ldots,n\right\}\to \left\{1,\ldots,n\right\}$, $n\in\mathbb{N}$, $i=1,\ldots,n$. В статье получены формулы для распределения длины отрезка апериодичности произвольной вершины в графе отображения $f_{\left[k\right]}$ с учетом ряда ограничений. Выписаны формулы для вероятностей принадлежности вершины множеству $f_{\left[k\right]}(\{1,\ldots,n\})$ и множеству висячих вершин в графе отображения $f_{\left[k\right]}$. Вычислены вероятности инцидентности двух произвольных вершин одной компоненте связности, попадания произвольной вершины в множество прообразов другой вершины, а также появления коллизии в указанном графе.