Abstract:
The properties of the graph of $k$-fold iteration of uniform random mapping $f\colon \{1,\ldots,n\}\to \{1,\ldots,n\}$ are studied. Some recurrence formulas for the probabilities for a vertex to belong to the set of images $f^k(\{1,\ldots,n\})$ and to the set of the initial vertices in the graph of $f^k$ are obtained.
Key words:
uniform random mapping, iteration of random mapping, graph of a mapping, image, pre-image, initial vertex.
Received 11.V.2017, 05.VI.2018
Bibliographic databases:
Document Type:
Article
UDC:519.212.2+519.719.2
Language: Russian
Citation:
V. O. Mironkin, V. G. Mikhailov, “On the sets of images of $k$-fold iteration of uniform random mapping”, Mat. Vopr. Kriptogr., 9:3 (2018), 99–108
\Bibitem{MirMik18}
\by V.~O.~Mironkin, V.~G.~Mikhailov
\paper On the sets of images of $k$-fold iteration of uniform random mapping
\jour Mat. Vopr. Kriptogr.
\yr 2018
\vol 9
\issue 3
\pages 99--108
\mathnet{http://mi.mathnet.ru/mvk264}
\crossref{https://doi.org/10.4213/mvk264}
\elib{https://elibrary.ru/item.asp?id=35601224}
Linking options:
https://www.mathnet.ru/eng/mvk264
https://doi.org/10.4213/mvk264
https://www.mathnet.ru/eng/mvk/v9/i3/p99
This publication is cited in the following 5 articles:
V. O. Mironkin, “Sloi v grafe kompozitsii nezavisimykh ravnoveroyatnykh sluchainykh otobrazhenii”, Matem. vopr. kriptogr., 11:1 (2020), 101–114
V. O. Mironkin, “Sloi v grafe $k$-kratnoi iteratsii ravnoveroyatnogo sluchainogo otobrazheniya”, Matem. vopr. kriptogr., 10:1 (2019), 73–82
V. O. Mironkin, “Collisions and incidence of vertices and components in the graph of $k$-fold iteration of the uniform random mapping”, Discrete Math. Appl., 31:4 (2021), 259–269
V. O. Mironkin, “Raspredelenie dliny otrezka aperiodichnosti v grafe kompozitsii nezavisimykh ravnoveroyatnykh sluchainykh otobrazhenii”, Matem. vopr. kriptogr., 10:3 (2019), 89–99
V. O. Mironkin, “Ob otsenkakh raspredeleniya dliny otrezka aperiodichnosti v grafe $k$-kratnoi iteratsii ravnoveroyatnogo sluchainogo otobrazheniya”, PDM, 2018, no. 42, 6–17
Citation in format AMSBIB
Contact us: