|
Zapiski Nauchnykh Seminarov POMI, 2016, Volume 454, Pages 195–215
(Mi znsl6393)
|
|
|
|
Random partitions induced by random maps
D. Krachuna, Yu. Yakubovichb a Chebyshev Laboratory, St. Petersburg State University, Department of Mathematics and Mechanics, St. Petersburg, Russia
b St. Petersburg State University, St. Petersburg, Russia
Abstract:
The lattice of the set partitions of $[n]$ ordered by refinement is studied. Given a map $\phi\colon[n]\to[n]$, by taking preimages of elements we construct a partition of $[n]$. Suppose $t$ partitions $p_1,p_2,\dots,p_t$ are chosen independently according to the uniform measure on the set of mappings $[n]\to[n]$. The probability that the coarsest refinement of all $p_i$'s is the finest partitions $\{\{1\},\dots,\{n\}\}$ is shown to approach $1$ for any $t\geq3$ and $e^{-1/2}$ for $t=2$. The probability that the finest coarsening of all $p_i$'s is the one-block partition is shown to approach $1$ if $t(n)-\log n\to\infty$ and $0$ if $t(n)-\log n\to-\infty$. The size of the maximal block of the finest coarsening of all $p_i$'s for a fixed $t$ is also studied.
Key words and phrases:
random partition, random maps.
Received: 01.11.2016
Citation:
D. Krachun, Yu. Yakubovich, “Random partitions induced by random maps”, Probability and statistics. Part 24, Zap. Nauchn. Sem. POMI, 454, POMI, St. Petersburg, 2016, 195–215; J. Math. Sci. (N. Y.), 229:6 (2018), 727–740
Linking options:
https://www.mathnet.ru/eng/znsl6393 https://www.mathnet.ru/eng/znsl/v454/p195
|
|